重新分析两种分布式优化方法，揭示其在弱凸函数下的优势
Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis
- 在弱凸条件下分析局部SGD与SCAFFOLD的收敛性
- 局部SGD在高阶相似性下收敛更快，无需强梯度相似假设
- 适用于联邦学习等场景，适合研究分布式优化的学者
LocalSGD 和 SCAFFOLD 是分布式随机优化中广泛使用的方法，广泛应用于机器学习、大规模数据处理和联邦学习。然而，严格证明它们相比简单方法（如小批量SGD）的理论优势一直具有挑战性，因为现有分析往往依赖于强假设、不现实的前提或过于受限的情景。本文在多种现有或较弱条件下重新审视了 LocalSGD 与 SCAFFOLD 的收敛性质，包括梯度相似性、海森相似性、弱凸性以及海森矩阵的利普希茨连续性。分析表明：(i) 局部SGD 在弱凸函数上比小批量SGD 收敛更快，且无需更强的梯度相似性假设；(ii) 局部SGD 显著受益于更高阶的相似性和光滑性；(iii) SCAFFOLD 在更广泛的非二次函数类上表现出比小批量SGD 更快的收敛速度。这些理论洞见为 LocalSGD 与 SCAFFOLD 超越小批量SGD 的条件提供了更清晰的理解。
原文摘要 · Abstract (English)
LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization, with numerous applications in machine learning, large-scale data processing, and federated learning. However, rigorously establishing their theoretical advantages over simpler methods, such as minibatch SGD (MbSGD), has proven challenging, as existing analyses often rely on strong assumptions, unrealistic premises, or overly restrictive scenarios. In this work, we revisit the convergence properties of LocalSGD and SCAFFOLD under a variety of existing or weaker conditions, including gradient similarity, Hessian similarity, weak convexity, and Lipschitz continuity of the Hessian. Our analysis shows that (i) LocalSGD achieves faster convergence compared to MbSGD for weakly convex functions without requiring stronger gradient similarity assumptions; (ii) LocalSGD benefits significantly from higher-order similarity and smoothness; and (iii) SCAFFOLD demonstrates faster convergence than MbSGD for a broader class of non-quadratic functions. These theoretical insights provide a clearer understanding of the conditions under which LocalSGD and SCAFFOLD outperform MbSGD.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。