mlsanityData to 14 Oct 2026

Correlated quantization for distributed mean estimation and optimization

arXiv 2203.04925 ↗First posted 9 Mar 2022cs.LG cs.DS cs.ITcited by 14

Not on the map. Why?

Abstract (arXiv)

We study the problem of distributed mean estimation and optimization under communication constraints. We propose a correlated quantization protocol whose leading term in the error guarantee depends on the mean deviation of data points rather than only their absolute range. The design doesn't need any prior knowledge on the concentration property of the dataset, which is required to get such dependence in previous works. We show that applying the proposed protocol as sub-routine in distributed optimization algorithms leads to better convergence rates. We also prove the optimality of our protocol under mild assumptions. Experimental results show that our proposed algorithm outperforms existing mean estimation protocols on a diverse set of tasks.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 29 of its 39 references that are in the map. First posted on arXiv 9 Mar 2022.

Builds on

29 of 39 references.

References · 29

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  4. 2019Towards Federated Learning at Scale: System Designcited by 832
  5. 2018LEAF: A Benchmark for Federated Settingscited by 792
  6. 2014Convex Optimization: Algorithms and Complexitycited by 575
  7. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  8. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 478
  9. 2018Sparsified SGD with Memorycited by 376
  10. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 256
  11. 2017Sparse Communication for Distributed Gradient Descentcited by 249
  12. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 238
17 more
  1. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 181
  2. 2018Expanding the Reach of Federated Learning by Reducing Client Resource Requirementscited by 163
  3. 2016Distributed Mean Estimation with Limited Communicationcited by 136
  4. 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 136
  5. 2019Communication-efficient distributed SGD with Sketchingcited by 81
  6. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  7. 2021DRIVE: One-bit Distributed Mean Estimationcited by 52
  8. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  9. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  10. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 36
  11. 2021FedJAX: Federated learning simulation with JAXcited by 32
  12. 2021Permutation Compressors for Provably Faster Distributed Nonconvex Optimizationcited by 32
  13. 2014On Communication Cost of Distributed Statistical Estimation and Dimensionalitycited by 24
  14. 2019RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimizationcited by 23
  15. 2020Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithmscited by 17
  16. 20183LC: Lightweight and Effective Traffic Compression for Distributed Machine Learningcited by 16
  17. 2022Optimizing the Communication-Accuracy Trade-off in Federated Learning with Rate-Distortion Theorycited by 14

Built on by

Cited by year (2026 to 14 Oct)

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

14 papers.

Sort:

By area:

  1. 2023Matrix Compression via Randomized Low Rank and Low Precision Factorizationcited by 25
  2. 2024Training Diffusion Models with Federated Learningcited by 15
  3. 2023Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimationcited by 9
  4. 2022QUIC-FL: Quick Unbiased Compression for Federated Learningcited by 7
  5. 2026Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimescited by 6
  6. 2023Private Federated Learning with Autotuned Compressioncited by 5
  7. 2025Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexitycited by 5
  8. 2026Robust Mean Estimation under Quantizationcited by 5
  9. 2026DynamiQ: Accelerating Gradient Synchronization using Compressed Multi-hop All-reducecited by 4
  10. 2023Collaboratively Learning Linear Models with Structured Missing Datacited by 3
  11. 2023Correlation Aware Sparsified Mean Estimation Using Random Projectioncited by 3
  12. 2024CorBin-FL: A Differentially Private Federated Learning Mechanism using Common Randomnesscited by 1
2 more
  1. 2026Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budgetcited by 1
  2. 2026SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuantcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Correlated Quantization for Faster Nonconvex Distributed Optimization
  2. 2024Truncated Non-Uniform Quantization for Distributed SGD
  3. 2022Convergence Theory of Generalized Distributed Subgradient Method with Random Quantization
  4. 2022Quantization for decentralized learning under subspace constraints
  5. 2024Quantization Avoids Saddle Points in Distributed Optimization
  6. 2024Differential error feedback for communication-efficient decentralized learning
  7. 2026Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation
  8. 2022A Fundamental Limit of Distributed Hypothesis Testing Under Memoryless Quantization