Abstract
We consider the generic regularized optimization problem β̂(λ)=arg min<sub>β</sub> L(y, Xβ)+λJ(β). 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(β)=‖β‖<sub>1</sub> is the ℓ<sub>1</sub> norm of β—the optimal coefficient path is piecewise linear, that is, ∂β̂(λ)/∂λ 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.
Keywords
MathematicsPiecewisePiecewise linear functionLasso (programming language)Regularization (linguistics)Path (computing)Applied mathematicsNorm (philosophy)Mathematical optimizationLinear regressionSpline (mechanical)AlgorithmStatisticsMathematical analysisArtificial intelligenceComputer science
Affiliated Institutions
Related Publications
On the LASSO and its Dual
Abstract Proposed by Tibshirani, the least absolute shrinkage and selection operator (LASSO) estimates a vector of regression coefficients by minimizing the residual sum of squa...
Least angle regression
The purpose of model selection algorithms such as All Subsets, Forward Selection and Backward Elimination is to choose a linear model on the basis of the same set of data to whi...
SLIM: Sparse Linear Methods for Top-N Recommender Systems
This paper focuses on developing effective and efficient algorithms for top-N recommender systems. A novel Sparse Linear Method (SLIM) is proposed, which generates top-N recomme...
For most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution
Abstract We consider linear equations y = Φ x where y is a given vector in ℝ n and Φ is a given n × m matrix with n < m ≤ τ n , and we wish to solve for x ∈ ℝ m . We suppose ...
A computational algorithm for minimizing total variation in image restoration
A reliable and efficient computational algorithm for restoring blurred and noisy images is proposed. The restoration process is based on the minimal total variation principle in...
Publication Info
- Year
- 2007
- Type
- article
- Volume
- 35
- Issue
- 3
- Citations
- 484
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
484
OpenAlex
Cite This
Saharon Rosset,
Ji Zhu
(2007).
Piecewise linear regularized solution paths.
The Annals of Statistics
, 35
(3)
.
https://doi.org/10.1214/009053606000001370
Identifiers
- DOI
- 10.1214/009053606000001370