Source-linked AI summary
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
Anastasia Koloskova, Sebastian U. Stich, Martin Jaggi
TL;DR
Decentralized learning seeks scalable, privacy-preserving optimization without a central coordinator, while communication compression introduces accuracy and convergence challenges. The paper proposes compressed gossip algorithms for optimization and consensus, showing centralized-like leading convergence behavior, linear consensus convergence, and strong experimental performance.
Problem
Decentralized optimization needs to reduce communication bottlenecks while supporting low-accuracy and biased compression operators.
Method
The paper introduces Choco-SGD for decentralized stochastic optimization and Choco-Gossip for compressed distributed average consensus.
Results
Choco-SGD converges at O(1/(nT) + 1/(Tδ^2ω)^2), while Choco-Gossip converges linearly in O(1/(δ^2ω) log(1/ε)); experiments show Choco-SGD significantly outperforms ECD-SGD and DCD-SGD.
Takeaways & Limitations
Choco-SGD matches centralized mini-batch SGD in iteration efficiency while avoiding centralized communication bottlenecks and can reduce communication by a factor of 100.
Takeaways & Limitations
The analysis assumes a symmetric doubly stochastic gossip matrix, and prior quantized gossip methods may converge only to a neighborhood rather than the optimum.
Abstract
from arXiv · showhide
We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning task) being distributed over $n$ machines that can only communicate to their neighbors on a fixed communication graph. To reduce the communication bottleneck, the nodes compress (e.g. quantize or sparsify) their model updates. We cover both unbiased and biased compression operators with quality denoted by $ω\leq 1$ ($ω=1$ meaning no compression). We (i) propose a novel gossip-based stochastic gradient descent algorithm, CHOCO-SGD, that converges at rate $\mathcal{O}\left(1/(nT) + 1/(T δ^2 ω)^2\right)$ for strongly convex objectives, where $T$ denotes the number of iterations and $δ$ the eigengap of the connectivity matrix. Despite compression quality and network connectivity affecting the higher order terms, the first term in the rate, $\mathcal{O}(1/(nT))$, is the same as for the centralized baseline with exact communication. We (ii) present a novel gossip algorithm, CHOCO-GOSSIP, for the average consensus problem that converges in time $\mathcal{O}(1/(δ^2ω) \log (1/ε))$ for accuracy $ε> 0$. This is (up to our knowledge) the first gossip algorithm that supports arbitrary compressed messages for $ω> 0$ and still exhibits linear convergence. We (iii) show in experiments that both of our algorithms do outperform the respective state-of-the-art baselines and CHOCO-SGD can reduce communication by at least two orders of magnitudes.
1 Introduction
The paper develops decentralized stochastic optimization and compressed gossip methods for distributed data and local-neighbor communication, targeting scalability without a central coordinator. Choco-SGD preserves the centralized iteration-rate term while supporting compressed communication, and experiments report strong performance and substantial communication reduction.
- Problem setting: Decentralized optimization distributes local objectives across n devices and permits stochastic structures such as empirical risk minimization.The setting uses on-device computation and communication only with neighboring devices.
- Problem setting: Centralized topologies can create communication, bandwidth, latency, and fault-tolerance bottlenecks, whereas decentralized networks can have constant or slowly growing maximum degree.A centralized master exchanges Θ(n) messages per round, while ring or torus networks can keep degree constant.
- Choco-SGD: O(1/(nT)) convergence is achieved for strongly convex decentralized stochastic optimization, matching the leading iteration-rate term of centralized mini-batch SGD.The result concerns stochastic gradient descent and ignores higher-order terms.
- Choco-SGD: Choco-SGD supports unbiased and biased compression, addressing prior analyses limited to unbiased operators with very high accuracy constraints.Compression can use quantization or sparsification, and the quality factor satisfies ω ≤ 1 with ω = 1 denoting no compression.
- Choco-SGD: O(1/(nT) + 1/(Tδ^2ω)^2) is the reported Choco-SGD rate, with topology and compression affecting higher-order terms.The rate uses T iterations, n workers, δ as the gossip-matrix eigengap, and ω as compression quality.
- Empirical results: Experiments report that Choco-SGD outperforms ECD-SGD and DCD-SGD and reduces communication by a factor of 100 on a ring topology.The conclusion also reports performance almost matching the exact algorithm without communication restrictions.
2 Related Work
Related work spans centralized and decentralized stochastic optimization, gradient compression, and average consensus. The paper distinguishes its approach by supporting arbitrary compressed communication while retaining linear convergence to the true consensus solution.
- Decentralized optimization: Mini-batch SGD is the centralized parallel baseline in which a master collects updates from all worker nodes.Serial SGD does not inherently account for distributed settings.
- Decentralized optimization: Prior decentralized stochastic analyses assumed equal data distributions across nodes, restricting their applicability to many distributed settings.The cited restriction is described as strong because it excludes most distributed machine-learning applications.
- Gradient compression: Gradient compression transmits Q(g) instead of a full gradient vector, using representations such as quantization or sparsification.The paper discusses unbiased quantization, random sparsification, and methods that maintain additional states.
- Average consensus: Standard gossip with compressed communication may fail to converge to the correct average, while adaptive schemes can revert to full communication at high accuracy.The paper positions its method as avoiding adaptive accuracy while converging linearly to the true solution.
- Average consensus: The paper presents a gossip method that converges linearly to the true consensus solution under arbitrary compressed communication without adaptive accuracy.It claims no known literature method with similar guarantees.
3 Average Consensus with Communication Compression
Choco-Gossip is introduced as a compressed-communication gossip method for average consensus, designed to preserve averages and eliminate compression noise while converging linearly for arbitrary compression quality.
- Proposed method: Choco-Gossip is proposed as a gossip algorithm for distributed average consensus with compressed communication.The average consensus problem is also described as an important special case of the broader decentralized optimization problem.
- Gossip algorithms: The network is modeled by a symmetric doubly stochastic gossip matrix W whose spectral gap δ governs connectivity and convergence.The matrix has eigenvalue magnitude ordering 1 = |λ1(W)| > |λ2(W)| ≥ ··· ≥ |λn(W)|, with δ defined as the spectral gap.
- Gossip algorithms: Classical exact gossip converges linearly to the average, but each communication round exchanges full-dimensional vectors across graph links.Compression replaces each transmitted vector with Q(g), such as a sparsified or quantized representation, to reduce communication.
- Existing compressed gossip: Directly compressing gossip messages can fail to preserve the average and may prevent convergence to the optimal consensus solution.Other schemes preserve the average but can leave nonvanishing compression noise, causing iterates to oscillate around the average.
- Proposed method: Choco-Gossip uses auxiliary stored variables and a compression-dependent stepsize to control communication noise while preserving the iterates' average.The proposed scheme stores local and neighbor-related variables; its compression operator satisfies a quality condition with parameter ω > 0.
4 Decentralized Stochastic Optimization
The section develops decentralized stochastic optimization for heterogeneous local objectives under neighbor-only communication, introducing CHOCO-SGD with compressed gossip updates. Its analysis recovers centralized mini-batch behavior in the leading term while topology and compression affect higher-order terms.
- Problem setting: The framework allows each node to have a distinct stochastic local objective, including stochastic optimization and empirical risk minimization with different data distributions.The local distributions may be identical for stochastic optimization or discrete with disjoint support for machine-learning risk minimization.
- Proposed method: CHOCO-SGD—Communication-Compressed Decentralized SGD—is the proposed method for decentralized optimization.The algorithm uses stochastic gradient steps, compression, local Choco-G communication, and a final iterate update.
- Proposed method: The algorithm operates over a communication graph with mixing matrix W, consensus stepsize γ, SGD stepsizes {η_t}, and initialized node models.Workers compute gradients in parallel and communicate with neighboring nodes.
- Convergence analysis: Under smoothness, strong convexity, and bounded worker-level variance, Theorem 4 establishes convergence for suitable SGD and consensus stepsizes.The stated conditions include L-smoothness, µ-strong convexity, and bounded variance on each worker.
- Convergence analysis: O(1/(nT)) is recovered as the leading convergence term, matching centralized mini-batch SGD with exact communication, while δ and ω affect higher-order terms.Here δ is the eigengap of W and ω is the compression ratio; the setting also yields an n× speedup over serial SGD on one worker.
5 Experiments
The experiments evaluate Choco-Gossip and Choco-SGD against compressed-communication baselines across consensus and decentralized optimization settings. Choco-Gossip converges robustly under quantization and sparsification, while Choco-SGD approaches exact-communication performance with substantially lower communication cost.
- Experimental Setup: The experiments report both iteration counts and transmitted bits, using epsilon and rcv1 datasets for the decentralized optimization evaluation.These quantities are intended to be independent of system architecture and network bandwidth.
- Average Consensus: Choco-Gossip with qsgd256 converges at the same rate as exact communication while transmitting much less data.Q1-G and Q2-G fail to converge beyond accuracies of 10^-4–10^-5 in this setting.
- Average Consensus: With rand1% sparsification, Choco-Gossip converges while Q1-G zeros coordinates and Q2-G diverges.The observed iteration rate is about 100× slower than exact communication, but total transmitted data reaches convergence at the same speed; rand1% is most data-efficient.
- Decentralized SGD: Figure 4 evaluates exact-communication Algorithm 3 on ring, torus, and fully connected topologies with n = 9, 25, and 64 nodes.Increasing the worker count shows a mild effect of network topology on convergence, while sorted data is harder than randomly shuffled data.
- Decentralized SGD: Choco-SGD performs nearly as well as exact Algorithm 3 while using 100× less communication with rand1% and approximately 15× less with qsgd4.The top1% variant performs slightly better than rand1% sparsification.
- Decentralized SGD: Choco-SGD consistently outperforms DCD-SGD, whereas ECD-SGD often performs worse than DCD-SGD and often diverges.DCD-SGD improves with larger qsgds level counts, but this increases communication cost.
A Basic Identities and Inequalities
This section defines the smoothness, convexity, variance, matrix, and gossip-network notation used to analyze compressed decentralized algorithms. It also expresses Choco-Gossip in matrix form.
- Function properties: Strong convexity and smoothness provide the function properties used in the convergence analysis.The supplied passages introduce definitions and related remarks for differentiable objectives, though the defining inequalities are truncated.
- Stochastic gradients: Independent worker randomness makes cross-worker stochastic-gradient inner products have zero expectation.This follows from independence between ξ_i and ξ_j for distinct workers.
- Matrix formulation: Choco-Gossip updates compressed disagreement through Q(t) = Q(X(t) − ˆX(t)), then mixes the stored estimates with W − I.The matrix algorithm preserves the stored-message structure across neighboring workers.
- Network notation: The gossip matrix W is symmetric and doubly stochastic, with eigengap δ = 1 − |λ2(W)| governing connectivity.Its stochastic structure gives the consensus direction as the first eigenvector and preserves averages.
C Proof of Theorem 2—Convergence of Choco-Gossip
The proof establishes Choco-Gossip convergence by tracking average preservation and disagreement under compressed updates. A parameter choice yields a contraction controlled by the eigengap and compression quality.
- Error decomposition: The analysis separates consensus error and compression error through coupled bounds on X(t) and ˆX(t).Lemmas 17 and 18 provide the two components used in the theorem proof.
- Average preservation: Choco-Gossip preserves the average of the iterates because the mixing matrix W is doubly stochastic.The proof explicitly uses X(W − I) = 0 to show that the average remains unchanged.
- Contraction bound: 1 − δ^2ω^2 / [2(16δ + δ^2 + 4β^2 + 2δβ^2 − 8δω)] bounds the selected contraction factor.The bound follows after choosing parameters and a stepsize to control the maximum of the two error factors.
- Parameter bounds: The final simplification uses 0 ≤ δ ≤ 1, β ≤ 2, and ω ≥ 0 to obtain a coarser contraction estimate.Here β is the largest value of 1 − λ_i(W), while δ is the eigengap.
D Proof of Theorem 4—Convergence of Choco-SGD
The Choco-SGD proof is generalized to decentralized SGD using an arbitrary averaging scheme, then instantiated with compressed consensus. The averaging scheme must preserve means and converge linearly.
- Generalized algorithm: Algorithm 4 replaces a fixed gossip routine with a blackbox averaging scheme h, which may be random.The proof analyzes decentralized SGD for this broader class before specializing to Choco-Gossip.
- Averaging assumptions: The averaging scheme preserves the average of the first iterate and contracts a potential at linear rate 1 − p.These are the two conditions imposed by Assumption 3.
- Choco-Gossip instantiation: For Choco-Gossip, the averaging parameter is p = ωδ^2 / 8^2, linking convergence to compression quality and the mixing-matrix eigengap.The supplied passage identifies ω as the compression ratio and δ as the eigengap.
- Convergence theorem: Theorem 19 applies decreasing stepsizes η_t = 4/[μ(a + t)] to establish convergence for the generalized decentralized SGD scheme.The theorem assumes a parameter a large enough relative to μ and the averaging rate.
- Specialization: The proof of Theorem 4 combines Theorem 19 with the Choco-Gossip averaging rate and a bound on the initial distance to the optimum.This transfers the blackbox averaging result to the compressed consensus algorithm.
D.1 Proof of Theorem 19
Theorem 19 is proved by combining recursive bounds for averaging and optimization errors with a decreasing-stepsize argument. The resulting estimates depend explicitly on the averaging convergence parameter p.
- Theorem setup: Theorem 19 analyzes decentralized SGD under a blackbox averaging scheme with convergence parameter p.The proof uses the assumption that averaging preserves the mean and contracts a potential linearly.
- Average-iterate bound: The proof bounds the average iterates through a recursion involving the averaging rate p and stochastic-gradient terms.Lemma 20 provides the bound used before applying the sequence estimates.
- Auxiliary recursion: The auxiliary recursion is controlled with stepsize η_t = b/(t + a), requiring a ≥ 5/p and b > 0.Lemma 22 supplies the sequence bound used in the main proof.
- Optimization estimate: The optimization proof uses η_t = 4/[μ(a + t)] together with smoothness and strong-convexity stepsize conditions.The argument invokes a bound ensuring η_t ≤ 1/(4L).
- Final bound: The final theorem combines the recursive bounds, variance term σ^2, and averaging parameter p to obtain the stated convergence estimate.The conclusion uses polynomial-sum bounds and convexity of f.
E Efficient Implementation of the Algorithms
The paper gives memory-efficient implementations of Choco-Gossip and Choco-SGD, with each node storing three vectors and using graph and mixing-matrix inputs. The algorithms are presented as parallel worker procedures over communication-graph neighbors.
- Three vectors—x, x̂_i, and s_i—are stored at each node in the memory-efficient implementations.
- Algorithm 5 is the memory-efficient Choco-Gossip procedure for initial values on nodes, a consensus stepsize, a graph, and a mixing matrix.
- Algorithm 6 is the memory-efficient Choco-SGD procedure for initial values on nodes, a stepsize, a graph, and a mixing matrix.
- Both procedures iterate in parallel over workers and process communication with graph neighbors, including self-edges.
F Parameters Search Details of SGD Experiments
SGD experiment parameters were tuned in stages: consensus stepsizes were calibrated on matching average-consensus problems, while algorithm-specific parameters were selected using short runs and grid search.
- The consensus stepsize γ was tuned on a separate average-consensus problem matching topology, node count, quantization, and dimension.
- Parameters a and b were tuned separately for each algorithm by running it for 10 epochs and performing independent grid searches for each quantization function.
- The search used logarithmic powers of 10 for a and the set {1, 0.1d, d, 10d, 100d} for b.
G Additional Experiments
Additional experiments report parameter settings for SGD and compare Algorithm 3 with decentralized baselines across several topologies, datasets, compression schemes, iteration counts, and communication costs.
- Table 5 lists initial and consensus learning rates used in the SGD experiments, with γ obtained by tuning average consensus under the same configuration.
- Figure 7 evaluates Algorithm 3 on ring, torus, and fully connected topologies with n ∈{9, 25, 64} nodes.
- Figure 8 compares Algorithm 3, ECD-SGD, DCD-SGD, and sparsified Choco-SGD on epsilon and rcv1 using iterations and communication cost.
- Figure 9 compares the same algorithms on epsilon and rcv1 with qsgd16 quantization using iterations and communication cost.