# Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 18 Dec 2024.

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

- [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)
- [The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2](https://mlsanity.com/paper/1510.08740/) (2015)
- [From the Ravine method to the Nesterov method and vice versa: a dynamical system perspective](https://mlsanity.com/paper/2201.11643/) (2022)
- [Gradient Norm Minimization of Nesterov Acceleration: o(1/k3)](https://mlsanity.com/paper/2209.08862/) (2022)
- [Proximal Subgradient Norm Minimization of ISTA and FISTA](https://mlsanity.com/paper/2211.01610/) (2022)
- [Revisiting the acceleration phenomenon via high-resolution differential equations](https://mlsanity.com/paper/2212.05700/) (2022)
- [Linear Convergence of ISTA and FISTA](https://mlsanity.com/paper/2212.06319/) (2022)
- [On Underdamped Nesterov's Acceleration](https://mlsanity.com/paper/2304.14642/) (2023)
- [Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity](https://mlsanity.com/paper/2306.09694/) (2023)

## Abstract (arXiv)

Nesterov's accelerated gradient method (NAG) achieves faster convergence than gradient descent for convex optimization but lacks monotonicity in function values. To address this, Beck and Teboulle [2009b] proposed a monotonic variant, M-NAG, and extended it to the proximal setting as M-FISTA for composite problems such as Lasso. However, establishing the linear convergence of M-NAG and M-FISTA under strong convexity remains an open problem. In this paper, we analyze M-NAG via the implicit-velocity phase representation and show that an additional assumption, either the position update or the phase-coupling relation, is necessary to fully recover the NAG iterates. The essence of M-NAG lies in controlling an auxiliary sequence to enforce non-increase. We further demonstrate that the M-NAG update alone is sufficient to construct a Lyapunov function guaranteeing linear convergence, without relying on full NAG iterates. By modifying the mixed sequence to incorporate forward-indexed gradients, we develop a new Lyapunov function that removes the kinetic energy term, enabling a direct extension to M-NAG. The required starting index depends only on the momentum parameter and not on problem constants. Finally, leveraging newly developed proximal inequalities, we extend our results to M-FISTA, establishing its linear convergence and deepening the theoretical understanding of monotonic accelerated methods.