On Biased Stochastic Gradient Estimation
arXiv:1906.01133
Abstract
We present a uniform analysis of biased stochastic gradient methods for minimizing convex, strongly convex, and non-convex composite objectives, and identify settings where bias is useful in stochastic gradient estimation. The framework we present allows us to extend proximal support to biased algorithms, including SAG and SARAH, for the first time in the convex setting. We also use our framework to develop a new algorithm, Stochastic Average Recursive GradiEnt (SARGE), that achieves the oracle complexity lower-bound for non-convex, finite-sum objectives and requires strictly fewer calls to a stochastic gradient oracle per iteration than SVRG and SARAH. We support our theoretical results with numerical experiments that demonstrate the benefits of certain biased gradient estimators.
journal version, 35 pages
References in corpus (11)
- SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
- A Simple Practical Accelerated Method for Finite Sums
- Fast and Simple PCA via Convex Optimization
- ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
- Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
- A unified variance-reduced accelerated gradient method for convex optimization
- SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
- ASVRG: Accelerated Proximal SVRG
- Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization