Timezone: »

 
Poster
Adaptive Sampling for Estimating Probability Distributions
Shubhanshu Shekhar · Tara Javidi · Mohammad Ghavamzadeh

Tue Jul 14 01:00 PM -- 01:45 PM & Wed Jul 15 12:00 AM -- 12:45 AM (PDT) @
in Poster Session 7 »
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.
Keywords: Active Learning · Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Shubhanshu Shekhar (University of California, San Diego)
Tara Javidi (University of California San Diego)
Mohammad Ghavamzadeh (Google Research)

More from the Same Authors