Assran et al. (2018) — ARXIV-1811.10792
Key takeaways
This paper proposes Stochastic Gradient Push (SGP), which combines PushSum gossip with SGD to enable decentralized deep learning over directed, sparse, and time-varying communication topologies, and introduces Overlap SGP (OSGP) to hide communication latency by overlapping gradient computation with message passing.
- Theorem 1 and 2. SGP converges to a stationary point at rate (1/K) * sum_k E[||grad f(z_avg_k)||^2] = O(sigma / sqrt(nK) + consensus_error / K) Holds when: Non-convex L-smooth objectives; directed exponential graph with log2(n)-round exact consensus; convergence matches O(1/sqrt(nK)) of AllReduce SGD asymptotically
- Overlap SGP empirical result. 1-OSGP trains ResNet-50 on ImageNet to 77.1% top-1 accuracy in 2.7 hrs on 32 nodes vs 76.2% in 5.1 hrs for AllReduce SGD Holds when: 32 nodes, 10 Gbps Ethernet, bandwidth-limited regime; advantage disappears on high-bandwidth InfiniBand
What the evidence does not cover
- Approximate distributed averaging introduces a consensus error that grows with sparsity of the communication graph, degrading accuracy at scale (observed for 32-node experiments).
- Convergence analysis requires bounded message delays; very long delays can break guarantees.
- Performance degrades on high-bandwidth networks (InfiniBand) where AllReduce is no longer a bottleneck, reducing the advantage of SGP.
Standing in the anthology
Read — the reading is NOTE-151. Arrived in the imported batch, which brought in the decentralized branch, where there is no parameter server and the topology is the hyperparameter.