Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop

By Dmitry Kovalev, Samuel Horváth, Peter Richtárik. 2019

180 citations recorded by the source corpus.

The stochastic variance-reduced gradient method (SVRG) and its accelerated variant (Katyusha) have attracted enormous attention in the machine learning community in the last few years due to their superior theoretical properties and empirical behaviour on training supervised machine learning models via the empirical risk minimization paradigm. A key structural element in both of these methods is the inclusion of an outer loop at the beginning of which a full pass over the training data is made in order to compute the exact gradient, which is then used to construct a variance-reduced estimator of the gradient. In this work we design {\em loopless variants} of both of these methods. In particular, we remove the outer loop and replace its function by a coin flip performed in each iteration designed to trigger, with a small probability, the computation of the gradient. We prove that the new methods enjoy the same superior theoretical convergence properties as the original methods. However, we demonstrate through numerical experiments that our methods have substantially superior practical behavior.

Subfields: Artificial Intelligence, 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 Optimization & Training

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “In this subsection we present the main convergence results as presented in Gower et al. (2019) for SGD and in Kovalev et al. (2020); Gorbunov et al. (2020) for L-SVRG.”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, background): “We refer the interested reader to [1,26,35,36,41,95,96] and the references therein.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “Our base version (denoted as L-SVRG) is slightly different and inspired by observations made in (Hofmann et al., 2015; Raj & Stich, 2018) and following closely (Kovalev et al., 2019).”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “…of the Jacobian table (in such case, we obtain a particular case of SAGA (Defazio et al., 2014)) or do LSVRG-like replacement (Hofmann et al., 2015; Kovalev et al., 2020) (in such case, the algorithm is a particular case of GJS (Hanzely & Richtárik, 2019), but is not a special case of neither SAGA…”
L-SVRG and L-Katyusha with Arbitrary Sampling (2019, background): “Recently, this problem was remedied by the so called loopless SVRG (L-SVRG) and loopless Katyusha (L-Katyusha) [8].”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, methodology): “[23] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik.”
Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization (2020, methodology): “In case of SGD for ﬁnite sum problems, the momentum method Katyusha (Allen-Zhu, 2017) achieves the optimal rate; for enhancements, see also (Kovalev et al., 2020; Qian et al., 2019; Lan et al., 2019).”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, background): “…k , such that, for every k ∈ N , Assumption 1 is satisﬁed by several stochastic gradient estimators used in machine learning, including stochastic gradients used for coordinate descent [31], variance reduction [22,32–34] and stochastic gradients used in Federated learning [35], see Table 1 in [19].”
Towards closing the gap between the theory and practice of SVRG (2019, methodology): “Indeed, we found that Free-SVRG and L-SVRG-D with the parameter setting given by our theory are often faster than SVRG with settings suggested by the theory in [13], that is m = 20Lmax/µ and α = 1/10Lmax, see Figure 2, and Section G.1 for more experiments comparing different theoretical parameter se”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, methodology): “For instance, some particular methods we consider, such as L-SVRG (Alg 10) [18], were not analyzed in the proximal (R 6= 0) case before.”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, methodology): “In particular, we obtain the following methods in special cases, or their generalizations, always recovering the best-known convergence guarantees or improving upon them: SAGA [3, 26, 4], JacSketch [8], LSVRG [11, 14], SEGA [9], and ISEGA [20] (see Table 1, in which we list 17 special cases).”