
























Abstract: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 objective functions, 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 stochastic 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 the first high-probability bounds for SAG and SAGA that can be seamlessly extended to non-convex objectives and Markov 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.
| Comments: | To appear at the 43rd International Conference on Machine Learning (ICML) |
| Subjects: | Machine Learning (cs.LG); Systems and Control (eess.SY); Optimization and Control (math.OC) |
| Cite as: | arXiv:2602.05304 [cs.LG] |
| (or arXiv:2602.05304v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2602.05304 arXiv-issued DOI via DataCite |
From: Aritra Mitra [view email]
[v1]
Thu, 5 Feb 2026 04:57:20 UTC (30 KB)
[v2]
Thu, 21 May 2026 16:32:29 UTC (50 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。