PaperlayerView exact revision on arXiv

Source-linked AI summary

Coordinate descent algorithms for lasso penalized regression

Tong Tong Wu, Kenneth Lange

arXiv:0803.3876v1stat.AP

TL;DR

The paper studies how to compute lasso-penalized regression efficiently, including high-dimensional and grouped-predictor settings. It develops and tests cyclic ℓ2 and greedy Edgeworth-based ℓ1 coordinate descent, finding strong practical speed while noting convergence and small-sample bias caveats.

  • Problem

    Lasso estimation requires efficient objective minimization and tuning-parameter selection when standard matrix-based regression becomes costly for many predictors.

  • Method

    The paper uses cyclic coordinate descent for penalized ℓ2 regression, greedy coordinate descent with Edgeworth’s algorithm for penalized ℓ1 regression, and majorization for grouped penalties.

  • Results

    Coordinate descent methods are reported to be very fast on data sets with adequate numbers of cases, while grouped ℓ2 methods remain impressive despite majorization increasing iterations.

  • Takeaways & Limitations

    Coordinate descent offers practical advantages for exploratory analysis and modern data sets where predictors greatly outnumber cases.

  • Takeaways & Limitations

    Edgeworth-based methods can converge to an inferior point or slow seesaw pattern, and lasso estimates are biased toward zero in small samples.

Abstract

from arXiv · show

Imposition of a lasso penalty shrinks parameter estimates toward zero and performs continuous model selection. Lasso penalized regression is capable of handling linear regression problems where the number of predictors far exceeds the number of cases. This paper tests two exceptionally fast algorithms for estimating regression coefficients with a lasso penalty. The previously known $\ell_2$ algorithm is based on cyclic coordinate descent. Our new $\ell_1$ algorithm is based on greedy coordinate descent and Edgeworth's algorithm for ordinary $\ell_1$ regression. Each algorithm relies on a tuning constant that can be chosen by cross-validation. In some regression problems it is natural to group parameters and penalize parameters group by group rather than separately. If the group penalty is proportional to the Euclidean norm of the parameters of the group, then it is possible to majorize the norm and reduce parameter estimation to $\ell_2$ regression with a lasso penalty. Thus, the existing algorithm can be extended to novel settings. Each of the algorithms discussed is tested via either simulated or real data or both. The Appendix proves that a greedy form of the $\ell_2$ algorithm converges to the minimum value of the objective function.

1. Introduction.

The paper addresses efficient lasso estimation for high-dimensional regression and develops coordinate-descent approaches for separate and grouped penalties.

  • Lasso penalized regression shrinks coefficients toward zero, encourages sparse solutions, and supports continuous model selection when predictors outnumber cases.
  • Efficient lasso estimation poses both optimization and tuning-parameter selection problems, especially because standard matrix-based methods scale cubically with predictor count.
  • The paper highlights coordinate descent for its simplicity, speed, and stability in penalized regression.
  • The paper adapts Edgeworth’s algorithm to greedy coordinate descent for ℓ1 regression and reports that it is faster than cyclic coordinate descent for ℓ2 regression.
  • For correlated predictors, penalty majorization combines cyclic coordinate descent with ℓ1 or ℓ2 penalties on grouped parameter norms.
  • The paper covers algorithms, convergence, grouped parameters, tuning-constant selection, and empirical tests.

2. Cyclic coordinate descent for ℓ2 regression.

Cyclic coordinate descent updates regression parameters one at a time, using directional derivatives and residual tracking to obtain fast, stable lasso optimization.

  • Cyclic coordinate descent cycles through parameters and updates each in turn.
  • The lasso’s nondifferentiability is handled through separate forward and backward coordinate-direction derivatives.
  • For each coordinate, directional derivatives determine whether an update can improve the convex objective and which direction to solve.
  • Skipped updates leave irrelevant parameters at zero, while descent at every update provides numerical stability without matrix operations.
  • Residual bookkeeping enables fast evaluation of the objective and derivative updates after intercept or coefficient changes.

3. Greedy coordinate descent for ℓ1 regression.

The paper develops greedy coordinate descent for penalized ℓ1 regression by adapting Edgeworth’s algorithm, while documenting its practical speed and convergence limitations.

  • Greedy coordinate descent selects the coordinate with the most negative forward or backward directional derivative.
  • Edgeworth’s algorithm updates the intercept using a median and slope or coefficient coordinates using weighted medians.
  • Edgeworth’s algorithm can converge to an inferior point and may exhibit a slow seesaw pattern.
  • Greedy coordinate descent usually identifies relevant predictors and converges faster than cyclic coordinate descent in the numerical examples.
  • Lasso penalty terms can be represented as absolute values of pseudo-residuals, allowing Edgeworth’s algorithm to apply.
  • The nondifferentiability of the ℓ1 objective makes theoretical properties of ℓ1 estimators difficult to analyze.

4. Convergence of the algorithms.

The paper examines convergence for coordinate-descent algorithms when nondifferentiable lasso objectives make standard cyclic-coordinate arguments insufficient. It proves minimum-point convergence for the ℓ2 greedy algorithm but does not specify a convergence rate or a simple uniqueness condition.

  • Nondifferentiability complicates convergence because nonnegative coordinate directional derivatives alone do not guarantee a minimum point.The paper contrasts this with textbook cyclic-coordinate convergence results for continuously differentiable objectives.
  • Every cluster point of the ℓ2 greedy coordinate descent algorithm is a minimum point of the objective function.If the minimum is unique, the algorithm converges to it; if the algorithm converges, its limit is a minimum point.
  • The qualitative convergence theory does not specify the rate of convergence.
  • For underdetermined problems with lasso penalties, strict convexity can fail, and the paper conjectures that almost all design matrices nevertheless yield a unique minimum.The conjecture is stated with respect to Lebesgue measure and is not presented as a proved result.

5. ℓ2 regression with group penalties.

The paper extends ℓ2 coordinate descent to grouped parameters by using Euclidean-norm group penalties and majorization. The resulting updates preserve the coordinate-descent structure, although majorization can slow convergence while retaining impressive overall speed.

  • Euclidean-norm penalties couple parameters within groups while preserving convexity, making them suitable group penalties for cyclic coordinate descent.The paper contrasts them with separate ℓ1 penalties and scaled sums of squares, which it disqualifies as sensible group penalties.
  • Grouped effects encourage coordinated inclusion or exclusion of parameters rather than separate selection.If another parameter in a group is nonzero, the directional-derivative penalty contribution for a zero coordinate can drop, making movement away from zero easier.
  • Mixed penalties combine group-level Euclidean shrinkage with individual lasso shrinkage, and remain convex norms.Setting λ2 = 0 gives the lasso, while λ1 = 0 leaves only group penalties.
  • When a group is zero, coordinate minimization reduces to the standard ℓ2-with-lasso update with λ = λ1 + λ2.When the group is nonzero, the standard update is replaced by a majorization-based alternative motivated by MM estimation.
  • Majorizing the group norm produces a quadratic-plus-lasso surrogate whose minimization drives the objective downhill.The grouped algorithm therefore stays within the framework of penalized ℓ2 regression and uses standard update machinery.
  • Grouped updates preserve the structure of cyclic coordinate descent, although majorization may slow convergence.The paper reports that majorization approximately doubles iterations, while the cheap iterations keep overall speed impressive.
  • Cross-validation selects tuning constants by evaluating testing error across omitted data batches.The paper frames this as a one-dimensional selection problem for a single λ and recommends inspecting the cross-validation error curve.

6. Selection of the tuning constant

The paper discusses practical selection of lasso tuning constants using grid evaluation or search methods, with initialization strategies that reuse solutions as λ decreases. Joint selection of grouped penalties is more difficult.

  • Grid evaluation of the cross-validation error can be inefficient near λ = 0, motivating bracketing and golden-section search shortcuts.The paper recommends grid sampling for important problems but notes that coordinate descent is fastest at large λ.
  • For grouped parameters, the paper recommends searching the one-dimensional slices λ1 = 0, λ2 = 0, and λ1 = λ2 as rough candidate cases.These slices can be handled with bracketing and golden-section search, whereas selecting both parameters jointly is considerably more difficult.
  • Warm starts reuse estimates from a nearby larger λ when moving to a smaller λ, reducing iterations until convergence.For a single λ, the recommended initial values are θ0 = 0 and all residuals ri = 0.

7. Analysis of simulated data.

Simulations evaluate coordinate descent for lasso-penalized ℓ1 and ℓ2 regression in highly underdetermined settings, examining tuning, accuracy, sparsity, speed, and algorithm comparisons.

  • Simulation design: The simulations use independent or Laplace errors and multivariate-normal predictors, including settings where p ≫ n.True coefficients are set to 1 for the first five predictors and 0 thereafter.
  • Tuning: Cross-validation selects λ by minimizing a sampled 10-fold error curve, followed by re-estimation of active parameters without the lasso penalty.The minimum is located using bracketing and golden-section search.
  • ℓ1 regression: For ℓ1 regression, coordinate descent remains fast at problem sizes up to (p,n) = (50000,500), retains almost all true predictors, and discards most irrelevant ones.Approximate prediction errors are very close to true prediction errors.
  • ℓ1 regression: Cross-validation gives an optimal λ around 45, versus around 50 using 20,000 testing cases, indicating a conservative bias in the simulated setting.The figure compares 10-fold cross-validation errors with testing errors.
  • ℓ2 regression: For ℓ2 regression, cyclic coordinate descent is faster than greedy coordinate descent, while both are faster and more robust than LARS and more successful in model selection.The table comparison concerns simulated data with normally distributed errors.
  • Algorithm comparison: Some competing ℓ1 algorithms fail on the comparison problem sizes because of large matrix inversions, infinite weights, or software execution problems.The reported difficulties concern iteratively reweighted least squares and standard Barrodale–Roberts software.

8. Analysis of real data.

The mice analysis compares lasso regression models using gene-expression predictors, including sex-specific grouped effects, with tuning selected by 10-fold cross-validation. The preferred grouped model retained 41 genes and included findings connected to fat metabolism.

  • The data comprise fat mass for 311 F2 mice and liver expression levels for 23,388 genes per mouse.
  • Sex-specific intercepts and gene effects were modeled, with bivariate vectors grouping predictors and parameters.
  • The ungrouped ℓ1 model selected λ ≈ 3.5, averaging 88.5 nonzero predictors and testing error 0.6533 under 10-fold cross-validation.
  • The ungrouped ℓ2 model selected λ = 7.8, averaging 36.8 predictors and testing error 0.7; its full-data model had 41 nonzero predictors.
  • The grouped model’s optimal pair was approximately (λ1, λ2) = (5,1), yielding 40.1 average nonzero predictors and prediction error 0.8167.
  • Among the grouped model’s 41 retained genes, 25 appeared in the ℓ1 model and 26 in the ungrouped ℓ2 model, with 20 genes common to all three models.
  • Pdk4 was identified as a known fat-metabolism gene whose upregulation was a good predictor of fat pad mass.

9. Discussion.

The discussion emphasizes that coordinate descent is fast and useful for sparse, high-dimensional exploratory regression, while noting unresolved convergence theory and small-sample shrinkage bias. Grouped-parameter extensions remain computationally practical despite requiring more iterations.

  • Lasso regression supports continuous model selection without hypothesis testing, while coordinate descent helps address data sets where predictors greatly outnumber cases.
  • The algorithms’ speed is attributed to avoiding matrix operations and quickly dismissing poor predictors; empirical evidence reduced concerns about Edgeworth’s algorithm on adequately sized data sets.
  • Small-sample lasso estimates are biased toward zero, so the authors re-estimate active parameters without the penalty after selecting them.
  • Failure to remove the penalty tends to favor smaller λ values in cross-validation and inclusion of irrelevant predictors.
  • The convergence rate of the algorithms remains undetermined, and improving Edgeworth’s theoretical behavior without sacrificing speed is an open challenge.
  • Majorization approximately doubles iterations for grouped ℓ2 coordinate descent, but cheap iterations preserve impressive overall speed.
  • The authors report promising initial experiments with cyclic coordinate descent for logistic regression, where Newton’s method solves one-dimensional subproblems.

APPENDIX: CONVERGENCE THEORY

The appendix analyzes greedy ℓ2 coordinate descent for a convex, potentially nondifferentiable objective. It establishes that stationary points are minimum points and proves convergence of cluster points to minima.

  • The objective has a minimum because f(θ) is continuous and coercive, with f(θ) tending to infinity as ∥θ∥2 tends to infinity.
  • Greedy coordinate selection is governed by directional behavior of the objective along coordinate updates.
  • Although h(θ) is not continuous, it is upper semicontinuous, a property sufficient for the convergence argument.
  • For the convex objective, stationary points and minimum points coincide because nonnegative directional derivatives imply no feasible direction can reduce f(θ).
  • Every cluster point of greedy ℓ2 coordinate descent is a minimum; uniqueness makes the algorithm converge to that minimum.
  • The proof uses quadratic majorization of a coordinate-wise function on the side of zero with the most negative directional derivative.

SUPPLEMENTARY MATERIAL

The supplementary appendix proves weak consistency for penalized ℓ1 estimators by adapting arguments for nonlinear ℓ1 regression to linear models.

  • The supplementary appendix proves weak consistency of penalized ℓ1 estimators under relaxed and clarified regularity conditions for linear models.
Loading 0803.3876v1…