# Optimal local linear convergence of Nesterov's accelerated gradient method for C2 functions under the Polyak--Lojasiewicz inequality

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2026.

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

- [Lean Pool: An AI-Maintained Archive of Formalized Mathematics](https://mlsanity.com/paper/2609.25199/) (2026)
- [Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approach](https://mlsanity.com/paper/2605.14663/) (2026)

## Abstract (arXiv)

In this work, we establish that Nesterov's accelerated gradient method, applied to C2 functions satisfying the Polyak--Lojasiewicz inequality around local minimizers, achieves the optimal local linear convergence rate ρ=frac√3L+μ-2√μ√3L+μ+varepsilon, where varepsilon is an arbitrarily small constant. Our analysis requires neither higher-order smoothness beyond C2 of the objective function nor any additional geometric regularity of the submanifold of local minimizers. The key novelty lies in a two-stage argument: we first establish a coarse yet valid local linear convergence rate and then, building upon this a priori convergence guarantee, obtain a refined characterization of the linearized iteration operator, which yields the optimal rate. As a result, we only need to slightly strengthen the standard C1,1 assumption, which is commonly required in theoretical analyses of linear convergence for first-order methods, to C2 smoothness. Moreover, the same analytical framework allows us to recover, under identical conditions, the optimal local exponential convergence rate √μ for the continuous-time Heavy Ball dynamics. Finally, a representative numerical experiment corroborates our theoretical findings.