Papers › Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

1 Feb 2019arXiv:1902.00340archive 2025-07-28

Anastasia Koloskova, Sebastian U. Stich, Martin Jaggi

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 ω≤1 (ω=1 meaning no compression). We (i) propose a novel gossip-based stochastic gradient descent algorithm, CHOCO-SGD, that converges at rate 𝒪(1/(nT) + 1/(T δ² ω)²) 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, 𝒪(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 𝒪(1/(δ²ω) 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.

PaperPDFCode

In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.

Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

For agents, on Syntology's MCP service (how to connect):

Code

Adirlou/OptML_Project mentioned on GitHubSyntology: not harvested report
JYWa/MATCHA mentioned on GitHubpytorchSyntology: not harvested report
epfml/ChocoSGD mentioned on GitHubpytorchApache-2.0Syntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Decentralized Deep Learning with Arbitrary Communication Compression (arXiv:1907.09356; that paper's own run record: 5 ran (of which 0 constructed an object rather than computing a result; 5 with no instrument failure: 0 honoured, 1 violated, 4 with no contract checked; 0 where Syntology's instrument failed) · 0 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Stochastic Optimization

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections