揭示本地更新在异构数据下的有效性机制
What Makes Local Updates Effective: The Role of Data Heterogeneity and Smoothness
- 基于共识误差框架，分析异构数据中本地更新的收敛性
- 证明二阶异构性受限时，本地更新优于集中式方法
- 适用于联邦学习与在线学习，适合算法设计者参考
本论文深入探讨分布式与联邦优化中本地更新算法（尤其是Local SGD）的理论机制，聚焦于现实数据异构性模型。核心贡献在于提出并验证有界二阶异构性假设是本地更新在凸与非凸场景下优于集中式或小批量方法的必要且充分条件。论文在多种情形下建立了紧致的上下界，刻画了多类问题的极小极大复杂度。其核心为细粒度的共识误差分析框架，在三阶光滑性及弱异构假设下获得更紧的有限时间收敛界。研究还拓展至在线联邦学习，分别在梯度反馈与无梯度反馈下提供基础后悔界。整体结果明确了本地更新的适用条件与优势来源，可作为异构环境下分析Local SGD的自洽指南。
原文摘要 · Abstract (English)
This thesis contributes to the theoretical understanding of local update algorithms, especially Local SGD, in distributed and federated optimization under realistic models of data heterogeneity. A central focus is on the bounded second-order heterogeneity assumption, which is shown to be both necessary and sufficient for local updates to outperform centralized or mini-batch methods in convex and non-convex settings. The thesis establishes tight upper and lower bounds in several regimes for various local update algorithms and characterizes the min-max complexity of multiple problem classes. At its core is a fine-grained consensus-error-based analysis framework that yields sharper finite-time convergence bounds under third-order smoothness and relaxed heterogeneity assumptions. The thesis also extends to online federated learning, providing fundamental regret bounds under both first-order and bandit feedback. Together, these results clarify when and why local updates offer provable advantages, and the thesis serves as a self-contained guide for analyzing Local SGD in heterogeneous environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。