揭示局部SGD在数据异构下的收敛机制，给出更紧的理论保证。
What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity
- 基于二阶异构有界假设，改进局部SGD的收敛率分析。
- 证明了新上界几乎紧致，且首次给出带替换串行SGD下界。
- 适用于研究分布式优化理论或联邦学习的读者。
局部SGD（又称联邦平均）是一种广泛应用的分布式优化算法。尽管局部SGD在实践中常优于小批量SGD，但现有理论仍未能充分解释其在真实数据异构条件下的有效性。Patel等（2025）提出，二阶异构有界假设可刻画强凸目标下局部更新的效率，并推测该原理可推广至一般凸情形。本文证明了这一猜想，在一般凸目标下建立了基于二阶异构有界假设的局部SGD改进收敛保证。同时，我们提升了该设定下局部SGD的最优下界，表明我们的上界近乎紧致。这些结果共同构建了更精细、更严格的局部SGD收敛理论。作为技术应用，我们还为带替换的串行SGD提供了下界，揭示了罕见高曲率客户端对性能的影响。
原文摘要 · Abstract (English)
Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although Local SGD often outperforms alternatives such as Mini-batch SGD in practice, theory still only partially explains when and why local updates help under realistic data heterogeneity. Recent work by [Patel et al., 2025] shows that a bounded second-order heterogeneity assumption captures the efficiency of Local SGD for strongly convex objectives, and conjectures that the same principle extends to the general convex setting. In this paper, we prove this conjecture by establishing an improved convergence guarantee for Local SGD on general convex objectives under bounded second-order heterogeneity. We also improve the best-known lower bounds for Local SGD in this setting, showing that our upper bounds are nearly tight. Together, these results provide a sharper, more fine-grained convergence theory for Local SGD. As a further application of our techniques, we provide a lower bound for serial SGD with replacement, showing how second-order heterogeneity captures the impact of rare high-curvature clients.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。