StopWasting My Gradients: Practical SVRG

By Reza Babanezhad, Mohamed Osama Ahmed, Alim Virani, Mark W. Schmidt, Jakub Konecný, Scott Sallinen. 2015

139 citations recorded by the source corpus.

We present and analyze several strategies for improving the performance of stochastic variance-reduced gradient (SVRG) methods. We first show that the convergence rate of these methods can be preserved under a decreasing sequence of errors in the control variate, and use this to derive variants of SVRG that use growing-batch strategies to reduce the number of gradient calculations required in the early iterations. We further (i) show how to exploit support vectors to reduce the number of gradient computations in the later iterations, (ii) prove that the commonly-used regularized SVRG iteration is justified and improves the convergence rate, (iii) consider alternate mini-batch selection strategies, and (iv) consider the generalization error of the method.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training

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

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “By the assumption that the gradients at the optimum have bounded variance, from (Harikandeh et al., 2015; Lohr, 2019), E‖∇fb(x)‖ ≤ n− b n b z”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “If the iterates lie within a bounded set, then the above assumption holds for some finite γ (Bollapragada et al., 2018a; Berahas et al., 2020; Harikandeh et al., 2015).”
Understanding intermediate layers using linear classifier probes (2016, neutral): “• When dealing with features in the form of images (height, width, channels), we can perform 2D pooling along the (height, width) of each channel.”
Distributed optimization with arbitrary local solvers (2015, background): “This and several other practical issues have been recently addressed in [2].”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, neutral): “, [26] and references therein), that is SVRG has no storage, but works in epochs and requires slightly more accesses to the oracles, while SAGA is a pure online method with fewer parameters but requires some storage (for bi-linear saddle-point problems, we only need to store O(n+d) elements for the ”
Coupling Adaptive Batch Sizes with Learning Rates (2016, background): “However, two recent papers [11, 5] combine these variance-reduced methods with increasing sample sizes, i.e., the effective size of the training set is increased over time.”
Online Batch Selection for Faster Training of Neural Networks (2015, background): “The detailed theoretical analysis of advantages of batch size scheduling can be found in (Friedlander & Schmidt, 2012; Babanezhad et al., 2015).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “In [74], we propose several practical improvements to the S2GD algorithm from Chapter 2.”
Efficient Distributed SGD with Variance Reduction (2015, unknown): “Variance reduction (VR) methods [13], [14], [15], [16], [17], [18], [19], [20], [21], [22] have recently gained popularity as an alternative to classical SGD.”
AdaBatch: Adaptive Batch Sizes for Training Deep Neural Networks (2017, background): “Several authors have also studied adaptively increasing batch size with ﬁxed schedules from the context of accelerating the optimization method through variance reduction (Daneshmand et al., 2016; Harikandeh et al., 2015).”
Automated Inference with Adaptive Batches (2017, background): “In a recent paper (Harikandeh et al., 2015), the authors propose a growing batch strategy for a VR method that enjoys the same convergence guarantees.”
Big Batch SGD: Automated Inference using Adaptive Batch Sizes (2016, background): “In a recent paper (Harikandeh et al., 2015), the authors propose a growing batch strategy for a VR method that enjoys the same convergence guarantees.”
Less than a Single Pass: Stochastically Controlled Stochastic Gradient (2016, background): “This is proposed in [11], which calculates gj as 1 B ∑ i∈I ∇fi(x̃) where I is a subset of size B uniformly sampled from {1, .”
Non-convex Finite-Sum Optimization Via SCSG Methods (2017, methodology): “Unlike [14], we do not assume (cid:107) x ( j ) k − x ∗ to be bounded since this is invalid in unconstrained problems, even in convex cases.”
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”
Barzilai-Borwein Step Size for Stochastic Gradient Descent (2016, background): “(iv) The BB step size can also be naturally incorporated to other SVRG variants, such as SVRG with batching [1].”
Convergence Guarantees for RMSProp and ADAM in Non-Convex Optimization and an Empirical Comparison to Nesterov Acceleration (2018, background): “Further, there are also important motivations to study the behavior of these algorithms in the deterministic setting because of usecases where the amount of noise is controlled during optimization, either by using larger batches [27, 8, 3] or by employing variance-reducing techniques [17, 9].”