# Distributed Sparse Normal Means Estimation with Sublinear Communication

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Builds on (most cited first, 13 of 13)

- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Efficient Distributed Learning with Sparsity](https://mlsanity.com/paper/1605.07991/) (2016)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [On Communication Cost of Distributed Statistical Estimation and Dimensionality](https://mlsanity.com/paper/1405.1665/) (2014)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms](https://mlsanity.com/paper/2001.08877/) (2020)
- [On the Optimality of Averaging in Distributed Statistical Learning](https://mlsanity.com/paper/1407.2724/) (2014)
- [Distributed Statistical Estimation and Rates of Convergence in Normal Approximation](https://mlsanity.com/paper/1704.02658/) (2017)
- [Adaptive distributed methods under communication constraints](https://mlsanity.com/paper/1804.00864/) (2018)
- [Distributed Learning with Sublinear Communication](https://mlsanity.com/paper/1902.11259/) (2019)
- [Distributed Nonparametric Regression under Communication Constraints](https://mlsanity.com/paper/1803.01302/) (2018)

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

- [Robust Mean Estimation under Quantization](https://mlsanity.com/paper/2601.07074/) (2026)
- [Recovery Guarantees for Distributed-OMP](https://mlsanity.com/paper/2209.07230/) (2022)
- [Distributed Sparse Linear Regression under Communication Constraints](https://mlsanity.com/paper/2301.04022/) (2023)

## Abstract (arXiv)

We consider the problem of sparse normal means estimation in a distributed setting with communication constraints. We assume there are M machines, each holding d-dimensional observations of a K-sparse vector μ corrupted by additive Gaussian noise. The M machines are connected in a star topology to a fusion center, whose goal is to estimate the vector μ with a low communication budget. Previous works have shown that to achieve the centralized minimax rate for the ℓ2 risk, the total communication must be high - at least linear in the dimension d. This phenomenon occurs, however, at very weak signals. We show that at signal-to-noise ratios (SNRs) that are sufficiently high - but not enough for recovery by any individual machine - the support of μ can be correctly recovered with significantly less communication. Specifically, we present two algorithms for distributed estimation of a sparse mean vector corrupted by either Gaussian or sub-Gaussian noise. We then prove that above certain SNR thresholds, with high probability, these algorithms recover the correct support with total communication that is sublinear in the dimension d. Furthermore, the communication decreases exponentially as a function of signal strength. If in addition KMll tfracdlog d, then with an additional round of sublinear communication, our algorithms achieve the centralized rate for the ℓ2 risk. Finally, we present simulations that illustrate the performance of our algorithms in different parameter regimes.