mlsanityData to 7 Oct 2026

On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks

arXiv 2204.08160 ↗First posted 18 Apr 2022math.OC cs.LG cs.MAcited by 1

Not on the map. Why?

Abstract (arXiv)

We study the decentralized consensus and stochastic optimization problems with compressed communications over static directed graphs. We propose an iterative gradient-based algorithm that compresses messages according to a desired compression ratio. The proposed method provably reduces the communication overhead on the network at every communication round. Contrary to existing literature, we allow for arbitrary compression ratios in the communicated messages. We show a linear convergence rate for the proposed method on the consensus problem. Moreover, we provide explicit convergence rates for decentralized stochastic optimization problems on smooth functions that are either (i) strongly convex, (ii) convex, or (iii) non-convex. Finally, we provide numerical experiments to illustrate convergence under arbitrary compression ratios and the communication efficiency of our algorithm.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 21 of its 36 references that are in the map. First posted on arXiv 18 Apr 2022.

Builds on

21 of 36 references.

References · 21

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2020Adaptive Federated Optimizationcited by 1,036
  3. 2018Sparsified SGD with Memorycited by 373
  4. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 218
  5. 2015Federated Optimization:Distributed Optimization Beyond the Datacentercited by 193
  6. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  7. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  8. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  9. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  10. 2020On Biased Compression for Distributed Learningcited by 140
  11. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 109
  12. 2020A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!cited by 41
9 more
  1. 2018An Exact Quantized Decentralized Gradient Descent Algorithmcited by 34
  2. 2014Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphscited by 31
  3. 2018A Dual Approach for Optimal Algorithms in Distributed Optimization over Networkscited by 27
  4. 2020Quantized Decentralized Stochastic Learning over Directed Graphscited by 24
  5. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  6. 2021Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergencecited by 12
  7. 2014Nonasymptotic Convergence Rates for Cooperative Learning Over Time-Varying Directed Graphscited by 5
  8. 2021Communication-efficient Distributed Cooperative Learning with Compressed Beliefscited by 4
  9. 2021Scalable Average Consensus with Compressed Communicationscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023D-SVM over Networked Systems with Non-Ideal Linking Conditionscited by 0