Strong Convergence of FISTA Iterates under H{ö}lderian and Quadratic Growth Conditions

Jean–François Aujol, Charles Dossal, Hippolyte Labarrière, Aude RondepierrearXiv 2024 · DOI · arXiv

Abstract

Introduced by Beck and Teboulle, FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) is a first-order method widely used in convex optimization. Adapted from Nesterov's accelerated gradient method for convex functions, the generated sequence guarantees a decay of the function values of $\mathcal{O}(n^{-2})$ in the convex setting. We show that for coercive functions satisfying some local growth condition (namely a Hölderian or quadratic growth condition), this sequence strongly converges to a minimizer. This property, which has never been proved without assuming the uniqueness of the minimizer, is associated with improved convergence rates for the function values. The proposed analysis is based on a preliminary study of the Asymptotic Vanishing Damping system introduced by Su et al. to model Nesterov's accelerated gradient method in a continuous setting. Novel improved convergence results are also shown for the solutions of this dynamical system, including the finite length of the trajectory under the aforementioned geometry conditions.

Introduction

In the realm of convex optimization, FISTA is a cornerstone algorithm. As a first-order method utilizing Nesterov-style acceleration, it achieves a convergence rate of $\mathcal{O}(n^{-2})$ for objective function values. However, a long-standing theoretical gap has persisted: while function values decrease rapidly, the strong convergence of the iterates themselves (convergence in norm) has typically required the assumption of a unique minimizer. In many real-world applications, such as compressed sensing or machine learning with redundant features, this uniqueness is not guaranteed. This paper addresses this challenge by proving strong convergence and improved rates without assuming uniqueness, provided the objective function exhibits specific growth properties around its set of minimizers.

Methodology

The authors employ a dual approach, bridging discrete algorithms with continuous dynamical systems:

  1. Lyapunov Analysis: The core proof relies on constructing "Lyapunov energy functions" that combine the objective function's error with the momentum of the iterates. Demonstrating the decrease of these energies allows for bounding the algorithm's behavior.
  2. The AVD System: The paper analyzes the Asymptotic Vanishing Damping (AVD) system, an ordinary differential equation (ODE) that serves as the continuous-time limit of FISTA. Insights regarding the "finite length" of the trajectory in the ODE setting are translated back to the discrete FISTA iterates.
  3. Set-Based Projections: Unlike previous work focusing on a single point $x^*$, this analysis measures distance to the entire set of minimizers $X^*$. This requires sophisticated handling of projections onto convex sets and assuming the set of minimizers is "second-order regular" (a property satisfied by polyhedral sets and sets with smooth boundaries).

Key Insights and Ideas

  • Growth Conditions as a Catalyst: The authors demonstrate that if a function grows at least as fast as a power of the distance to the solution set (Hölderian growth: $d(x, X^*)^\gamma$) or quadratically ($d(x, X^*)^2$), FISTA performs significantly better than in the standard convex scenario.
  • Finite Trajectory Length: A critical finding is that under these growth conditions, the algorithm's path has a finite total length. This property is stronger than simple convergence, as it implies the algorithm does not oscillate indefinitely near the solution set.
  • Parameter Sensitivity: The inertial parameter $\alpha$ (standardly set to 3) significantly influences the convergence rate. For functions with quadratic growth, a larger $\alpha$ leads to a faster polynomial decay of the error.
  • Robustness to Non-Uniqueness: The "sharpness" of the function (the growth condition) is sufficient to pull iterates strongly toward the solution set, regardless of whether that set is a single point or a complex manifold.

Convergence Results

The paper establishes improved convergence rates for both discrete iterates and the continuous-time AVD system. For functions satisfying a local Hölderian growth condition with parameter $\gamma > 2$, the function value error $F(x_n) - F^*$ decays at a rate of $\mathcal{O}(n^{-\frac{2\gamma}{\gamma-2}})$. Under quadratic growth, the error decays as $\mathcal{O}(n^{-\frac{2\alpha}{3}})$. These results are summarized in the following tables, which compare the new findings with existing literature.

Convergence rates for discrete FISTA iterates under various growth conditions.

Similar improved rates and finite trajectory length properties were proven for the AVD dynamical system, as shown below.

Convergence rates for the continuous-time AVD system.

Discussion and Limitations

While the paper provides significant theoretical advancements, some limitations remain for future exploration. The continuous-time analysis assumes the set of minimizers $X^*$ is "second-order regular," a technical condition that may be difficult to verify for arbitrary functions. Additionally, while the paper provides theoretical ranges for the parameter $\alpha$, finding the optimal $\alpha$ for a specific growth constant in practical settings remains an open area for research. Finally, extending the "finite length" property to the fully non-smooth composite case in continuous time remains a technical challenge.

Summary updated

Abstract

Introduced by Beck and Teboulle, FISTA (for Fast Iterative Shrinkage-Thresholding Algorithm) is a first-order method widely used in convex optimization. Adapted from Nesterov's accelerated gradient method for convex functions, the generated sequence guarantees a decay of the function values of $\mathcal{O}\left(n^{-2}\right)$ in the convex setting. We show that for coercive functions satisfying some local growth condition (namely a H\''olderian or quadratic growth condition), this sequence strongly converges to a minimizer. This property, which has never been proved without assuming the uniqueness of the minimizer, is associated with improved convergence rates for the function values. The proposed analysis is based on a preliminary study of the Asymptotic Vanishing Damping system introduced by Su et al. in to modelNesterov's accelerated gradient method in a continuous setting. Novel improved convergence results are also shown for the solutions of this dynamical system, including the finite length of the trajectory under the aforementioned geometry conditions.
BibTeX
@misc{aujol2024strong,
  author = {Jean–François Aujol and Charles Dossal and Hippolyte Labarrière and Aude Rondepierre},
  title = {{Strong Convergence of FISTA Iterates under H\{ö\}lderian and Quadratic Growth Conditions}},
  year = {2024},
  eprint = {2407.17063},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.17063},
}
Figure