Distributed sparse normal means estimation with sublinear communication

DOI10.1093/IMAIAI/IAAB030zbMATH Open1501.94001arXiv2102.03060OpenAlexW4206745757MaRDI QIDQ5044121FDOQ5044121

Authors: Chen Amiraz, Robert Krauthgamer, Boaz Nadler 

Publication date: 24 October 2022

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: 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 $mu$ 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 $mu$ with a low communication budget. Previous works have shown that to achieve the centralized minimax rate for the $el{l}_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 $mu$ 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 $KMllfracdlogd$, then with an additional round of sublinear communication, our algorithms achieve the centralized rate for the $el{l}_2$ risk. Finally, we present simulations that illustrate the performance of our algorithms in different parameter regimes.

Full work available at URL: https://arxiv.org/abs/2102.03060

Recommendations

• Communication lower bounds for statistical estimation problems via a distributed data processing inequality
• Communication-efficient sparse regression
• Adaptive distributed methods under communication constraints
• Communication-efficient algorithms for statistical optimization
• Distributed nonparametric function estimation: optimal rate of convergence and cost of adaptation

zbMATH Keywords

support recoverysublinear communicationdistributed statistical inferencesparse normal mean estimation

Mathematics Subject Classification ID

Sequential statistical analysis (62L10) Communication theory (94A05)

Cited In (4)

• A communication-efficient and privacy-aware distributed algorithm for sparse PCA
• Communication lower bounds for statistical estimation problems via a distributed data processing inequality
• Adaptive distributed methods under communication constraints
• Distributed Sparse Total Least-Squares Over Networks

This page was built for publication: Distributed sparse normal means estimation with sublinear communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5044121)