Research map / Optimization / Nonconvex and smooth optimization
Nesterov acceleration in benignly non-convex landscapes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves accelerated convergence of Nesterov-type momentum methods (continuous-time heavy ball and discrete NAG, with additive and multiplicative noise variants) under a strong aiming condition on benignly non-convex objectives with non-isolated minimizers.
Problem
Momentum methods' acceleration guarantees are known only for convex/strongly convex objectives, yet deep learning losses are non-convex with curved manifolds of minimizers and slightly negative Hessian eigenvalues.
Approach
Replaces convexity with a strong aiming condition relative to the closest minimizer (plus closest-point projection regularity), and designs Lyapunov functions that handle tangential drift of the projection; yields accelerated rates (1-sqrt(mu*eta))^n for continuous and discrete Nesterov schemes, including noisy variants (AGNES-like scheme for multiplicative noise).
Key results
- Continuous-time heavy ball with gamma=2*sqrt(mu) gives f(x_t)-inf f <= e^{-sqrt(mu) t}(f(x_0)-inf f + mu/2 dist(x_0,M)^2), versus e^{-mu t} for gradient flow.
- Discrete Nesterov scheme with eta=1/L achieves rate (1-sqrt(mu/L))^n versus (1-mu/L)^n for gradient descent, under assumption of affine projection and Hessian negative eigenvalues bounded by sqrt(mu/eta).
- Additive-noise Nesterov attains noise floor sigma_a^2 sqrt(eta/mu) versus sigma_a^2/(2mu) for SGD at eta=1/L (per the paper's comparison).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Nesterov instead of gradient descent with step size η=1/L | Strongly aiming objectives in discrete time · Strongly aiming objectives | objective-gap convergence factor: (1-\mu/L)^n -> (1-\sqrt{\mu/L})^n | Helped |
| Use AGNES with multiplicative noise rather than deterministic Nesterov | Strongly aiming objectives · Strongly aiming objectives with multiplicative noise | objective-gap convergence factor: 1- \sqrt{\mu/L}/(1+\sigma_m^2) | Hurt |
Surprising findings
- Acceleration is possible even though the Hessian may have negative eigenvalues, as long as they are bounded in magnitude (bounded by sqrt(mu/eta) in discrete time).
- Under the PL condition alone, accelerated rates are not achievable, motivating the stronger aiming condition.
Limitations
- Discrete-time guarantees require the closest point projection to be affine linear (constant derivative), a restrictive assumption.
- Assumptions are global but can only be guaranteed locally in deep learning; the stochastic analysis does not guarantee staying in the good neighborhood.
Experimental setup
Datasets: synthetic regression data (100 points in R^12 with labels from random teacher network)
Metrics: loss convexity along gradient direction strong aiming parameter estimate objective decay rate
Baselines: gradient descent stochastic gradient descent gradient flow
Builds on: Nesterov accelerated gradient descent aiming condition quasar-convexity AGNES
Closest papers by meaning
- Nesterov acceleration despite very noisy gradients (NeurIPS 2024 · similarity 0.92)
- Gradient correlation is a key ingredient to accelerate SGD with momentum (ICLR 2025 · similarity 0.89)
- Random Scaling and Momentum for Non-smooth Non-convex Optimization (ICML 2024 · similarity 0.88)
- EMA-Nesterov: Stabilizing Nesterov's Lookahead for Accelerated Deep Learning Optimization (NeurIPS 2026 · similarity 0.88)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.87)
- Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.