Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
arXiv:1802.03866
Abstract
The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasingly important in machine learning, and is the core machinery for PCA, SVD, regularized Newton's method, accelerated non-convex optimization, and more. We show how to provably obtain an accelerated stochastic algorithm for minimizing sum-of-nonconvex functions, by to the well-known SVRG method. This line corresponds to momentum, and shows how to directly apply momentum to the finite-sum stochastic minimization of sum-of-nonconvex functions. As a side result, our method enjoys linear parallel speed-up using mini-batch.
References in corpus (7)
- Stochastic Variance Reduction for Nonconvex Optimization
- Non-convex Finite-Sum Optimization Via SCSG Methods
- Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
- Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
- Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
- LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain
- Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
Cited by in corpus (9)
- Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
- The Practicality of Stochastic Optimization in Imaging Inverse Problems
- Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
- Variance Reduction with Sparse Gradients
- Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
- On the Convergence of Memory-Based Distributed SGD
- Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always
- Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
- ADASS: Adaptive Sample Selection for Training Acceleration