Contribution
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.
Key insight
All major communication-efficient SGD algorithms differ only in how they trade off three communication-reduction strategies—periodic averaging (tau), mixing matrix sparsity (W), and auxiliary variables (v)—and a single unified bound on the “network error” captures all three, enabling direct comparison and new hybrid designs.
Assumptions
- L-smooth objective: each component f_i has L-Lipschitz gradients
- Bounded stochastic gradient variance: E[||g_i - grad f_i(x)||^2] <= sigma
- Doubly stochastic mixing matrix W (restricts to undirected/symmetric topologies)
- Second-largest absolute eigenvalue zeta of W governs consensus speed; zeta < 1 required
- IID or bounded heterogeneity data across workers (non-IID degrades convergence via network error term)
Key results
- 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
Claims
| id | claim | strength | support |
|---|---|---|---|
| C1 | PASGD, EASGD, and D-PSGD are all special cases of Cooperative SGD A(tau, W, v), recoverable by specific parameter choices. | strong | Algebraic derivation showing each algorithm’s update rule matches the general Cooperative SGD update for appropriate tau, W, v. |
| C2 | The error floor at convergence is determined by a ‘network error’ term that monotonically increases with the communication period tau and the second-largest absolute eigenvalue zeta of the mixing matrix. | strong | Theorem 1 convergence bound with explicit decomposition into fully-synchronous SGD error plus network error; validated empirically on CIFAR-10 with VGG-16. |
| C3 | The optimal elasticity parameter for EASGD is alpha = 2/(m+2), minimizing zeta and hence the error floor. | strong | Lemma 1 with closed-form derivation of eigenvalues of the EASGD mixing matrix; first theoretical justification for a best alpha choice. |
| C4 | For PASGD, the bound on tau can be relaxed to O(sqrt(K/m^3)) compared to the O((K/m^3)^{1/4}) in prior work, by removing the bounded-gradient assumption. | strong | Corollary 1 proof in Appendix; directly compared to Yu et al. 2018 which required bounded gradients. |
Method
Cooperative SGD A(tau, W, v).
Cooperative SGD maintains a joint state matrix X_k consisting of m worker model vectors and v auxiliary variable vectors. At each iteration, workers apply a local SGD gradient step, then at multiples of the communication period tau, a mixing step X_{k+1} = (X_k - eta*G_k) * W_k is applied where W_k equals the mixing matrix W at synchronization steps and identity otherwise. Auxiliary variables (v > 0) do not compute gradients and participate only in the averaging step, enabling non-blocking execution where their updates can overlap worker computation. The framework recovers PASGD (W=J, v=0), EASGD (W=W_alpha, v=1), and D-PSGD (W=sparse, tau=1, v=0) as special cases.
- Mixing matrix W encoding communication topology and consensus weights
- Communication period tau controlling frequency of synchronization
- Auxiliary variables v that participate in averaging but not gradient computation
- Second-largest absolute eigenvalue zeta of W as the key quantity governing network error
- Effective learning rate eta_eff = eta * m/(m+v) adjusted for auxiliary variables
Concepts
- Network error — The convergence error term arising from local model discrepancies due to infrequent or partial synchronization; bounded by a function of tau and zeta.
- Mixing matrix — Doubly-stochastic matrix W encoding the averaging weights between workers; its second-largest absolute eigenvalue zeta controls consensus speed.
- Cooperative SGD A(tau, W, v) — General parameterized framework for communication-efficient SGD where tau is the communication period, W is the mixing matrix, and v is the number of auxiliary variables.
- Non-blocking execution — Auxiliary variables broadcast their updates while workers compute local gradients, hiding communication latency by overlapping the two operations.
- Decentralized periodic averaging — New algorithm combining D-PSGD (sparse W) with periodic averaging (tau > 1) to balance convergence quality and communication efficiency.
Connections
Builds on.
- Can Decentralized Algorithms Outperform Centralized Algorithms? (LIT- tmphrzo0) — Subsumes D-PSGD as A(1, W, 0) and provides a unified proof; recovers the same convergence bound as Lian et al. 2017.
- Deep learning with Elastic Averaging SGD (LIT-370) — Subsumes EASGD as A(1, W_alpha, 1) and provides the first convergence analysis for EASGD on general nonconvex objectives, plus derives the optimal alpha.
Recommendations
- R1 — Set alpha = 2/(m+2) for EASGD to minimize the second-largest eigenvalue of the mixing matrix and thus minimize the error floor. Topic: EASGD hyperparameter tuning · Strength: strong · When: When using EASGD with m workers and a single auxiliary variable.
- R2 — Use decentralized periodic averaging A(tau, W, 0) with moderate tau and a sparse mixing matrix when workers are many: it combines the throughput benefits of periodic averaging with the communication reduction of D-PSGD. Topic: algorithm design for large-scale training · Strength: moderate · When: Large number of workers with fixed sparse inter-connection topology.
- R3 — Add an auxiliary variable (v=1) connected to all workers when using a sparse mixing matrix to reduce zeta and lower the convergence error floor without increasing wall-clock time. Topic: generalized elastic averaging · Strength: moderate · When: Sparse D-PSGD setting where convergence quality is poor due to large zeta.
Bearing on the record
The framework that makes local SGD, elastic averaging and decentralized SGD comparable in one set of terms. It bears on the record as the thing that would let a practice about communication frequency say why its number is the right one rather than reporting it.
Limitations
- 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.
Open questions
- What is the optimal joint choice of tau, W, and v for a given bandwidth constraint and number of workers?
- Can the framework be extended to directed graphs (column-stochastic rather than doubly-stochastic mixing) to cover algorithms like SGP?
- How do the new hybrid algorithms (decentralized periodic averaging, generalized elastic averaging) perform empirically at large scale?