mlsanityData to 7 Oct 2026

"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

arXiv 1705.02766 ↗First posted 8 May 2017math.OCcited by 46

Not on the map. Why?

Abstract (arXiv)

We develop and analyze a variant of Nesterov's accelerated gradient descent (AGD) for minimization of smooth non-convex functions. We prove that one of two cases occurs: either our AGD variant converges quickly, as if the function was convex, or we produce a certificate that the function is "guilty" of being non-convex. This non-convexity certificate allows us to exploit negative curvature and obtain deterministic, dimension-free acceleration of convergence for non-convex functions. For a function f with Lipschitz continuous gradient and Hessian, we compute a point x with |nabla f(x)| ≤ ε in O(ε-7/4 log(1/ ε) ) gradient and function evaluations. Assuming additionally that the third derivative is Lipschitz, we require only O(ε-5/3 log(1/ ε) ) evaluations.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 13; 2023: 12; 2024: 6; 2025: 5; 2026: 4.

46 papers.

Sort:

By area:

  1. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  2. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  3. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  4. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 18
  5. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  6. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  7. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  8. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  9. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
  10. 2023Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learningcited by 10
  11. 2021Provable Convergence of Nesterov's Accelerated Gradient Method for Over-Parameterized Neural Networkscited by 7
  12. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
34 more
  1. 2021The Minimax Complexity of Distributed Optimizationcited by 6
  2. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  3. 2023A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guaranteescited by 6
  4. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  5. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  6. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  7. 2023Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penaltiescited by 4
  8. 2023Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitzcited by 4
  9. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  10. 2021Second-order step-size tuning of SGD for non-convex optimizationcited by 3
  11. 2022A Convergence Analysis of Nesterov's Accelerated Gradient Method in Training Deep Linear Neural Networkscited by 3
  12. 2024Reevaluating Theoretical Analysis Methods for Optimization in Deep Learningcited by 3
  13. 2025Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimizationcited by 3
  14. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  15. 2026Stochastic Generative Plug-and-Play Priorscited by 3
  16. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2
  17. 2022A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guaranteescited by 2
  18. 2023A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimizationcited by 2
  19. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  20. 2021Escaping Saddle Points with Compressed SGDcited by 1
  21. 2023Beyond first-order methods for non-convex non-concave min-max optimizationcited by 1
  22. 2023Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networkscited by 1
  23. 2024Stochastic interior-point methods for smooth conic optimization with applicationscited by 1
  24. 2021Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methodscited by 0
  25. 2022HOUDINI: Escaping from Moderately Constrained Saddlescited by 0
  26. 2022DRSOM: A Dimension Reduced Second-Order Methodcited by 0
  27. 2022Convexity Certificates from Hessianscited by 0
  28. 2023Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessiancited by 0
  29. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
  30. 2024A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimizationcited by 0
  31. 2025Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapescited by 0
  32. 2026Fully First-Order Algorithms for Online Bilevel Optimizationcited by 0
  33. 2026A Parameter-Free First-Order Algorithm for Non-Convex Optimization with tildemkern1mu O(ε-5/3) Global Ratecited by 0
  34. 2026Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimizationcited by 0