Adaptive Sampling for Estimating Multiple Probability Distributions
This work addresses a fundamental sampling allocation challenge in statistics and machine learning for researchers and practitioners, but it appears incremental as it builds on existing tracking algorithms and distance measures.
The paper tackles the problem of allocating samples to learn multiple discrete probability distributions uniformly well across four distance measures, proposing a general optimistic tracking algorithm and deriving regret bounds for specific instantiations, with experimental verification.
We consider the problem of allocating samples to a finite set of discrete distributions in order to learn them uniformly well 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 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 the regret of their resulting allocation schemes. We verify our theoretical findings through some experiments. Finally, we show that the techniques developed in the paper can be easily extended to the related setting of minimizing the average error (in terms of the four distances) in learning a set of distributions.