mlsanityData to 7 Oct 2026

Natasha 2: Faster Non-Convex Optimization Than SGD

arXiv 1708.08694 ↗First posted 29 Aug 2017math.OC cs.DS cs.LGcited by 49

Not on the map. Why?

Abstract (arXiv)

We design a stochastic algorithm to train any smooth neural network to varepsilon-approximate local minima, using O(varepsilon-3.25) backpropagations. The best result was essentially O(varepsilon-4) by SGD. More broadly, it finds varepsilon-approximate local minima of any smooth nonconvex function in rate O(varepsilon-3.25), with only oracle access to stochastic gradients.

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Aug 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 12; 2023: 8; 2024: 6; 2025: 5; 2026: 1.

49 papers.

Sort:

  1. 2022Automatic Clipping: Differentially Private Deep Learning Made Easier and Strongercited by 87
  2. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  3. 2021Learning with User-Level Privacycited by 72
  4. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  5. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  6. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  7. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  8. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 18
  9. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  10. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  11. 2022Interference Management for Over-the-Air Federated Learning in Multi-Cell Wireless Networkscited by 15
  12. 2023How to escape sharp minima with random perturbationscited by 13
37 more
  1. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  2. 2021Wirelessly Powered Federated Edge Learning: Optimal Tradeoffs Between Convergence and Power Transfercited by 10
  3. 2021Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliabilitycited by 6
  4. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  5. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  6. 2022Optimization for Amortized Inverse Problemscited by 6
  7. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  8. 2025Integrated Sensing, Communication, and Computation for Over-the-Air Federated Edge Learningcited by 5
  9. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  10. 2023Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitzcited by 4
  11. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  12. 2021Second-order step-size tuning of SGD for non-convex optimizationcited by 3
  13. 2023Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimizationcited by 3
  14. 2023Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networkscited by 3
  15. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  16. 2021A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimizationcited by 2
  17. 2022Coordinate Descent Methods for Fractional Minimizationcited by 2
  18. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2
  19. 2022PINCH: An Adversarial Extraction Attack Framework for Deep Learning Modelscited by 2
  20. 2025Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequencescited by 2
  21. 2021A Comprehensive Study on Optimization Strategies for Gradient Descent In Deep Learningcited by 1
  22. 2021An Efficient Algorithm for Deep Stochastic Contextual Banditscited by 1
  23. 2021Escaping Saddle Points with Compressed SGDcited by 1
  24. 2021Faster Perturbed Stochastic Gradient Methods for Finding Local Minimacited by 1
  25. 2023A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guaranteescited by 1
  26. 2024A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothnesscited by 1
  27. 2024Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networkscited by 1
  28. 2024Noise is All You Need: Private Second-Order Convergence of Noisy SGDcited by 1
  29. 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learningcited by 1
  30. 2021Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithmcited by 0
  31. 2021Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methodscited by 0
  32. 2022Provable Constrained Stochastic Convex Optimization with XOR-Projected Gradient Descentcited by 0
  33. 2022Can We Do Better Than Random Start? The Power of Data Outsourcingcited by 0
  34. 2022HOUDINI: Escaping from Moderately Constrained Saddlescited by 0
  35. 2023Private Federated Learning with Dynamic Power Control via Non-Coherent Over-the-Air Computationcited by 0
  36. 2024Efficient Continual Finite-Sum Minimizationcited by 0
  37. 2025OptiVote: Non-Coherent FSO Over-the-Air Majority Vote for Communication-Efficient Distributed Federated Learning in Space Data Centerscited by 0