Optimal local linear convergence of Nesterov’s accelerated gradient method for $C^2$ functions under the Polyak–Łojasiewicz inequality

In this work, we establish that Nesterov's accelerated gradient method, applied to $C^2$ functions satisfying the Polyak–\L ojasiewicz (PL) inequality around local minimizers, achieves the optimal local linear convergence rate $\rho =\frac{\sqrt{3L+\mu }-2\sqrt{\mu }}{\sqrt{3L+\mu }}+\epsilon$, where $\epsilon$ is an arbitrarily small constant. Our analysis is distinctive in requiring only $C^2$ smoothness of the objective function, avoiding stronger assumptions regarding higher-order derivatives or the geometry of the local minimizer submanifold. Notably, this requirement is only a slight departure from the standard $C^{1,1}$ assumption commonly adopted in the linear convergence analysis of first-order methods. Moreover, under identical conditions ($C^2$ smoothness and the PL inequality), the same analytical framework allows us to recover the optimal local exponential convergence rate $\sqrt{\mu }$ for the continuous-time Heavy Ball dynamics. Finally, a representative numerical experiment corroborates our theoretical findings.