acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

In this work, we establish that Nesterov's accelerated gradient method, applied to functions satisfying the Polyak–\L ojasiewicz (PL) inequality around local minimizers, achieves the optimal local linear convergence rate , where is an arbitrarily small constant. Our analysis is distinctive in requiring only 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 assumption commonly adopted in the linear convergence analysis of first-order methods. Moreover, under identical conditions ( smoothness and the PL inequality), the same analytical framework allows us to recover the optimal local exponential convergence rate for the continuous-time Heavy Ball dynamics. Finally, a representative numerical experiment corroborates our theoretical findings.

Primary area:
optimization
Keywords:
Nesterov's accelerated gradient method, Polyak--Łojasiewicz inequality, optimal local linear convergence rate

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_6PMDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the local convergence of NAG under the local PL condition. It provides a sharp local rate for standard NAG that converges at a rate of (1-1/\sqrt{\kappa}).

Critical strengths

PL condition is a fundamental setting to study in optimization. This paper provides new insight for the nesterov accelerated gradient method. It shows that NAG provide acceleration for minimizing local PL objectives, locally.

Critical weaknesses
  1. The results are not clearly presented regarding the local region: in theorem 2.2, it only shows that there exists a sufficiently small open neighborhood, but the radius of the neighborhood is not clearly presented. This limits the practical impact of the proposed theory.

  2. The exact contrating factort of the local linear rate of NAG cannot be precisely quantified, which introduce additional ϵ\epsilon in the rate. I think this ϵ\epsilon should impact the initial condition or the local condition.

Questions for authors

Please refer to weakness.

1 comment

Response to W1:

We thank the reviewer for the constructive comments.

Theorem 2.2 establishes the existence of a sufficiently small neighborhood in which the local convergence result holds. Under the general assumptions of C2C^2 smoothness and the local PL condition, such a result is naturally qualitative. In particular, the continuity of the Hessian does not provide an explicit quantitative estimate of its variation. Therefore, the size of the admissible neighborhood depends on the specific objective function and its local properties, and cannot generally be determined explicitly under our assumptions. Obtaining an explicit radius would require additional quantitative regularity assumptions, which are beyond the scope of our current framework.

Our primary objective is to characterize the sharp local asymptotic convergence rate under these mild regularity assumptions, rather than to provide an explicit estimate of the attraction region.

Response to W2:

We emphasize that the optimal spectral radius is precisely characterized in Theorem 2.2 as

ρopt=3L+μ−2μ3L+μ.\rho_{\mathrm{opt}}=\frac{\sqrt{3L+\mu}-2\sqrt{\mu}}{\sqrt{3L+\mu}}. The additional ε>0\varepsilon>0 is an arbitrarily small allowance introduced in deriving the uniform geometric convergence estimate. It accounts for the higher-order nonlinear remainder terms arising from the C2C^2 linearization, as well as the passage from the spectral-radius estimate to a uniform bound on the iterates.

We also note that the admissible initial neighborhood and the constant in the convergence estimate may depend on ε\varepsilon. In particular, a smaller ε\varepsilon may require a smaller initial neighborhood to control the higher-order terms. This dependence is already reflected in the statement of Theorem 2.2.

Thus, ρopt\rho_{\mathrm{opt}} remains the precisely characterized optimal spectral radius, while the additional ε\varepsilon provides the required flexibility in establishing the local geometric convergence estimate.

We hope these clarifications address the reviewer's concerns.

Reviewer_FLzCOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the local convergence of Nesterov's accelerated gradient method for C2C^2 functions satisfying a local Polyak--Łojasiewicz inequality. It recovers, up to an arbitrarily small slack, the optimized asymptotic contraction factor known from the strongly convex setting while allowing non-isolated minimizers. The analysis also yields a local exponential convergence result for continuous-time Heavy Ball dynamics, and a synthetic example illustrates the predicted behavior.

Critical strengths

The paper establishes a sharp local acceleration guarantee under C2C^2 regularity and a local PL condition while accommodating non-isolated minimizers.

Critical weaknesses

W1. The main text provides limited insight into the mechanism behind the regularity improvement. Theorems 2.1 and 2.2 state Lyapunov contraction and a sharp iterate convergence rate, but the intermediate argument is deferred to the appendix. A concise outline explaining how C2C^2 regularity controls tangential motion and nonlinear remainders, and how the initial convergence estimate enables the refined spectral analysis, would clarify the methodological contribution.

W2. The numerical evidence is narrow relative to the claimed generality. The only test family is a C∞C^\infty polynomial with separable quadratic and radial quartic blocks, which does not illustrate the reduced regularity motivating the paper. Changing kk also changes dimension and conditioning simultaneously. A less regular C2C^2 example, a GD comparison, and independent variation of dimension and conditioning would provide more informative evidence. The conclusion should not attribute broad empirical generality to this single family.

W3. The experimental metric and initialization require clarification. Figure 1 calls ∣∣xn+1−xn∣∣||x^{n+1}-x^n|| the ``actual error,'' whereas Theorem 2.2 concerns ∣∣xn−x∗′∣∣||x^n-x_*'||. Please distinguish a geometric upper bound from an exact asymptotic factor and justify the use of iterate increments as a proxy. The red reference curve should be specified explicitly, including any prefactor in CρoptnC\rho_{\mathrm{opt}}^n. The second initial point x1x^1 and the random-seed protocol should also be reported.

Questions for authors

Q1. Line 346 gives κ=L/μ=1/(k+1)\kappa=L/\mu=1/(k+1), but the preceding line states μ=1\mu=1 and L=k+1L=k+1. Please correct this to κ=k+1\kappa=k+1 and confirm the values used in the implementation.

Q2. Please correct duplicated author names in citations, such as "Nesterov Nesterov (2018)'' and "Polyak Polyak (1963),'' and preserve the capitalization of Nesterov consistently in the bibliography. In the paragraph following Eq.~(2.5), "a precise quantification the contraction factor'' should read "a precise quantification of the contraction factor.''

2 comments

Thank you for the detailed feedback.

Response to W1:

Theorem 2.1 gives geometric decay of the increments, which yields convergence to a minimizer x∗′x_*'. At this limit, the local PL condition identifies the tangent space with the Hessian kernel. The C2C^2 gradient expansion therefore leaves a momentum term and a little-oo remainder in the tangential velocity update. Restarting the geometric estimate at iteration nn bounds the sum of the future remainders by a vanishing multiple of the current error and velocity. This expresses tangential displacement through tangential velocity to first order. The state XnX^n, consisting of two successive normal errors and the tangential velocity, then satisfies Xn+1=GXn+o(∥Xn∥)X^{n+1}=GX^n+o(\|X^n\|). The spectral radius of GG gives the refined rate in Theorem 2.2.

Response to W2:

We replaced the polynomial example in Section 3 with a coupled C2∖C3C^2\setminus C^3 objective that satisfies the local PL condition and has a circle of minimizers. Figure 2 and Table 1 compare NAG with GD. We vary κ\kappa at fixed d=32d=32 and vary dd at fixed κ=100\kappa=100.

Response to W3: Figure 1 plots the increment dn=∥xn+1−xn∥d_n=\|x^{n+1}-x^n\|. For the point error en=∥xn−x∗′∥e_n=\|x^n-x_*'\|, the inequalities dn≤en+en+1d_n\le e_n+e_{n+1} and en≤∑j=n∞dje_n\le\sum_{j=n}^{\infty}d_j allow geometric bounds to transfer between the two quantities. Theorem 2.2 gives an upper bound with factor ρopt+ε\rho_{\rm opt}+\varepsilon. The red curve is rn=n d1ρoptn−1r_n=n\,d_1\rho_{\rm opt}^{n-1}, where d1=∥x2−x1∥d_1=\|x^2-x^1\| and ρopt=1−2/3κ+1\rho_{\rm opt}=1-2/\sqrt{3\kappa+1}. The factor nn accounts for a repeated characteristic root in the quadratic linearization. The curve bounds increments in that linearized model and serves as a reference for the nonlinear runs. Figure 2(a) reports errors relative to each method's numerical limit.

We set x0=x1=xinitx^0=x^1=x_{\rm init} and use NumPy PCG64 for the random component of the initial point. Figures 1 and 2(a) use seed 20261108. Figure 2(b) and Table 1 use seeds 20261108, 20261109, and 20261110. For each dimension and seed, both methods and all tested condition numbers share the same initial point.

Response to Q1:

For the original example, μ=1\mu=1 and L=k+1L=k+1 give κ=L/μ=k+1\kappa=L/\mu=k+1. We verified that the revised implementation uses μ=1\mu=1 and L=κL=\kappa to set the NAG and GD parameters reported in Section 3.

Response to Q2:

We have made corrections in the revised manuscript.

Thank you for the response. I keep the score.

Reviewer_1sADOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the local convergence of NAG for C2C^2 objective functions satisfying a local PL condition. The authors first establish local linear convergence using a Lyapunov function and then obtain the sharp local rate. The result recovers the optimal local rate previously known in the strongly convex setting. The paper also establishes a corresponding local exponential convergence result for the continuous-time Heavy Ball dynamics using a similar proof framework and provides a numerical experiment.

Critical strengths
  • Nesterov's accelerated gradient method achieves the optimal local linear convergence rate under weaker assumptions than previously established, namely C2C^2 smoothness and the PL condition. To the best of this reviewer's understanding, the result appears to be new.
  • The Lyapunov function in equation (2.4) also appears to be a useful technical contribution.
  • The fact that the proof framework can also be used for the continuous-time Heavy Ball dynamics seems interesting to this reviewer.
Critical weaknesses

This reviewer did not identify any major weaknesses in the paper. As a relatively minor issue, the paper does not seem to follow the standard ICLR formatting. The main concern is not the deviation from the ICLR format itself, but rather that theorem statements and surrounding paragraphs are not clearly distinguished, which makes the paper somewhat difficult to read. This reviewer believes that improving the formatting would help readability.

Questions for authors
  • Q1. Could the authors provide more details on the technical bottlenecks in applying previously known techniques (for example, those used in analyses requiring C4C^4 smoothness) under only C2C^2 smoothness and the local PL condition? It would also be helpful to clarify which parts of the proposed proof framework are new and how they overcome these difficulties.
  • Q2. This reviewer understands that the C2C^2 smoothness and local PL setting relaxes the strong convexity assumption and extends previous results. However, the example in the experimental section seems somewhat artificial. Around line 64, the authors mention that problems without strong convexity arise in machine learning, signal processing, and inverse problems. Could the authors consider an experiment based on one of these applications, or provide further justification for the current experimental setting? This reviewer believes that a clearer justification of the theoretical setting and its connection to practical applications would help readers better understand the significance of the contribution.
3 comments

Response to Q1:

We thank the reviewer for this insightful question.

The main technical difficulty lies in the regularity of the local manifold formed by the minimizer set under low regularity assumptions. Under C2C^2 smoothness and the local Polyak-\L ojasiewicz (PL) condition, the minimizer set locally forms a C1C^1 manifold, and the Hessian is degenerate along its tangent space. If higher regularity were assumed, such as C4C^4, this local manifold would be C3C^3, allowing one to readily employ tools from differential geometry to construct a local chart that cleanly separates the non-degenerate and degenerate components, thereby enabling convergence analysis in decoupled coordinates. However, under merely C2C^2 smoothness, such a geometric decoupling via smooth local charts cannot be guaranteed. Consequently, a direct spectral analysis of the full linearized NAG iteration fails to capture the desired convergence rate due to the degenerate tangential directions, and the inability to rigorously separate the degenerate and non-degenerate dynamics constitutes the core technical challenge.

Our proof framework addresses these difficulties through two key ingredients.

First, we establish an a priori local linear convergence estimate using a Lyapunov function. Specifically, the Lyapunov function in equation (2.4), together with Theorem 2.1, provides geometric decay of the Lyapunov sequence and hence local linear convergence of the iterates and their successive differences. This estimate is essential for the subsequent spectral analysis.

Second, we develop a tangential reduction based on the a priori linear convergence estimate to handle the degeneracy of the Hessian. Leveraging the a priori linear convergence, we decompose the dynamics into non-degenerate and degenerate components. We show that the degenerate component can be asymptotically controlled by the non-degenerate component. This allows us to construct an augmented state vector for which the nonlinear iteration admits the asymptotic representation Xn+1=Gα,β(x∗′)Xn+o(∥Xn∥).X^{n+1}=G_{\alpha,\beta}(x_*')X^n+o(\|X^n\|). We can then apply a classical spectral-radius argument to obtain the sharp local linear convergence rate in Theorem 2.2.

The main novelty therefore lies in combining the a priori Lyapunov estimate with the tangential reduction and augmented-state construction, which makes the optimal spectral analysis possible under only C2C^2 smoothness and the local PL condition, without requiring higher-order derivatives or additional geometric regularity assumptions on the minimizer manifold..

We hope this clarifies the technical difficulties and the main contributions of our approach.

Response to Q2:

Thank you for the suggestion. In Section3, we replaced the original example with a C2∖C3C^2 \setminus C^3 objective that satisfies the local PL condition and has a circle of minimizers. The circle illustrates the kind of nonuniqueness that arises in matrix factorization, where different factor pairs can represent the same matrix. This controlled example lets us compare NAG with gradient descent under the theorem's assumptions while varying dimension and conditioning independently.

Thank you for your thorough responses and revisions. I have raised my rating accordingly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.