On the Convergence of the Empirical Distribution

2012/05/30 by Daniel Berend, Berend, Daniel, Aryeh Kontorovich +1 · 5 citations
Decision Sciences · Mathematics · #62G07 #62G20 #FOS: Mathematics #Probability and Risk Models #Risk and Portfolio Optimization #Statistical Methods and Inference #Statistics Theory (math.ST) #math.ST #msc:62G07 #msc:62G20 #stat.TH

paper · pdf · doi:10.48550/arxiv.1205.6711

openalex publication_date 2012/05/30 · arxiv created 2012/06/05 · arxiv updated 2012/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

• The Sample Complexity of Lossless Data Compression
• TRAIL: Near-Optimal Imitation Learning with Suboptimal Data
• Continuity of Generalized Entropy and Statistical Learning
• Generalization Guarantees for Multi-View Representation Learning and Application to Regularization via Gaussian Product Mixture Prior
• Provable Representation Learning for Imitation with Contrastive Fourier Features

Related

• Learning discrete distributions with infinite support
• Approximations for the number of maxima and near-maxima in independent data
• Convergence of the empirical measure in expected Wasserstein distance: non asymptotic explicit bounds in ℝ^d
• Concentration Inequalities for the Empirical Distribution
• Total Variation Distance for Product Distributions is #P-Complete