Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction

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

126 citations recorded by the source corpus.

Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels $\mathcal {W}$ , which can be instantiated to capture, among others, both the communication- and privacy-constrained settings. The referee uses the players’ messages to solve an inference problem on the unknown distribution that generated the samples. We derive lower bounds for the sample complexity of learning and testing discrete distributions in this information-constrained setting. Underlying our bounds is a characterization of the contraction in chi-square distance between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both public- and private-coin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.

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

In Statistics and Probability

In Information 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].”
Learning discrete distributions: user vs item-level privacy (2020, background): “…al., 2019, Acharya et al., 2020, Kamath et al., 2020, Acharya et al., 2019a,b], learning machine learning models [Chaudhuri et al., 2011, Bassily et al., 2014, McMahan et al., 2018b, Dwork et al., 2014], hypothesis testing [Aliakbarpour et al., 2018, Acharya et al., 2018], and various other tasks.”
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].”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “This `1 risk is optimal over all protocols, even while allowing public-coins [26, 32, 24].”
The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information (2018, neutral): “use for minimax bounds to a variety of information constraints [2, 3].”
The Role of Interactivity in Local Differential Privacy (2019, background): “[1, 2] gives a qualitatively different separation between the private-coin and public-coin models of noninteractive local privacy.”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, background): “…et al. (2013) for a general treatment of estimation problems under locally differentially private (LDP) constraints, while optimal schemes (and lower bounds) for estimating discrete distributions are proposed in Kairouz et al. (2016); Wang et al. (2016); Ye and Barg (2018); Acharya et al. (2019c).”
Fisher Information Under Local Differential Privacy (2020, background): “Other works such as [13], [17], [18] have also noted the connection between communication and privacy constraints in statistical estimation.”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, background): “The problem has also been considered in the non-local differentially private setting [Wang et al., 2015, Gaboardi et al., 2016, Cai et al., 2017, Aliakbarpour et al., 2018, Acharya et al., 2018].”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, methodology): “SMP protocols can themselves be classified into public- and private-coin protocols based on whether or not the common random variable U is available to the players; see [3] for definitions.”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, methodology): “2 Lower bound under LDP constraints We now prove the sample complexity lower bound in Theorem 1 using the chi-squared contraction method in [4] and an extension of Fano’s method from [20].”
Inference Under Information Constraints III: Local Privacy Constraints (2021, methodology): “Furthermore, this is asymptotically optimal from the result of [2], and the mechanism only uses one bit of communication from each player, making it as communication-efficient as possible.”