← All setups

Nesterov under Local Strong Aiming

Descriptions may be stale. Consult the linked Lean sources.

Nesterov under Local Strong Aiming

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a finite-dimensional real Hilbert space E using Nesterov’s method. Around its nonempty minimizer set, f has an L-Lipschitz gradient, a quadratic lower model, and a strong aiming condition toward nearest minimizers, with 0<μ≤L. These conditions hold within distance r>0 of that set; the given starting point x0 lies there with objective gap at most μr2/256. The oracle returns ∇f(x) at x. For ε>0, the goal is a last iterate x¯ satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of algorithm randomness, where x⋆ is a global minimizer.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. For the minimizer set M, define d(x,M):=infz∈M∥x−z∥,Ur:={x∈E:d(x,M)<r}. The algorithm receives only E, L, μ, and x0; the radius r, initial gap bound Δ, and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Minimizers and initialization). There exists a global minimizer x⋆∈E. With M:={x∈E:f(x)=f(x⋆)}, the parameters and starting point satisfy 0<μ≤L,r>0,Δ≥0,ε>0,256Δ≤μr2,f(x0)−f(x⋆)≤Δ,d(x0,M)<r.

Assumption 2 (Local regularity). The function f is Fréchet differentiable everywhere on E. For every x,y∈Ur, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,f(y)≥f(x)+⟨∇f(x),y−x⟩−μL∥y−x∥2.

Assumption 3 (Local strong aiming). For every x∈Ur and every nearest minimizer z∈M, meaning ∥x−z∥=d(x,M), f(x)−f(x⋆)+μ2∥x−z∥2≤⟨∇f(x),x−z⟩.

The formulation is algorithm-specific: we analyze Nesterov’s method with position xk and velocity vk. Set s:=12L,q:=μs,v0:=0, with position initialized at the given x0. At each iteration k≥0, the method queries yk and updates according to yk=xk+svk,gk=∇f(yk),xk+1=xk+svk−s2gk,vk+1=1−q1+q(vk−sgk). Queries may be made at any point of E. After K≥0 oracle calls, the output is the last position x¯=xK. The required accuracy is f(x¯)−f(x⋆)≤εP-a.s.

Results

A differentiable function f on a finite-dimensional real Hilbert space attains f∗=f(x⋆); exact gradients are available. On Ur={x:d(x,M)<r}, ∇f is L-Lipschitz and f(y)≥f(x)+⟨∇f(x),y−x⟩−μL∥y−x∥2 for all x,y∈Ur. Strong aiming means ⟨∇f(x),x−z⟩≥f(x)−f∗+μ2∥x−z∥2 for every x∈Ur and every nearest z∈M. Assume 0<μ≤L, r>0, x0∈Ur, and 0≤f(x0)−f∗≤Δ≤μr2/256. Target: f(xK)−f(x⋆)≤ε, ε>0. Result (1) constructs fixed-parameter Nesterov with deterministic last-iterate accuracy; updates use L,μ, and the horizon uses Δ,ε.

Local acceleration under strong aiming: LocalStrongAiming.
Result Oracle complexity Novelty Limitations
(1) LocalStrongAimingNesterov (Ours) (⋆⋆⋆) (review) O(1+L/μlog⁡(1+Δ/ε)) gradient calls.
(2) Nesterov (Gupta and Wojtowytsch 2025, Thm. 11) O(1+L/μlog⁡(1+Δ/ε)) gradient calls. Affine M; global smoothness and strong aiming; weak-curvature coefficient at most μL/2. (1): Scope extends to curved, nonconvex M under tube assumptions. Matches the rate on the common affine, globally regular subclass. (1) needs local initialization; worse contraction constant (1/2 versus 1). Classes are not nested.
(3) Continuized Nesterov (Hermant et al. 2026, sec. 5.2), constant-probability guarantee Derived bound: O(1+L/μalog⁡(1+Δ/ε)) gradient calls for success probability 3/4. Global smoothness and strong aiming; convex M with C2 boundary; μ/L<ϕ−4. (1): Nonconvex curved M allowed; deterministic instead of constant-probability accuracy. Different guarantees preclude a like-for-like speedup claim. (1) needs weak convexity and local initialization; (3) is global without a weak-curvature bound. Classes are not nested.
(4) Nesterov (Feng and Yuan 2026, Thm. 2.2) No explicit call budget in (L,μ,Δ,ε). Local distance contraction approaches 1−2μ/3L+μ; basin and prefactor are implicit. Requires C2 and local PL. (1): Explicit nonasymptotic budget and basin Δ≤μr2/256; no C2 requirement. No comparable explicit cost bound in (4). (1) needs strong aiming and weak convexity beyond local PL; worse asymptotic contraction constant, with different error criteria.

Abbr: M=argminf; d(x,M)=infz∈M∥x−z∥; Δ is the initial objective-gap bound; L is the gradient Lipschitz constant; μ is the strong-aiming constant (the PL constant in (4)); ε is target objective accuracy; ϕ=(1+5)/2; a=1−ϕ(μ/L)1/4>0; PL means ∥∇f(x)∥2≥2μ(f(x)−f∗). Weak-curvature coefficient c denotes the coefficient of −∥y−x∥2 in the two-point lower bound.

Feng, Zixu, and Hao Yuan. 2026. Optimal Local Linear Convergence of Nesterov’s Accelerated Gradient Method for C2 Functions Under the Polyak–Łojasiewicz Inequality. https://doi.org/10.48550/arXiv.2603.21516.
Gupta, Kanan, and Stephan Wojtowytsch. 2025. Nesterov Acceleration in Benignly Non-Convex Landscapes. https://doi.org/10.48550/arXiv.2410.08395.
Hermant, Julien, Jean-François Aujol, Charles Dossal, Lorick Huang, and Aude Rondepierre. 2026. Continuized Nesterov Acceleration for Non-Convex Optimization. https://doi.org/10.48550/arXiv.2512.16533.

Lean setup