On Learning Distributions from Their Samples
Abstract
One of the most natural and important questions in statistical learning is: how well can a distribution be approximated from its samples. Surprisingly, this question has so far been resolved for only one loss, the KL-divergence and even in this case, the estimator used is ad hoc and not well understood. We study distribution approximations for general loss measures. For \ell_2^2 we determine the best approximation possible, for \ell_1 and χ^2 we derive tight bounds on the best approximation, and when the probabilities are bounded away from zero, we resolve the question for all sufficiently smooth loss measures, thereby providing a coherent understanding of the rate at which distributions can be approximated from their samples.
Cite
Text
Kamath et al. "On Learning Distributions from Their Samples." Annual Conference on Computational Learning Theory, 2015.Markdown
[Kamath et al. "On Learning Distributions from Their Samples." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/kamath2015colt-learning/)BibTeX
@inproceedings{kamath2015colt-learning,
title = {{On Learning Distributions from Their Samples}},
author = {Kamath, Sudeep and Orlitsky, Alon and Pichapati, Dheeraj and Suresh, Ananda Theertha},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {1066-1100},
url = {https://mlanthology.org/colt/2015/kamath2015colt-learning/}
}