# EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 82 references that are in the map.
- First posted on arXiv 19 Aug 2021.

## Builds on (most cited first, 30 of 36)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Measuring the Intrinsic Dimension of Objective Landscapes](https://mlsanity.com/paper/1804.08838/) (2018)
- [Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edge](https://mlsanity.com/paper/1804.08333/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Expanding the Reach of Federated Learning by Reducing Client Resource Requirements](https://mlsanity.com/paper/1812.07210/) (2018)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Communication-efficient distributed SGD with Sketching](https://mlsanity.com/paper/1903.04488/) (2019)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [From Local SGD to Local Fixed-Point Methods for Federated Learning](https://mlsanity.com/paper/2004.01442/) (2020)
- [Scaling Distributed Machine Learning with In-Network Aggregation](https://mlsanity.com/paper/1903.06701/) (2019)

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

- [Heterogeneous Federated Learning: State-of-the-art and Research Challenges](https://mlsanity.com/paper/2307.10616/) (2023)
- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [Quartet: Native FP4 Training Can Be Optimal for Large Language Models](https://mlsanity.com/paper/2505.14669/) (2025)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [QuEST: Stable Training of LLMs with 1-Bit Weights and Activations](https://mlsanity.com/paper/2502.05003/) (2025)
- [Pushing the Limits of Large Language Model Quantization via the Linearity Theorem](https://mlsanity.com/paper/2411.17525/) (2024)
- [Quartet II: Accurate LLM Pre-Training in NVFP4 by Improved Unbiased Gradient Estimation](https://mlsanity.com/paper/2601.22813/) (2026)
- [THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression](https://mlsanity.com/paper/2302.08545/) (2023)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [ScionFL: Efficient and Robust Secure Quantized Aggregation](https://mlsanity.com/paper/2210.07376/) (2022)
- [A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Work](https://mlsanity.com/paper/2604.18555/) (2026)
- [Provable Quantization with Randomized Hadamard Transform](https://mlsanity.com/paper/2605.13810/) (2026)
- [SDR: Efficient Neural Re-ranking using Succinct Document Representation](https://mlsanity.com/paper/2110.02065/) (2021)
- [QUIC-FL: Quick Unbiased Compression for Federated Learning](https://mlsanity.com/paper/2205.13341/) (2022)
- [GlueFL: Reconciling Client Sampling and Model Masking for Bandwidth Efficient Federated Learning](https://mlsanity.com/paper/2212.01523/) (2022)
- [High-Rate Quantized Matrix Multiplication I](https://mlsanity.com/paper/2601.17187/) (2026)
- [Communication-Efficient Design for Quantized Decentralized Federated Learning](https://mlsanity.com/paper/2303.08423/) (2023)
- [Adaptive Compression in Federated Learning via Side Information](https://mlsanity.com/paper/2306.12625/) (2023)
- [LASER: Linear Compression in Wireless Distributed Optimization](https://mlsanity.com/paper/2310.13033/) (2023)
- [Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression](https://mlsanity.com/paper/2407.01378/) (2024)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven](https://mlsanity.com/paper/2605.06014/) (2026)
- [Blockchain-empowered Federated Learning: Benefits, Challenges, and Solutions](https://mlsanity.com/paper/2403.00873/) (2024)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Masked Random Noise for Communication Efficient Federated Learning](https://mlsanity.com/paper/2408.03220/) (2024)
- [DynamiQ: Accelerating Gradient Synchronization using Compressed Multi-hop All-reduce](https://mlsanity.com/paper/2602.08923/) (2026)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)

## Abstract (arXiv)

Distributed Mean Estimation (DME) is a central building block in federated learning, where clients send local gradients to a parameter server for averaging and updating the model. Due to communication constraints, clients often use lossy compression techniques to compress the gradients, resulting in estimation inaccuracies. DME is more challenging when clients have diverse network conditions, such as constrained communication budgets and packet losses. In such settings, DME techniques often incur a significant increase in the estimation error leading to degraded learning performance. In this work, we propose a robust DME technique named EDEN that naturally handles heterogeneous communication budgets and packet losses. We derive appealing theoretical guarantees for EDEN and evaluate it empirically. Our results demonstrate that EDEN consistently improves over state-of-the-art DME techniques.