A short note on learning discrete distributions

2020/02/25 by Clément L. Canonne, Canonne, Clément L. · 8 citations
Computer Science · #FOS: Mathematics #Machine Learning and Algorithms #Probability (math.PR) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2002.11457

openalex publication_date 2020/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The goal of this short note is to provide simple proofs for the "folklore facts" on the sample complexity of learning a discrete probability distribution over a known domain of size k to various distances ε, with error probability δ.

Cited by

• Efficient graph-diagonal characterization of noisy states distributed over quantum networks via Bell sampling
• The Rate-Distortion-Perception Trade-Off with Algorithmic Realism
• Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep's clothing
• Estimation of discrete distributions with high probability under χ²-divergence
• The Price of Tolerance in Distribution Testing
• Distributed clustering in partially overlapping feature spaces
• Learning to Play Multi-Follower Bayesian Stackelberg Games
• SPAM Tolerance for Pauli Error Estimation

Related

• The sample complexity of multi-distribution learning
• Learning discrete distributions with infinite support
• Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem
• Learning mixtures of structured distributions over discrete domains
• The Sample Complexity of Multi-Distribution Learning for VC Classes