← Research

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

Kumar Kshitij Patel

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.

PDF ↗

Models

Loading
EVIDENCE / COMPARISON

Benchmarks

Explore every benchmark

Loading

These charts contain model-linked results. The charts above also include unlinked source profiles. Compare scores within each evaluation. Model quality, usage, transparency and system performance measure different things.

Install TensorTrace