# Natasha 2: Faster Non-Convex Optimization Than SGD

arXiv: https://arxiv.org/abs/1708.08694 · HTML: https://mlsanity.com/paper/1708.08694/

## Key facts

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

## Built on by (most cited first, 30 of 49)

- [Automatic Clipping: Differentially Private Deep Learning Made Easier and Stronger](https://mlsanity.com/paper/2206.07136/) (2022)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Random Scaling and Momentum for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2405.09742/) (2024)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Interference Management for Over-the-Air Federated Learning in Multi-Cell Wireless Networks](https://mlsanity.com/paper/2206.02398/) (2022)
- [How to escape sharp minima with random perturbations](https://mlsanity.com/paper/2305.15659/) (2023)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Wirelessly Powered Federated Edge Learning: Optimal Tradeoffs Between Convergence and Power Transfer](https://mlsanity.com/paper/2102.12357/) (2021)
- [Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability](https://mlsanity.com/paper/2107.08461/) (2021)
- [A Stochastic Newton Algorithm for Distributed Convex Optimization](https://mlsanity.com/paper/2110.02954/) (2021)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Optimization for Amortized Inverse Problems](https://mlsanity.com/paper/2210.13983/) (2022)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Integrated Sensing, Communication, and Computation for Over-the-Air Federated Edge Learning](https://mlsanity.com/paper/2508.15185/) (2025)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences](https://mlsanity.com/paper/2512.13123/) (2025)
- [Second-order step-size tuning of SGD for non-convex optimization](https://mlsanity.com/paper/2103.03570/) (2021)
- [Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization](https://mlsanity.com/paper/2301.00631/) (2023)
- [Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networks](https://mlsanity.com/paper/2304.09221/) (2023)
- [Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism](https://mlsanity.com/paper/2510.03167/) (2025)
- [A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization](https://mlsanity.com/paper/2102.09893/) (2021)
- [Coordinate Descent Methods for Fractional Minimization](https://mlsanity.com/paper/2201.12691/) (2022)

## 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.