Distributed Statistical Estimation of High-Dimensional and Nonparametric Distributions

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

54 citations recorded by the source corpus.

We consider the problem of estimating high-dimensional and nonparametric distributions in distributed networks, where each sensor in the network observes an independent sample from the underlying distribution and can communicate it to a central processor by writing at most $k$ bits on a public blackboard. We obtain matching upper and lower bounds for the minimax risk of estimating the underlying distribution under $L$ 1loss. Our results reveal that the minimax risk reduces exponentially in k. Instead of relying on strong data processing inequalities for the converse as commonly done in the literature, we build on a new representation of the communication constraint, which leads to a tight characterization of the problem.

Subfields: Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

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 II: Communication Constraints and Shared Randomness (2019, neutral): “Among these, our work is closest to the results in [32], [31] and [21].”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, background): “2 Previous results and our contribution Discrete distribution estimation under communication [24, 23, 4, 3] and LDP [19, 21, 25, 35, 6, 5] constraints is well studied, and it is now known that for l-bit communication constraints Wl, and ε-LDP channels Wε (for ε = O(1)), SC(α, △k, Wl, dTV) = Θ ( k(2)”
A Geometric Characterization of Fisher Information from Quantized Samples with Applications to Distributed Statistical Estimation (2018, background): “Corollary 3 matches the upper bound from the achievable scheme in [2], while Corollary 1 matches the upper bound from [14] if we are allowed to use the interactive or blackboard models.”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, methodology): “The highdimensional discrete distribution estimation problem is studied in Diakonikolas et al. (2017); Han et al. (2018a), where extensions to distributed property testing are studied in Acharya et al. (2019b,a).”
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].”
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.”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, methodology): “In the blackboard communication model, [20] and [19] obtained several tight bounds for mean estimation and density estimation under l2 and l1 loss, respectively.”
Distributed Signal Detection under Communication Constraints (2020, background): “…has been considered in a number of recent works (Zhang et al., 2013; Garg et al., 2014; Shamir, 2014; Braverman et al., 2016; Xu and Raginsky, 2017; Han et al., 2018a,b; Barnes et al., 2019; Cai and Wei, 2020; Acharya et al., 2019b,d), while distributed testing of distributions in the ﬁnite sample…”