Trading-off variance and complexity in stochastic gradient descent
arXiv:1603.06861
Abstract
Stochastic gradient descent is the method of choice for large-scale machine learning problems, by virtue of its light complexity per iteration. However, it lags behind its non-stochastic counterparts with respect to the convergence rate, due to high variance introduced by the stochastic updates. The popular Stochastic Variance-Reduced Gradient (SVRG) method mitigates this shortcoming, introducing a new update rule which requires infrequent passes over the entire input dataset to compute the full-gradient. In this work, we propose CheapSVRG, a stochastic variance-reduction optimization scheme. Our algorithm is similar to SVRG but instead of the full gradient, it uses a surrogate which can be efficiently computed on a small subset of the input data. It achieves a linear convergence rate ---up to some error level, depending on the nature of the optimization problem---and features a trade-off between the computational complexity and the convergence rate. Empirical evaluation shows that CheapSVRG performs at least competitively compared to the state of the art.
arXiv comment14 pages, 13 figures, first edition on 9th of October 2015
References in corpus (8)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
- On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
- Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
- Stop Wasting My Gradients: Practical SVRG
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
- Online Learning to Sample