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
- Martin Jaggi
- Jakub Konecný
- Percy Liang
- Qiang Yang
- Peter Richtárik
- Yoshua Bengio
- Michael I. Jordan
- Sebastian U. Stich
In Computational Mechanics
- Jakub Konecný
- Peter Richtárik
- Jason D. Lee
- Sebastian U. Stich
- Martin Jaggi
- Tengyu Ma
- Nati Srebro
- H. Brendan McMahan
In Computer Networks and Communications
- Ayfer Özgür
- Jayadev Acharya
- Leighton Pate Barnes
- Yanjun Han
- Ziteng Sun
- Himanshu Tyagi
- Clément Louis Canonne
- Peter Kairouz
In Statistical Learning Theory
- Ayfer Özgür
- Leighton Pate Barnes
- Jason D. Lee
- Jayadev Acharya
- Yanjun Han
- Clément Louis Canonne
- Himanshu Tyagi
- Tengyu Ma
In Information Theory
- Ayfer Özgür
- Jayadev Acharya
- Ziteng Sun
- Wei-Ning Chen
- Peter Kairouz
- Himanshu Tyagi
- Clément Louis Canonne
- Leighton Pate Barnes
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, background): “Characterizing such fundamental trade-offs between accuracy and communication has been of recent interest in theoretical statistics [434, 81, 195, 11, 47, 380].”
- Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “If we further assume X are drawn from some discrete distribution p, then the problem falls into distribution estimation under local differential privacy [9], [13], [34], [36], [42], [43], [44], [45], [46] and limited communication [11], [25], [45], [46], [47], [48], [49], [50].”
- rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, background): “A sparse variation of the Gaussian mean estimation problem has been studied in [29], [30], [32], where = {θ ∈”
- Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Similar bounds have also been provided for the generally easier statistical estimation setting in Duchi et al. (2014); Braverman et al. (2015); Zhang et al. (2013).”
- Learning Distributions from their Samples under Communication Constraints (2019, methodology): “As an application of our framework, we use upper bounds on Fisher information to derive lower bounds on the minimax risk of the distributed estimation problems we discuss above and recover many of the existing results in the literature [6], [12], [13], [4], which are known to be (order-wise) tight.”
- Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, background): “[7] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff.”
- Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, methodology): “Distributed parameter estimation and function computation has been considered in many recent works; we refer to Duchi et al. (2013); Zhang et al. (2013); Shamir (2014); Garg et al. (2014); Braverman et al. (2016); Xu and Raginsky (2017) and the references therein for an overview.”
- Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “…in understanding various inference tasks under limited communication, where the users do not have enough communication to even transmit their data [19, 20], and recent works have established optimal bounds, and algorithms for fundamental problems such as distribution estimation and hypothesis…”
- Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “In such a setup, the goal is to estimate the true mean of the underlying distribution [200, 197, 65, 25].”
- Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “xponent and communication rate per sample. Closer to our work is distributed parameter estimation and functional estimation that has gained significant attention in recent years (see e.g., [23], [25], [14], [45]). In these works, much like our setting, independent samples are distributed across playe”
- Communication-efficient Sparse Regression (2017, background): “In Braverman et al. (2015), the authors established that to obtain risk R ≤ s log pN at least Ω (mmin(n,p) log p ) bits of communication is required.”
- One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Them (2019, methodology): “For learning statistical models in a distributed fashion, several works have focused on designing communication-efficient algorithms for various machine learning applications (Duchi et al., 2012; Braverman et al., 2016; Chang et al., 2017; Diakonikolas et al., 2017; Lee et al., 2017).”
- Order Optimal One-Shot Distributed Learning (2019, methodology): “…settings is often the communication between machines, and several recent works have focused on designing communication-efficient algorithms for different machine learning applications [Duchi et al., 2012, Braverman et al., 2016, Chang et al., 2017, Diakonikolas et al., 2017, Lee et al., 2017].”
- Fisher Information for Distributed Estimation under a Blackboard Communication Protocol (2019, methodology): “In this follow-up paper, we show how to characterize and bound the Fisher information from the blackboard transcript Y , and use these bounds to recover the results of [5], [6], [7], [3] under a blackboard protocol, which is also the model considered in these works except [5].”
- Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “A series of works Zhang et al. (2013); Garg et al. (2014); Braverman et al. (2016); Jordan et al. (2016); Diakonikolas et al. (2017b); Han et al. (2018b,a) studied distributed learning in both parametric and nonparametric settings obtaining (nearly-) matching upper and lower bounds.”