Inference Under Information Constraints II: Communication Constraints and Shared Randomness

DOI10.1109/TIT.2020.3028439MaRDI QIDQ5138937zbMATH 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/1905.08302

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• Information Inequalities for Joint Distributions, With Interpretations and Applications
• A Conditional Information Inequality and Its Combinatorial Applications
• scientific article; zbMATH DE number 1735960
• Information-Theoretic Secret Sharing From Correlated Gaussian Random Variables and Public Communication
• Information Transmission under Random Emission Constraints
• A Finite-Sample, Distribution-Free, Probabilistic Lower Bound on Mutual Information
• scientific article; zbMATH DE number 7306916
• Proving and Disproving Information Inequalities: Theory and Scalable Algorithms
• A theory of conditional information with applications
• Variational Bayes and a problem of reliable communication. II: Infinite systems

Cited in

(12)

• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
• The mathematics of coordinated inference. A study of generalized hat problems
• scientific article; zbMATH DE number 1735960 (Why is no real title available?)
• Two Party Distribution Testing: Communication and Security
• scientific article; zbMATH DE number 7306916 (Why is no real title available?)
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Optimal high-dimensional and nonparametric distributed testing under communication constraints
• Distribution testing with a confused collector
• Private distribution testing with heterogeneous constraints: your epsilon might not be mine
• Differentially private sampling from distributions
• Distributed online learning for joint regret with communication constraints
• Comparison graphs: a unified method for uniformity testing

This page was built for publication: Inference Under Information Constraints II: Communication Constraints and Shared Randomness

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