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

2017/02/02 by Zeyuan Allen-Zhu, Allen-Zhu, Zeyuan · 3 citations
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1702.00763

openalex publication_date 2017/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 σ₀ so that the currently fastest methods for σ>σ₀ and for σ

Citations

• Un-regularizing: approximate proximal point and faster stochastic\n algorithms for empirical risk minimization
• Stochastic Variance Reduction for Nonconvex Optimization
• LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain
• Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly\n Convex Composite Objectives
• Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• Lower Bounds for Higher-Order Convex Optimization

Related

• Lower Bounds for Non-Convex Stochastic Optimization
• Natasha 2: Faster Non-Convex Optimization Than SGD
• New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points