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

Stochastic variance-reduced algorithms such as Stochastic Average Gradient (SAG) and SAGA, and their deterministic counterparts like the Incremental Aggregated Gradient (IAG) method, have been extensively studied in large-scale machine learning. Despite their popularity, existing analyses for these algorithms are disparate, relying on different proof techniques tailored to each method. Furthermore, the original proof of SAG is known to be notoriously involved, requiring computer-aided analysis. Focusing on finite-sum optimization with smooth and strongly convex objectives, our main contribution is to develop a single unified convergence analysis that applies to all three algorithms: SAG, SAGA, and IAG. Our analysis features two key steps: (i) establishing a bound on delays due to sub-sampling using simple concentration tools, and (ii) carefully designing a novel Lyapunov function that accounts for such delays. The resulting proof is short and modular, providing high-probability bounds for SAG and SAGA that can be seamlessly extended to non-convex objectives and Markovian sampling. As an immediate byproduct of our new analysis technique, we obtain the best known rates for the IAG algorithm, significantly improving upon prior bounds.

Training modern machine learning models often involves solving massive optimization problems using specialized efficient algorithms like SAG, SAGA, and IAG. While these algorithms are widely used, the mathematical proofs showing exactly how fast and reliably they work (their "convergence analysis") have traditionally been incredibly complex and different for each one, making them difficult for researchers to fully master or compare. Our main contribution is to establish the surprising result that a single, unified mathematical framework suffices to explain all three algorithms at once. We achieve this by identifying a common thread shared by the dynamics of these methods, that was overlooked by prior work, leading to separate and long-winded explanations. By identifying a common analysis template that considerably simplifies existing convergence proofs, our work unlocks the potential to demystify the behavior of many other related optimization algorithms, contributing to a deeper understanding of modern machine learning training methods.