⚡ electrical engineering

A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms

This paper presents a unified, short, and modular convergence analysis for the SAG, SAGA, and IAG algorithms by introducing a novel Lyapunov function and delay bounds, which yields the first high-probability convergence guarantees for SAG and SAGA while significantly improving the known rates for IAG.

Original authors: Feng Zhu, Robert W. Heath Jr., Aritra Mitra

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Feng Zhu, Robert W. Heath Jr., Aritra Mitra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley (the "optimal solution" to a machine learning problem). You have a map, but it's made up of thousands of tiny, separate pieces of terrain data (the "component functions").

To find the bottom, you need to know the slope of the ground right where you are standing.

The Old Ways: Too Slow or Too Wobbly

The "Full Map" Approach (Gradient Descent): You stop and ask every single one of your 1,000 surveyors to report the slope of their specific piece of land. You average their answers to get the true slope, then take a step.
- The Problem: It's incredibly accurate, but it takes forever. If you have a million pieces of data, asking everyone every time is too slow.
The "Guess and Check" Approach (Stochastic Gradient Descent): To save time, you just ask one random surveyor for their opinion and take a step based on that.
- The Problem: It's fast, but your surveyors might be giving you bad advice. One might say "go left," while the next says "go right." You end up wobbling around the valley, taking a very long time to actually get to the bottom.

The New Heroes: SAG, SAGA, and IAG

To fix this, researchers invented "Variance-Reduced" algorithms (SAG, SAGA, and IAG). Think of these as smart teams that keep a memory bank.

How they work: Instead of asking everyone every time, they ask just one surveyor. But, they also remember what the other 999 surveyors said in the past. They combine the fresh report with the old memory to get a very accurate slope estimate without doing all the work.
The Catch: The memory isn't perfect. The information about Surveyor #5 might be from 10 steps ago. In math terms, this is called "staleness" or "delay."

The Problem with Previous Math

For years, mathematicians tried to prove these algorithms worked well.

For SAG, the proof was so incredibly complex it required a computer to check the math. It was like trying to solve a Rubik's cube while blindfolded.
For SAGA, the proof was simpler, but it was a different proof entirely.
For IAG (the deterministic version where you ask surveyors in a strict order), the math was totally different again, and it suggested the algorithm was much slower than it actually was.

It was like having three different rulebooks for three very similar games.

The Paper's Big Idea: One Unified Rulebook

The authors of this paper say: "Stop using three different rulebooks. Let's use one."

They developed a single, short, and simple mathematical framework that explains how SAG, SAGA, and IAG all work. Here is their secret sauce, explained simply:

1. The "Good Day" Guarantee (Bounding the Delay)

The authors realized that even though the surveyors' reports are old (stale), they aren't ancient.

Analogy: Imagine you are waiting for a bus. You might wait a long time, but with high probability, you won't wait forever.
The Math: They used a statistical tool (Bernstein's inequality) to prove that, with very high confidence, no single piece of data will be "stale" for more than a certain amount of time (let's call this time $\tau$ ).
The Result: They can treat these smart algorithms as if they are just "Gradient Descent" but with a slight, predictable delay.

2. The "Memory Weight" Scale (The Lyapunov Function)

Once they knew the delay was bounded, they needed a way to measure progress.

Analogy: Imagine you are walking down a hill, but you are carrying a backpack of old, heavy rocks (the stale data). If you only measure how far you walked today, you ignore the weight of the rocks slowing you down.
The Innovation: The authors designed a special "scorecard" (called a Lyapunov function). This scorecard doesn't just look at your current position; it also looks at the recent history of your steps. It gives more weight to recent steps and less weight to older ones.
The Result: By tracking this "weighted score," they could mathematically prove that the algorithm must converge to the bottom of the valley, and they could calculate exactly how fast.

Why This Matters (The Takeaways)

It's Short and Simple: They replaced a computer-aided, nightmare-proof with a clean, logical argument that fits on a few pages.
It's More Reliable: Previous proofs only said, "On average, this works." The new proof says, "With very high probability, this works, and here is exactly how likely it is to fail." This is crucial for safety-critical applications.
It Fixes the "Slow" Algorithm: For the IAG algorithm (the deterministic one), previous math suggested it was painfully slow. The authors' new method shows it is actually much faster—almost as fast as the best methods. It's like realizing a car you thought was a slow sedan is actually a sports car.
It Works Everywhere: They showed this same logic works even if the surveyors don't pick data randomly (like in a strict line) or if the data comes from a shifting pattern (Markov sampling).

Summary

The authors took three complex, messy algorithms that were previously analyzed with different, difficult math, and showed they are all just variations of the same simple idea: "Use memory, but account for the fact that memory gets old." They built a single, sturdy bridge to prove they all work, making the math easier to understand and the algorithms more trustworthy.

Technical Summary: A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms

Problem Statement
The paper addresses the finite-sum optimization problem common in machine learning empirical risk minimization:
$\min_{x \in \mathbb{R}^d} f(x) := \frac{1}{N} \sum_{i=1}^N f_i(x)$
where each component function $f_i$ is $L$ -smooth and the composite function $f$ is $\mu$ -strongly convex. The authors focus on three prominent algorithms designed to balance the computational cost of Gradient Descent (GD) and the variance issues of Stochastic Gradient Descent (SGD):

SAG (Stochastic Average Gradient): A stochastic method that maintains a memory of past gradients but uses a biased gradient estimator.
SAGA: A stochastic variant of SAG that corrects the bias to provide an unbiased estimator.
IAG (Incremental Aggregated Gradient): A deterministic counterpart that updates parameters using a cyclic or deterministic order of component functions.

Existing literature suffers from disparate analysis techniques. The original proof for SAG is notoriously complex, requiring computer-aided verification. Furthermore, analyses for IAG have historically yielded significantly slower convergence rates compared to SAG and SAGA, and high-probability bounds for SAG and SAGA have been elusive.

Methodology
The authors propose a unified proof framework that treats SAG, SAGA, and IAG under a single analytical structure. The methodology relies on two primary steps:

Bounding Delays via Concentration:
The core observation is that the "staleness" of component gradients (the time elapsed since a specific $f_i$ was last sampled) is random but controllable.
- For I.I.D. sampling (SAG/SAGA), the authors use Bernstein's inequality to show that with high probability, the maximum delay $\tau$ for any component is bounded by $\tilde{O}(N \log(NK/\delta))$ .
- For Markov sampling, they leverage a Bernstein-type concentration bound for uniformly ergodic Markov chains (Paulin, 2015) to establish a similar bound dependent on the mixing time and minimum visitation probability.
- For Deterministic sampling (IAG), the delay is deterministically bounded by the sampling period $\tau$ .
  This allows the authors to define a "good event" $\mathcal{G}$ where all gradient estimators use information no older than $\tau$ steps.
Novel Lyapunov Function Construction:
Recognizing that the gradient error depends on a window of past gradients, the authors construct a specific Lyapunov function $V_k$ for $k \ge \tau$ :
$V_k = f(x_k) - f(x^*) + L\alpha^2 W_k$
where $W_k = \sum_{j=1}^{\tau} (\tau - j + 1) \|g_{k-j}\|_2^2$ .
The weights $(\tau - j + 1)$ are chosen to account for how stale gradients accumulate in the descent inequalities over the delay window. By establishing a one-step contractive recursion for this Lyapunov function conditioned on event $\mathcal{G}$ , they derive linear convergence rates.

Key Contributions and Results

Unified Proof Technique: The paper provides the first single proof framework that applies to both biased (SAG) and unbiased (SAGA) stochastic algorithms, as well as their deterministic counterpart (IAG). This unifies the analysis of stochastic and deterministic variance-reduced methods, which previously required fundamentally different approaches.
High-Probability Bounds for SAG and SAGA: The authors derive the first high-probability convergence bounds for SAG and SAGA. Unlike previous in-expectation guarantees, these bounds hold with probability at least $1-\delta$ . The convergence rate is linear, with an exponent scaling as $\tilde{O}(1/(\tau \kappa))$ , where $\kappa = L/\mu$ is the condition number and $\tau \approx N$ .
Improved Rates for IAG: The analysis yields a significantly tighter convergence rate for IAG compared to prior work (Gurbuzbalaban et al., 2017).
- Prior Rate: Scales as $\exp(-K / (\kappa^2 N^2))$ .
- New Rate: Scales as $\exp(-K / (\kappa N))$ .
  This improvement removes the quadratic dependence on the condition number and the number of samples in the exponent, aligning IAG's theoretical performance more closely with GD and stochastic VR methods.
Extensions:
- Non-Convex Objectives: The framework extends to smooth, non-convex objectives, providing high-probability bounds on the average squared gradient norm.
- Markov Sampling: The results are extended to settings where component functions are sampled via a Markov chain, with the staleness parameter $\tau$ adjusted based on the chain's mixing time.

Significance and Claims
The paper claims that its primary significance lies in the simplicity and modularity of the proof. The authors argue that the traditional difficulty in analyzing SAG (often attributed to its biased estimator) is resolved by treating the algorithm as a "delayed" version of Gradient Descent, where the delay is bounded with high probability.

Key claims regarding the work's impact include:

Simplification: The proof is "short and modular," avoiding the complex, computer-aided polynomial verification required for the original SAG analysis.
Unification: It demonstrates that the dynamics of biased and unbiased, stochastic and deterministic variance-reduced algorithms can be explained by a single framework.
Tightness: The improved rate for IAG suggests that previous pessimistic bounds were artifacts of the analysis technique rather than inherent limitations of the algorithm.
Generality: The "bounded delay" concept is presented as a property of the sampling scheme rather than the specific algorithm, suggesting the framework can be applied to other single-loop variance-reduced methods (e.g., accelerated or second-order methods) in future work.

The authors explicitly state that they do not provide experimental results, focusing entirely on theoretical convergence analysis. They acknowledge that the derived rates depend on prior knowledge of the horizon $K$ to set the step size, though they conjecture that "doubling tricks" could remove this requirement.