mlsanityData to 7 Oct 2026

CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization

arXiv 2210.13277 ↗First posted 24 Oct 2022cs.LG cs.DC math.OCcited by 11

Not on the map. Why?

Abstract (arXiv)

In distributed optimization, a large number of machines alternate between local computations and communication with a coordinating server. Communication, which can be slow and costly, is the main bottleneck in this setting. To reduce this burden and therefore accelerate distributed gradient descent, two strategies are popular: 1) communicate less frequently; that is, perform several iterations of local computations between the communication rounds; and 2) communicate compressed information instead of full-dimensional vectors. We propose CompressedScaffnew, the first algorithm for distributed optimization that jointly harnesses these two strategies and converges linearly to an exact solution in the strongly convex setting, with a doubly accelerated rate: it benefits from the two acceleration mechanisms provided by local training and compression, namely a better dependency on the condition number of the functions and on the dimension of the model, respectively.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 30 of its 40 references that are in the map. First posted on arXiv 24 Oct 2022.

Builds on

30 of 40 references.

References · 30

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  4. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  5. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  6. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
  7. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  8. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  9. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
  10. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  11. 2020On Biased Compression for Distributed Learningcited by 140
  12. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
18 more
  1. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  2. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  3. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  4. 2019Natural Compression for Distributed Deep Learningcited by 88
  5. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  6. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  7. 2020Variance-Reduced Methods for Machine Learningcited by 79
  8. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  9. 2020Linearly Converging Error Compensated SGDcited by 61
  10. 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
  11. 2020Faster Non-Convex Federated Learning via Global and Local Momentumcited by 48
  12. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  13. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  14. 2019A Double Residual Compression Algorithm for Efficient Distributed Learningcited by 31
  15. 2022RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updatescited by 27
  16. 2021Preserved central model for faster bidirectional compression in distributed settingscited by 21
  17. 2022EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimizationcited by 17
  18. 2021MURANA: A Generic Framework for Stochastic Variance-Reduced Optimizationcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 4; 2024: 4; 2025: 0; 2026: 1.

11 papers.

  1. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  2. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  3. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 7
  4. 2022Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Designcited by 6
  5. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  6. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  7. 2023Explicit Personalization and Local Training: Double Communication Acceleration in Federated Learningcited by 5
  8. 2024FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Modelscited by 5
  9. 2024Communication Efficient ConFederated Learning: An Event-Triggered SAGA Approachcited by 2
  10. 2026BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Trainingcited by 1
  11. 2022An Optimal Algorithm for Strongly Convex Min-min Optimizationcited by 0