FISTA is an automatic geometrically optimized algorithm for strongly convex functions

Jean-François Aujol, Charles Dossal, Aude RondepierreMath. Program 2024 · DOI

Introduction

In first-order optimization, algorithms are typically categorized by the geometry of the functions they solve. For general convex functions, the Forward-Backward (FB) method converges at a rate of $O(1/n)$, while accelerated methods like the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) achieve $O(1/n^2)$. However, when functions exhibit "bowl-like" geometry—known as strong convexity or quadratic growth—much faster exponential convergence is possible.

Traditionally, achieving these top-tier rates required dedicated schemes like Nesterov’s Strongly Convex (NSC) method, which necessitates an accurate estimate of the strong convexity parameter ($\mu$). Underestimating $\mu$ leads to significant slowdowns, while many real-world problems (like LASSO) satisfy quadratic growth without being strictly strongly convex. This paper, published in Mathematical Programming (2023), explains why FISTA often outperforms expectations on these "easy" problems without needing $\mu$.

Theoretical Framework

The authors analyze a variant of FISTA proposed by Chambolle and Dossal, which incorporates a friction-like parameter $\alpha$. Their methodology bridges the gap between discrete iterations and continuous-time dynamics:

  1. Lyapunov Energy Analysis: By defining a discrete "energy" function that accounts for both objective value and iterate momentum, the authors prove that this energy decays at a rate consistent with fast convergence.
  2. ODE Correspondence: The analysis leverages the continuous-time limit of FISTA—a second-order differential equation with vanishing damping—to derive robust discrete-time bounds.
  3. Non-Asymptotic Analysis: Unlike previous asymptotic studies, this work provides explicit iteration bounds for finite $n$, allowing practitioners to determine the exact number of steps required to reach a target accuracy $\epsilon$.

Comparative Analysis of Optimization Algorithms

The core contribution of the paper is demonstrating that FISTA is "automatically" optimized for functions with quadratic growth. It achieves a convergence rate of $O(\frac{1}{\sqrt{\kappa}} \log(1/\epsilon))$, matching dedicated strongly convex solvers without requiring their parameter sensitivity.

Comparison of convergence rates and iteration complexities for various optimization methods under different geometric assumptions.

As shown in the table above, FISTA (with appropriate $\alpha$) provides a competitive alternative to NSC, especially when the geometry of the problem is not perfectly known or when the function satisfies quadratic growth rather than global strong convexity.

Key Insights

  • Self-Adaptivity: FISTA exploits the underlying geometry of the objective function automatically, making it more robust than NSC in practical scenarios where $\mu$ is difficult to estimate.
  • The Power of $\alpha$: The parameter $\alpha$ can be tuned based on the target accuracy $\epsilon$ rather than the function's hidden parameters. For instance, in image inpainting tasks, setting $\alpha=30$ significantly outperforms the standard $\alpha=3$.
  • Robustness over NSC: Nesterov’s dedicated strongly convex algorithm (NSC) is faster only if $\mu$ is known exactly. If $\mu$ is underestimated by even a factor of 10, FISTA (which ignores $\mu$) can actually outperform it.
  • Quadratic Growth Sufficiency: The theoretical results hold for functions satisfying a "quadratic growth" condition. This is a weaker assumption than global strong convexity, making the findings applicable to a broader range of problems, including LASSO and signal processing tasks.

Results and Numerical Verification

Numerical experiments on synthetic least squares and image inpainting validate the theory. In image recovery tasks using LASSO formulations, FISTA with a properly chosen $\alpha$ tracks the performance of an "ideal" NSC solver. The paper proves that FISTA reaches an $\epsilon$-solution in $n = O(\frac{1}{\sqrt{\kappa}} \log(1/\epsilon))$ iterations, providing the rigorous theoretical backing for its long-observed empirical success.

Conclusion

This research offers a compelling reason for FISTA's continued use as a robust, parameter-free alternative to more complex accelerated schemes. By proving that FISTA adapts to quadratic growth geometries, the authors bridge the gap between optimization theory and practice. Future work may focus on extending these results to problems with non-unique minimizers or developing dynamic restarting strategies for the parameter $\alpha$.

Summary updated

BibTeX
@article{aujol2024fista,
  author = {Jean-François Aujol and Charles Dossal and Aude Rondepierre},
  title = {{FISTA is an automatic geometrically optimized algorithm for strongly convex functions}},
  journal = {Math. Program.},
  year = {2024},
  doi = {10.1007/s10107-023-01960-6},
}
Figure