Inference Under Information Constraints II: Communication Constraints and Shared Randomness

By Jayadev Acharya, Clément Louis Canonne, Himanshu Tyagi. 2019

66 citations recorded by the source corpus.

A central server needs to perform statistical inference based on samples that are distributed over multiple users who can each send a message of limited length to the center. We study problems of distribution learning and identity testing in this distributed inference setting and examine the role of shared randomness as a resource. We propose a general-purpose simulate-and-infer strategy that uses only private-coin communication protocols and is sample-optimal for distribution learning. This general strategy turns out to be sample-optimal even for distribution testing among private-coin protocols. Interestingly, we propose a public-coin protocol that outperforms simulate-and-infer for distribution testing and is, in fact, sample-optimal. Underlying our public-coin protocol is a random hash that when applied to the samples minimally contracts the chi-squared distance of their distribution to the uniform distribution.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

In Information 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].”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, background): “(2018a), where extensions to distributed property testing are studied in Acharya et al. (2019b,a). These works show that the dependence of the estimation performance on k can be qualitatively different: the estimation error decays linearly in k for the Gaussian location model, while for distribution”
Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints (2021, methodology): “Lower bounds on `1 sample complexity developed in (Acharya et al., 2021, 2019a) imply that 1) n∗(s, d, b) = Ω ( s2 log(d/s) 2b ) in the non-interactive case; and n∗(s, d, b) = Ω ( s2 2b ) for the interac- tive setting.”
Distributed Signal Detection under Communication Constraints (2020, methodology): “…j by taking term-wise signs, and then solve the binary distribution mean detection problem over the Y j ’s. Theorem 13 There exists a private-coin protocol for distributed Gaussian mean testing with Proof The proof follows the idea of “distributed simulation” introduced in (Acharya et al., 2019c).”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “In particular, [2] provides a framework for deriving lower bounds for such problems and [3] provides sample-optimal algorithms for communication constraints.”