Ryabinin et al. (2021) — ARXIV-2103.03239
Key takeaways
Moshpit SGD introduces Moshpit All-Reduce, a fully decentralized averaging protocol that dynamically organizes unreliable workers into small groups via a DHT-based matchmaking algorithm and runs standard all-reduce within each group, achieving exponential convergence to the global average without dependence on communication graph topology.
- Theorem 3.2 — Moshpit All-Reduce averaging convergence. After K rounds of Moshpit All-Reduce, the per-peer deviation from the global mean decreases exponentially: E[||x_i - x_bar||^2] <= (1 - rho)^K * initial_deviation, where rho depends on minimum group size and grid fill rate, not on any graph spectral gap. Holds when: Requires grid fill rate above a threshold; convergence rate rho degrades gracefully as nodes drop out.
- Equations 11-12 — Moshpit SGD iteration complexity. For smooth non- convex objectives, Moshpit SGD achieves O(1/sqrt(nT)) convergence (matching centralized Local-SGD) when averaging error per round is bounded by a quantity that decreases with group size M. Holds when: n workers, T total iterations, local steps tau; assumes peer dropout rate < 50% and bounded gradient variance.
- Empirical speedup over SGP (C3). 1.3x wall-clock speedup over Stochastic Gradient Push on 81 GPUs for ResNet-50/ImageNet to 75% top-1 accuracy. Holds when: 64 heterogeneous servers, 1Gb/s Ethernet, heterogeneous hardware configurations.
What the evidence does not cover
- When fewer than half the grid positions are filled, Moshpit’s advantage over random group averaging diminishes; the grid structure provides benefit primarily at high utilization.
- Each averaging round requires O(log N) DHT operations for matchmaking, adding latency overhead compared to static all-reduce topologies.
- Pseudo-gradient recovery for adaptive optimizers is a heuristic; theoretical convergence guarantees with this trick are not established in the paper.
- Convergence bounds assume peer dropout and averaging error satisfy specific magnitude conditions; these may not hold with very high failure rates or very heterogeneous hardware.
Standing in the anthology
Read — the reading is NOTE-089. Arrived in the imported batch, which brought in the volunteer- and internet-scale branch, where workers join and leave.