Minimizing finite sums with the stochastic average gradient

By Mark W. Schmidt, Nicolas Le Roux, Francis R. Bach. 2013

1,339 citations recorded by the source corpus.

We analyze the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method’s iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from O(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1/\sqrt{k})$$\end{document} to O(1 / k) in general, and when the sum is strongly-convex the convergence rate is improved from the sub-linear O(1 / k) to a linear convergence rate of the form O(ρk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\rho ^k)$$\end{document} for ρ<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho < 1$$\end{document}. Further, in many cases the convergence rate of the new method is also faster than black-box deterministic gradient methods, in terms of the number of gradient evaluations. This extends our earlier work Le Roux et al. (Adv Neural Inf Process Syst, 2012), which only lead to a faster rate for well-conditioned strongly-convex problems. Numerical experiments indicate that the new algorithm often dramatically outperforms existing SG and deterministic gradient methods, and that the performance may be further improved through the use of non-uniform sampling strategies.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…et al., 2011, Hazan and Kale, 2014, Rakhlin et al., 2012] or growth condition ( E (cid:107)∇ f i ( x ) 2 ≤ c 1 (cid:107)∇ f ( x ) 2 + c 2 ) [Bottou et al., 2018, Schmidt et al., 2017]. of shows (cid:107) (cid:107) However, a recent line work that these assumptions might be restrictive or…”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “Some popular examples of variance reduced algorithms are SAG (Schmidt et al., 2017), SAGA (Defazio et al., 2014), SVRG (Johnson & Zhang, 2013) and SARAH (Nguyen et al., 2017).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “The overall objective is typically minimized using stochastic first order methods such as stochastic gradient descent (SGD) or its variance-reduced versions [62, 27, 18].”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “This approach has previously been used in the context of VR-SGD methods [74, 73], and several related stochastic methods have also appeared in the recent literature [12, 64, 85].”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “In order to get an estimator of the gradient with a vanishing variance, the optimization literature proposed to take advantage of the finite-sum formulation that often appears in machine learning (Schmidt et al., 2017, and references therein).”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “Schmidt et al. (2016) introduced an implementation technique denoted lagged updates in which each iteration has a cost proportional to the size of the support of f ′i(x).”
Variance Reduced Stochastic Gradient Descent with Neighbors (2015, methodology): “As used in [9], this leads to significant memory savings as one only needs to store the scalars ξ′ i(w) as xi is always given when performing an update.”
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives (2014, methodology): “This procedure has been successfully used with SAG [1].”
Optimization Methods for Large-Scale Machine Learning (2016, background): “2 has its origins in the stochastic average gradient (SAG) algorithm [133, 88], where the stochastic direction is defined as”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “In optimization, they were used for ﬁnite-sum minimization by SVRG (Johnson and Zhang, 2013; Zhang et al., 2013) and then in SAGA (Defazio et al., 2014) to simplify the linearly convergent method SAG (Schmidt et al., 2017).”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “• R-IAG (Chen et al., 2018; Schmidt et al., 2017): A non-uniform sampling version of stochastic average gradient (SAG).”
D2: Decentralized Training over Decentralized Data (2018, methodology): “Variance reduction technology There have been many methods developed for reducing the variance in SGD, including SVRG [Johnson and Zhang, 2013], SAGA [Defazio et al., 2014], SAG [Schmidt et al., 2017], MISO [Mairal, 2015], and mS2GD [Koneˇcn`y et al., 2016].”
Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, methodology): “In order to test the scalability of each component of our pipeline, we upsample the dataset and augment the feature sets by feature products, and record the runtime of our implementations of entity resolution and logistic regression solve by SAG.”
Hyperparameter optimization with approximate gradient (2016, background): “Given the success of recent stochastic optimization techniques (Schmidt et al., 2013; Johnson and Zhang, 2013) it seems natural to study a stochastic variant of this algo-rithm, that is, one in which the updates in the inner and outer optimization schemes have a cost that is independent of the…”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “Another recent trend in the literature has been to use variance-reduction techniques [31, 14, 8] that exploit the finite-sum structure of the loss function in machine-learning applications.”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “While one could use any of recent fast algorithms for finite sums [17, 4, 19, 3] with comparable results, we highlight the consequences of applying the SVRG algorithm [6, 8] as a local solver in INEXACTDANE.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The ﬁrst attempt to unify algorithms such as SVRG and SAG/SAGA already appeared in the SAGA paper [26], where the authors interpret SAGA as a midpoint between SAG and SVRG. Recent work [76] presents a general algorithm, which recovers SVRG, SAGA, SAG and GD as special cases, and obtains an asynchron”
Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods (2019, methodology): “Leveraging correlation between random estimates, the CV method has formed the backbone of many state-of-the-art stochastic optimization algorithms [33–35].”
An Alternative View: When Does SGD Escape Local Minima? (2018, background): “Therefore, for the standard empirical risk minimizing problems with n points and smoothness L , to get to (cid:15) -close to x ∗ , GD needs O ( Ln/(cid:15) ) gradient evaluations [24], but SGD with reduced variance only needs O ( n log 1 + ) gradient evaluations [17, 4, 26, 1].”
Sparsified SGD with Memory (2018, background): “The regularization parameter is set to λ = 1/n for both datasets following [32].”