Adaptive Sampling for Estimating Probability Distributions

Shubhanshu Shekhar, Tara Javidi, Mohammad Ghavamzadeh
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:8687-8696, 2020.

Abstract

We consider the problem of allocating a fixed budget of samples to a finite set of discrete distributions to learn them uniformly well (minimizing the maximum error) in terms of four common distance measures: $\ell_2^2$, $\ell_1$, $f$-divergence, and separation distance. To present a unified treatment of these distances, we first propose a general \emph{optimistic tracking algorithm} and analyze its sample allocation performance w.r.t. an oracle. We then instantiate this algorithm for the four distance measures and derive bounds on their regret. We also show that the allocation performance of the proposed algorithm cannot, in general, be improved, by deriving lower-bounds on the expected deviation from the oracle allocation for any adaptive scheme. We verify our theoretical findings through some experiments. Finally, we show that the techniques developed in the paper can be easily extended to learn some classes of continuous distributions as well as to the related setting of minimizing the average error (in terms of the four distances) in learning a set of distributions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-shekhar20a, title = {Adaptive Sampling for Estimating Probability Distributions}, author = {Shekhar, Shubhanshu and Javidi, Tara and Ghavamzadeh, Mohammad}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {8687--8696}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/shekhar20a/shekhar20a.pdf}, url = {https://proceedings.mlr.press/v119/shekhar20a.html}, abstract = {We consider the problem of allocating a fixed budget of samples to a finite set of discrete distributions to learn them uniformly well (minimizing the maximum error) in terms of four common distance measures: $\ell_2^2$, $\ell_1$, $f$-divergence, and separation distance. To present a unified treatment of these distances, we first propose a general \emph{optimistic tracking algorithm} and analyze its sample allocation performance w.r.t. an oracle. We then instantiate this algorithm for the four distance measures and derive bounds on their regret. We also show that the allocation performance of the proposed algorithm cannot, in general, be improved, by deriving lower-bounds on the expected deviation from the oracle allocation for any adaptive scheme. We verify our theoretical findings through some experiments. Finally, we show that the techniques developed in the paper can be easily extended to learn some classes of continuous distributions as well as to the related setting of minimizing the average error (in terms of the four distances) in learning a set of distributions.} }
Endnote
%0 Conference Paper %T Adaptive Sampling for Estimating Probability Distributions %A Shubhanshu Shekhar %A Tara Javidi %A Mohammad Ghavamzadeh %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-shekhar20a %I PMLR %P 8687--8696 %U https://proceedings.mlr.press/v119/shekhar20a.html %V 119 %X We consider the problem of allocating a fixed budget of samples to a finite set of discrete distributions to learn them uniformly well (minimizing the maximum error) in terms of four common distance measures: $\ell_2^2$, $\ell_1$, $f$-divergence, and separation distance. To present a unified treatment of these distances, we first propose a general \emph{optimistic tracking algorithm} and analyze its sample allocation performance w.r.t. an oracle. We then instantiate this algorithm for the four distance measures and derive bounds on their regret. We also show that the allocation performance of the proposed algorithm cannot, in general, be improved, by deriving lower-bounds on the expected deviation from the oracle allocation for any adaptive scheme. We verify our theoretical findings through some experiments. Finally, we show that the techniques developed in the paper can be easily extended to learn some classes of continuous distributions as well as to the related setting of minimizing the average error (in terms of the four distances) in learning a set of distributions.
APA
Shekhar, S., Javidi, T. & Ghavamzadeh, M.. (2020). Adaptive Sampling for Estimating Probability Distributions. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:8687-8696 Available from https://proceedings.mlr.press/v119/shekhar20a.html.

Related Material