Source-linked AI summary
Complexity Analysis of the Lasso Regularization Path
Julien Mairal, Bin Yu
TL;DR
The Lasso path is piecewise linear, but its worst-case segment complexity had not been characterized. This paper analyzes exact and approximate paths, proving an exact worst-case segment count and presenting a practical approximate homotopy algorithm.
Problem
The worst-case complexity of the Lasso regularization path remained unknown, although empirical experience suggested its segment count was linear in problem size.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
A practical approximate homotopy algorithm can provide approximate paths at a desired precision when an exact path is not required.
Source: §5 · p. 8Exact homotopy assumes variables enter or leave one at a time, and can fail when a path segment is shorter than numerical precision.
Source: §2 · p. 3
Abstract
from arXiv · showhide
The regularization path of the Lasso can be shown to be piecewise linear, making it possible to "follow" and explicitly compute the entire path. We analyze in this paper this popular strategy, and prove that its worst case complexity is exponential in the number of variables. We then oppose this pessimistic result to an (optimistic) approximate analysis: We show that an approximate path with at most O(1/sqrt(epsilon)) linear segments can always be obtained, where every point on the path is guaranteed to be optimal up to a relative epsilon-duality gap. We complete our theoretical analysis with a practical algorithm to compute these approximate paths.
1. Introduction
The Lasso path’s worst-case complexity was unknown despite empirical experience suggesting linear growth. This paper establishes an exact worst-case result and gives an approximate-path analysis and algorithm.
1. Introduction
- Homotopy methods follow piecewise-linear regularization paths by computing each segment’s direction and the points where that direction changes.The regularization path is the set of solutions over values of the regularization parameter.Source: §1 · p. 1
- The paper addresses the gap that Lasso path complexity remained theoretically unknown, despite empirical experience suggesting a linear number of segments.The introduction compares this gap with worst-case complexity results for the simplex algorithm and SVM paths.Source: §1 · p. 1
- Exactly (3p+1)/2 linear segments are possible in the worst case for a Lasso path with p variables.The proof constructs examples recursively, adding a variable to increase path complexity multiplicatively.Source: §1 · p. 1
- The paper’s constructive adversarial proof differs from earlier simplex and SVM approaches and produces surprisingly simple pathological examples.It builds a p+1-variable problem from a p-variable problem, multiplying path complexity.Source: §1 · p. 1
- Approximate paths can be obtained with every point guaranteed optimal up to a relative ε-duality gap.The analysis leads to a practical approximate homotopy algorithm.Source: §1 · pp. 1–2
2. Background on the Lasso
The Lasso uses an ℓ1 penalty to induce sparsity, and under a full-rank condition its path is continuous and piecewise linear. Homotopy follows that path, subject to numerical and event assumptions.
2. Background on the Lasso
- The ℓ1 penalty induces sparsity, λ controls regularization, and the regularization path collects solutions for all positive λ.The paper assumes uniqueness under conditions detailed later.Source: §2 · p. 2
- Lasso optimality is characterized by residual-correlation conditions; when the active-set matrix is full rank, the solution is unique and has the stated active-set form.The active set contains indices whose residual correlations attain λ; η records residual-correlation signs.Source: §2 · p. 2
- Under the stated full-rank assumption, the Lasso solution is unique and its regularization path is continuous and piecewise linear.Solutions with the same signs at two parameter values define a linear segment between them.Source: §2 · pp. 2–3
- Homotopy initializes at λ = ∥X⊤y∥∞, follows the path direction, and updates the active set when variables enter or leave.It records successive parameter-solution pairs until λ reaches zero.Source: §2 · p. 3
- Exact homotopy assumes invertibility and one-at-a-time variable events; ill-conditioning can truncate the path, and sub-precision segments can cause failure.The paper says its approximate homotopy algorithm is robust to the short-segment issue; the exact algorithm can have exponential complexity.Source: §2 · p. 3
3. Worst-Case Complexity
The section bounds Lasso path length by possible sparsity patterns, then constructs an adversarial variable-extension scheme that attains the worst-case bound.
3. Worst-Case Complexity
- The upper bound follows because the path cannot contain both a nonzero sparsity pattern and its opposite, reducing the possible patterns to at most (3^p+1)/2.Although there are 3^p possible sign patterns, opposite nonzero patterns cannot both occur on the same path.Source: §3 · p. 3
- Adding one variable can expand a path with k segments into one with 3k−1 segments by cycling through original and sign-reversed sparsity patterns.The first k patterns retain the original variables’ patterns; later patterns reverse their signs while the new variable is active.Source: §3 · pp. 3–4
- The worst-case Lasso path has exactly (3^p+1)/2 linear segments, attained by a recursively constructed example.The construction starts with one variable and adds variables recursively, with k_{p+1}=3k_p−1.Source: §3 · p. 5
3.1. Numerical Simulations
- For p = 11, the implementation produced 88,574 segments; closely spaced kinks cause precision issues as p grows.Figure 1 illustrates a p = 6 path with 365 kinks, with coefficient values shown on a nonlinear scale.Source: §3.1 · p. 5, Figure 1 · p. 5
4. Approximate Homotopy
The paper gives an approximate-path complexity guarantee and a homotopy algorithm that avoids exact path sampling, then reports simulations consistent with the analysis. Approximation sharply reduces complexity on the pathological example, while real-data paths remain on the order of problem size.
4. Approximate Homotopy
- Approximate optimality conditions support ε-approximate regularization paths, and sampling solutions yields an ε-approximate piecewise-linear, in fact piecewise-constant, path.Compared with prior O(1/ε) linear-segment paths guaranteed by δ ≤ ε duality gap, this uses relative duality gaps δ ≤ εfλ(w).Source: §4 · p. 6
- The paper compares its relative-gap analysis with prior approximate-path results, which offer O(1/ε) segments under a weaker guarantee.The paper notes that related methodology for relative duality gaps can yield complexity bounds for other problems, but not for the Lasso.Source: §4 · p. 6
- The approximate homotopy algorithm avoids exact path solutions, follows piecewise-linear segments when possible, and uses a first-order method when segments are too short.It returns an ε-approximate path on [λ∞, λ1] and provides optimality guarantees along the path.Source: §4 · pp. 6–7
4.1. Numerical Simulations
- The simulations sample approximate paths and check their duality gaps, reporting results consistent with Propositions 3 and 4.The four datasets are SYNTH, PATHOL, MADELON, and PC-MAC; the columns of X and vector y are centered and normalized.Source: §4.1 · pp. 7–8
- For ε = 10^-3, the pathological example’s approximate path has less than 0.5% of the full path’s complexity, while real-data paths are of the same order as problem size.Real-data path complexity also decreases as ε increases.Source: §4.1 · p. 8
5. Conclusion
The paper establishes exponential worst-case complexity for the Lasso regularization path, then shows that approximate paths require relatively few points and proposes an algorithm to compute them at a desired precision.
5. Conclusion
- The Lasso regularization path has exponential worst-case complexity.The paper states that this had not previously been formally proved, to the authors’ knowledge.Source: §5 · p. 8
- When an exact path is unnecessary, only a relatively small number of path points need to be computed.Source: §5 · p. 8
- The paper proposes a practical approximate homotopy algorithm for computing approximate paths at a desired precision.Source: §5 · p. 8