Piecewise linear regularized solution paths

Abstract

We consider the generic regularized optimization problem $\hat{\beta }(\lambda )=\arg {\min }_{\beta }L(\mathsf{y},X\beta )+\lambda J(\beta )$. Efron, Hastie, Johnstone and Tibshirani [Ann. Statist. 32 (2004) 407--499] have shown that for the LASSO--that is, if $L$ is squared error loss and $J(\beta )=\Vert \beta {\Vert }_1$ is the ${\ell }_1$ norm of $\beta$--the optimal coefficient path is piecewise linear, that is, $\partial \hat{\beta }(\lambda )/\partial \lambda$ is piecewise constant. We derive a general characterization of the properties of (loss $L$, penalty $J$) pairs which give piecewise linear coefficient paths. Such pairs allow for efficient generation of the full regularized coefficient paths. We investigate the nature of efficient path following algorithms which arise. We use our results to suggest robust versions of the LASSO for regression and classification, and to develop new, efficient algorithms for existing problems in the literature, including Mammen and van de Geer's locally adaptive regression splines.

Published at http://dx.doi.org/10.1214/009053606000001370 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (11)

• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Nonconcave penalized likelihood with a diverging number of parameters

Cited by in corpus (85)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Nearly unbiased variable selection under minimax concave penalty
• One-step sparse estimates in nonconcave penalized likelihood models
• The composite absolute penalties family for grouped and hierarchical variable selection
• The solution path of the generalized lasso
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Adaptive piecewise polynomial estimation via trend filtering
• Least angle and ${\ell }_1$ penalized regression: A review
• Feature Selection with Annealing for Computer Vision and Big Data Learning
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• Generalized Methods and Solvers for Noise Removal from Piecewise Constant Signals
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Stop Wasting My Gradients: Practical SVRG
• Sparse SVM for Sufficient Data Reduction
• Complexity Analysis of the Lasso Regularization Path
• On the Optimality of Averaging in Distributed Statistical Learning
• Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig
• Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs
• A Selective Overview of Variable Selection in High Dimensional Feature Space (Invited Review Article)
• Regularization of Case-Specific Parameters for Robustness and Efficiency
• Finite-Sample Optimal Estimation and Inference on Average Treatment Effects Under Unconfoundedness
• Sensitivity Analysis using Approximate Moment Condition Models
• Asymptotic properties for combined $L_1$ and concave regularization
• Robust Parametric Classification and Variable Selection by a Minimum Distance Criterion
• Accelerated Variance Reduced Stochastic ADMM
• High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
• Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization
• A Path Algorithm for Constrained Estimation
• MM Algorithms for Minimizing Nonsmoothly Penalized Objective Functions
• More Powerful Conditional Selective Inference for Generalized Lasso by Parametric Programming
• Regularization with the Smooth-Lasso procedure
• DECOrrelated feature space partitioning for distributed sparse regression
• A ROAD to Classification in High Dimensional Space
• Solution Paths of Variational Regularization Methods for Inverse Problems
• Uniformly Valid Confidence Sets Based on the Lasso
• Combined l_1 and greedy l_0 penalized least squares for linear model selection
• Robust subset selection
• Parametric Programming Approach for More Powerful and General Lasso Selective Inference
• Online Learning as Stochastic Approximation of Regularization Paths
• Sparse Quantile Huber Regression for Efficient and Robust Estimation
• Algorithms for Fitting the Constrained Lasso
• A Combinatorial Algorithm to Compute Regularization Paths
• Support Vector Machine Classifier via $L_{0/1}$ Soft-Margin Loss
• Safe Grid Search with Optimal Complexity
• The Geometry of Adversarial Training in Binary Classification
• Regularization Path of Cross-Validation Error Lower Bounds
• Bias-Aware Inference in Regularized Regression Models
• Quantum Algorithms for the Pathwise Lasso
• Classifier Chain Networks for Multi-Label Classification
• Valid and Exact Statistical Inference for Multi-dimensional Multiple Change-Points by Selective Inference
• The Smooth-Lasso and other ${\ell }_1+{\ell }_2$-penalized methods
• More Powerful and General Selective Inference for Stepwise Feature Selection using the Homotopy Continuation Approach
• MM for Penalized Estimation
• A Generic Path Algorithm for Regularized Statistical Estimation
• The Well Tempered Lasso
• A generalised OMP algorithm for feature selection with application to gene expression data
• An algorithmic view of ${\ell }_2$ regularization and some path-following algorithms
• On the connections between algorithmic regularization and penalization for convex losses
• Streaming regularization parameter selection via stochastic gradient descent
• Indirect Gaussian Graph Learning beyond Gaussianity
• A simple and efficient algorithm for fused lasso signal approximator with convex loss function
• Inference of genetic networks from time course expression data using functional regression with lasso penalty
• On the Limit Imbalanced Logistic Regression by Binary Predictors
• Adaptive regularization for Lasso models in the context of non-stationary data streams
• Cross Validation for Penalized Quantile Regression with a Case-Weight Adjusted Solution Path
• Estimating Piecewise Monotone Signals
• The Maximum Entropy Relaxation Path
• APPLE: Approximate Path for Penalized Likelihood Estimators
• Integrative learning of individualized treatment rules from multiple studies with partially overlapping treatments
• An Exact Solution Path Algorithm for SLOPE and Quasi-Spherical OSCAR
• Image denoising via K-SVD with primal-dual active set algorithm
• Primal path algorithm for compositional data analysis
• A Greedy Homotopy Method for Regression with Nonconvex Constraints
• An efficient algorithm for structured sparse quantile regression
• Multi-parametric Solution-path Algorithm for Instance-weighted Support Vector Machines
• Simultaneous Parameter Learning and Bi-Clustering for Multi-Response Models