← All setups

Local Strong Aiming Nesterov — Nesterov under Local Strong Aiming

Descriptions may be stale. Consult the linked Lean sources.

Nesterov under Local Strong Aiming · Lean proof

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.

Proved result

⌈2⋅Lμ⋅log⁡(1+2⋅Δε)⌉+

OracleTemplate.Convergence LongTails.Setups.LocalStrongAiming.spec OracleTemplate.NearestAiming.budget

Relevant previous results

  • Kanan Gupta and Stephan Wojtowytsch. Nesterov acceleration in benignly non-convex landscapes. 2025, ICLR; preprint 2024, version used: v3. Complexity: O(1+L/μlog⁡(1+Δ/ε)) fixed exact-gradient calls for Nesterov acceleration to achieve f(xn)−f∗≤ε.
  • Julien Hermant, Jean-François Aujol, Charles Dossal, Lorick Huang, and Aude Rondepierre. Continuized Nesterov Acceleration for Non-Convex Optimization. 2025 preprint, version used: v2, revised 2026. Complexity: O(L/μ1−φ(μ/L)1/4log⁡(1+Δ/ε)) expected exact-gradient calls for continuized Nesterov acceleration to achieve E[f(xt)−f∗]≤ε, in the comparable regime 0<μ/L≤1/16; φ=(1+5)/2.