Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

Speaker: Huy L. Nguyen , Northeastern U.

Date: Wednesday, November 09, 2016

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, MIT CSAIL

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Huy L. Nguyen: Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

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 \theta which is promised to be k-sparse. The machines communicate by message passing and aim to estimate the mean \theta. 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 \Omega(min{n, d}m), where n is the number of observations that each machine receives and d is the ambient dimension. 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.

This is joint work with Mark Braverman, Ankit Garg, Tengyu Ma, and David Woodruff.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar at Tuesday, November 01, 2016 at 1:10 PM.