# Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2017.

## Built on by (most cited first, 8 of 8)

- [Towards Communication-efficient Vertical Federated Learning Training via Cache-enabled Local Updates](https://mlsanity.com/paper/2207.14628/) (2022)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2211.13668/) (2022)
- [Adaptive Message Quantization and Parallelization for Distributed Full-graph GNN Training](https://mlsanity.com/paper/2306.01381/) (2023)
- [CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models](https://mlsanity.com/paper/2312.03256/) (2023)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization](https://mlsanity.com/paper/2408.12209/) (2024)
- [Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods](https://mlsanity.com/paper/2103.04413/) (2021)

## Abstract (arXiv)

Given a nonconvex function that is an average of n smooth functions, we design stochastic first-order methods to find its approximate stationary points. The convergence of our new methods depends on the smallest (negative) eigenvalue -σ of the Hessian, a parameter that describes how nonconvex the function is. Our methods outperform known results for a range of parameter σ, and can be used to find approximate local minima. Our result implies an interesting dichotomy: there exists a threshold σ0 so that the currently fastest methods for σ>σ0 and for σ<σ0 have different behaviors: the former scales with n2/3 and the latter scales with n3/4.