SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Aaron DefazioFrancis BachSimon Lacoste-Julien

article2014NeurIPS2,025 citations

Introduces SAGA, an incremental gradient method that delivers faster convergence rates than SAG and SVRG while natively supporting composite regularizers on both strongly and non-strongly convex objectives.

Listen

Modern large-scale machine learning and data analysis tasks frequently involve optimizing functions defined over massive collections of data points. Standard approaches often struggle to balance computational speed and versatility: traditional gradient descent methods process all data points at each step, ensuring steady progress but incurring substantial computational expense, whereas conventional stochastic methods evaluate one data point at a time but introduce random noise that prevents them from converging quickly without carefully decaying step sizes. Recent variance-reduced incremental algorithms have sought to combine the speed of stochastic updates with the steady convergence of batch methods, yet existing options often suffer from restricted theoretical support, inability to handle non-smooth regularizers, or excessive tuning requirements.

The article introduces and analyzes SAGA, a novel incremental gradient optimization algorithm designed to deliver fast, reliable convergence across a broad spectrum of convex machine learning problems. The authors set out to rigorously prove its theoretical convergence rates—including settings with non-smooth regularizers and problems lacking strong convexity—and to demonstrate its practical computational performance against leading alternatives.

The research combines rigorous mathematical analysis with empirical benchmarking. The theoretical evaluation establishes convergence bounds by analyzing the expected step-by-step progress using a dedicated mathematical tracking function. To substantiate the theory, the authors implemented SAGA alongside competing algorithms—such as SAG, SVRG, SDCA, and Finito—and evaluated their optimization performance on standard benchmark datasets (MNIST, COVTYPE, IJCNN1, and MILLIONSONG) spanning binary classification and least-squares regression under both smooth and non-smooth regularization.

The evaluation yielded several central findings. First, SAGA matches or improves upon theoretical convergence rates of prior methods, establishing linear convergence for strongly convex problems while natively supporting non-smooth composite regularizers via standard proximal operations. Second, SAGA directly handles non-strongly convex objectives without requiring artificial regularization, achieving a standard convergence rate of order 1/k while automatically adapting to any underlying strong convexity. Third, by utilizing an unbiased gradient update direction, SAGA avoids the complex biases of earlier algorithms like SAG and eliminates the inner-loop tuning parameters required by methods such as SVRG. Fourth, in empirical benchmarks, SAGA demonstrates optimization efficiency comparable to top-performing methods like SDCA and Finito while requiring only a single tunable step-size parameter, avoiding the two- to three-fold higher gradient evaluation overhead incurred by SVRG.

These findings indicate that SAGA offers a versatile and mathematically sound optimization framework that reduces operational complexity. By requiring only a single parameter to be tuned and supporting diverse regularizers directly, SAGA reduces the engineering time and compute costs typically spent searching over algorithm hyperparameters. It also unifies several previously fragmented algorithmic approaches into a clear conceptual spectrum between biased storage-heavy methods and parameter-heavy recalculation methods.

For practical implementation, practitioners should deploy SAGA when solving large-scale linear classification and regression problems, particularly when non-smooth regularizers like L1 penalties are required. For models where gradients cannot be represented compactly as simple scalars, practitioners should weigh the trade-off between SAGA’s memory footprint and SVRG’s extra computational passes. When deploying SAGA on sparse data, teams should use just-in-time updating heuristics to maintain linear computational efficiency.

The primary practical constraint of SAGA is its memory requirement: the algorithm maintains a table of historical gradient information across all data points, which can become costly for high-dimensional models such as deep neural networks where compact gradient representations are unavailable. Overall, confidence in the reported results is high for convex and composite convex empirical risk minimization problems, supported by complete mathematical proofs and consistent multi-dataset empirical performance.

Amiata Australian National University Ecole Normale Supérieure INRIA gradient algorithm multi-objective optimisation optimization problems SAGA algorithm fast incremental gradient method non-strongly convex composite objectives

arXiv: 1407.0202 adefazio/point-saga

Paper: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson et al. (2013). This paper introduces the stochastic variance reduced gradient (SVRG) method, establishing foundational variance-reduction mechanics that SAGA directly analyzes, builds upon, and improves.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). This work establishes proximal updates and adaptive subgradient principles in stochastic optimization, providing critical theoretical groundwork for handling composite objective functions.
Paper: HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent, Feng Niu et al. (2011). This paper analyzes stochastic gradient convergence and sparsity assumptions, providing essential foundational concepts for modern incremental first-order methods.
Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). This seminal paper introduces online convex programming and projected gradient methods, which form the mathematical basis for analyzing iterative convex optimization algorithms.

Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). This survey provides a comprehensive synthesis of large-scale machine learning optimization, situating variance-reduced incremental gradient methods like SAGA alongside modern stochastic algorithms.
Paper: An overview of gradient descent optimization algorithms, Sebastian Ruder (2016). This overview contextualizes first-order gradient methods and advanced optimizers across machine learning workflows, contrasting variance-reduction and adaptive learning rate strategies.
Paper: CVXPY: A Python-Embedded Modeling Language for Convex Optimization, Steven Diamond et al. (2016). This work develops a high-level modeling framework for specifying and executing composite and non-strongly convex optimization problems suited for modern first-order solvers.

Cover for SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Abstract

In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for composite objectives where a proximal operator is used on the regulariser. Unlike SDCA, SAGA supports non-strongly convex problems directly, and is adaptive to any inherent strong convexity of the problem. We give experimental results showing the effectiveness of our method.

Topics

gradient algorithm multi-objective optimisation optimization problems

Keywords

SAGA algorithm fast incremental gradient method non-strongly convex composite objectives stochastic dual coordinate ascent variance reduction approach proximal operator linear convergence rate convex conjugate

1 Introduction
2 SAGA Algorithm
3 Related Work
4 Implementation
5 Theory
6 Experiments
References
A The SDCA/Finito Midpoint Algorithm
B Lemmas
C Non-strongly-convex Problems
D Example Code for Sparse Least Squares & Ridge Regression

Knowls

Knowl 1 — SAGA Algorithm for Composite Optimization
algorithm
The SAGA algorithm minimizes composite finite-sum objective functions of the form:

$F(x) = f(x) + h(x) = \frac{1}{n} \sum_{i=1}^n f_i(x) + h(x)$

where $x \in \mathbb{R}^d$ , each $f_i: \mathbb{R}^d \to \mathbb{R}$ is convex and has $L$ -Lipschitz continuous gradient ( $L$ -smooth), and $h: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ is a convex, lower semi-continuous, potentially non-differentiable regularizer whose proximal operator $\text{prox}_\gamma^h(y) := \arg\min_{x \in \mathbb{R}^d} \{ h(x) + \frac{1}{2\gamma} \|x - y\|^2 \}$ is computable.
Input: Initial iterate $x^0 \in \mathbb{R}^d$ , step size $\gamma > 0$ , initial stored derivatives $f'_i(\phi_i^0) = f'_i(x^0)$ for all $i \in \{1, \dots, n\}$ , and iteration count $K$ .
Initialize average gradient vector $g^0 = \frac{1}{n} \sum_{i=1}^n f'_i(\phi_i^0)$ .
for $k = 0, 1, \dots, K-1$ do
    Sample index $j \in \{1, \dots, n\}$ uniformly at random.
    Compute non-composite update direction:
     $w^{k+1} = x^k - \gamma \left( f'_j(x^k) - f'_j(\phi_j^k) + g^k \right)$
    Apply proximal operator:
     $x^{k+1} = \text{prox}_\gamma^h(w^{k+1})$
    Update gradient average:
     $g^{k+1} = g^k + \frac{1}{n}\left( f'_j(x^k) - f'_j(\phi_j^k) \right)$
    Store updated gradient:
     $f'_j(\phi_j^{k+1}) = f'_j(x^k)$
    For all $i \neq j$ , keep $f'_i(\phi_i^{k+1}) = f'_i(\phi_i^k)$ .
Output: Final iterate $x^K$ .
The points $\phi_i^k$ represent the iterate value at which the derivative $f'_i$ was last computed for index $i$ . SAGA does not require storing the vectors $\phi_i^k$ explicitly, but only the table of gradient vectors $f'_i(\phi_i^k)$ and their running average $g^k$ .
Knowl 2 — Linear Convergence Rate of SAGA for Strongly Convex Objectives
theoretical result
Let $F(x) = \frac{1}{n}\sum_{i=1}^n f_i(x) + h(x)$ , where each $f_i: \mathbb{R}^d \to \mathbb{R}$ is $\mu$ -strongly convex ( $\mu > 0$ ) with $L$ -Lipschitz continuous gradient, and $h: \mathbb{R}^d \to \mathbb{R}$ is convex. Let $x^* = \arg\min_{x \in \mathbb{R}^d} F(x)$ denote the unique minimizer.

When SAGA is executed with constant step size $\gamma = \frac{1}{2(\mu n + L)}$ , the iterates $x^k$ satisfy the linear convergence bound in expectation:

$\mathbb{E}\left[ \|x^k - x^*\|^2 \right] \le \left( 1 - \frac{\mu}{2(\mu n + L)} \right)^k \left[ \|x^0 - x^*\|^2 + \frac{n}{\mu n + L} \left( f(x^0) - \langle f'(x^*), x^0 - x^* \rangle - f(x^*) \right) \right]$

where $f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$ and the expectation is taken over all random index selections up to iteration $k$ .

If the $\mu$ -strong convexity assumption holds only for the average function $f$ rather than for each individual $f_i$ , setting the step size to $\gamma = \frac{1}{3(\mu n + L)}$ yields the geometric convergence rate $\left( 1 - \frac{\mu}{6(\mu n + L)} \right)^k$ .
Knowl 3 — Sublinear Convergence Rate of SAGA for Non-Strongly Convex Composite Objectives
theoretical result
Let $F(x) = f(x) + h(x) = \frac{1}{n}\sum_{i=1}^n f_i(x) + h(x)$ , where each $f_i: \mathbb{R}^d \to \mathbb{R}$ is convex and has $L$ -Lipschitz continuous gradient (with no strong convexity, $\mu = 0$ ), and $h$ is a convex regularizer. Let $x^* \in \arg\min_{x \in \mathbb{R}^d} F(x)$ .

When SAGA is run with constant step size $\gamma = \frac{1}{3L}$ , the average iterate $\bar{x}^k := \frac{1}{k}\sum_{t=1}^k x^t$ (excluding the initialization $x^0$ ) satisfies the $O(1/k)$ sub-optimality bound:

$\mathbb{E}\left[ F(\bar{x}^k) \right] - F(x^*) \le \frac{4n}{k} \left[ \frac{2L}{n} \|x^0 - x^*\|^2 + f(x^0) - \langle f'(x^*), x^0 - x^* \rangle - f(x^*) \right]$

where the expectation is taken over all random choices of indices up to step $k$ .
Knowl 4 — Adaptivity of SAGA to Unknown Strong Convexity
theoretical result
When SAGA is run using the step size $\gamma = \frac{1}{3L}$ designed for non-strongly convex problems, it automatically adapts to any strong convexity $\mu > 0$ naturally present in the objective without requiring knowledge or tuning of $\mu$ .

Under this fixed step size, SAGA achieves the geometric convergence rate:

$\mathbb{E}\left[ \|x^k - x^*\|^2 \right] \le \left( 1 - \min\left\{ \frac{1}{4n}, \frac{\mu}{3L} \right\} \right)^k \left[ \|x^0 - x^*\|^2 + \frac{2n}{3L} \left( f(x^0) - \langle f'(x^*), x^0 - x^* \rangle - f(x^*) \right) \right]$

where $x^*$ is the optimal minimizer, $n$ is the number of component functions, and the expectation is taken over the sequence of randomly selected indices.
Knowl 5 — Lyapunov Function for SAGA Convergence Analysis
definition
For the finite-sum optimization problem $\min_{x \in \mathbb{R}^d} \frac{1}{n}\sum_{i=1}^n f_i(x) + h(x)$ with minimizer $x^*$ , the Lyapunov function $T^k$ used to establish linear convergence of SAGA is defined as:

$T^k := T\left(x^k, \{\phi_i^k\}_{i=1}^n\right) = \frac{1}{n} \sum_{i=1}^n f_i(\phi_i^k) - f(x^*) - \frac{1}{n} \sum_{i=1}^n \langle f'_i(x^*), \phi_i^k - x^* \rangle + c \|x^k - x^*\|^2$

where $x^k$ is the iterate at step $k$ , $\phi_i^k$ is the vector where $f'_i$ was last evaluated, and $c = \frac{1}{2\gamma(1 - \gamma \mu)n}$ with step size $\gamma = \frac{1}{2(\mu n + L)}$ and strong convexity parameter $\mu > 0$ .

Conditioned on the state at step $k$ , the Lyapunov function contracts in expectation:

$\mathbb{E}[T^{k+1} \mid T^k] \le \left( 1 - \frac{1}{\kappa} \right) T^k$

with contraction parameter $\kappa = \frac{1}{\gamma \mu} = \frac{2(\mu n + L)}{\mu}$ .
Knowl 6 — Unified Variance Reduction Framework for SAG, SVRG, and SAGA
model/method
To approximate the full gradient $\nabla f(x^k) = \mathbb{E}[X]$ using a single stochastic gradient sample $X = f'_j(x^k)$ (where $j \in \{1, \dots, n\}$ uniformly) and a correlated random variable $Y$ whose expectation $\mathbb{E}[Y]$ is known, a generalized variance-reduced estimator is:

$\theta_\alpha = \alpha(X - Y) + \mathbb{E}[Y], \quad \alpha \in [0, 1]$

with $\mathbb{E}[\theta_\alpha] = \alpha \mathbb{E}[X] + (1 - \alpha)\mathbb{E}[Y]$ and $\operatorname{Var}(\theta_\alpha) = \alpha^2 [\operatorname{Var}(X) + \operatorname{Var}(Y) - 2\operatorname{Cov}(X, Y)]$ . The fast incremental gradient algorithms correspond to specific choices of $Y$ and $eta$ :
- SAG (Stochastic Average Gradient): Chooses $Y = f'_j(\phi_j^k)$ (stored individual gradients) and $\alpha = 1/n$ . This produces a biased gradient estimate with variance scaled down by $1/n^2$ , which impedes proximal operator integration and complicates proofs.
- SVRG (Stochastic Variance Reduced Gradient): Chooses $Y = f'_j(\tilde{x})$ and $\alpha = 1$ , where $\tilde{x}$ is a snapshot vector updated periodically across all indices in an outer loop. The update is unbiased ( $\mathbb{E}[\theta_1] = \nabla f(x^k)$ ) but requires periodic full gradient passes.
- SAGA: Chooses $Y = f'_j(\phi_j^k)$ and $\alpha = 1$ , updating each stored derivative $f'_j(\phi_j^{k+1}) = f'_j(x^k)$ individually whenever index $j$ is picked. The resulting update direction $f'_j(x^k) - f'_j(\phi_j^k) + \frac{1}{n}\sum_{i=1}^n f'_i(\phi_i^k)$ is unbiased ( $\mathbb{E}[\theta_1] = \nabla f(x^k)$ ), enabling simple Lyapunov analysis and proximal support.
Knowl 7 — Primal Formulation of Stochastic Dual Coordinate Ascent (SDCA)
algorithm
Stochastic Dual Coordinate Ascent (SDCA) maximizes a dual objective using block-coordinate ascent over dual variables $\alpha_i \in \mathbb{R}^d$ . By applying the Moreau decomposition identity:

$\text{prox}_{f^*}(v) = v - \text{prox}_f(v)$

where $f^*$ is the Fenchel conjugate of $f$ , exact block-coordinate dual updates can be computed entirely in the primal domain without evaluating conjugate functions:
Input: Strong convexity parameter $\mu > 0$ , number of samples $n$ , initial stored gradient table entries $f'_i(\phi_i^0)$ for all $i \in \{1, \dots, n\}$ , and step size $\gamma = \frac{1}{\mu n}$ .
for $k = 0, 1, 2, \dots$ do
    Pick index $j \in \{1, \dots, n\}$ uniformly at random.
    Compute $z = -\gamma \sum_{i \neq j} f'_i(\phi_i^k)$ .
    Compute primal representative $\phi_j^{k+1} = \text{prox}_{\gamma f_j}(z) = \arg\min_x \left\{ f_j(x) + \frac{1}{2\gamma} \|x - z\|^2 \right\}$ .
    Store updated gradient $f'_j(\phi_j^{k+1}) = \frac{1}{\gamma}(z - \phi_j^{k+1})$ in table at index $j$ .
    For all $i \neq j$ , keep $f'_i(\phi_i^{k+1}) = f'_i(\phi_i^k)$ .
Output: Current primal iterate $x^k = -\gamma \sum_{i=1}^n f'_i(\phi_i^k)$ .
The dual variables satisfy $\alpha_i = -f'_i(\phi_i)$ , and the KKT conditions ensure that dual optimality implies primal optimality of $x^k = \gamma \sum_i \alpha_i$ .
Knowl 8 — SDCA/Finito Midpoint Algorithm
algorithm
By distributing problem strong convexity $\mu > 0$ directly into each loss component $f_i$ rather than handling it as a separate global quadratic regularizer $\frac{\mu}{2}\|x\|^2$ , SDCA and Finito merge into an exact parameter-free midpoint algorithm:
Input: Strong convexity parameter $\mu > 0$ , sample count $n$ , initial points $\phi_i^0 \in \mathbb{R}^d$ , and initial gradients $f'_i(\phi_i^0)$ for $i \in \{1, \dots, n\}$ .
for $k = 0, 1, 2, \dots$ do
    Pick index $j \in \{1, \dots, n\}$ uniformly at random.
    Compute surrogate center $z = \frac{1}{n-1} \sum_{i \neq j} \phi_i^k - \frac{1}{\mu(n-1)} \sum_{i \neq j} f'_i(\phi_i^k)$ .
    Compute $\phi_j^{k+1} = \text{prox}_{\frac{1}{\mu(n-1)} f_j}(z) = \arg\min_x \left\{ f_j(x) + \frac{\mu(n-1)}{2} \|x - z\|^2 \right\}$ .
    Set iterate $x^{k+1} = \phi_j^{k+1} = \frac{1}{n} \sum_{i=1}^n \phi_i^{k+1} - \frac{1}{\mu n} \sum_{i=1}^n f'_i(\phi_i^{k+1})$ .
    For all $i \neq j$ , set $\phi_i^{k+1} = \phi_i^k$ .
Output: Final iterate $x^{k+1}$ .
The proximal operator $\text{prox}_{\frac{1}{\mu(n-1)} f_j}$ resolves the implicit circular dependency present in Finito where $x^{k+1} = \phi_j^{k+1}$ appears on both sides of the update equation, removing the need for step size tuning.
Knowl 9 — Memory Reduction and Just-In-Time Updates for Sparse SAGA
model/method
For linear prediction models where $f_i(x) = \psi_i(a_i^T x)$ with feature vector $a_i \in \mathbb{R}^d$ and scalar loss $\psi_i$ , the gradient is $f'_i(x) = \psi'_i(a_i^T x) a_i$ . Instead of storing full $d$ -dimensional gradient vectors $f'_i(\phi_i) \in \mathbb{R}^d$ in the table, SAGA only needs to store the scalar derivative $c_i = \psi'_i(a_i^T \phi_i) \in \mathbb{R}$ for each sample $i \in \{1, \dots, n\}$ (or $p-1$ scalars for $p$ -class classification). This reduces table memory from $O(nd)$ to $O(n)$ , matching SDCA.

When features $a_i$ are sparse, computing dense gradient average updates at every iteration is avoided via just-in-time (lagged) updates:
1. Maintain a vector $\text{lag} \in \mathbb{N}^d$ where $\text{lag}[l]$ records the last iteration at which coordinate $l$ of $x$ was updated.
2. When coordinate $l$ is accessed at iteration $k$ , apply the accumulated missed updates: $x[l] \leftarrow x[l] - \gamma (k - \text{lag}[l]) g^k[l]$ , and update $\text{lag}[l] = k$ .
3. When an explicit quadratic regularizer $\frac{\mu}{2}\|x\|^2$ is present, scaling $x^{k+1} = (1 - \gamma \mu)x^k - \dots$ is tracked via a global multiplier $\beta_k \leftarrow (1 - \gamma \mu)\beta_k$ , with partial sums of the geometric series $\sum_{t=0}^{\Delta - 1} (1 - \gamma \mu)^t$ pretabulated to perform exact lagged updates in $O(1)$ operations per non-zero feature.
Knowl 10 — Empirical Convergence Comparison of SAGA, SAG, SVRG, SDCA, and Finito
empirical result
SAGA was empirically evaluated against SAG, SVRG, SDCA, Finito (with and without per-pass permuted access order), and L-BFGS across four benchmark datasets:
- Binary classification ( $L_2$ and $L_1$ regularized logistic regression): MNIST ( $n=60{,}000$ ), COVTYPE ( $n=581{,}012$ ), IJCNN1 ( $n=49{,}990$ ).
- Least squares regression ( $L_2$ and $L_1$ regularization): MILLIONSONG ( $n=463{,}715$ ).
Experimental findings:
1. Epoch-equivalent rate: Permuted Finito showed the fastest sub-optimality decrease per effective epoch. SAGA performed on par with unpermuted Finito and SDCA across all datasets.
2. Gradient evaluation cost: SVRG showed per-epoch convergence rates comparable to SAGA, but required approximately double the number of gradient evaluations per epoch due to its periodic full-gradient recalculation passes.
3. Initial progress: Constant step-size SAG exhibited slower initial convergence before reaching asymptotic rates, whereas SAGA achieved fast linear convergence immediately without requiring adaptive step-size heuristics.
4. Proximal regularization: SAGA and SVRG natively accommodated non-smooth $L_1$ regularization through proximal updates, whereas basic Finito and standard SDCA could not handle general non-smooth composite regularizers without approximations.

Coverage note — Intermediate mathematical lemmas (Lemmas 1 through 7) and the specific Cython code implementation listing from Appendix D were deliberately omitted as they represent intermediate proof machinery and concrete programming script formatting rather than standalone scientific contributions.

References

1.Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Technical report, INRIA, hal-0086005, 2013.
2.Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. JMLR, 14:567–599, 2013.
3.Paul Tseng and Sangwoon Yun. Incrementally updated gradient methods for constrained and regularized optimization. Journal of Optimization Theory and Applications, 160:832:853, 2014.
4.Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. Technical report, Microsoft Research, Redmond and Rutgers University, Piscataway, NJ, 2014.
5.Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. NIPS, 2013.
6.Taiji Suzuki. Stochastic dual coordinate ascent with alternating direction method of multipliers. Proceedings of The 31st International Conference on Machine Learning, 2014.
7.Evan Greensmith, Peter L. Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. JMLR, 5:1471–1530, 2004.
8.Jakub Konečný and Peter Richtárik. Semi-stochastic gradient descent methods. ArXiv e-prints, arXiv:1312.1666, December 2013.
9.Aaron Defazio, Tiberio Caetano, and Justin Domke. Finito: A faster, permutable incremental gradient method for big data problems. Proceedings of the 31st International Conference on Machine Learning, 2014.
10.Julien Mairal. Incremental majorization-minimization optimization with application to largescale machine learning. Technical report, INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann, 2014.
11.Shai Shalev-Shwartz and Tong Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. Technical report, The Hebrew University, Jerusalem and Rutgers University, NJ, USA, 2013.
12.Patrick Combettes and Jean-Christophe Pesquet. Proximal Splitting Methods in Signal Processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Springer, 2011.
13.Yu. Nesterov. Introductory Lectures On Convex Programming. Springer, 1998.
14.Aaron Defazio. New Optimization Methods for Machine Learning. PhD thesis, (draft under examination) Australian National University, 2014. http://www.aarondefazio.com/pubs.html.

Citation

MLA

Defazio, A., et al. “SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives”. arXiv, 2014, http://arxiv.org/abs/1407.0202v3.

APA

Defazio, A., Bach, F., & Lacoste-Julien, S. (2014). SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. arXiv. http://arxiv.org/abs/1407.0202v3

Chicago

Defazio, A., F. Bach, and S. Lacoste-Julien. 2014. “SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives”. arXiv. http://arxiv.org/abs/1407.0202v3.

Harvard

Defazio, A., Bach, F. and Lacoste-Julien, S. (2014) “SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1407.0202v3.

Vancouver

1. Defazio A, Bach F, Lacoste-Julien S (2014) SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. arXiv

BibTeX

@article{defazio2014saga,
  title = {SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives},
  author = {Defazio, Aaron and Bach, Francis and Lacoste-Julien, Simon},
  year = {2014},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1407.0202v3},
  eprint = {1407.0202}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

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

Open PDF

License: Published with permission

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — SAGA Algorithm for Composite Optimization

Knowl 2 — Linear Convergence Rate of SAGA for Strongly Convex Objectives

Knowl 3 — Sublinear Convergence Rate of SAGA for Non-Strongly Convex Composite Objectives

Knowl 4 — Adaptivity of SAGA to Unknown Strong Convexity

Knowl 5 — Lyapunov Function for SAGA Convergence Analysis

Knowl 6 — Unified Variance Reduction Framework for SAG, SVRG, and SAGA

Knowl 7 — Primal Formulation of Stochastic Dual Coordinate Ascent (SDCA)

Knowl 8 — SDCA/Finito Midpoint Algorithm

Knowl 9 — Memory Reduction and Just-In-Time Updates for Sparse SAGA

Knowl 10 — Empirical Convergence Comparison of SAGA, SAG, SVRG, SDCA, and Finito

References

Citation

BibTeX

Source Code

Access the Paper