标题： 什么使本地更新有效：数据异质性和平滑性的作用 显示英文标题

标题： What Makes Local Updates Effective: The Role of Data Heterogeneity and Smoothness

摘要： 本论文对在数据异质性现实模型下分布式和联邦优化中的局部更新算法，尤其是局部SGD的理论理解做出了贡献。 核心关注点是有限的二阶异质性假设，该假设被证明在凸和非凸设置中，对于局部更新优于集中式或小批量方法是必要且充分的。 论文在多种局部更新算法的多个情况下建立了紧致的上下界，并表征了多个问题类的最小最大复杂度。 其核心是一个基于共识误差的细粒度分析框架，在三阶光滑性和放松的异质性假设下，得到了更精确的有限时间收敛界限。 论文还扩展到在线联邦学习，在一阶和赌徒反馈下提供了基本的遗憾界限。 这些结果共同阐明了局部更新何时以及为何能提供可证明的优势，本论文可作为在异质环境中分析局部SGD的自包含指南。 显示英文摘要

摘要： 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.