# On Communication Cost of Distributed Statistical Estimation and Dimensionality

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2014.

## Built on by (most cited first, 24 of 24)

- [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)
- [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)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [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)
- [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)
- [Distributed Nonparametric Function Estimation: Optimal Rate of Convergence and Cost of Adaptation](https://mlsanity.com/paper/2107.00179/) (2021)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [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)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [Efficient Unbiased Sparsification](https://mlsanity.com/paper/2402.14925/) (2024)
- [Sequential Estimation under Multiple Resources: a Bandit Point of View](https://mlsanity.com/paper/2109.14703/) (2021)
- [Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints](https://mlsanity.com/paper/2206.00707/) (2022)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Non-Convex Federated Optimization under Cost-Aware Client Selection](https://mlsanity.com/paper/2512.05327/) (2025)
- [Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget](https://mlsanity.com/paper/2601.18950/) (2026)
- [Meta-analysis of individualized treatment rules via sign-coherency](https://mlsanity.com/paper/2211.15476/) (2022)
- [Efficient Covariance Estimation for Sparsified Functional Data](https://mlsanity.com/paper/2511.18237/) (2025)
- [Matching Rates and Optimal Allocation for Federated Probe-Logit Distillation under Heterogeneous Bandwidth Budgets](https://mlsanity.com/paper/2605.29642/) (2026)
- [Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model](https://mlsanity.com/paper/2606.07124/) (2026)

## Abstract (arXiv)

We explore the connection between dimensionality and communication cost in distributed learning problems. Specifically we study the problem of estimating the mean vecθ of an unknown d dimensional gaussian distribution in the distributed setting. In this problem, the samples from the unknown distribution are distributed among m different machines. The goal is to estimate the mean vecθ at the optimal minimax rate while communicating as few bits as possible. We show that in this setting, the communication cost scales linearly in the number of dimensions i.e. one needs to deal with different dimensions individually. Applying this result to previous lower bounds for one dimension in the interactive setting citeZDJW13 and to our improved bounds for the simultaneous setting, we prove new lower bounds of Omega(md/log(m)) and Omega(md) for the bits of communication needed to achieve the minimax squared loss, in the interactive and simultaneous settings respectively. To complement, we also demonstrate an interactive protocol achieving the minimax squared loss with O(md) bits of communication, which improves upon the simple simultaneous protocol by a logarithmic factor. Given the strong lower bounds in the general setting, we initiate the study of the distributed parameter estimation problems with structured parameters. Specifically, when the parameter is promised to be s-sparse, we show a simple thresholding based protocol that achieves the same squared loss while saving a d/s factor of communication. We conjecture that the tradeoff between communication and squared loss demonstrated by this protocol is essentially optimal up to logarithmic factor.