Thresholding gradient methods in Hilbert spaces: support identification\n and linear convergence

Guillaume Garrigos, Lorenzo Rosasco, Silvia Villa

Abstract

This paper investigates the $\ell^1$ regularized least squares optimization problem within separable Hilbert spaces. We demonstrate that the Iterative Soft-Thresholding Algorithm (ISTA) achieves linear convergence without requiring restrictive assumptions on the linear operator or the specific problem instance. This result stems from two fundamental concepts: the "extended support"—a finite set encompassing the solution's support—and the property of conditioning over finite-dimensional sets. We prove that ISTA identifies the solution's extended support in a finite number of iterations. Once identified, the problem effectively reduces to a finite-dimensional one where conditioning ensures linear convergence. Our analysis generalizes to a broad class of thresholding gradient algorithms, offering a novel proof of strong convergence and explicit convergence rates.

Introduction

In signal processing and machine learning, $\ell^1$ regularization (e.g., LASSO) is a standard technique for promoting sparsity. The Iterative Soft-Thresholding Algorithm (ISTA) is the primary tool for solving these problems, especially in high-dimensional or infinite-dimensional settings. While ISTA's convergence is well-established, its rate of convergence often appears faster in practice than theoretical bounds suggest. Traditionally, linear convergence guarantees required strict conditions like the Restricted Isometry Property (RIP) or injectivity of the linear operator. This work bridges the gap by showing that linear convergence is an inherent structural property of $\ell^1$ regularized least squares in Hilbert spaces.

Theoretical Framework: Forward-Backward Splitting

The authors frame thresholding gradient methods as instances of Forward-Backward splitting. The objective function is decomposed into a smooth data-fidelity term (least squares) and a non-smooth sparsity-promoting regularizer.

Thresholding operators used in gradient methods to promote sparsity.

The core innovation lies in two theoretical pillars:

  1. Extended Support Identification: The "extended support" is defined as a finite set of indices containing the solution's support and indices where dual constraints are active. The paper proves that ISTA iterates eventually reside within this finite-dimensional subspace after a finite number of steps.
  2. Finite Uniform Conditioning: For $\ell^1$ regularized problems, the objective function exhibits "2-conditioning" on finite-dimensional subspaces. This ensures that once the algorithm identifies the extended support, it behaves like a gradient method on a well-conditioned finite-dimensional problem, leading to linear convergence.

Key Insights

  • Emergent Finite-Dimensionality: Even in infinite-dimensional Hilbert spaces, the algorithm naturally "shrinks" the problem into a finite-dimensional subspace.
  • Structural Linear Convergence: Linear convergence for $\ell^1$ least squares is a structural property—it does not depend on specific properties of the linear operator $A$, but rather on the interplay between the $\ell^1$ norm and the least squares loss.
  • Generalization: The framework extends beyond $\ell^1$ to elastic-net penalties ($\ell^1 + \ell^p$), providing a unified convergence analysis for various thresholding schemes.
Geometric illustration of level sets and support identification in the optimization landscape.

Convergence Results

  • Finite Identification (Theorem 3.9): The number of iterations to identify the extended support is finite and depends on the initial error and dual stability.
  • Linear Convergence (Theorem 4.8): For $\ell^1$ regularized least squares, iterates $x^n$ converge to $\bar{x}$ at a linear rate: $\|x^{n+1} - \bar{x}\| \leq C\sqrt{\epsilon^n}$.
  • Rates for $\ell^1 + \ell^p$ (Theorem 4.11):
    • For $1 < p < 2$, convergence remains linear.
  • For $p > 2$, convergence is sublinear ($O(n^{-\frac{1}{p-2}})$), outperforming the general $O(1/n)$ rate.

Conclusion and Future Directions

This work provides a robust theoretical foundation for the observed efficiency of ISTA. Future research may explore extending these results to non-separable penalties like the Group LASSO or "gridless" problems involving measures in Banach spaces. While linear convergence is guaranteed, precisely estimating the convergence constant remains a challenge as it depends on the local geometry of the operator restricted to the extended support.

Summary updated

Abstract

We study $\\ell^1$ regularized least squares optimization problem in a\nseparable Hilbert space. We show that the iterative soft-thresholding algorithm\n(ISTA) converges linearly, without making any assumption on the linear operator\ninto play or on the problem. The result is obtained combining two key concepts:\nthe notion of extended support, a finite set containing the support, and the\nnotion of conditioning over finite dimensional sets. We prove that ISTA\nidentifies the solution extended support after a finite number of iterations,\nand we derive linear convergence from the conditioning property, which is\nalways satisfied for $\\ell^1$ regularized least squares problems. Our analysis\nextends to the the entire class of thresholding gradient algorithms, for which\nwe provide a conceptually new proof of strong convergence, as well as\nconvergence rates.\n
BibTeX
@inproceedings{garrigos2019thresholding,
  author = {Guillaume Garrigos and Lorenzo Rosasco and Silvia Villa},
  title = {{Thresholding gradient methods in Hilbert spaces: support identification\textbackslash\{\}n and linear convergence}},
  booktitle = {ESAIM},
  year = {2019},
  doi = {10.1051/cocv/2019011},
}
Figure