Stich (2018) — ARXIV-1805.09767
Key takeaways
Provides the first rigorous convergence proof showing that local SGD achieves linear speedup in the number of workers K on strongly convex objectives, matching mini-batch SGD in gradient evaluations while reducing communication rounds by up to O(T
- Theorem 1 (Synchronous Local SGD). After T steps with K workers and synchronization interval H = O(sqrt(T/(Kb))), local SGD converges at rate O(1/(KTb)), matching mini-batch SGD. Holds when: Strongly convex, L-smooth objectives; bounded gradients; H = O(sqrt(T/(Kb))).
- Communication Reduction Corollary. Communication rounds can be reduced by a factor of up to O(sqrt(T)) relative to mini-batch SGD with no asymptotic loss in convergence rate. Holds when: Same conditions as Theorem 1; requires T large enough for the bound to be tight.
- Theorem 2 (Asynchronous Local SGD). Asynchronous local SGD achieves the same O(1/(KTb)) rate when the combined constraint H + tau = O(sqrt(T/K)) is satisfied, where tau is the maximum delay. Holds when: Strongly convex, L-smooth objectives; asynchronous delay tau bounded uniformly.
What the evidence does not cover
- Convergence proof restricted to strongly convex objectives; non-convex guarantees were not established in this paper.
- Bounded gradient assumption (||gradient|| <= G) may not hold in practice for deep neural networks.
- Analysis becomes loose for extreme settings (one-shot averaging H=T); one- shot SGD is not covered.
- Asymptotic bounds may be too conservative to predict optimal H for short training runs or large clusters.
Standing in the anthology
Read — the reading is NOTE-133. Arrived in the imported batch, which brought in the local-update branch — train apart for H steps, then average.