# The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2015.

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

- [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)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)
- [A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces](https://mlsanity.com/paper/2310.17610/) (2023)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Faster Convergence in Deep-Predictive-Coding Networks to Learn Deeper Representations](https://mlsanity.com/paper/2101.06848/) (2021)
- [Towards understanding Accelerated Stein Variational Gradient Flow -- Analysis of Generalized Bilinear Kernels for Gaussian target distributions](https://mlsanity.com/paper/2509.04008/) (2025)
- [A globally convergent fast iterative shrinkage-thresholding algorithm with a new momentum factor for single and multi-objective convex optimization](https://mlsanity.com/paper/2205.05262/) (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)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [FolkTalent: Enhancing Classification and Tagging of Indian Folk Paintings](https://mlsanity.com/paper/2405.08776/) (2024)
- [Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms](https://mlsanity.com/paper/2412.13527/) (2024)
- [Sequential Regression Learning with Randomized Algorithms](https://mlsanity.com/paper/2507.03759/) (2025)
- [Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples](https://mlsanity.com/paper/2509.08954/) (2025)

## Abstract (arXiv)

The it forward-backward algorithm is a powerful tool for solving optimization problems with a it additively separable and it smooth + it nonsmooth structure. In the convex setting, a simple but ingenious acceleration scheme developed by Nesterov has been proved useful to improve the theoretical rate of convergence for the function values from the standard mathcal O(k-1) down to mathcal O(k-2). In this short paper, we prove that the rate of convergence of a slight variant of Nesterov's accelerated forward-backward method, which produces it convergent sequences, is actually o(k-2), rather than mathcal O(k-2). Our arguments rely on the connection between this algorithm and a second-order differential inclusion with vanishing damping.