Wang and Joshi (2018) — ARXIV-1808.07576
Key takeaways
This paper introduces Cooperative SGD, a unified framework parameterized by (tau, W, v) that subsumes periodic-averaging SGD (PASGD), Elastic Averaging SGD (EASGD), and Decentralized SGD (D-PSGD) as special cases, enabling a single convergence analysis and principled design of new communication- efficient SGD algorithms.
- Theorem 1. After K steps, (1/K) * sum_k E[||grad f(x_avg_k)||^2] <= O(sigma*L / sqrt(mK)) + O(network_error) Holds when: Non-convex L-smooth objectives; network error bounded by a function of tau, zeta, sigma, and L; reduces to standard SGD bound when tau=1 and W=J (full averaging)
- Corollary 1 (PASGD tau bound). PASGD with communication period tau achieves linear speedup when tau = O(sqrt(K/m^3)), relaxing prior O((K/m^3)^{1/4}) bound Holds when: Bounded gradient assumption removed relative to Yu et al. 2018; requires tau small enough that network error is dominated by O(sigma/sqrt(mK)) term
- Lemma 1 (optimal EASGD alpha). Optimal elasticity parameter for EASGD is alpha* = 2/(m+2), minimizing the second-largest eigenvalue zeta of the EASGD mixing matrix Holds when: m workers, v=1 auxiliary variable; closed-form derivation of eigenvalues of W_alpha
What the evidence does not cover
- Analysis assumes doubly-stochastic mixing matrices, restricting to symmetric (undirected) communication topologies.
- The network error bound is an upper bound; actual error floors may be considerably lower, limiting the precision of comparisons between algorithms.
- Non-i.i.d. data distributions are not addressed; convergence results assume identical or bounded data heterogeneity.
- The framework does not cover gradient compression or quantization techniques.
Standing in the anthology
Read — the reading is NOTE-127. Arrived in the imported batch, which brought in the local-update branch — train apart for H steps, then average.