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
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
Results
A differentiable function
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) LocalStrongAimingNesterov
(Ours) |
|||
| (2) Nesterov (Gupta and Wojtowytsch 2025, Thm. 11) | (1): Scope extends to
curved, nonconvex |
(1) needs local
initialization; worse contraction constant ( |
|
| (3) Continuized Nesterov (Hermant et al. 2026, sec. 5.2), constant-probability guarantee | Derived bound: |
(1): Nonconvex curved
|
(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 |
(1): Explicit
nonasymptotic budget and basin |
(1) needs strong aiming and weak convexity beyond local PL; worse asymptotic contraction constant, with different error criteria. |
Abbr: