Source-linked AI summary
Pathwise coordinate optimization
Jerome Friedman, Trevor Hastie, Holger Höfling, Robert Tibshirani
TL;DR
The paper asks whether largely overlooked one-at-a-time coordinate-wise descent can efficiently solve convex statistical optimization problems. It develops pathwise coordinate algorithms and generalized procedures for lasso-related models, finding strong lasso performance, broader applicability, and faster fused-lasso solutions while identifying limits for the general fused lasso.
Problem
Coordinate-wise descent is not commonly used for convex optimization, and its effectiveness across lasso-related and fused-lasso problems requires examination.
Method
The paper develops one-at-a-time coordinate descent with repeated soft-thresholding and generalized descent, fusion, and smoothing procedures for fused-lasso variants.
Results
Coordinate descent is very competitive with LARS for large lasso problems, converges to lasso estimates, applies to related methods, and generalized procedures solve fused-lasso variants much faster than standard convex optimization.
Takeaways & Limitations
Coordinate-wise algorithms are simple and well-suited to large convex statistical problems, including lasso, garrote, elastic net, and selected fused-lasso settings.
Takeaways & Limitations
Coordinate-wise descent does not work for the fused lasso because its objective is nondifferentiable and its penalty is nonseparable; the general fused-lasso extension is not guaranteed to yield the exact solution.
Abstract
from arXiv · showhide
We consider ``one-at-a-time'' coordinate-wise descent algorithms for a class of convex optimization problems. An algorithm of this kind has been proposed for the $L_1$-penalized regression (lasso) in the literature, but it seems to have been largely ignored. Indeed, it seems that coordinate-wise algorithms are not often used in convex optimization. We show that this algorithm is very competitive with the well-known LARS (or homotopy) procedure in large lasso problems, and that it can be applied to related methods such as the garotte and elastic net. It turns out that coordinate-wise descent does not work in the ``fused lasso,'' however, so we derive a generalized algorithm that yields the solution in much less time that a standard convex optimizer. Finally, we generalize the procedure to the two-dimensional fused lasso, and demonstrate its performance on some image smoothing problems.
1. Introduction.
The paper explores simple one-at-a-time coordinate-wise descent for convex statistical optimization, showing its effectiveness for lasso-related problems and extending it to broader settings. For the lasso, repeated soft-thresholding updates converge to the solution and provide an efficient pathwise algorithm.
- Motivation: Coordinate-wise descent is investigated for convex optimization problems where standard quadratic programming is commonly used, despite limited adoption of these simple algorithms.The paper focuses on problems with inequality constraints and on the potential value of coordinate-wise methods for convex statistical models.
- Scope and performance: The method is reported as very competitive with LARS for large lasso problems, delivers solution paths efficiently, and applies to the garrote and elastic net.The approach is described as especially useful for large p and as simple but fast for solving the lasso.
- Scope and performance: Fast coordinate descent depends on quick coordinate minimizations and efficient updates as variables are cycled, with many parameter minimizers often unchanged between iterations.These properties explain the reported speed of the iterations for the considered problem class.
- Lasso coordinate updates: The lasso solution with one standardized predictor is obtained by soft-thresholding the least-squares estimate.For positive estimates, γ is subtracted; for negative estimates, γ is added; sufficiently large γ yields zero.
- Lasso coordinate updates: For correlated predictors, the algorithm repeatedly applies soft-thresholding to partial residuals while holding the other coefficients fixed.Updates cycle through coordinates until convergence, extending the simple univariate solution to the multivariate lasso.
- Convergence: Starting from any coefficient values, the iterates converge to the lasso estimate, and on the diabetes data algorithm (9) converged after 14 steps for γ = 88.The example used 442 observations and 10 predictors.
2. Pathwise coordinatewise optimization algorithms.
The paper develops pathwise coordinate-wise descent for convex statistical problems, extending it beyond the lasso to related penalties and fused-lasso settings. It explains when separable coordinate updates converge, why fused-lasso coordinates can fail, and how generalized updates address that failure.
- Pathwise coordinatewise optimization algorithms: Pathwise coordinate descent solves a sequence of single-parameter optimization problems while varying the regularization parameter, using each solution as a warm start.This approach is attractive when each single-parameter problem is easy to solve.
- Lasso and related penalties: The same coordinate-wise framework extends to the nonnegative garotte, LAD-lasso, elastic net, grouped lasso, and Berhu penalty.Examples include weighted-median updates for LAD-type problems, proportional ridge shrinkage for elastic net, and group-wise updates for grouped lasso.
- Convergence and separability: Coordinate descent converges for separable penalties because the objective decomposes into convex functions of individual parameters or nonoverlapping parameter groups.This convergence result covers the lasso, grouped lasso, elastic net, and related methods.
- Fused lasso: In the fused lasso, the nonseparable penalty and nondifferentiable corners allow coordinate descent to become stuck even though the objective is strictly convex.A two-parameter example requires β63 and β64 to move together to reach the minimum; the coordinate-wise procedure remains at (−0.69, −0.69) instead of (−1.05, −1.05).
- Fused lasso: A generalized coordinate-wise procedure modifies the updates for the fused lasso and yields the solution much faster than a general quadratic-program solver.The paper also applies the fused-lasso approach to signal smoothing, including Glioblastoma copy-number data.
3. The fused lasso signal approximator.
The fused-lasso signal approximator extends coordinate-wise optimization to one-dimensional signals, combining coordinate descent with fusion and smoothing cycles. The procedure follows a path over λ2, collapses fused neighboring parameters, and is supported by assumptions about how fusions occur and persist.
- Fused-lasso signal approximator: The fused-lasso signal approximator applies coordinate-wise optimization to one-dimensional signals and also connects to total variation denoising when λ1 = 0.There is one parameter per observation, and the method is presented as a fast implementation for total variation denoising.
- Algorithm: The algorithm uses three nested cycles: coordinate descent, neighboring-parameter fusion, and λ2 smoothing.The smoothing cycle increases λ2 incrementally and reruns the descent and fusion cycles.
- Descent cycle: Each coordinate minimization searches piecewise-linear intervals separated by zero and neighboring parameter values, then checks discontinuities if no zero-crossing exists.This gives an explicit solution when a zero-crossing exists and otherwise selects the active constraint with the smallest objective value.
- Fusion cycle: When single-coordinate descent stalls, the fusion cycle temporarily constrains neighboring parameters to a common value and accepts the fused move if it decreases the objective.The fusion is equivalent to collapsing the pair into one weighted observation and one parameter.
- Smoothing cycle: The smoothing cycle starts from λ2 = 0 and repeatedly increments λ2, converges the descent and fusion cycles, collapses equal nonzero neighbors, and updates weights.Solutions are therefore obtained sequentially over an increasing grid of λ2 values, with each collapsed problem retaining weighted averages.
4. Optimality conditions.
The paper formulates FLSA optimality through subgradient equations and uses them to analyze fusion behavior along the λ2 path. The resulting conditions establish the relevant fusion assumptions for FLSA under stated data and increment conditions.
- Optimality conditions: Subgradient equations provide necessary and sufficient optimality conditions for the fused-lasso signal approximation problem.The sign variables for coefficients and adjacent differences may lie in [−1,1] when the corresponding quantities are zero.
- Persistence of fusions: The FLSA analysis proves that fused sets remain fused as λ2 increases because the associated subgradient values remain within [−1,1].The path changes when a boundary point fuses with the current set.
- Fusion events: When the observations are in general position and λ2 increments are sufficiently small, fusions occur one pair of neighboring points at a time.The proof identifies distinct λ2 values at which these fusion events occur.
5. Comparison of run times.
The paper compares pathwise coordinate optimization with standard methods for lasso and fused-lasso problems. Coordinate descent is competitive for lasso, scales roughly linearly, and can be substantially faster for fused lasso.
- Lasso timings: Coordinate descent is fastest at small predictor correlations, slows as correlations increase, and remains competitive with LARS and homotopy methods.The authors report potential speedups especially when n > p.
- Lasso timings: CPU times for coordinate descent are roughly linear in both n and p.Figure 8 averages times over five runs and over the other varying parameter.
- Lasso timings: Efficient coordinate updates exploit squared-error structure, avoiding repeated O(n) calculations at every step.Feature-response inner products are computed initially, while later updates reuse quantities as variables enter the model.
- Fused-lasso timings: Timing comparisons are conservative because each coordinate-method table entry computes an entire solution path, while warm starts could produce all λ2 solutions for a fixed λ1 in one run.The standard procedure was also allowed to exploit warm starts.
6. The two-dimensional fused lasso.
The two-dimensional fused lasso extends spatial fusion to pixel grids and is addressed with a pathwise descent-and-fusion strategy. Experiments show useful image denoising, while correctness is established only empirically in the reported two-dimensional setting.
- Model and motivation: The two-dimensional fused-lasso penalties encourage parameter maps to be sparse and spatially smooth.The formulation relates the model to total-variation denoising, though its two-dimensional discretization uses absolute first differences rather than Euclidean norms.
- Algorithm: For a p × p grid, the quadratic-programming formulation has 7p^2 variables and 3p^2 + 3 constraints, making exact optimization impractical at p = 256.At p = 256, this corresponds to 458,752 variables and 196,611 constraints, besides nonnegativity constraints.
- Algorithm: The pathwise algorithm starts with individual pixels, performs coordinate descent over four-neighborhood groups, and fuses accepted neighboring groups.After fusion, the new neighborhood is the union of the joined groups’ neighborhoods, excluding the groups themselves.
- Caveat: The two-dimensional procedure was found to give the exact solution in limited experiments, but the authors provide no correctness proof and anticipate additional assumptions may be needed.The method was also tested on a 512 × 512 block image, where the noiseless reconstruction was perfect and the noisy reconstruction captured most important features.
- Examples: In a toy plus-shaped image with N(0,1) noise, tuning parameters were selected by a two-fold odd-pixel training and even-pixel testing scheme.The reconstruction panels compare lasso and fused lasso solutions.
- Examples: For the Fisher image, pure fusion reduced reconstruction error from 6.18 to 1.15, whereas pure lasso produced no improvement.The noisy 256 × 256 grayscale image used Gaussian noise with standard deviation 2.5; the best pure-lasso penalty was λ1 = 0.
7. Discussion.
The discussion argues that coordinate-wise descent merits broader use in convex optimization because it is simple, scalable, and effective for several structured problems. Its guarantees and effectiveness depend on problem structure, especially separable or limited-constraint settings.
- Discussion: Coordinate-wise descent is simple and well-suited to large convex optimization problems.The authors report that it is very competitive with LARS for lasso.
- Discussion: The generalized procedure handles problems where constraints involve only a limited number of parameters, including the fused lasso signal approximator.For this special fused-lasso case, it runs many times faster than a standard convex optimizer.
- Discussion: The general fused-lasso problem remains a boundary case because coordinate-wise descent is not guaranteed to reach the solution and can become stuck away from it.The paper distinguishes this limitation from the favorable behavior observed for the fused lasso signal approximator.
- Implementation: For the lasso and one- and two-dimensional fused lasso, the authors planned to release Fortran and R implementations freely.The release covers the computational procedures discussed in the paper.
A.1. Proof of Proposition 1.
The appendix proves that increasing the coefficient penalty produces solutions obtained by soft-thresholding a solution with the same fusion penalty. This result supports pathwise optimization across regularization parameters.
- Setup: The fused-lasso penalty generalizes by allowing an L1 penalty on selected coefficient differences, including one-dimensional and two-dimensional neighbor structures.The set C identifies penalized pairs, with λi,j specifying their fusion penalties.
- Proof strategy: The proof assumes the solution at λ1 = 0 and fixed λ2 is known, then analyzes the subgradient equations for λ1 > 0.The subgradient variables encode coefficient signs and signs of pairwise differences, with values in [-1,1] at zero or equality points.
- Proof strategy: Soft-thresholding preserves the ordering of nonzero coefficient pairs, allowing the fusion subgradient values to remain fixed as λ1 changes.When both coefficients are zero, the corresponding fusion subgradient can be chosen arbitrarily within [-1,1].
- Proof strategy: The coefficient subgradient is handled either by retaining its sign for nonzero coefficients or by choosing βi(0)/λ1 when the thresholded coefficient is zero.These choices keep the subgradient equations valid for every λ1 > 0.
- Result: Therefore, soft-thresholding the λ1 = 0 solution gives the solution for positive λ1, and more generally increasing λ1 soft-thresholds the solution at the smaller λ1.The proposition relies on existence and uniqueness of the minimizer for nonnegative λ1 and λ2.