统一分析SAG/SAGA/IAG三类算法,证明其收敛性并获得最优速率。
A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms
- 用统一框架分析三类优化算法,通过简单集中工具控制采样延迟。
- 设计新李雅普诺夫函数,首次给出SAG/SAGA的高概率收敛界。
- 得到IAG最佳已知收敛率,适用于非凸和马尔可夫采样场景。
在光滑且强凸目标函数的有限和优化问题中,本文提出一种统一的收敛性分析,涵盖随机方差减少算法SAG、SAGA及其确定性版本IAG。核心思想包括:(i) 利用简单的集中不等式控制随机子采样带来的延迟;(ii) 构造一个能反映延迟影响的新李雅普诺夫函数。该分析简洁模块化,首次为SAG和SAGA提供了高概率收敛边界,并可自然扩展至非凸目标与马尔可夫采样情形。作为副成果,本文获得了IAG算法目前最优的收敛速率,显著优于以往结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。