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

DOI10.1109/TIT.2020.3028440MaRDI QIDQ5138936zbMATH OpenOpenAlexFDO

Authors Jayadev Acharya, Clement L. Canonne, Himanshu Tyagi

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.11476

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Statistical aspects of information-theoretic topics (62B10) Point estimation (62F10) Statistical aspects of big data and data science (62R07) Parametric inference under constraints (62F30)

Abstract: 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 $mathcalW$, which can be instantiated to capture both the communication- and privacy-constrained settings and beyond. The referee uses the messages from players to solve an inference problem for the unknown distribution that generated the samples. We derive lower bounds for 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 distances 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.

Cited in

(6)

• Optimal high-dimensional and nonparametric distributed testing under communication constraints
• Testing distributions of huge objects
• Differentially private sampling from distributions
• Comparison graphs: a unified method for uniformity testing
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Private distribution testing with heterogeneous constraints: your epsilon might not be mine

This page was built for publication: Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138936)