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.

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.