mlsanityData to 14 Oct 2026

Correlated Quantization for Faster Nonconvex Distributed Optimization

arXiv 2401.05518 ↗First posted 10 Jan 2024cs.LG cs.AI cs.DCcited by 3

Not on the map. Why?

Abstract (arXiv)

Quantization (Alistarh et al., 2017) is an important (stochastic) compression technique that reduces the volume of transmitted bits during each communication round in distributed model training. Suresh et al. (2022) introduce correlated quantizers and show their advantages over independent counterparts by analyzing distributed SGD communication complexity. We analyze the forefront distributed non-convex optimization algorithm MARINA (Gorbunov et al., 2022) utilizing the proposed correlated quantizers and show that it outperforms the original MARINA and distributed SGD of Suresh et al. (2022) with regard to the communication complexity. We significantly refine the original analysis of MARINA without any additional assumptions using the weighted Hessian variance (Tyurin et al., 2022), and then we expand the theoretical framework of MARINA to accommodate a substantially broader range of potentially correlated and biased compressors, thus dilating the applicability of the method beyond the conventional independent unbiased compressor setup. Extensive experimental results corroborate our theoretical findings.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 29 of its 41 references that are in the map. First posted on arXiv 10 Jan 2024.

Builds on

29 of 41 references.

References · 29

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  4. 2019Advances and Open Problems in Federated Learningcited by 3,046
  5. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  6. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 478
  7. 2014The Loss Surfaces of Multilayer Networkscited by 280
  8. 2018The Convergence of Sparsified Gradient Methodscited by 229
  9. 2020On Biased Compression for Distributed Learningcited by 140
  10. 2016Distributed Mean Estimation with Limited Communicationcited by 136
  11. 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 136
  12. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
17 more
  1. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  2. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  3. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  4. 2019Natural Compression for Distributed Deep Learningcited by 90
  5. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  6. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  7. 2021DRIVE: One-bit Distributed Mean Estimationcited by 52
  8. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  9. 2023A Guide Through the Zoo of Biased SGDcited by 40
  10. 2021Permutation Compressors for Provably Faster Distributed Nonconvex Optimizationcited by 32
  11. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 24
  12. 2019RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimizationcited by 23
  13. 20183LC: Lightweight and Effective Traffic Compression for Distributed Machine Learningcited by 16
  14. 2015SparkNet: Training Deep Networks in Sparkcited by 13
  15. 2022Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Samplingcited by 10
  16. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 8
  17. 2023TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participationcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 3.

3 papers.

  1. 2024A Unified Theory of Stochastic Proximal Point Methods without Smoothnesscited by 4
  2. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 2
  3. 2024MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizescited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2024Truncated Non-Uniform Quantization for Distributed SGD
  2. 2021Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
  3. 2021Unbiased Single-scale and Multi-scale Quantizers for Distributed Optimization
  4. 2022Correlated quantization for distributed mean estimation and optimization
  5. 2024Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance
  6. 2024Quantization Avoids Saddle Points in Distributed Optimization
  7. 2021NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization
  8. 2024Improved Quantization Strategies for Managing Heavy-tailed Gradients in Distributed Learning