Smoothing proximal gradient method for general structured sparse regression

Abstract

We study the problem of estimating high-dimensional regression models regularized by a structured sparsity-inducing penalty that encodes prior structural information on either the input or output variables. We consider two widely adopted types of penalties of this kind as motivating examples: (1) the general overlapping-group-lasso penalty, generalized from the group-lasso penalty; and (2) the graph-guided-fused-lasso penalty, generalized from the fused-lasso penalty. For both types of penalties, due to their nonseparability and nonsmoothness, developing an efficient optimization method remains a challenging problem. In this paper we propose a general optimization approach, the smoothing proximal gradient (SPG) method, which can solve structured sparse regression problems with any smooth convex loss under a wide spectrum of structured sparsity-inducing penalties. Our approach combines a smoothing technique with an effective proximal gradient method. It achieves a convergence rate significantly faster than the standard first-order methods, subgradient methods, and is much more scalable than the most widely used interior-point methods. The efficiency and scalability of our method are demonstrated on both simulation experiments and real genetic data sets.

Published in at http://dx.doi.org/10.1214/11-AOAS514 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (10)

• Pathwise coordinate optimization
• The composite absolute penalties family for grouped and hierarchical variable selection
• A note on the group lasso and a sparse group lasso
• The solution path of the generalized lasso
• Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization
• Coordinate descent algorithms for lasso penalized regression
• Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
• Network Flow Algorithms for Structured Sparsity
• Fast Overlapping Group Lasso
• A path algorithm for the Fused Lasso Signal Approximator

Cited by in corpus (37)

• Deep Air Learning: Interpolation, Prediction, and Feature Analysis of Fine-grained Air Quality
• Group-Sparse Signal Denoising: Non-Convex Regularization, Convex Optimization
• Network classification with applications to brain connectomics
• Group Sparse Recovery via the ${\ell }^0({\ell }^2)$ Penalty: Theory and Algorithm
• Deep Predictive Coding Networks
• Image classification by visual bag-of-words refinement and reduction
• Proximal-Proximal-Gradient Method
• Latent Semantic Learning with Structured Sparse Representation for Human Action Recognition
• A Path Algorithm for Constrained Estimation
• Parallel Direction Method of Multipliers
• Penalized Estimation of Frailty-Based Illness-Death Models for Semi-Competing Risks
• Joint Fairness Model with Applications to Risk Predictions for Under-represented Populations
• Screening Rules for Overlapping Group Lasso
• Sparse Variable Selection on High Dimensional Heterogeneous Data with Tree Structured Responses
• Easily parallelizable and distributable class of algorithms for structured sparsity, with optimal acceleration
• A Sparse Graph-Structured Lasso Mixed Model for Genetic Association with Confounding Correction
• Learning Hierarchical Interactions at Scale: A Convex Optimization Approach
• Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery
• A Generic Path Algorithm for Regularized Statistical Estimation
• Joint Estimation and Inference for Multi-Experiment Networks of High-Dimensional Point Processes
• Modelling Heterogeneity Using Bayesian Structured Sparsity
• High-dimensional Fused Lasso Regression using Majorization-Minimization and Parallel Processing
• Disease Prediction based on Functional Connectomes using a Scalable and Spatially-Informed Support Vector Machine
• Proximal methods for the latent group lasso penalty
• It's All Relative: New Regression Paradigm for Microbiome Compositional Data
• Sparse Group Fused Lasso for Model Segmentation
• An Algorithm for Graph-Fused Lasso Based on Graph Decomposition
• Linearly Constrained Smoothing Group Sparsity Solvers in Off-grid Model
• Sharp Oracle Inequalities for Low-complexity Priors
• Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than $O(1/\epsilon )$
• Multi-class Vector AutoRegressive Models for Multi-store Sales Data
• Fast Nonsmooth Regularized Risk Minimization with Continuation
• Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations
• An Algorithmic Theory of Dependent Regularizers, Part 1: Submodular Structure
• Structured functional regression models for high-dimensional spatial spectroscopy data
• Alternating Linearization for Structured Regularization Problems
• Local Neighborhood Fusion in Locally Constant Gaussian Graphical Models