Minimizing finite sums with the stochastic average gradient

Mark SchmidtNicolas Le RouxFrancis Bach

article2013Mathematical programming1,344 citations2018 Lagrange Prize in Continuous Optimization

Introduces the stochastic average gradient method, which stores past gradient evaluations to achieve the fast linear convergence of full-batch gradient descent while maintaining the cheap per-iteration cost of stochastic methods for finite-sum convex optimization.

Listen

Modern data analysis and machine learning frequently require minimizing functions structured as the average of a massive collection of individual data points. Organizations working with these large datasets face a persistent computational dilemma: standard full gradient algorithms make steady, accurate progress toward the optimal solution but become prohibitively slow because each step requires processing the entire dataset, while standard stochastic gradient algorithms are fast per step because they sample only one data point at a time, but their overall convergence stalls significantly as they approach the solution.

The article introduces and evaluates the stochastic average gradient (SAG) algorithm, demonstrating how maintaining a memory of previously evaluated gradients allows an optimization method to retain the low per-iteration cost of stochastic methods while achieving the fast convergence rates typical of full gradient methods.

To establish these results, the authors combine rigorous mathematical analysis using dynamical system Lyapunov functions with extensive empirical testing. The evaluation benchmarks the proposed method against competitive stochastic gradient, accelerated full gradient, quasi-Newton (L-BFGS), and coordinate descent methods across nine standard benchmark classification datasets containing up to roughly 700,000 data points and over 1.3 million variables.

The findings demonstrate substantial improvements across theoretical and practical benchmarks. First, the method improves the general theoretical convergence rate for convex objectives from sublinear error reduction to an order-of-magnitude faster decay, achieving a linear (exponential) error reduction rate for strongly-convex objectives using constant step sizes. Second, on ill-conditioned problems, the algorithm operates at roughly the speed of full gradient methods per effective pass through data while using iterations that are n times cheaper (where n is the dataset size). Third, empirical tests on logistic regression show that the algorithm tolerates step sizes 100 to 10,000 times larger than its deterministic cyclic predecessor (IAG), preventing divergence and drastically outperforming existing stochastic and deterministic baselines within the critical regime of 1 to 50 passes over the data. Fourth, practical extensions such as non-uniform sampling and mini-batching up to 500 examples maintain rapid convergence while yielding up to 100-fold reductions in storage requirements.

These results demonstrate that organizations can train high-accuracy models on large-scale datasets with significantly less computational infrastructure and runtime. Practitioners no longer need to choose between the rapid early progress of stochastic methods and the long-term precision of batch gradient methods. Furthermore, the algorithm is self-adapting to local geometric curvature and supports an efficient line-search whose per-step cost is entirely independent of the dataset size.

For engineering and data science teams implementing large-scale empirical risk minimization, the article supports adopting the stochastic average gradient method with an adaptive line-search, particularly when model training permits between 2 and 50 data passes. When applied to linearly parameterized models such as logistic and least-squares regression, teams should leverage just-in-time updates to reduce memory storage from large matrices down to linear space proportional to the number of data points, and employ non-uniform sampling proportional to individual Lipschitz constants to further accelerate performance.

Confidence in these findings is high for smooth, convex finite-sum problems, supported by computer-aided formal proofs and consistent experimental benchmarks. However, leaders should note that the base algorithm requires storing past gradient approximations (which requires structural model simplifications to avoid high memory overhead) and that theoretical guarantees assume smooth convex loss functions, meaning application to non-convex models such as deep neural networks requires further validation.

Ecole Normale Supérieure INRIA deterministic gradient algorithm numerical experiments stochastic average gradient stochastic gradient descent finite sums

arXiv: 1309.2388

Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). Introduces foundational adaptive gradient concepts and convergence principles for online and stochastic optimization that inform memory-based stochastic update strategies.
Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). Establishes the fundamental theoretical framework and regret bounds for online convex gradient-based optimization.
Paper: Pegasos: primal estimated sub-gradient solver for SVM, Shai Shalev-Shwartz et al. (2007). Demonstrates the efficiency and sample-size independence of stochastic sub-gradient steps on convex machine learning objectives that SAG builds upon.

Paper: SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives, Aaron Defazio et al. (2014). Extends SAG to the SAGA algorithm, enabling unbiased gradient estimates, simpler convergence proofs, and support for non-smooth composite regularizers.
Paper: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson et al. (2013). Develops SVRG, achieving the same fast linear convergence rate as SAG without requiring explicit storage of historical gradients.
Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). Surveys large-scale optimization methods and contextualizes the theoretical breakthroughs of variance-reduced algorithms like SAG alongside classical stochastic gradient methods.

Cover for Minimizing finite sums with the stochastic average gradient

Abstract

We propose 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^{1/2}) 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(p^k) for p \textless{} 1. 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. 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.

Topics

deterministic gradient algorithm numerical experiments rate of convergence

Keywords

stochastic average gradient stochastic gradient descent finite sums empirical risk minimization variance reduction stochastic dual coordinate ascent proximal-gradient methods convex optimization stochastic approximation algorithms Kaczmarz algorithm

1 Introduction
2 Related Work
3 Convergence Analysis
4 Implementation Details
4.1 Structured gradients and just-in-time parameter updates
4.2 Re-weighting on early iterations
4.3 Exact and efficient regularization
4.4 Warm starting
4.5 Larger step sizes
4.6 Line-search when LL is not known
4.7 Mini-batches for vectorized computation and reduced storage
4.8 Non-uniform example selection
5 Experimental Results
5.1 Comparison to FG and SG Methods
5.2 Comparison to Coordinate Optimization Methods
5.3 Comparison of Step-Size Strategies
5.4 Effect of mini-batches
5.5 Effect of non-uniform sampling
6 Discussion
6.1 Alternative Algorithms
6.2 Generalizations and Other Issues
A.3 Full Gradient Methods
A.4 Coordinate-Descent Methods
A.5 Stochastic Average Gradient
B.3 Problem set-up and notation
B.4 General Lyapunov function
B.5 Lyapunov upper bound
B.6 Domination of g⁡(xk)−g⁡(x∗)g(x^{k})-g(x^{\ast})
B.7 Finding constants
B.8 Verifying the result
B.8.1 Well-conditioned problems (μ⩾2/n\mu\geqslant 2/n)
B.8.2 Ill-conditioned problems (μ⩽2/n\mu\leqslant 2/n)
B.9 Convergence Rate
B.10 Intial values of Lyapunov function
B.10.1 Initialization with the zero vector
B.10.2 Initialization with average gradient
References

Knowls

Knowl 1 — Convergence Rate Bounds for the Stochastic Average Gradient Method
theoretical result
Let $g(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$ be a finite sum of $n$ differentiable convex functions $f_i: \mathbb{R}^p \to \mathbb{R}$ , where each gradient $\nabla f_i$ is Lipschitz continuous with constant $L$ , so that for all $x, y \in \mathbb{R}^p$ ,

$\|\nabla f_i(x) - \nabla f_i(y)\| \le L \|x - y\|.$

Assume there exists an optimal parameter vector $x^* \in \arg\min_{x} g(x)$ . For the stochastic average gradient (SAG) method run with a constant step size $\alpha_k = \frac{1}{16L}$ , the expected sub-optimality after $k \ge 1$ iterations satisfies the following bounds:
1. For general convex objectives $g$ , the average iterate $\bar{x}^k = \frac{1}{k} \sum_{i=0}^{k-1} x^i$ satisfies an $O(1/k)$ sublinear convergence rate:
$\mathbb{E}[g(\bar{x}^k)] - g(x^*) \le \frac{32n}{k} C_0.$
1. When $g$ is additionally $\mu$ -strongly convex with constant $\mu > 0$ (so $x \mapsto g(x) - \frac{\mu}{2}\|x\|^2$ is convex), the iterate $x^k$ achieves a linear convergence rate:
$\mathbb{E}[g(x^k)] - g(x^*) \le \left(1 - \min\left\{\frac{\mu}{16L}, \frac{1}{8n}\right\}\right)^k C_0,$

which implies iterate convergence $\frac{\mu}{2}\|x^k - x^*\|^2 \le \mathbb{E}[g(x^k)] - g(x^*)$ .

The initial constant $C_0$ depends on the initialization of the gradient memory variables $y_i^0$ :
- If initialized with the zero vector $y_i^0 = 0$ for all $i \in \{1, \dots, n\}$ :
$C_0 = g(x^0) - g(x^*) + \frac{4L}{n}\|x^0 - x^*\|^2 + \frac{\sigma^2}{16L},$

where $\sigma^2 = \frac{1}{n} \sum_{i=1}^n \|\nabla f_i(x^*)\|^2$ denotes the gradient variance at the optimum.
- If initialized with centered gradients $y_i^0 = \nabla f_i(x^0) - \nabla g(x^0)$ :
$C_0 = \frac{3}{2}\left(g(x^0) - g(x^*)\right) + \frac{4L}{n}\|x^0 - x^*\|^2.$
Knowl 2 — Basic Stochastic Average Gradient Algorithm
algorithm
The Stochastic Average Gradient (SAG) method minimizes a finite sum objective $g(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$ over $x \in \mathbb{R}^p$ . It maintains an auxiliary memory vector $y_i \in \mathbb{R}^p$ for each component function $f_i$ containing the most recently evaluated gradient for index $i$ , as well as a running sum vector $d = \sum_{i=1}^n y_i$ . At each iteration, a single index $i$ is sampled uniformly at random, its gradient is updated in memory, $d$ is adjusted incrementally, and $x$ is updated using the average gradient $\frac{1}{n}d$ . Each iteration requires evaluating the gradient of only one component function, yielding an iteration cost of $O(p)$ that is independent of $n$ .
Input: Initial iterate $x \in \mathbb{R}^p$ , step size $\alpha > 0$ , component functions $f_1, \dots, f_n$
Initialize $d = 0 \in \mathbb{R}^p$
Initialize $y_i = 0 \in \mathbb{R}^p$ for all $i = 1, \dots, n$
for $k = 0, 1, 2, \dots$ do
    Sample $i$ uniformly at random from $\{1, 2, \dots, n\}$
     $d = d - y_i + \nabla f_i(x)$
     $y_i = \nabla f_i(x)$
     $x = x - \frac{\alpha}{n} d$
end for
Knowl 3 — Sparse and Memory-Efficient SAG with Just-In-Time Updates and Exact Regularization
algorithm
For $\ell_2$ -regularized linearly parameterized optimization problems of the form $\min_{x \in \mathbb{R}^p} \frac{\lambda}{2}\|x\|^2 + \frac{1}{n} \sum_{i=1}^n l_i(a_i^T x)$ , where each $a_i \in \mathbb{R}^p$ is a sparse data vector, the storage cost of the gradient vectors can be reduced from $O(np)$ to $O(n)$ by storing only the scalar derivatives $y_i = l_i'(a_i^T x) \in \mathbb{R}$ . Furthermore, dense vector updates on $x$ are avoided by: (1) representing $x = \kappa z$ with scalar $\kappa$ and vector $z$ to apply the regularization shrink factor $(1 - \alpha \lambda)$ in $O(1)$ time; (2) updating only the non-zero coordinate entries of $a_i$ using lazy, just-in-time cumulative sum updates tracked by a scalar accumulator $S_k$ and a timestamp vector $V$ ; and (3) re-weighting the average by dividing by the number of unique visited data points $m \le n$ during early iterations.
Input: Initial vector $x \in \mathbb{R}^p$ , step size $\alpha > 0$ , regularizer parameter $\lambda > 0$ , sparse feature vectors $a_1, \dots, a_n \in \mathbb{R}^p$ , scalar loss functions $l_1, \dots, l_n$
Initialize $d = 0 \in \mathbb{R}^p$ , $y_i = 0 \in \mathbb{R}$ for $i = 1, \dots, n$
Initialize $z = x$ , $\kappa = 1$ , $m = 0$
Initialize $C_i = 0$ for $i = 1, \dots, n$
Initialize $S_{-1} = 0$ , $V_j = 0$ for $j = 1, \dots, p$
for $k = 0, 1, 2, \dots$ do
    Sample $i$ uniformly at random from $\{1, \dots, n\}$
    if $C_i == 0$ then
         $m = m + 1$
         $C_i = 1$
    end if
    for $j$ non-zero in $a_i$ do
         $z_j = z_j - (S_{k-1} - S_{V_j - 1}) d_j$
         $V_j = k$
    end for
    Let $J$ be the support of $a_i$
     $u = \kappa a_{iJ}^T z_J$
     $g_{\text{new}} = l_i'(u)$
     $d_J = d_J - a_{iJ}(y_i - g_{\text{new}})$
     $y_i = g_{\text{new}}$
     $\kappa = \kappa (1 - \alpha \lambda)$
     $S_k = S_{k-1} + \frac{\alpha}{\kappa m}$
end for
for $j = 1, 2, \dots, p$ do
     $x_j = \kappa (z_j - (S_{k-1} - S_{V_j - 1}) d_j)$
end for
Output: $x$

Knowl 4 — Theoretical Convergence Rates Comparison: Full Gradient vs Accelerated Gradient vs SAG

data/table

For $\mu$ -strongly convex objectives with $L$ -Lipschitz gradients, the theoretical contraction factors of the optimization error per effective pass through the dataset ( $n$ component gradient evaluations) are compared across first-order methods:

Algorithm	Step Size	Theoretical Rate per Step	Rate in Case 1	Rate in Case 2
FG	$1/L$	$(1 - \mu/L)^2$	0.9998	1.000
FG	$2/(\mu+L)$	$(1 - 2\mu/(L+\mu))^2$	0.9996	1.000
AFG	$1/L$	$(1 - \sqrt{\mu/L})$	0.9900	0.9990
Lower-Bound	—	$(1 - 2\sqrt{\mu}/(\sqrt{L}+\sqrt{\mu}))^2$	0.9608	0.9960
SAG ( $n$ iters)	$1/(16L)$	$(1 - \min\{\mu/(16L), 1/(8n)\})^n$	0.8825	0.9938

In the table, $n = 100\,000$ and $L = 100$ . Case 1 represents a well-conditioned setting where $\mu = 0.01$ (such that $n > 2L/\mu$ ). Here, SAG's rate is $(1 - 1/(8n))^n \le \exp(-1/8) \approx 0.8825$ , reducing the error by a constant factor per pass independent of the condition number and surpassing the lower bound of black-box deterministic first-order methods. Case 2 represents an ill-conditioned setting where $\mu = 0.0001$ ( $n \le 2L/\mu$ ). In this regime, SAG achieves $(1 - \mu/(16L))^n \approx \exp(-n\mu/16L) = 0.9938$ , yielding the per-step rate of full gradient descent while using iterations that are $n$ times cheaper.

Knowl 5 — Stochastic Backtracking Line-Search for Unknown Lipschitz Constant in SAG
model/method
When the Lipschitz constant $L$ of component gradients is unknown, it can be estimated dynamically during SAG optimization without requiring full-gradient passes over the data. At iteration $k$ , with selected function $f_{i_k}$ , the local estimate $L_k$ is tested via the descent condition:

$f_{i_k}\left(x^k - \frac{1}{L_k} \nabla f_{i_k}(x^k)\right) \le f_{i_k}(x^k) - \frac{1}{2L_k}\|\nabla f_{i_k}(x^k)\|^2.$

This check is only executed when $\|\nabla f_{i_k}(x^k)\|^2 > 10^{-8}$ to prevent numerical instability. At each iteration, $L_k$ is initialized to a slightly reduced value $L_k = L_{k-1} 2^{-1/n}$ , which allows the estimate to halve over one effective pass through the dataset ( $n$ steps) if no violations occur. If the inequality is violated, $L_k$ is doubled ( $L_k \leftarrow 2 L_k$ ) repeatedly until the inequality holds.

For linearly-parameterized models $f_i(a_i^T x)$ , the argument of $f_{i_k}$ simplifies using $\delta^k = a_{i_k}^T x^k$ :

$f_{i_k}\left(a_{i_k}^T \left(x^k - \frac{1}{L_k} \nabla f_{i_k}(x^k)\right)\right) = f_{i_k}\left(\delta^k - \frac{f_{i_k}'(\delta^k)}{L_k} \|a_{i_k}\|^2\right),$

enabling the line search to run in $O(1)$ time on scalar operations with precomputed squared norms $\|a_i\|^2$ , independent of both $n$ and $p$ .
Knowl 6 — Non-Uniform Example Sampling Strategy for SAG
model/method
Unlike standard stochastic gradient methods where non-uniform sampling introduces bias into the gradient estimator that requires explicit reweighting, the SAG direction $d = \sum_{i=1}^n y_i$ weights all stored gradients uniformly by $1/n$ , allowing non-uniform sampling of training examples without asymptotic bias.

When component functions have different Lipschitz constants $L_i$ for $\nabla f_i$ , sampling index $i$ with probability proportional to $L_i + c$ , where $c = L_{\text{mean}} = \frac{1}{n}\sum_{i=1}^n L_i$ , allows the algorithm to focus updates on faster-changing terms. Setting $L_{\text{max}} = \max_i L_i$ , the appropriate step size for this non-uniform sampling scheme is:

$\alpha = \frac{L_{\text{max}} + c}{L_{\text{max}}(L_{\text{mean}} + c)} = \frac{1}{2 L_{\text{max}}} + \frac{1}{2 L_{\text{mean}}}.$

After an initial $O(n)$ preprocessing step to compute the cumulative distribution, non-uniform samples can be drawn in $O(\log n)$ time per iteration via binary search.
Knowl 7 — Empirical Comparison of SAG with Full Gradient, Stochastic Gradient, and Coordinate Methods
empirical result
On benchmark binary classification datasets (including rcv1, covertype, news, spam, protein, quantum, sido, and alpha) optimizing $\ell_2$ -regularized logistic regression with regularization $\lambda = 1/n$ :
1. Stochastic Gradient (SG) and Averaged SG (ASG) make rapid initial progress during the first 1 to 2 effective data passes, but plateau quickly due to gradient variance.
2. Deterministic Full Gradient methods (Accelerated Full Gradient and L-BFGS) make steady linear progress but require many costly $O(np)$ epochs before reaching competitive accuracy.
3. SAG (specifically SAG with line-search, SAG-LS) matches the fast initial rate of SG on the first few passes and sustains continuous linear convergence, outperforming L-BFGS, AFG, SG, and ASG over 50 effective passes.
4. Incremental Aggregated Gradient (IAG, the deterministic cyclic counterpart of SAG) requires step sizes roughly 100 to 10,000 times smaller to avoid divergence, resulting in convergence that is orders of magnitude slower than SAG.
5. Compared to randomized coordinate descent methods (primal coordinate descent PCD/PCD-L and dual coordinate ascent DCA), SAG performs robustly across all datasets regardless of whether $n > p$ or $p > n$ , whereas PCD-L and DCA show uneven performance depending heavily on the ratio of $n$ to $p$ .
Knowl 8 — Empirical Performance of Mini-Batching and Adaptive Non-Uniform Sampling in SAG
empirical result
Empirical evaluation of mini-batching and adaptive sampling in SAG on large-scale datasets indicates:
1. While theoretical worst-case analysis suggests mini-batch sizes must not exceed $\frac{n\mu}{2L}$ to maintain convergence rates, in practice mini-batch sizes up to 500 can be used without any degradation in convergence rate per effective pass. This allows substantial memory reductions (storing one memory vector per batch) and improves computational throughput via vectorized hardware.
2. When larger mini-batches are used, larger step sizes (e.g., based on $1/L_{\text{mean}}$ or $1/L_{\text{Hessian}}$ of the mini-batch rather than $1/L_{\text{max}}$ ) are critical to maintaining fast convergence.
3. Combining adaptive non-uniform sampling with stochastic line-search (SAG-LS Lipschitz), where sampling probabilities adapt dynamically based on local Lipschitz estimates $L_i^k + L_{\text{mean}}^k$ , achieves optimization solutions orders of magnitude more accurate within 50 passes than uniform SAG on datasets with heterogeneous example difficulty (such as protein, covertype, and sido).

Coverage note — Omitted the specialized Lyapunov polynomial verification scripts/algebraic feasibility checks in Appendices B.1-B.6 and the literature survey of subsequent algorithms (e.g. SVRG, SAGA, SDCA, MISO) in Section 6 as they do not constitute core primary contributions of this paper.

References

1.A. Agarwal and L. Bottou. A lower bound for the optimization of finite sums. arXiv preprint, 2014.
2.A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58(5), 2012.
3.F. Bach and E. Moulines. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in Neural Information Processing Systems, 2011.
4.F. Bach and E. Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate o(1/n). arXiv preprint, 2013.
5.D. P. Bertsekas. A new class of incremental gradient methods for least squares problems. SIAM Journal on Optimization, 7(4):913–926, 1997.
6.D. Blatt, A. O. Hero, and H. Gauchman. A convergent incremental gradient method with a constant step size. SIAM Journal on Optimization, 18(1):29–51, 2007.
7.Antoine Bordes, Léon Bottou, and Patrick Gallinari. Sgd-qn: Careful quasi-newton stochastic gradient descent. Journal of Machine Learning Research, 10:1737–1754, 2009.
8.L. Bottou and Y. LeCun. Large scale online learning. Advances in Neural Information Processing Systems, 2003.
9.P. Carbonetto. New probabilistic inference algorithms that harness the strengths of variational and Monte Carlo methods. PhD thesis, Univ. of British Columbia, May 2009.
10.R. Caruana, T. Joachims, and L. Backstrom. KDD-cup 2004: results and analysis. ACM SIGKDD Newsletter, 6(2):95–108, 2004.
11.A.L. Cauchy. Méthode générale pour la résolution des systèmes d’équations simultanées. Comptes rendus des séances de l’Académie des sciences de Paris, 25:536–538, 1847.
12.Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011.
13.M. Collins, A. Globerson, T. Koo, X. Carreras, and P.L. Bartlett. Exponentiated gradient algorithms for conditional random fields and max-margin markov networks. The Journal of Machine Learning Research, 9:1775–1822, 2008.
14.G. V. Cormack and T. R. Lynam. Spam corpus creation for TREC. In Proc. 2nd Conference on Email and Anti-Spam, 2005. http://plg.uwaterloo.ca/~gvcormac/treccorpus/.
15.Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in Neural Information Processing Systems, 2014a.
16.Aaron J Defazio, ANUEDU AU, Tibério S Caetano, NICTA COM AU, and Justin Domke. Finito: A faster, permutable incremental gradient method for big data problems. International Conference on Machine Learning, 2014b.
17.B. Delyon and A. Juditsky. Accelerated stochastic approximation. SIAM Journal on Optimization, 3(4):868–881, 1993.
18.John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121–2159, 2011.
19.A. Frank and A. Asuncion. UCI machine learning repository, 2010. URL http://archive.ics.uci.edu/ml.
20.M. P. Friedlander and M. Schmidt. Hybrid deterministic-stochastic methods for data fitting. SIAM Journal of Scientific Computing, 34(3):A1351–A1379, 2012.
21.S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. Optimization Online, July, 2010.
22.Pinghua Gong and Jieping Ye. Linear convergence of variance-reduced projected stochastic gradient without strong convexity. arXiv preprint, 2014.
23.I. Guyon. Sido: A phamacology dataset, 2008. URL http://www.causality.inf.ethz.ch/data/SIDO.html.
24.E. Hazan and S. Kale. Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. Conference on Learning Theory, 2011.
25.C. Hu, J.T. Kwok, and W. Pan. Accelerated gradient methods for stochastic optimization and online learning. Advances in Neural Information Processing Systems, 2009.
26.R. Johnson and T Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 2013.
27.S.S. Keerthi and D. DeCoste. A modified finite newton method for fast solution of large scale linear svms. Journal of Machine Learning Research, 6:341–361, 2005.
28.H. Kesten. Accelerated stochastic approximation. Annals of Mathematical Statistics, 29(1):41–59, 1958.
29.Jakub Konečný and Peter Richtárik. Semi-stochastic gradient descent methods. arXiv preprint, 2013.
30.Jakub Konečný, Zheng Qu, and Peter Richtárik. Semi-stochastic coordinate descent. arXiv preprint, 2014.
31.H. J. Kushner and G. Yin. Stochastic approximation and recursive algorithms and applications. Springer-Verlag, Second edition, 2003.
32.S. Lacoste-Julien, M. Jaggi, M. Schmidt, and P. Pletscher. Block-coordinate frank-wolfe optimization for structural svms. International Conference on Machine Learning, 2013.
33.N. Le Roux, M. Schmidt, and F. Bach. A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets. Advances in Neural Information Processing Systems, 2012.
34.D.D. Lewis, Y. Yang, T. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5:361–397, 2004.
35.Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated proximal coordinate gradient method and its application to regularized empirical risk minimization. arXiv preprint, 2014.
36.J. Liu, J. Chen, and J. Ye. Large-scale sparse logistic regression. ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2009.
37.Zhi-Quan Luo and Paul Tseng. On the convergence of the coordinate descent method for convex differentiable minimization. Journal of Optimization Theory and Applications, 72(1):7–35, 1992.
38.M. Mahdavi and R. Jin. Mixedgrad: An o(1/t) convergence rate algorithm for stochastic smooth optimization. Advances in Neural Information Processing Systems, 2013.
39.Julien Mairal. Optimization with first-order surrogate functions. International Conference on Machine Learning, 2013.
40.Julien Mairal. Incremental majorization-minimization optimization with application to large-scale machine learning. arXiv preprint, 2014.
41.J. Martens. Deep learning via Hessian-free optimization. International Conference on Machine Learning, 2010.
42.A. Nedic and D. Bertsekas. Convergence rate of incremental subgradient algorithms. In Stochastic Optimization: Algorithms and Applications, pages 263–304. Kluwer Academic, 2000.
43.D. Needell, N. Srebro, and R. Ward. Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Advances in Neural Information Processing Systems, 2014.
44.A. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983.
45.A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.
46.Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence O(1/k2). Doklady AN SSSR, 269(3):543–547, 1983.
47.Y. Nesterov. Introductory lectures on convex optimization: A basic course. Springer, 2004.
48.Y. Nesterov. Gradient methods for minimizing composite objective function. CORE Discussion Papers, 2007.
49.Y. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221–259, 2009.
50.Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. CORE Discussion Paper, 2010.
51.Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005.
52.Atsushi Nitanda. Stochastic proximal gradient descent with acceleration techniques. Advances in Neural Information Processing Systems, 2014.
53.J. Nocedal and S. J. Wright. Numerical Optimization. Springer, New York, second edition, 2006.
54.B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992.
55.Zheng Qu, Peter Richtárik, and Tong Zhang. Randomized dual coordinate ascent with arbitrary sampling. arXiv preprint arXiv:1411.5873, 2014.
56.A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. International Conference on Machine Learning, 2012.
57.H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22(3):400–407, 1951.
58.Christian P Robert and George Casella. Monte Carlo Statistical Methods. Springer, 2nd edition, 2004.
59.M. Schmidt. minfunc: unconstrained differentiable multivariate optimization in matlab. https://www.cs.ubc.ca/~schmidtm/Software/minFunc.html, 2005.
60.M. Schmidt and N. Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint, 2013.
61.M. Schmidt, N. Le Roux, and F. Bach. Convergence rates of inexact proximal-gradient methods for convex optimization. Advances in Neural Information Processing Systems, 2011.
62.M. Schmidt, R. Babanezhad, M.O. Ahemd, A. Clifton, and A. Sarkar. Non-uniform stochastic average gradient method for training conditional random fields. International Conference on Artificial Intelligence and Statistics, 2015.
63.S. Shalev-Schwartz and T. Zhang. Proximal stochastic dual coordinate ascent. arXiv preprint, 2013a.
64.S. Shalev-Schwartz and T. Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14:567–599, 2013b.
65.S. Shalev-Schwartz and T. Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. International Conference on Machine Learning, 2014.
66.S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter. Pegasos: primal estimated sub-gradient solver for svm. Mathematical programming, 127(1):3–30, 2011.
67.Shai Shalev-Shwartz and Tong Zhang. Accelerated mini-batch stochastic dual coordinate ascent. Advances in Neural Information Processing Systems, 2013.
68.Jascha Sohl-Dickstein, Ben Poole, and Surya Ganguli. Fast large-scale optimization by unifying stochastic gradient and quasi-newton methods. International Conference on Machine Learning, 2014.
69.M.V. Solodov. Incremental gradient algorithms with stepsizes bounded away from zero. Computational Optimization and Applications, 11(1):23–35, 1998.
70.N. Srebro and K. Sridharan. Theoretical basis for “more data less work”? NIPS Workshop on Computataional Trade-offs in Statistical Learning, 2011.
71.T. Strohmer and R. Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15(2):262–278, 2009.
72.P. Sunehag, J. Trumpf, SVN Vishwanathan, and N. Schraudolph. Variable metric stochastic approximation theory. International Conference on Artificial Intelligence and Statistics, 2009.
73.Taiji Suzuki. Stochastic dual coordinate ascent with alternating direction method of multipliers. International Conference on Machine Learning, 2014.
74.C. H. Teo, Q. Le, A. J. Smola, and S. V. N. Vishwanathan. A scalable modular convex solver for regularized risk minimization. ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2007.
75.P. Tseng. An incremental gradient(-projection) method with momentum term and adaptive stepsize rule. SIAM Journal on Optimization, 8(2):506–531, 1998.
76.Chong Wang, Xi Chen, Alex Smola, and Eric Xing. Variance reduction for stochastic gradient optimization. Advances in Neural Information Processing Systems, 2013.
77.L. Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543–2596, 2010.
78.Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(2):2057–2075, 2014.
79.Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number independent access of full gradients. Advances in Neural Information Processing Systems, 2013.
80.Yuchen Zhang and Lin Xiao. Stochastic primal-dual coordinate method for regularized empirical risk minimization. arXiv preprint, 2014.
81.Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling. arXiv preprint arXiv:1401.2753, 2014.
82.L.W. Zhong and J.T. Kwok. Fast stochastic alternating direction method of multipliers. International Conference on Machine Learning, 2014.

Citation

MLA

Schmidt, M., et al. “Minimizing Finite Sums with the Stochastic Average Gradient”. arXiv, 2013, http://arxiv.org/abs/1309.2388v2.

APA

Schmidt, M., Roux, N. L., & Bach, F. (2013). Minimizing Finite Sums with the Stochastic Average Gradient. arXiv. http://arxiv.org/abs/1309.2388v2

Chicago

Schmidt, M., N. L. Roux, and F. Bach. 2013. “Minimizing Finite Sums with the Stochastic Average Gradient”. arXiv. http://arxiv.org/abs/1309.2388v2.

Harvard

Schmidt, M., Roux, N.L. and Bach, F. (2013) “Minimizing Finite Sums with the Stochastic Average Gradient”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1309.2388v2.

Vancouver

1. Schmidt M, Roux NL, Bach F (2013) Minimizing Finite Sums with the Stochastic Average Gradient. arXiv

BibTeX

@article{schmidt2013minimizing,
  title = {Minimizing Finite Sums with the Stochastic Average Gradient},
  author = {Schmidt, Mark and Roux, Nicolas Le and Bach, Francis},
  year = {2013},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1309.2388v2},
  eprint = {1309.2388}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Minimizing finite sums with the stochastic average gradient

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Convergence Rate Bounds for the Stochastic Average Gradient Method

Knowl 2 — Basic Stochastic Average Gradient Algorithm

Knowl 3 — Sparse and Memory-Efficient SAG with Just-In-Time Updates and Exact Regularization

Knowl 4 — Theoretical Convergence Rates Comparison: Full Gradient vs Accelerated Gradient vs SAG

Knowl 5 — Stochastic Backtracking Line-Search for Unknown Lipschitz Constant in SAG

Knowl 6 — Non-Uniform Example Sampling Strategy for SAG

Knowl 7 — Empirical Comparison of SAG with Full Gradient, Stochastic Gradient, and Coordinate Methods

Knowl 8 — Empirical Performance of Mini-Batching and Adaptive Non-Uniform Sampling in SAG

References

Citation

BibTeX

Access the Paper