Communication lower bounds for statistical estimation problems via a distributed data processing inequality?

Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

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 sparse linear regression problem: to achieve the statistical minimax error, the total communication is at least?(min{n,d}m), where n is the number of observations that each machine receives and d is the ambient dimension. These lower bound results improve upon Shamir (NIPS'14) and Steinhardt, Duchi (COLT'15) by allowing a multi-round interactive communication model. We also give the first optimal simultaneous protocol in the dense case for mean estimation. As our main technique, we prove a distributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages1011-1020
Number of pages10
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication complexity
  • Information complexity
  • Statistical estimation

Fingerprint Dive into the research topics of 'Communication lower bounds for statistical estimation problems via a distributed data processing inequality?'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Garg, A., Ma, T., Nguyen, H. L., & Woodruff, D. P. (2016). Communication lower bounds for statistical estimation problems via a distributed data processing inequality? In Y. Mansour, & D. Wichs (Eds.), STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1011-1020). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897582