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
The optimization problem is
Our assumptions:
Assumption 1 (Minimizers and initialization). There
exists a global minimizer
Assumption 2 (Local regularity). The function
Assumption 3 (Local strong aiming). For every
The formulation is algorithm-specific: we analyze Nesterov’s method
with position
Proved result
OracleTemplate.Convergence LongTails.Setups.LocalStrongAiming.spec OracleTemplate.NearestAiming.budgetRelevant previous results
- Kanan Gupta and Stephan Wojtowytsch. Nesterov acceleration in
benignly non-convex landscapes. 2025, ICLR; preprint 2024, version
used: v3. Complexity:
fixed exact-gradient calls for Nesterov acceleration to achieve . - 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:
expected exact-gradient calls for continuized Nesterov acceleration to achieve , in the comparable regime ; .