# Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2015.

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

- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Communication-Efficient Federated Learning with Binary Neural Networks](https://mlsanity.com/paper/2110.02226/) (2021)
- [Correlated quantization for distributed mean estimation and optimization](https://mlsanity.com/paper/2203.04925/) (2022)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [BAFFLE: A Baseline of Backpropagation-Free Federated Learning](https://mlsanity.com/paper/2301.12195/) (2023)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.06755/) (2024)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [Universal Exact Compression of Differentially Private Mechanisms](https://mlsanity.com/paper/2405.20782/) (2024)
- [Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation](https://mlsanity.com/paper/2110.07751/) (2021)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Distributed Nonparametric Function Estimation: Optimal Rate of Convergence and Cost of Adaptation](https://mlsanity.com/paper/2107.00179/) (2021)
- [Tight Memory-Regret Lower Bounds for Streaming Bandits](https://mlsanity.com/paper/2306.07903/) (2023)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Differentiated Aggregation to Improve Generalization in Federated Learning](https://mlsanity.com/paper/2404.11754/) (2024)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Distributed Sparse Normal Means Estimation with Sublinear Communication](https://mlsanity.com/paper/2102.03060/) (2021)
- [Over-the-Air Statistical Estimation](https://mlsanity.com/paper/2103.04014/) (2021)
- [Optimal high-dimensional and nonparametric distributed testing under communication constraints](https://mlsanity.com/paper/2202.00968/) (2022)

## Abstract (arXiv)

We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the m machines receives n data points from a d-dimensional Gaussian distribution with unknown mean θ which is promised to be k-sparse. The machines communicate by message passing and aim to estimate the mean θ. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed textitsparse linear regression problem: to achieve the statistical minimax error, the total communication is at least Omega(minn,dm), where n is the number of observations that each machine receives and d is the ambient dimension. These lower results improve upon [Sha14,SD'14] by allowing multi-round iterative communication model. We also give the first optimal simultaneous protocol in the dense case for mean estimation. As our main technique, we prove a textitdistributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.