Abstract
We study the $\ell^1$ regularized least squares optimization problem in a separable Hilbert space. We show that the iterative soft-thresholding algorithm (ISTA) converges linearly, without making any assumption on the linear operator into play or on the problem. The result is obtained combining two key concepts: the notion of extended support, a finite set containing the support, and the notion of conditioning over finite-dimensional sets. We prove that ISTA identifies the solution extended support after a finite number of iterations, and we derive linear convergence from the conditioning property, which is always satisfied for $\ell^1$ regularized least squares problems. Our analysis extends to the entire class of thresholding gradient algorithms, for which we provide a conceptually new proof of strong convergence, as well as convergence rates.
Introduction
The Iterative Soft-Thresholding Algorithm (ISTA) is a cornerstone of sparse optimization, particularly for solving the Lasso problem ($\ell^1$ regularized least squares). While its convergence is well-established, the rate of convergence—especially in infinite-dimensional Hilbert spaces—has historically been thought to depend on specific properties of the linear operator, such as the Finite Basis Injective (FBI) property.
Recent research by Garrigos, Rosasco, and Villa demonstrates that ISTA achieves linear convergence universally for these problems, without requiring such restrictive assumptions. This result stems from the algorithm's ability to identify a finite-dimensional "extended support" in finite time, effectively reducing the problem's complexity.
Theoretical Framework: Extended Support and Conditioning
The core of the proof relies on two pillars:
- Extended Support: This is a finite set that contains the indices of the non-zero components of the solution (the support). It also incorporates information from the dual problem, specifically the "active constraints."
- Finite Uniform Conditioning: Although the objective function may not be strongly convex over the entire Hilbert space, it exhibits quadratic growth (conditioning) when restricted to finite-dimensional subspaces.
The authors show that ISTA identifies this extended support in a finite number of iterations. Once identified, the algorithm's iterates are confined to a finite-dimensional subspace where the objective function is naturally well-conditioned, leading to geometric (linear) convergence.
Convergence Analysis
The paper provides a rigorous analysis of the "Forward-Backward" class of algorithms.
Finite Identification
Theorem 3.10 establishes an explicit upper bound on the iterations needed to find the extended support. This bound is determined by the initial error and a stability constant $\rho_{sol}$ from the dual problem.
Linear Convergence Rates
For the standard Lasso problem, linear convergence is shown to be an inherent property. The error $f(x^n) - \inf f$ decreases at a geometric rate $\epsilon^n$. This analysis is further generalized to $\ell^1 + \ell^p$ regularizers, where linear rates are maintained for $p \in (1, 2]$, while sublinear rates appear for $p > 2$.
Discussion and Future Directions
The significance of this work lies in removing the need for "non-degeneracy" conditions to guarantee fast convergence. However, the current results are limited to separable penalties. Future work may explore:
- Structured Sparsity: Extending these concepts to non-separable penalties like Group Lasso.
- Gridless Recovery: Adapting the framework for sparse recovery in measures where supports may not be finite.
In conclusion, linear convergence of ISTA is a fundamental property of $\ell^1$ regularization in Hilbert spaces, driven by the finite-time identification of the problem's underlying sparse structure.
Summary updated