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:
- 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.
- 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.
- 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.
Similar improved rates and finite trajectory length properties were proven for the AVD dynamical system, as shown below.
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