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) @ None #None
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.
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
-
2020 Poster: Predictive Coding for Locally-Linear Control »
Rui Shu · Tung Nguyen · Yinlam Chow · Tuan Pham · Khoat Than · Mohammad Ghavamzadeh · Stefano Ermon · Hung Bui -
2020 Poster: Multi-step Greedy Reinforcement Learning Algorithms »
Manan Tomar · Yonathan Efroni · Mohammad Ghavamzadeh -
2019 Poster: Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits »
Branislav Kveton · Csaba Szepesvari · Sharan Vaswani · Zheng Wen · Tor Lattimore · Mohammad Ghavamzadeh -
2019 Oral: Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits »
Branislav Kveton · Csaba Szepesvari · Sharan Vaswani · Zheng Wen · Tor Lattimore · Mohammad Ghavamzadeh -
2019 Tutorial: Active Hypothesis Testing: An Information Theoretic (re)View »
Tara Javidi -
2018 Poster: Active Learning with Logged Data »
Songbai Yan · Kamalika Chaudhuri · Tara Javidi -
2018 Oral: Active Learning with Logged Data »
Songbai Yan · Kamalika Chaudhuri · Tara Javidi -
2018 Poster: More Robust Doubly Robust Off-policy Evaluation »
Mehrdad Farajtabar · Yinlam Chow · Mohammad Ghavamzadeh -
2018 Poster: Path Consistency Learning in Tsallis Entropy Regularized MDPs »
Yinlam Chow · Ofir Nachum · Mohammad Ghavamzadeh -
2018 Oral: Path Consistency Learning in Tsallis Entropy Regularized MDPs »
Yinlam Chow · Ofir Nachum · Mohammad Ghavamzadeh -
2018 Oral: More Robust Doubly Robust Off-policy Evaluation »
Mehrdad Farajtabar · Yinlam Chow · Mohammad Ghavamzadeh -
2017 Poster: Active Learning for Accurate Estimation of Linear Models »
Carlos Riquelme Ruiz · Mohammad Ghavamzadeh · Alessandro Lazaric -
2017 Poster: Model-Independent Online Learning for Influence Maximization »
Sharan Vaswani · Branislav Kveton · Zheng Wen · Mohammad Ghavamzadeh · Laks V.S Lakshmanan · Mark Schmidt -
2017 Poster: Online Learning to Rank in Stochastic Click Models »
Masrour Zoghi · Tomas Tunys · Mohammad Ghavamzadeh · Branislav Kveton · Csaba Szepesvari · Zheng Wen -
2017 Poster: Bottleneck Conditional Density Estimation »
Rui Shu · Hung Bui · Mohammad Ghavamzadeh -
2017 Talk: Active Learning for Accurate Estimation of Linear Models »
Carlos Riquelme Ruiz · Mohammad Ghavamzadeh · Alessandro Lazaric -
2017 Talk: Bottleneck Conditional Density Estimation »
Rui Shu · Hung Bui · Mohammad Ghavamzadeh -
2017 Talk: Online Learning to Rank in Stochastic Click Models »
Masrour Zoghi · Tomas Tunys · Mohammad Ghavamzadeh · Branislav Kveton · Csaba Szepesvari · Zheng Wen -
2017 Talk: Model-Independent Online Learning for Influence Maximization »
Sharan Vaswani · Branislav Kveton · Zheng Wen · Mohammad Ghavamzadeh · Laks V.S Lakshmanan · Mark Schmidt