Learning Distributions from their Samples under Communication Constraints

By Leighton Pate Barnes, Yanjun Han, Ayfer Özgür. 2019

18 citations recorded by the source corpus.

We consider the problem of learning high-dimensional, nonparametric and structured (e.g. Gaussian) distributions in distributed networks, where each node in the network observes an independent sample from the underlying distribution and can use $k$ bits to communicate its sample to a central processor. We consider three different models for communication. Under the independent model, each node communicates its sample to a central processor by independently encoding it into $k$ bits. Under the more general sequential or blackboard communication models, nodes can share information interactively but each node is restricted to write at most $k$ bits on the final transcript. We characterize the impact of the communication constraint $k$ on the minimax risk of estimating the underlying distribution under $\ell^2$ loss. We develop minimax lower bounds that apply in a unified way to many common statistical models and reveal that the impact of the communication constraint can be qualitatively different depending on the tail behavior of the score function associated with each model. A key ingredient in our proof is a geometric characterization of Fisher information from quantized samples.

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

In Computer Networks and Communications

In Statistics and Probability

In Information Theory

Citations in the corpus

Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, background): “For estimating discrete distributions under communication constraints, the optimal sample complexity is established in [24, 2, 9], and for local privacy constraints in [19, 21, 25, 35, 10, 6, 5].”
Distributed Signal Detection under Communication Constraints (2020, background): “…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 regime was…”