Less than a Single Pass: Stochastically Controlled Stochastic Gradient
By Lihua Lei, Michael I. Jordan. 2016
103 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Peter Richtárik
- Filip Hanzely
- Jakub Konecný
- Michael I. Jordan
- Zeyuan Allen-Zhu
- Nicolas Loizou
- L. Eon Bottou
- Simon Lacoste-Julien
In Computational Mechanics
- Peter Richtárik
- Filip Hanzely
- Zeyuan Allen-Zhu
- L. Eon Bottou
- Aaron Defazio
- Michael I. Jordan
- Jakub Konecný
- Ashok Cutkosky
Citations in the corpus
- On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, methodology): “This approach has been explored as the Stochastically Controlled Stochastic Gradient (SCSG) method [Lei and Jordan, 2017].”
- One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, background): “However, in a general form, such algorithm resembles SCSG [17].”
- Non-convex Finite-Sum Optimization Via SCSG Methods (2017, background): “The question has been partially answered in the convex case by [21] in their formulation of the stochastically controlled stochastic gradient (SCSG) methods.”
- Distributed Stochastic Optimization via Adaptive SGD (2018, methodology): “minibatch-SGD [5] Not Needed 1 N1/4 No prior SVRG-like [9, 12, 18, 10] Not Needed 1 1 No”
- Data-Driven Optimal Transport Cost Selection For Distributionally Robust Optimization (2017, methodology): “(10) min β sup P :DcΛ (P,Pn)≤δ E[l(X,Y, β)].”