Piecewise linear regularized solution paths

By Saharon Rosset, Ji Zhu. 2007

534 citations recorded by the source corpus.

We consider the generic regularized optimization problem β(λ) = argminβ 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(β) = ∥β∥ 1 is the l 1 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.

Subfields: Computational Mechanics, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Regularization Paths for Generalized Linear Models via Coordinate Descent (2010, background): “Rosset and Zhu (2007) characterize the class of problems where piecewise-linearity exists—both the loss function and the penalty have to be quadratic or piecewise linear.”
Joint covariate selection and joint subspace selection for multiple classification problems (2010, background): “There are problems—including 1-regularized least-squares regression and the 1- and 2-regularized support vector machines—for which this path is piecewise linear and for which it is possible to follow the path exactly (Efron et al. 2004; Rosset and Zhu 2007).”
Nearly unbiased variable selection under minimax concave penalty (2010, methodology): “Extensions of the LARS with large step size ∆(k) have been considered by Rosset and Zhu (2007) for support vector machine and by Zhang (2007a) for continuous generalized gradient descent.”
Adaptive piecewise polynomial estimation via trend filtering (2013, background): “…locally adaptive regression estimate (15) is the main object of theoretical study in Mammen and van de Geer (1997), but practically speaking, this estimate is diﬃcult to compute when k ≥ 2, because the possible knot locations are generally not easy to determine [see also Rosset and Zhu (2007)].”
Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence (2017, methodology): “[34] derive an analogous homotopy method for SVMs, while Rosset and Zhu [80] derive a generic homotopy method for the case of piecewise-linear gi functions.”
Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig (2007, unknown): “However, the flat faces of both the loss and the penalty functions can cause jumps in the path, similarly to what happens in the 1-penalized quantile regression (Rosset and Zhu [16]).”
Model selection and estimation in regression with grouped variables (2006, background): “Rosset and Zhu (2004) studied several related piecewise linear solution path algorithms.”
The solution path of the generalized lasso (2010, unknown): “The ﬁrst of its kind, LARS inspired the development of path algorithms for various other optimization problems that appear in statistics [16, 25, 19, 20], and our case is no exception.”
Sensitivity analysis using approximate moment condition models (2018, methodology): “To minimize the above display and give the solution path as ` varies, we use arguments similar to those in Theorem 2 of Rosset and Zhu (2007). For i ∈ I, write κi = κ+,i − κ−,i, where κ+,i = max{κi, 0} and κ−,i = −min{κi, 0}.”
Approximating Concavely Parameterized Optimization Problems (2012, methodology): “Initially, exact path tracking methods have been developed for many machine learning problems [16, 18, 3, 9] starting with the algorithm for SVMs by Hastie et al.”
The Smooth-Lasso and other ℓ1+ℓ2-penalized methods (2011, methodology): “We emphasize this dependency by adding a subscript n to these parameters.”
Variable Selection in Predictive Regressions (2013, methodology): “Rosset and Zhu (2007) show that the optimal path β̂(γ) is piecewise linear in γ. This is an attractive property because the solution path can be computed at the same cost as a least squares calculation. A more efficient solution can be obtained by using the homotopy algorithm of Osborne, Presnell, a”