Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints

By Yanjun Han, Ayfer Özgür, Tsachy Weissman. 2018

101 citations recorded by the source corpus.

We consider parameter estimation in distributed networks, where each sensor in the network observes an independent sample from an underlying distribution and has <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> bits to communicate its sample to a centralized processor which computes an estimate of a desired parameter. We develop lower bounds for the minimax risk of estimating the underlying parameter for a large class of losses and distributions. Our results show that under mild regularity conditions, the communication constraint reduces the effective sample size by a factor of <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> when <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> is small, where <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> is the dimension of the estimated parameter. Furthermore, this penalty reduces at most exponentially with increasing <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>, which is the case for some models, e.g., estimating high-dimensional distributions. For other models however, we show that the sample size reduction is re-mediated only linearly with increasing <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>, e.g. when some sub-Gaussian structure is available. We apply our results to the distributed setting with product Bernoulli model, multinomial model, Gaussian location models, and logistic regression which recover or strengthen existing results. Our approach significantly deviates from existing approaches for developing information-theoretic lower bounds for communication-efficient estimation. We circumvent the need for strong data processing inequalities used in prior work and develop a geometric approach which builds on a new representation of the communication constraint. This approach allows us to strengthen and generalize existing results with simpler and more transparent proofs.

Subfields: 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 Computer Networks and Communications

In Statistics and Probability

In Statistical Learning Theory

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 = {θ ∈”
Learning Distributions from their Samples under Communication Constraints (2019, methodology): “This result recovers the corresponding result in [3] and matches the upper bound from the achievable scheme developed in [4] (when the performance of the scheme is evaluated under `(2) loss rather than `(1)).”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, methodology): “For this special case, our general approach reduces to a similar procedure as [34], which was obtained independently of our work.”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “Distribution estimation has also been studied recently under very low communication budget (Diakonikolas et al., 2017; Han et al., 2018; Acharya et al., 2018a) , where each user sends only ` < log k bits to R.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “in [33] (see, also, [3]), any -bit public-coin (possibly interactive) (k, ε, 1/3)-learning protocol must have Ω k(2)/(2 ε(2)) players.”
A Geometric Characterization of Fisher Information from Quantized Samples with Applications to Distributed Statistical Estimation (2018, methodology): “In a flavor similar to [1], our upper bounds on the trace of the Fisher information matrix reveal that the the tail of the distribution of the score function Sθ(X) dictates the dependence on the quantization rate k.”
Lower Bounds for Locally Private Estimation via Communication Complexity (2019, background): “The work in information-limited estimation [39, 19, 6, 21] typically strongly relies on some type of independence among estimands, which allows decoupling approaches to apply.”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, background): “[36, 22, 13, 24] consider sparse Gaussian mean estimation under communication constraints ([22, 13] consider interactive protocols with the goal of bounding the total amount of communication from all users).”
Distributed Signal Detection under Communication Constraints (2020, methodology): “We also note that the aforementioned work of (Han et al., 2018b) contains lower bound for the (related) task of distributed estimation for the Gaussian Location Model (GLM), and some of their arguments rely on tools similar to ours (speciﬁcally, Lemma 5).”
Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints (2021, methodology): “Under the b-bit communication constraint, our first encoding scheme is based on the grouping idea (Han et al., 2018a), where each client only encodes symbols in a pre-specified subset of [d] and ignores others.”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “, the (non-distributed) uniformity test of Paninski (2008), we can perform uniformity testing using √ 2`/(θ2ε2) samples.”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, methodology): “Finally, we mention that very recently, following the appearance of [2], an updated version of [20] appeared online as [22], which has similar results as ours for the high-dimensional mean estimation problem under communication constraints.”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, methodology): “We also extend the results of [11] to derive minimax lower bounds for statistical models with sub-exponential score functions, which is useful, for example, when we are interested in estimating the variance of a Gaussian distribution.”
Fisher Information for Distributed Estimation under a Blackboard Communication Protocol (2019, methodology): “For the distribution estimation problem, Corollary 2 matches both the lower bound and achievability result from [2].”