Optimal local linear convergence of Nesterov's accelerated gradient method for $C^2$ functions under the Polyak--Łojasiewicz inequality
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915881585475584 |
|---|---|
| author | Feng, Zixu Yuan, Hao |
| author_facet | Feng, Zixu Yuan, Hao |
| contents | In this work, we establish that Nesterov's accelerated gradient method, applied to $C^2$ functions satisfying the Polyak--Łojasiewicz inequality around local minimizers, achieves the optimal local linear convergence rate $ρ=\frac{\sqrt{3L+μ}-2\sqrtμ}{\sqrt{3L+μ}}+\varepsilon$, where $\varepsilon$ is an arbitrarily small constant. Our analysis requires neither higher-order smoothness beyond $C^2$ 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 $C^{1,1}$ assumption, which is commonly required in theoretical analyses of linear convergence for first-order methods, to $C^2$ smoothness. Moreover, the same analytical framework allows us to recover, under identical conditions, the optimal local exponential convergence rate $\sqrtμ$ for the continuous-time Heavy Ball dynamics. Finally, a representative numerical experiment corroborates our theoretical findings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_21516 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal local linear convergence of Nesterov's accelerated gradient method for $C^2$ functions under the Polyak--Łojasiewicz inequality Feng, Zixu Yuan, Hao Optimization and Control Numerical Analysis In this work, we establish that Nesterov's accelerated gradient method, applied to $C^2$ functions satisfying the Polyak--Łojasiewicz inequality around local minimizers, achieves the optimal local linear convergence rate $ρ=\frac{\sqrt{3L+μ}-2\sqrtμ}{\sqrt{3L+μ}}+\varepsilon$, where $\varepsilon$ is an arbitrarily small constant. Our analysis requires neither higher-order smoothness beyond $C^2$ 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 $C^{1,1}$ assumption, which is commonly required in theoretical analyses of linear convergence for first-order methods, to $C^2$ smoothness. Moreover, the same analytical framework allows us to recover, under identical conditions, the optimal local exponential convergence rate $\sqrtμ$ for the continuous-time Heavy Ball dynamics. Finally, a representative numerical experiment corroborates our theoretical findings. |
| title | Optimal local linear convergence of Nesterov's accelerated gradient method for $C^2$ functions under the Polyak--Łojasiewicz inequality |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2603.21516 |