Natasha 2: Faster Non-Convex Optimization Than SGD

Abstract

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

V2 and V3 polished writing; V4 was a deep revision and simplified proofs

Cited by in corpus (14)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Interference Management for Over-the-Air Federated Learning in Multi-Cell Wireless Networks
• STAR-RIS Integrated Non-Orthogonal Multiple Access and Over-the-Air Federated Learning: Framework, Analysis, and Optimization
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Second-order step-size tuning of SGD for non-convex optimization
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Uniform Convergence of Gradients for Non-Convex Learning and Optimization
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Generalized Left-Localized Cayley Parametrization for Optimization with Orthogonality Constraints
• Variance Reduction on General Adaptive Stochastic Mirror Descent
• On the Analysis of Trajectories of Gradient Descent in the Optimization of Deep Neural Networks