Data to 7 Oct 2026

Distributed Mean Estimation with Limited Communication

arXiv 1611.00429 ↗First posted 2 Nov 2016cs.LGcited by 134

Not on the map. Why?

Abstract (arXiv)

Motivated by the need for distributed learning and optimization algorithms with low communication cost, we study communication efficient algorithms for distributed mean estimation. Unlike previous works, we make no probabilistic assumptions on the data. We first show that for d dimensional data with n clients, a naive stochastic binary rounding approach yields a mean squared error (MSE) of Theta(d/n) and uses a constant number of bits per dimension per client. We then extend this naive algorithm in two ways: we show that applying a structured random rotation before quantization reduces the error to O((log d)/n) and a better coding strategy further reduces the error to O(1/n) and uses a constant number of bits per dimension per client. We also show that the latter coding strategy is optimal up to a constant in the minimax sense i.e., it achieves the best MSE for a given communication cost. We finally demonstrate the practicality of our algorithms by applying them to distributed Lloyd's algorithm for k-means and power iteration for PCA.

Key facts. Cited by 134 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Nov 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 31; 2022: 29; 2023: 25; 2024: 20; 2025: 13; 2026: 16.

134 papers.

Sort:

By area:

2021A Field Guide to Federated Optimizationcited by 312
2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 127
2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
2021Learning with User-Level Privacycited by 72
2021Pufferfish: Communication-efficient Models At No Extra Costcited by 61
2021Adaptive Quantization of Model Updates for Communication-Efficient Federated Learningcited by 60
2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 53
2021DRIVE: One-bit Distributed Mean Estimationcited by 52
2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learningcited by 39
2025Quartet: Native FP4 Training Can Be Optimal for Large Language Modelscited by 37
2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
2022SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compressioncited by 34

38 more

2021FedJAX: Federated learning simulation with JAXcited by 32
2022Sparse Random Networks for Communication-Efficient Federated Learningcited by 32
2022FedSynth: Gradient Compression via Synthetic Data in Federated Learningcited by 30
2022Federated Learning Under Intermittent Client Availability and Time-Varying Communication Constraintscited by 30
2022FedSpace: An Efficient Federated Learning Framework at Satellites and Ground Stationscited by 28
2021Lossless Compression of Efficient Private Local Randomizerscited by 27
2023DoCoFL: Downlink Compression for Cross-Device Federated Learningcited by 27
2021On the Utility of Gradient Compression in Distributed Training Systemscited by 26
2022TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernelscited by 26
2022Scaling Language Model Size in Cross-Device Federated Learningcited by 25
2023Matrix Compression via Randomized Low Rank and Low Precision Factorizationcited by 25
2021Optimal Compression of Locally Differentially Private Mechanismscited by 22
2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
2024Towards Robust and Efficient Federated Low-Rank Adaptation with Heterogeneous Clientscited by 22
2025QuEST: Stable Training of LLMs with 1-Bit Weights and Activationscited by 21
2024Pushing the Limits of Large Language Model Quantization via the Linearity Theoremcited by 20
2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
2021FedDQ: Communication-Efficient Federated Learning with Descending Quantizationcited by 18
2021Applications of Federated Learning in Smart Cities: Recent Advances, Taxonomy, and Open Challengescited by 17
2026Quartet II: Accurate LLM Pre-Training in NVFP4 by Improved Unbiased Gradient Estimationcited by 16
2021Unified Group Fairness on Federated Learningcited by 15
2021Optimal Rate Adaption in Federated Learning with Compressed Communicationscited by 15
2023THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compressioncited by 15
2024Training Diffusion Models with Federated Learningcited by 15
2022Optimizing the Communication-Accuracy Trade-off in Federated Learning with Rate-Distortion Theorycited by 14
2022FedLite: A Scalable Approach for Federated Learning on Resource-constrained Clientscited by 14
2022Correlated quantization for distributed mean estimation and optimizationcited by 14
2022Adaptive Compression for Communication-Efficient Distributed Trainingcited by 14
2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
2021Communication-Efficient Federated Learning with Binary Neural Networkscited by 13
2022Federated Learning and Meta Learning: Approaches, Applications, and Directionscited by 12
2023BAFFLE: A Baseline of Backpropagation-Free Federated Learningcited by 12
2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
2022Towards Energy-Aware Federated Learning on Battery-Powered Clientscited by 11
2022Exploring Parameter-Efficient Fine-Tuning to Enable Foundation Models in Federated Learningcited by 11
2021Communication-Efficient Agnostic Federated Averagingcited by 10
2021Slashing Communication Traffic in Federated Learning by Transmitting Clustered Model Updatescited by 10
2021A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problemscited by 9

50 most cited of 134 All 134 (JSON)