# Randomized Distributed Mean Estimation: Accuracy vs Communication

arXiv: https://arxiv.org/abs/1611.07555 · HTML: https://mlsanity.com/paper/1611.07555/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2016.

## Built on by (most cited first, 30 of 39)

- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Pufferfish: Communication-efficient Models At No Extra Cost](https://mlsanity.com/paper/2103.03936/) (2021)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [Federated Learning Under Intermittent Client Availability and Time-Varying Communication Constraints](https://mlsanity.com/paper/2205.06730/) (2022)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [Adaptive Compression for Communication-Efficient Distributed Training](https://mlsanity.com/paper/2211.00188/) (2022)
- [THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression](https://mlsanity.com/paper/2302.08545/) (2023)
- [Communication-Efficient Federated Learning with Binary Neural Networks](https://mlsanity.com/paper/2110.02226/) (2021)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning](https://mlsanity.com/paper/2104.06685/) (2021)
- [Slashing Communication Traffic in Federated Learning by Transmitting Clustered Model Updates](https://mlsanity.com/paper/2105.04153/) (2021)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques](https://mlsanity.com/paper/2106.03524/) (2021)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [SacFL: Self-Adaptive Federated Continual Learning for Resource-Constrained End Devices](https://mlsanity.com/paper/2505.00365/) (2025)
- [SDR: Efficient Neural Re-ranking using Succinct Document Representation](https://mlsanity.com/paper/2110.02065/) (2021)
- [Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation](https://mlsanity.com/paper/2110.07751/) (2021)
- [QUIC-FL: Quick Unbiased Compression for Federated Learning](https://mlsanity.com/paper/2205.13341/) (2022)
- [Shifted Compression Framework: Generalizations and Improvements](https://mlsanity.com/paper/2206.10452/) (2022)
- [Personalized Federated Learning with Communication Compression](https://mlsanity.com/paper/2209.05148/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Bristle: Decentralized Federated Learning in Byzantine, Non-i.i.d. Environments](https://mlsanity.com/paper/2110.11006/) (2021)
- [A Unified Theory of Stochastic Proximal Point Methods without Smoothness](https://mlsanity.com/paper/2405.15941/) (2024)
- [Wyner-Ziv Gradient Compression for Federated Learning](https://mlsanity.com/paper/2111.08277/) (2021)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [FedDIP: Federated Learning with Extreme Dynamic Pruning and Incremental Regularization](https://mlsanity.com/paper/2309.06805/) (2023)

## Abstract (arXiv)

We consider the problem of estimating the arithmetic average of a finite collection of real vectors stored in a distributed fashion across several compute nodes subject to a communication budget constraint. Our analysis does not rely on any statistical assumptions about the source of the vectors. This problem arises as a subproblem in many applications, including reduce-all operations within algorithms for distributed and federated optimization and learning. We propose a flexible family of randomized algorithms exploring the trade-off between expected communication cost and estimation error. Our family contains the full-communication and zero-error method on one extreme, and an ε-bit communication and cal Oleft(1/(ε n)right) error method on the opposite extreme. In the special case where we communicate, in expectation, a single bit per coordinate of each vector, we improve upon existing results by obtaining O(r/n) error, where r is the number of bits used to represent a floating point value.