ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
Preprint
Abstract
We propose a new stochastic first-order algorithmic framework to solve stochastic composite nonconvex optimization problems that covers both finite-sum and expectation settings. Our algorithms rely on the SARAH estimator introduced in (Nguyen et al, 2017) and consist of two steps: a proximal gradient and an averaging step making them different from existing nonconvex proximal-type algorithms. The algorithms only require an average smoothness assumption of the nonconvex objective term and additional bounded variance assumption if applied to expectation problems. They work with both constant and adaptive step-sizes, while allowing single sample and mini-batches. In all these cases, we prove that our algorithms can achieve the best-known complexity bounds. One key step of our methods is new constant and adaptive step-sizes that help to achieve desired complexity bounds while improving practical performance. Our constant step-size is much larger than existing methods including proximal SVRG schemes in the single sample case. We also specify the algorithm to the non-composite case that covers existing state-of-the-arts in terms of complexity bounds. Our update also allows one to trade-off between step-sizes and mini-batch sizes to improve performance. We test the proposed algorithms on two composite nonconvex problems and neural networks using several well-known datasets.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Inexact SARAH algorithm for stochastic optimizationOptimization Methods and Software, 2020
- Stochastic Frank-Wolfe methods for nonconvex optimization2016
- Minimizing finite sums with the stochastic average gradientMathematical Programming, 2016
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimizationMathematical Programming, 2014
- A Proximal Stochastic Gradient Method with Progressive Variance ReductionSIAM Journal on Optimization, 2014
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic ProgrammingSIAM Journal on Optimization, 2013
- Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex OptimizationIEEE Transactions on Information Theory, 2012
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic FrameworkSIAM Journal on Optimization, 2012
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- Cubic regularization of Newton method and its global performanceMathematical Programming, 2006