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

Aaron Defazio; Francis Bach; Simon Lacoste-Julien

Source-linked AI summary

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

Aaron Defazio, Francis Bach, Simon Lacoste-Julien

arXiv:1407.0202v3Jul 1, 2014cs.LGmath.OCstat.ML

TL;DR

Finite-sum optimization methods with fast convergence have limited support for composite and non-strongly convex objectives. SAGA introduces an unbiased incremental-gradient method with proximal support, and the paper reports stronger theory than SAG and SVRG, direct non-strongly convex applicability, and effective experiments.

Problem
Fast finite-sum optimization methods do not uniformly support composite objectives or non-strongly convex problems directly.
Method
SAGA uses an unbiased incremental-gradient update with stored derivative information and supports proximal operators for composite objectives.
Results
SAGA has theoretical strongly convex convergence rates better than SAG and SVRG, supports composite objectives, and applies directly to non-strongly convex problems while adapting to inherent strong convexity.
Takeaways & Limitations
SAGA provides one method that covers composite and non-strongly convex settings without modification or an additional regularization parameter, with experiments showing effectiveness.
Takeaways & Limitations
The related SDCA formulation assumes strong convexity induced by a separate strongly convex regularizer, while the problem setting requires easy proximal computation for the regularizer.

Abstract

from arXiv · show

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.

1 Introduction

SAGA targets finite-sum optimization problems common in machine learning, including composite objectives, while extending fast incremental-gradient methods beyond strong convexity.

Motivation: Finite-sum structure enables faster expected minimization of strongly convex objectives than methods without that structure.This matters because finite sums commonly arise in empirical risk minimization.
Problem setting: The problem class assumes convex functions with L-Lipschitz continuous derivatives and also considers strong convexity and composite regularization.The composite case adds a potentially nonsmooth convex regularizer whose proximal operation is easy to compute.
Contributions: SAGA is a novel incremental gradient method with theoretical strongly convex convergence rates better than SAG and SVRG and within a factor of 2 of SDCA.The rates also hold in the composite setting.
Contributions: Unlike SDCA, SAGA applies to non-strongly convex problems without modification and has theoretical convergence rates for that case.The paper also relates fast incremental-gradient methods through small algorithmic modifications.

2 SAGA Algorithm

SAGA maintains stored derivative information while updating one randomly selected component per iteration, then applies a proximal step when needed. Its analysis covers strongly convex, non-strongly convex, composite, and automatically adaptive settings.

Algorithm: SAGA initializes known derivatives at x0 and stores them in a table, updating the selected component while leaving other entries unchanged.For some problems, storage can be reduced from full gradients to a single floating-point value per component.
Algorithm: Each iteration picks an index j uniformly at random and uses the updated derivative together with the table average.The method uses a step size γ and supports a proximal operation for the regularizer.
Convergence: With γ = 1/(2(µn+L)), SAGA has a convergence rate in the strongly convex composite case, and therefore also in the non-composite case.The paper states that this result is proved in Section 5.
Convergence: In the non-strongly convex case, convergence is established for the average iterate rather than the initial iterate.The average is defined over iterates excluding step 0.
Adaptivity: Using γ = 1/(3L), SAGA automatically adapts to inherent strong convexity µ > 0 and obtains a corresponding geometric convergence rate.The result is proved in the supplementary material.
Non-strong convexity: SAGA avoids the additional tunable regularization parameter otherwise used to apply incremental gradient methods to non-strongly convex problems.Adding a small quadratic regularizer can recover a convergence rate, but its amount must be selected separately.

3 Related Work

SAGA is presented as a unifying midpoint among fast incremental-gradient methods, combining unbiased variance reduction with support for proximal objectives and non-strongly convex problems.

Method relationships: SAGA, SAG, SVRG, Finito, MISOµ, and SDCA are related through small modifications of incremental-gradient updates.The paper uses SAGA as a midpoint to provide a unified view of these methods.
SAGA versus SAG: SAGA uses an unbiased variance-reduced update, whereas SAG uses a biased update with a smaller update variance.For the same stored quantities, the SAG update variance is 1/n^2 that of SAGA, while SAGA enables simpler convergence theory and proximal rates.
SAGA versus SVRG: SAGA updates one stored gradient whenever its index is sampled, while SVRG refreshes all stored gradients in batches at outer iterations.This places SAGA between SAG and SVRG in how gradient information is maintained.
SAGA versus SVRG: SAGA avoids SVRG’s second tuning parameter, the inner-loop length m, whereas SVRG must select it in addition to the step size.The paper identifies tuning one parameter instead of two as a practical advantage for SAGA.
SAGA versus Finito/MISOµ: Compared with Finito/MISOµ, SAGA does not require strong convexity, supports proximal operators, and does not require storing the φ_i values.Finito/MISOµ can achieve empirical speed-ups with per-pass re-permuted access, especially when evaluating f_i is expensive.
SAGA versus SDCA: The paper gives a primal interpretation of SDCA and relates its proximal update to the proximal operator of a convex conjugate through Moreau decomposition.This transformation makes SDCA closely related to MISOµ in the paper’s primal formulation.

4 Implementation

The implementation discussion focuses on reducing storage and handling initialization, regularization, sparse updates, and just-in-time scaling.

Storage: For logistic regression and least squares, SAGA can store one weighting constant per example instead of each full derivative.For multiclass classifiers with p classes, the storage can similarly be reduced to p − 1 values per example.
Initialization: SAGA assumes all initial gradients at x0 are known, but a first-pass heuristic can introduce data points sequentially and compute averages.The supplied passage describes this as a non-randomized initialization heuristic.
Regularization: When a quadratic regularizer is explicit, the algorithm can be modified to incorporate the regularizer directly.
Sparse updates: Sparse implementations can scale a separate constant β_k instead of scaling x_k at every step.The paper describes this as a standard stochastic-gradient implementation trick.
Sparse updates: Sparse problems with quadratic regularization require careful just-in-time updating, for which supplementary Python code is provided.

5 Theory

The theory defines a Lyapunov function for SAGA and proves an expected contraction under explicit step-size and parameter choices. The analysis also establishes adaptivity to strong convexity.

Assumptions: The analysis begins with convex finite-sum assumptions, optionally requiring each f_i to be μ-strongly convex with L-Lipschitz gradients.Expectations are conditioned on the current iterate and stored derivatives.
Lyapunov analysis: Theorem 1 defines a Lyapunov function T for SAGA relative to the optimal solution x∗.The function tracks the iterate and auxiliary stored-gradient quantities.
Proof strategy: The proof simplifies the Lyapunov terms using proximal non-expansiveness, the conditional expectation of w^{k+1}, and bounds from the preceding lemmas.The proof also applies variance-related bounds and fixes auxiliary constants to make bracketed terms non-positive.
Adaptivity: Using γ = 1/(3L) provides an adaptivity-to-strong-convexity result with the same c and β = 2.The parameter choice is used to ensure the relevant terms are non-positive.
Convergence consequence: Chaining expectations and substituting the constants yields the stated convergence corollary for the expected distance to x∗.The expectation covers all sampled indices through step k.

6 Experiments

Experiments compare incremental methods on four datasets with L2 regularisation and, for a subset, L1 regularisation. SAGA performs similarly to non-permuted Finito and SDCA, while method rankings depend on computational cost and implementation properties.

Experimental setup: The experiments evaluate binary classification on MNIST, COVTYPE, and IJCNN1, plus least-squares prediction on MILLIONSONG.All methods use the same code base with only the main update rule changed.
Experimental setup: All methods support the L2-regularised setting, while only a subset is tested with an L1 regulariser.Step sizes are selected for fastest convergence, and SVRG includes a recalibration pass every n iterations.
Results: Finito (perm) performs best per epoch but can be the most expensive method per step.The comparison distinguishes epoch-level convergence from per-step computational cost.
Results: SAGA performs similarly to non-permuted Finito and SDCA in the reported experiments.SVRG is similarly fast per epoch but uses twice as many gradient evaluations per epoch for this problem.
Interpretation: The experiments indicate that method selection should use algorithmic properties rather than convergence rate alone.SAG is slower initially under the constant step size used, although an adaptive rule is needed for its optimal results.

A The SDCA/Finito Midpoint Algorithm

This section derives a method positioned between SDCA and Finito by modifying how strong convexity is represented and resolving a resulting circular dependency with a proximal operator.

Derivation: SDCA can be expressed as minimizing a lower bound derived through Lagrangian duality.The section then replaces direct regulariser inclusion with a strong-convexity lower bound for each f_i.
Derivation: Removing μ from the bound yields a simple algorithmic modification involving the stored representatives φ_i.The resulting update is subsequently compared with Finito’s update.
Relation to Finito: The resulting equation reveals similarity to Finito, differing in whether the right-hand-side vectors use step k+1 or step k values.This creates a circular dependency because φ_j^{k+1} appears in the definition of x^{k+1}.
Midpoint algorithm: The proximal operator resolves the circular dependency, producing a midpoint algorithm between Finito and SDCA.The method is reported to have robustness to permuted orderings similar to Finito and no tunable parameters like SDCA.
Method properties: SDCA can be the best method among those discussed when its proximal operator is about as fast to compute as evaluating f_j.Its main limitations include direct handling of non-strongly convex problems and proximal operators for composite regularisers.

B Lemmas

The lemmas provide convexity and smoothness inequalities used to bound SAGA’s error terms. The proof relies on a strengthened inequality and repeated variance decompositions.

Basic inequalities: Lemma 4 assumes μ-strong convexity and L-Lipschitz gradients and establishes an inequality valid for all x and y.Its proof applies a standard smooth-convex inequality at a minimizer and sums over component functions.
Basic inequalities: A derived inequality expresses function differences through gradient differences and a mixed inner-product term involving L and μ.The expression is obtained by applying a convexity inequality to g(x) = f(x) − μ∥x∥²/2.
Finite-sum bounds: The finite-sum assumption averages the component-function inequalities to obtain a bound for f(x) relative to x∗.This is stated as a corollary of Lemma 4.
SAGA-specific bounds: The proof of the SAGA-specific bound uses ∥x + y∥² ≤ (1 + β^-1)∥x∥² + (1 + β)∥y∥² instead of fixing β = 1.It also applies the standard variance decomposition three times.
SAGA-specific bounds: Additional displayed terms and substitutions complete the variance-based bounds used in the convergence proof.These intermediate steps include repeated variance decompositions and gradient terms.

C Non-strongly-convex Problems

For convex component functions, the analysis establishes a non-strongly-convex convergence result using a Lyapunov function augmented with an iterate-distance term. The proof combines conditional-expectation bounds, convexity, and parameter choices that make the key terms vanish.

Theorem 2: Theorem 2 analyzes the convex case with step size γ = 1 3L and an averaged iterate ¯xk.The stated theorem introduces the convergence result for convex fi under this step-size choice.
Proof strategy: The analysis takes expectations over sampled indices and prior steps, then telescopes the resulting Lyapunov inequalities across iterations.Convexity is subsequently used to move the summation inside F before rescaling by 4n/k.
Proof strategy: The proof adds an α xk −x∗ 2 term to the Lyapunov function and uses a prox-SVRG result for the gradient-approximation difference.The argument relies on the zero-expectation property of the corresponding difference quantity.
Parameter choice: Choosing γ = 1 3L, β = 1, and c = 3L sets the three bracketed terms to zero.The step size is selected to match the adaptive-to-strong-convexity step size, while convexity ensures the square-bracketed terms are positive.

D Example Code for Sparse Least Squares & Ridge Regression

The example implements SAGA for sparse least-squares and ridge-regression data stored in compressed sparse column format. It avoids dense per-iteration work through lag tracking, just-in-time updates, and compact stored quantities.

Implementation: The example is written in compiled Python using Cython and includes sparse dot products and weighted dense-plus-sparse operations.The main saga lstsq routine exposes the maximum iteration count and algorithm properties such as inverse step size and regularization.
Data representation: The implementation stores data points as columns in CSC format and represents the matrix through data, indices, and indptr arrays.The dimensions m and n denote the feature dimension and number of data points, respectively.
Sparse updates: Sparse updates use a lag array and lagged-update routines to apply missed coordinate changes only when the relevant entries are accessed.The code tracks each entry's last update iteration and applies the accumulated scaling before modifying sparse coordinates.
Stored state: For least squares, the code stores one scalar Ai ∗betak ∗x value per data point instead of a full gradient vector.This compact table supports the gradient-average update used by SAGA.