On the Convergence of the Empirical Distribution

Abstract

We develop a general technique for bounding the tail of the total variation distance between the empirical and the true distributions over countable sets. Our methods sharpen a deviation bound of Devroye (1983) for distributions over finite sets, and also hold for the broader class of distributions with countable support. We also provide some lower bounds of possible independent interest.

Cited by in corpus (7)

• On testing pseudorandom generators via statistical tests based on the arcsine law
• Provable Representation Learning for Imitation with Contrastive Fourier Features
• TRAIL: Near-Optimal Imitation Learning with Suboptimal Data
• Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding
• Continuity of Generalized Entropy and Statistical Learning
• Qubit Readout Error Mitigation with Bit-flip Averaging
• Minimum KL-divergence on complements of $L_1$ balls