# Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity

arXiv: https://arxiv.org/abs/2306.09694 · HTML: https://mlsanity.com/paper/2306.09694/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 21 references that are in the map.
- First posted on arXiv 16 Jun 2023.

## Builds on (most cited first, 13 of 13)

- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Understanding the Acceleration Phenomenon via High-Resolution Differential Equations](https://mlsanity.com/paper/1810.08907/) (2018)
- [Heavy Ball Neural Ordinary Differential Equations](https://mlsanity.com/paper/2110.04840/) (2021)
- [A Dynamical Systems Perspective on Nesterov Acceleration](https://mlsanity.com/paper/1905.07436/) (2019)
- [Acceleration via Symplectic Discretization of High-Resolution Differential Equations](https://mlsanity.com/paper/1902.03694/) (2019)
- [The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2](https://mlsanity.com/paper/1510.08740/) (2015)
- [Fast convex optimization via inertial dynamics with Hessian driven damping](https://mlsanity.com/paper/1601.07113/) (2016)
- [Gradient Norm Minimization of Nesterov Acceleration: o(1/k3)](https://mlsanity.com/paper/2209.08862/) (2022)
- [Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization](https://mlsanity.com/paper/2102.11537/) (2021)
- [Proximal Subgradient Norm Minimization of ISTA and FISTA](https://mlsanity.com/paper/2211.01610/) (2022)
- [From differential equation solvers to accelerated first-order methods for convex optimization](https://mlsanity.com/paper/1909.03145/) (2019)
- [Linear Convergence of ISTA and FISTA](https://mlsanity.com/paper/2212.06319/) (2022)

## Built on by (most cited first, 1 of 1)

- [Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms](https://mlsanity.com/paper/2412.13527/) (2024)

## Abstract (arXiv)

A significant milestone in modern gradient-based optimization was achieved with the development of Nesterov's accelerated gradient descent (NAG) method. This forward-backward technique has been further advanced with the introduction of its proximal generalization, commonly known as the fast iterative shrinkage-thresholding algorithm (FISTA), which enjoys widespread application in image science and engineering. Nonetheless, it remains unclear whether both NAG and FISTA exhibit linear convergence for strongly convex functions. Remarkably, these algorithms demonstrate convergence without requiring any prior knowledge of strongly convex modulus, and this intriguing characteristic has been acknowledged as an open problem in the comprehensive review [Chambolle and Pock, 2016, Appendix B]. In this paper, we address this question by utilizing the high-resolution ordinary differential equation (ODE) framework. Expanding upon the established phase-space representation, we emphasize the distinctive approach employed in crafting the Lyapunov function, which involves a dynamically adapting coefficient of kinetic energy that evolves throughout the iterations. Furthermore, we highlight that the linear convergence of both NAG and FISTA is independent of the parameter r. Additionally, we demonstrate that the square of the proximal subgradient norm likewise advances towards linear convergence.