A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem

Lin Xiao; Tong Zhang

Source-linked AI summary

A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem

Lin Xiao, Tong Zhang

arXiv:1203.3002v1Mar 14, 2012math.OCcs.ITstat.ML

TL;DR

The paper addresses slow convergence for ℓ1-regularized least-squares in underdetermined sparse-recovery settings. It uses proximal-gradient homotopy to preserve sparsity along the solution path, enabling geometric convergence under suitable conditions.

Problem
For m < n, the ℓ1-LS objective is not strongly convex, so direct proximal-gradient methods have O(1/ε) iteration complexity despite low per-iteration cost.
Method
The proximal-gradient homotopy method solves successive problems with decreasing regularization parameters, using each approximate solution to warm start the next stage.
Results
Under suitable sparse-recovery conditions, all iterates along the homotopy path remain sparse, making the objective effectively strongly convex and yielding geometric convergence.
Takeaways & Limitations
The homotopy strategy provides a theoretically supported global geometric convergence approach for sparse ℓ1-LS recovery, with numerical experiments supporting the analysis.
Takeaways & Limitations
The guarantees apply only to problems with provable sparse solutions, and parameters η and δ depend on A and λ.

Abstract

from arXiv · show

We consider solving the $\ell_1$-regularized least-squares ($\ell_1$-LS) problem in the context of sparse recovery, for applications such as compressed sensing. The standard proximal gradient method, also known as iterative soft-thresholding when applied to this problem, has low computational cost per iteration but a rather slow convergence rate. Nevertheless, when the solution is sparse, it often exhibits fast linear convergence in the final stage. We exploit the local linear convergence using a homotopy continuation strategy, i.e., we solve the $\ell_1$-LS problem for a sequence of decreasing values of the regularization parameter, and use an approximate solution at the end of each stage to warm start the next stage. Although similar strategies have been studied in the literature, there have been no theoretical analysis of their global iteration complexity. This paper shows that under suitable assumptions for sparse recovery, the proposed homotopy strategy ensures that all iterates along the homotopy solution path are sparse. Therefore the objective function is effectively strongly convex along the solution path, and geometric convergence at each stage can be established. As a result, the overall iteration complexity of our method is $O(\log(1/ε))$ for finding an $ε$-optimal solution, which can be interpreted as global geometric rate of convergence. We also present empirical results to support our theoretical analysis.

1 Introduction

The paper develops a proximal-gradient homotopy method for sparse ℓ1-regularized least squares, addressing slow single-stage convergence and the lack of global complexity analysis for approximate homotopy strategies. Under sparse-recovery conditions, it establishes geometric convergence and O(log(1/ε)) iteration complexity.

Motivation: The ℓ1-LS problem is a convex sparse-recovery formulation used in compressed sensing, machine learning, signal processing, and statistics.The ℓ1 penalty promotes sparse solutions, and the compressed-sensing setting models recovery of a sparse vector from noisy measurements.
Motivation: Standard proximal-gradient methods have low per-iteration cost but can have slow convergence when the underdetermined objective is not strongly convex.For dense matrices, proximal-gradient steps use soft thresholding, while general-purpose alternatives can incur substantial per-iteration computational costs.
Proposed approach: Approximate homotopy continuation solves successively smaller regularization problems, warm-starting each stage with the previous approximate solution; this is called proximal-gradient homotopy (PGH).The method starts from a large regularization parameter and decreases it until reaching the target value.
Contribution: The paper addresses the previously unanalyzed global iteration complexity of approximate proximal-gradient homotopy methods by specifying how regularization values and stage accuracies should be chosen.Prior work reported strong empirical performance for sparse solutions but left key continuation choices largely heuristic.
Guarantees: Under a sufficiently large target λ and a RIP-like condition, PGH achieves geometric convergence at each stage and O(log(1/ε)) overall iteration complexity.Because each proximal-gradient iteration costs O(mn) flops, the resulting computational complexity is O(mn log(1/ε)).
Comparison: The method avoids tracking every homotopy breakpoint and can require fewer proximal-gradient steps than the number of nonzeros in the target solution.The paper reports that this predicted advantage is supported by empirical studies.
Scope: The guarantees apply only when sparse solutions are provable, whereas interior-point performance is described as insensitive to solution sparsity and λ.The PGH parameters η and δ depend on the problem data A and the regularization parameter λ.

2 Preliminaries and notations

The preliminaries define composite-gradient tools, adaptive proximal-gradient updates, and restricted sparse-curvature conditions. These ingredients explain why ordinary convergence is sublinear without strong convexity but becomes geometric along a suitably sparse homotopy path.

Composite optimization: The objective is represented as a composite function with a convex differentiable part and a closed convex regularizer.For ℓ1-LS, the objective is written as φλ(x) = f(x) + λ∥x∥1.
Composite-gradient tools: The composite gradient mapping measures proximity to the optimality condition and defines the proximal-gradient step through a quadratic local model.When the regularizer is zero, the mapping reduces to the ordinary gradient and 1/L acts as the step size.
Proximal updates: For ℓ1-LS, the proximal step has a closed-form soft-thresholding solution, and the optimality residue can be computed with O(n) additional work.The residue is used as the stopping criterion for the proximal-gradient method.
Adaptive line search: Adaptive line search increases the estimated Lipschitz constant until its descent condition is satisfied, while later iterations can reduce the estimate.The line search is guaranteed to terminate once the estimate reaches the Lipschitz constant of the smooth component.
Convergence properties: The method decreases the objective monotonically unless the gradient mapping vanishes, in which case the new iterate is optimal.This descent property follows from the proximal-gradient model inequality.
Baseline rates: For a convex but not strongly convex objective, Nesterov’s method has O(1/ε) iteration complexity, whereas strong convexity yields O(log(1/ε)) complexity.The same algorithm can exploit strong convexity without knowing in advance whether it holds.
Restricted curvature: In the underdetermined case, homotopy enforces sparse iterates; under a RIP-like condition, this gives effective strong convexity along the path and a global geometric rate.Restricted smoothness and restricted strong convexity characterize the relevant sparse curvature behavior.

3 A proximal-gradient homotopy method

The PGH method decreases the regularization parameter through a sequence of stages, solving each ℓ1-LS problem approximately and warm-starting the next stage. Under sparse-recovery assumptions, its iterates remain sparse and the method achieves geometric convergence with O(log(1/ε)) total proximal-gradient steps.

Method: PGH starts at a large regularization parameter and gradually decreases it, using each stage’s approximate solution to warm-start the next stage.For intermediate stages it targets proportional precision δλK; the final stage uses absolute precision ε.
Method: The method uses Nesterov’s proximal-gradient method with adaptive line search to solve each fixed-λ subproblem.The algorithm initializes λ0 = ||A^T b||∞ and decreases λK geometrically using η.
Assumptions: Sparse iterates are guaranteed when λ dominates the noise and A satisfies the stated restricted-eigenvalue or RIP-like conditions.The analysis also requires conditions involving γ, δ′, ˜s, and Lmin; these ensure the target solution and all homotopy iterates are sparse.
Convergence results: Theorem 1 establishes local geometric convergence when the initial point is sparse and satisfies an adequate optimality condition.The convergence rate is expressed using a restricted condition number κ and is independent of λ.
Convergence results: O(log(1/ε)) proximal-gradient steps suffice for an ε-optimal solution, yielding a global geometric convergence rate.The per-stage bound is independent of the stage regularization parameter, while the constant depends on the restricted condition number and sparsity-related parameters.
Remarks: Solving every stage to high precision can instead yield the near-geometric bound O((log(λ0/ε))^2).For the noise-free basis-pursuit case, the same framework gives a global geometric interpretation for the solution path.

4 Proofs of convergence results

The convergence proof first establishes sparsity preservation for the iterates and then uses restricted strong convexity to derive geometric convergence and convergence to the unique sparse minimizer.

Sparsity preservation: If the initial iterate is sparse and has sufficiently small optimality residue, Algorithm 2 preserves sparsity across all generated iterates.Monotonic decrease of the objective allows the initial sublevel-set condition to propagate through the iterations.
Sparsity preservation: The proximal-gradient soft-thresholding map produces a sparse next iterate under the assumptions of Lemma 6.The proof bounds the number of nonzeros outside the target support using threshold splitting and restricted-eigenvalue estimates.
Limit convergence: Every accumulation point satisfies the optimality condition and is sparse, so the unique sparse minimizer x⋆(λ) is the limit of the iterate sequence.Boundedness and monotonic objective decrease provide accumulation points; sparsity and restricted strong convexity establish uniqueness.
Geometric convergence: Restricted strong convexity on the sparse iterates yields geometric decrease of the objective or distance to the optimum.The resulting rate is governed by a restricted condition number κ and does not depend on λ.
Overall complexity: Using absolute precision ε at the final target-λ stage gives an overall iteration complexity bounded by O(log(1/ε)).This converts the stagewise geometric behavior into a global geometric rate for the homotopy method.

5 Numerical experiments

Numerical experiments show that PGH maintains sparse iterates across homotopy stages, achieving geometric convergence and favorable computational cost on sufficiently sparse problems. Parameter studies and comparisons also identify trade-offs from continuation accuracy and reduced sparsity.

PGH maintains sparse iterates throughout the solution path and achieves geometric convergence at each homotopy stage.In the random sparse instance, PG iterates are initially dense and converge slowly, whereas PGH iterates remain below 300 nonzeros.
19 inner iterations reached absolute precision 10^-5 in PGH’s final stage, while earlier stages required only 1 to 4 iterations.The number of inner iterations remained relatively constant across intermediate stages despite changing tolerances.
PGH’s advantage is more pronounced when measured by matrix-vector multiplications, because proximal-gradient steps cost roughly three oracle calls versus eight for ADG steps.Matrix-vector multiplication counts were reported as a precise indicator of running time.
Varying η changed iterate sparsity substantially without greatly changing total iterations, because intermediate stages required only rough precision.The experiments found that η = 0.2 worked well for the tested instance despite the stated sufficient conditions.
On a non-sparse instance, all methods showed sublinear convergence, homotopy methods improved over single-stage methods less strongly, and ADG and ADGH performed best.The non-sparse case used a vector with 500 nonzero elements.
For basis pursuit, PGH achieved high-precision recovery in fewer than 150 iterations, corresponding to roughly 450 matrix-vector multiplications.This was reported as more efficient than exact homotopy path-following methods requiring at least 1000 breakpoints.

6 Conclusion and discussions

The paper analyzes a proximal-gradient homotopy method for sparse ℓ1-LS recovery, showing that sparsity along the solution path enables geometric convergence. Its discussion also identifies estimating restricted strong convexity for accelerated methods as outside the paper’s scope.

Under suitable sparse-recovery conditions, all proximal-gradient homotopy iterates along the solution path are sparse.
The iterates’ sparsity makes the objective effectively strongly convex along the solution path, enabling geometric convergence.
The paper focuses on ℓ1-regularized least squares for sparse recovery, where the objective is not strongly convex in general.
Accelerated gradient methods require the strong-convexity parameter or a non-trivial lower bound to obtain geometric convergence.
For m < n, exploiting restricted strong convexity with accelerated methods requires estimating its parameter on the fly, which the paper leaves for future investigation.