Less than a Single Pass: Stochastically Controlled Stochastic Gradient
Abstract
We develop and analyze a procedure for gradient-based optimization that we refer to as stochastically controlled stochastic gradient (SCSG). As a member of the SVRG family of algorithms, SCSG makes use of gradient estimates at two scales, with the number of updates at the faster scale being governed by a geometric random variable. Unlike most existing algorithms in this family, both the computation cost and the communication cost of SCSG do not necessarily scale linearly with the sample size $n$; indeed, these costs are independent of $n$ when the target accuracy is low. An experimental evaluation on real datasets confirms the effectiveness of SCSG.
Cite
Text
Lei and Jordan. "Less than a Single Pass: Stochastically Controlled Stochastic Gradient." International Conference on Artificial Intelligence and Statistics, 2017.Markdown
[Lei and Jordan. "Less than a Single Pass: Stochastically Controlled Stochastic Gradient." International Conference on Artificial Intelligence and Statistics, 2017.](https://mlanthology.org/aistats/2017/lei2017aistats-less/)BibTeX
@inproceedings{lei2017aistats-less,
title = {{Less than a Single Pass: Stochastically Controlled Stochastic Gradient}},
author = {Lei, Lihua and Jordan, Michael I.},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2017},
pages = {148-156},
url = {https://mlanthology.org/aistats/2017/lei2017aistats-less/}
}