A short note on learning discrete distributions

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 $\varepsilon$, with error probability $δ$.

Machine Learning and Algorithms

Source

Paper

Similar papers

Bessel Smoothing and Multi-Distribution Property EstimationHao Yi, Ping Li2020 · Conference on Learning Theory In Library

Optimal testing of discrete distributions with high probabilityIlias Diakonikolas, Themis Gouleakis, Daniel M. Kane et al.2021 In Library

Learning discrete distributions: user vs item-level privacyYuhan Liu, Ananda Theertha Suresh, Felix Yu et al.2020 · arXiv (Cornell University) · 60 citations In Library

The sample complexity of multi-distribution learningBinghui Peng2023 · arXiv (Cornell University) In Library

Locally Differentially-Private Randomized Response for Discrete Distribution LearningA. Pastore, M. Gastpar2018 · Journal of machine learning research · 13 citations In Library

Locally Differentially-Private Randomized Response for Discrete Distribution LearningAdriano Pastore, Michael Gastpar2018 · Infoscience (Ecole Polytechnique Fédérale de Lausanne) In Library

Differentially Private Sampling from DistributionsSofya Raskhodnikova, Satchit Sivakumar, Adam Smith et al.2022 · arXiv (Cornell University) · 14 citations In Library

Testing with Non-identically Distributed SamplesShivam Garg, Chirag Pabbaraju, Kirankumar Shiragur et al.2023 · arXiv (Cornell University) In Library

Differentially Private Testing of Identity and Closeness of Discrete DistributionsJayadev Acharya, Ziteng Sun, Huanyu Zhang2017 · Neural Information Processing Systems · 83 citations In Library

Downsampling for Testing and Learning in Product DistributionsNathaniel Harms, Yuichi Yoshida2020 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) In Library

Patents near this paper

DISTRIBUTED KERNEL DENSITY ESTIMATIONUS 7,743,086 · MICROSOFT CORPORATION · 2010 LEARNING DOMAIN RANDOMIZATION DISTRIBUTIONS FOR TRANSFER LEARNINGUS 11,501,167 · THE ROYAL INSTITUTION FOR THE ADVANCEMENT OF LEARNING/MCGILL UNIVERSITY · 2022 DISCRETE EVENT DISTRIBUTION SAMPLING APPARATUS AND METHODSUS 8,031,926 · BOARD OF REGENTS OF THE NEVADA SYSTEM OF HIGHER EDUCATION ON BEHALF OF THE UNIVERSITY OF NEVADA, RENO · 2011 Patent US 10,977,336US 10,977,336 DEPTH-CONSTRAINED KNOWLEDGE DISTILLATION FOR INFERENCE ON ENCRYPTED DATAUS 11,599,806 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2023

Source of record

OpenAlex