Variance Reduced Stochastic Gradient Descent with Neighbors

By Thomas Hofmann, Aurélien Lucchi, Simon Lacoste-Julien, Brian McWilliams. 2015

159 citations recorded by the source corpus.

Stochastic Gradient Descent (SGD) is a workhorse in machine learning, yet its slow convergence can be a computational bottleneck. Variance reduction techniques such as SAG, SVRG and SAGA have been proposed to overcome this weakness, achieving linear convergence. However, these methods are either based on computations of full gradients at pivot points, or on keeping per data point corrections in memory. Therefore speed-ups relative to SGD may need a minimal number of epochs in order to materialize. This paper investigates algorithms that can exploit neighborhood structure in the training data to share and re-use information about past stochastic gradients across data points, which offers advantages in the transient optimization phase. As a side-product we provide a unified convergence analysis for a family of variance reduction algorithms, which we call memorization algorithms. We provide experimental results supporting our theory.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “One advantage of Hofmann et al. (2015)’s framework is also that the sampling of the epoch size does not depend on the condition number of the problem, whereas the original proof for SVRG had to consider an epoch size larger than the condition number (see Leblond et al.”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “(Hofmann et al. (2015), Eq (7) & (8)) D.2 Proof of Theorem 22 (convergence guarantee and rate of Hogwild) Master inequality derivation.”
ASAGA: Asynchronous Parallel SAGA (2016, methodology): “An asynchronous variant of Sgd with constant step size called Hogwild was presented by Niu et al. (2011); part of their framework of analysis was re-used and inspired most of the recent literature on asynchronous parallel optimization algorithms with convergence rates, including asynchronous variant”
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.”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “If the aggregation is not done, we have two options – either keep replacing the columns 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 particu”
Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “While this provides an unbiased estimate of the full gradient, the randomized batches introduce variance in the gradient estimate (Hofmann et al., 2015), and therefore stochastic gradient methods are in general slow to converge (Johnson & Zhang, 2013; Defazio et al., 2014).”
Less than a Single Pass: Stochastically Controlled Stochastic Gradient (2016, background): “Recently we found that [13] also implicitly uses the geometric size of the inner loop.”
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).”
L-SVRG and L-Katyusha with Arbitrary Sampling (2019, methodology): “The same as in (Hofmann et al., 2015), we use a factor p ∈ (0, 1] to control the frequency of updating the reference point wk.”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, methodology): “[15] proposed a simple SVRG version with convergence guarantees for both SC and non-SC problems as in SAGA.”
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].”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, unknown): “Analogous results can be obtained for L-SVRG .”
Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters (2016, methodology): “published in NIPS 2015 [11], they introduced N-SAGA, the first ERM training algorithm that takes into account the similarities between data vectors.”
Towards closing the gap between the theory and practice of SVRG (2019, methodology): “Our method, L-SVRG-D, uses the same loopless structure as in [11, 16, 17] but introduces different step sizes at each iteration, see Algorithm 2.”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “We make a more detailed comparison between our results and [14] in Sect.”
On the Convergence of Weighted AdaGrad with Momentum for Training Deep Neural Networks (2018, methodology): “When data perturbation/augmentation and dropout techniques [37] are introduced in the training process, the training model falls into problem (1) in which inﬁnite datasets and noise gradient are unavoidable [2, 18].”