Foundations and Trends® in Communications and Information Theory > Vol 19 > Issue 6

Topics and Techniques in Distribution Testing: A Biased but Representative Sample

By Clément L. Canonne, University of Sydney, Australia, clement.canonne@sydney.edu.au

 
Suggested Citation
Clément L. Canonne (2022), "Topics and Techniques in Distribution Testing: A Biased but Representative Sample", Foundations and Trends® in Communications and Information Theory: Vol. 19: No. 6, pp 1032-1198. http://dx.doi.org/10.1561/0100000114

Publication Date: 22 Nov 2022
© 2022 C. L. Canonne
 
Subjects
Detection and estimation,  Information theory and computer science,  Information theory and statistics,  Learning and statistical methods,  Computational learning,  Design and analysis of algorithms,  Randomness in computation
 

Free Preview:

Download extract

Share

Download article
In this article:
1. What Is Distribution Testing?
2. Testing Goodness-of-fit of Univariate Distributions
3. Information-theoretic Lower Bounds
4. Testing with Constrained Measurements
Acknowledgements
Appendices
References

Abstract

We focus on some specific problems in distribution testing, taking goodness-of-fit as a running example. In particular, we do not aim to provide a comprehensive summary of all the topics in the area; but will provide self-contained proofs and derivations of the main results, trying to highlight the unifying techniques.

DOI:10.1561/0100000114
ISBN: 978-1-63828-100-9
178 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-63828-101-6
178 pp. $145.00
Buy E-book (.pdf)
Table of contents:
1. What Is Distribution Testing?
2. Testing Goodness-of-fit of Univariate Distributions
3. Information-theoretic Lower Bounds
4. Testing with Constrained Measurements
Acknowledgements
Appendices
References

Topics and Techniques in Distribution Testing

This monograph serves as an introduction and detailed overview of some important topics in distribution testing, an area of theoretical computer science which falls under the general umbrella of property testing, and sits at the intersection of computational learning, statistical learning and hypothesis testing, information theory, and the theory of machine learning.

Written in a tutorial style, the author provides the reader with a thorough overview, including a historical perspective on work to date. After introducing the reader to distribution testing, the author proceeds to cover uniformity testing in-depth, and then builds on this to include techniques and “ready-to-use” theorems that establish sample complexity lower bounds. Finally the author discusses the most appropriate techniques to adopt in various settings, including: Quantization, Privacy, Noisy channels, Streaming and memory-limited devices, and Communication constraints.

Throughout the tutorial the reader is guided through the basic concepts and mathematical complexities of the topics under review. The inclusion of Exercises and a separately available Solutions manual make this book ideal to be used as part of a graduate course.

 
CIT-114