Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

By Rie Johnson, Tong Zhang. 2013

3,007 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, methodology): “• The green circles (SVRGfo) give values for our proposed algorithm.”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “We compare the proposed algorithms against common first-order methods: SGD, SVRG (Johnson and Zhang, 2013), Adam (Kingma and Ba, 2015) and Adagrad (Duchi et al.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Stochastic gradient descent (SGD) and its variants [22, 91, 40, 84, 74, 36, 19] are the preferred optimization methods in modern machine learning.”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, background): “Method Complexity µ-adaptivity SVRG ln( 1 ✏ )⇥(n+ L̄ 2 µ2 ) no Acc.”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “First, while Saga trades memory for less computation, in the case of generalized linear models the memory cost can be reduced to O(n), compared to O(d) for Svrg (Johnson and Zhang, 2013).”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, background): “Johnson and Zhang (2013) coined the name stochastic variance reduced gradient (SVRG) and Defazio et al. (2014) uniﬁed the family.”
Variance Reduced Stochastic Gradient Descent with Neighbors (2015, methodology): “It is a surprising recent finding [11, 5, 9, 6] that the finite sum structure of f allows for significantly faster convergence in expectation.”
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives (2014, methodology): “In [5], the authors make the observation that the variance of the standard stochastic gradient (SGD) update direction can only go to zero if decreasing step sizes are used, thus preventing a linear convergence rate unlike for batch gradient descent.”
The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, neutral): “11, m=1) 1 β O( β α) SAG [RSB12] 1 2n·β O( n·β α ) SVRG [JZ13] 1 10β O(n+ β α) SAGA [DBLJ14] 1 3β O(n+ β α) Katyusha [AZ16] (momentum) adaptive O(n+ √ n·β α ) Remarkably, in the interpolated regime, Theorem 1 implies that SGD obtains the benefits of variance reduction “for free" without the need for”
Deep Learning with Differential Privacy (2016, methodology): “Since our approach applies directly to gradient computations, it can be adapted to many other classical and more recent first-order optimization methods, such as NAG [45], Momentum [50], AdaGrad [17], or SVRG [33].”
Optimization Methods for Large-Scale Machine Learning (2016, background): “riants of SVRG is presented as Algorithm5.1. For both options (b) and (c), it has been shown that when applied to minimize a strongly convex R n, Algorithm5.1 can achieve a linear rate of convergence [82]. More precisely, if the stepsize and the length of the inner cycle mare chosen so that ˆ:= 1 1 ”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “er interesting framework that has been considered is known as ‘mixed optimization’, ‘stochastic variance-reduced gradient’ (SVRG), or ‘semi-stochastic gradient descent’ (S2GD) [Mahdavi and Jin, 2013, Johnson and Zhang, 2013, Zhang et al., 2013, Konecny and Richtarik, 2013].8 Unlike FG methods that u”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, methodology): “momentum) and an SVRG style correction [12] in order to mimic the updates of the centralized algorithm run on iid data.”
Adaptive Federated Optimization (2020, methodology): “FL across edge devices) (Kairouz et al., 2019, Table 1). In cross-silo FL, most clients participate in every round and can maintain state between rounds. In the more challenging cross-device FL, our primary focus, only a small fraction of clients participate in each round, and clients cannot maintai”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “− − This idea of control iterates is inspired by (and is similar to) those used for variance reduction in SVRG (Johnson and Zhang, 2013) and SAGA (Defazio et al., 2014).”
Natural Compression for Distributed Deep Learning (2019, background): “, variants utilizing minibatching [14], importance sampling [20, 25], momentum [34], or variance reduction [24, 7]), is the cost of communication of the typically dense gradient vector gi(x), and in a parameter-sever implementation with a master node, also the cost of broadcasting the aggregated gra”
Wireless Network Intelligence at the Edge (2018, methodology): “(23) Similar to CSGD, the learning rate η needs to decrease with k in order to reduce the weight update variance induced by the randomness of the user-generated training samples. b) Federated SVRG: Allowing a constant learning rate can reduce the training latency compared to FAvg whose learning rate”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “The SVRG analysis [13] requires the number of stochastic gradient updates to be scales as the condition number, so here we will use O(H √ nB/(LK)) communication rounds to perform the stochastic updates, since one chain within each communication round has length K.”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, methodology): “Notably, our framework can be applied to any ﬁrst-order methods, including gradient descent, SVRG [JZ13], coordinate descent, and projected or accelerated versions of these algorithms.”