Skip to main content

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

Author(s): Braverman, Mark; Garg, A; Ma, T; Nguyen, HL; Woodruff, DP

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1wd4w
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 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.
Publication Date: 16-Jun-2016
Electronic Publication Date: 19-Jun-2016
Citation: Braverman, M, Garg, A, Ma, T, Nguyen, HL, Woodruff, DP. (2016). Communication lower bounds for statistical estimation problems via a distributed data processing inequality?. 19-21-June-2016 (1011 - 1020. doi:10.1145/2897518.2897582
DOI: doi:10.1145/2897518.2897582
Pages: 1011 - 1020
Type of Material: Journal Article
Series/Report no.: STOC '16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing;
Journal/Proceeding Title: STOC '16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.