On Communication Cost of Distributed Statistical Estimation and Dimensionality

By A. Garg, Tengyu Ma, Huy L. Nguyen. 2014

113 citations recorded by the source corpus.

We explore the connection between dimensionality and communication cost in distributed learning problems. Specifically we study the problem of estimating the mean θ→ of an unknown d dimensional gaussian distribution in the distributed setting. In this problem, the samples from the unknown distribution are distributed among m different machines. The goal is to estimate the mean θ→ at the optimal minimax rate while communicating as few bits as possible. We show that in this setting, the communication cost scales linearly in the number of dimensions i.e. one needs to deal with different dimensions individually. Applying this result to previous lower bounds for one dimension in the interactive setting [1] and to our improved bounds for the simultaneous setting, we prove new lower bounds of Ω(md/ log(m)) and Ω(md) for the bits of communication needed to achieve the minimax squared loss, in the interactive and simultaneous settings respectively. To complement, we also demonstrate an interactive protocol achieving the mini-max squared loss with O(md) bits of communication, which improves upon the simple simultaneous protocol by a logarithmic factor. Given the strong lower bounds in the general setting, we initiate the study of the distributed parameter estimation problems with structured parameters. Specifically, when the parameter is promised to be s-sparse, we show a simple thresholding based protocol that achieves the same squared loss while saving a d/s factor of communication. We conjecture that the tradeoff between communication and squared loss demonstrated by this protocol is essentially optimal up to logarithmic factor.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability, Statistical Learning 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

In Computer Networks and Communications

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

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 = {θ ∈”
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.”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “This is along the line of recent work on distributed mean estimation under communication constraints [14], [28], [45], [55], [58], although some of these works consider more general communication models than what we allow.”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, background): “[11] Ankit Garg, Tengyu Ma, and Huy Nguyen.”
Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, background): “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.”
Information-Theoretic Lower Bounds on Bayes Risk in Decentralized Estimation (2016, positive): “We also analyze the probability of excess distortion and the expected distortion via the distribution of the conditional information density i ( W ; (cid:99) W | U ) .”
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].”
The Role of Interactivity in Local Differential Privacy (2019, methodology): “More recently, Duchi and Rogers [15] showed how to combine the above analogue of Assouad’s method with techniques from information complexity [8, 21] to prove”
Memory, Communication, and Statistical Queries (2016, background): “Several authors have also considered communication and/or privacy restrictions in the distributed data setting (Balcan et al., 2012; Duchi et al., 2013; Zhang et al., 2013; Garg et al., 2014; Braverman et al., 2015).”
Lower Bounds for Locally Private Estimation via Communication Complexity (2019, background): “Work in informationlimited estimation (Zhang et al., 2013; Garg et al., 2014; Braverman et al., 2016) typically strongly relies on independence among estimands, which allows decoupling them.”
Communication-Efficient Distributed Learning of Discrete Probability Distributions (2017, background): “Recent works [40, 21, 24, 5] study the communication cost of mean estimation problems of structured, parametrized distributions.”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, methodology): “An estimator using the blackboard communication protocol that achieves this result is given in Garg et al. (2014).”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “Among other works on high-dimensional mean estimation under communication constraints, [18, 11] consider communication-constrained Gaussian mean estimation in the blackboard communication model, under l2 loss.”