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

By Mark Braverman, A. Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff. 2015

193 citations recorded by the source corpus.

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 results improve upon Shamir (NIPS'14) and Steinhardt-Duchi (COLT'15) 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 distributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Statistical Learning Theory, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Martin Jaggi
  2. Jakub Konecný
  3. Percy Liang
  4. Qiang Yang
  5. Peter Richtárik
  6. Yoshua Bengio
  7. Michael I. Jordan
  8. Sebastian U. Stich

In Computational Mechanics

  1. Jakub Konecný
  2. Peter Richtárik
  3. Jason D. Lee
  4. Sebastian U. Stich
  5. Martin Jaggi
  6. Tengyu Ma
  7. Nati Srebro
  8. H. Brendan McMahan

In Computer Networks and Communications

  1. Ayfer Özgür
  2. Jayadev Acharya
  3. Leighton Pate Barnes
  4. Yanjun Han
  5. Ziteng Sun
  6. Himanshu Tyagi
  7. Clément Louis Canonne
  8. Peter Kairouz

In Statistical Learning Theory

  1. Ayfer Özgür
  2. Leighton Pate Barnes
  3. Jason D. Lee
  4. Jayadev Acharya
  5. Yanjun Han
  6. Clément Louis Canonne
  7. Himanshu Tyagi
  8. Tengyu Ma

In Information Theory

  1. Ayfer Özgür
  2. Jayadev Acharya
  3. Ziteng Sun
  4. Wei-Ning Chen
  5. Peter Kairouz
  6. Himanshu Tyagi
  7. Clément Louis Canonne
  8. Leighton Pate Barnes

Citations in the corpus