Timezone: »
Poster
The Multi-fidelity Multi-armed Bandit
Kirthevasan Kandasamy · Gautam Dasarathy · Barnabas Poczos · Jeff Schneider
We study a variant of the classical stochastic $K$-armed bandit where observing the outcome of each arm is expensive, but cheap approximations to this outcome are available. For example, in online advertising the performance of an ad can be approximated by displaying it for shorter time periods or to narrower audiences. We formalise this task as a \emph{multi-fidelity} bandit, where, at each time step, the forecaster may choose to play an arm at any one of $M$ fidelities. The highest fidelity (desired outcome) expends cost $\costM$. The $m$\ssth fidelity (an approximation) expends $\costm < \costM$ and returns a biased estimate of the highest fidelity. We develop \mfucb, a novel upper confidence bound procedure for this setting and prove that it naturally adapts to the sequence of available approximations and costs thus attaining better regret than naive strategies which ignore the approximations. For instance, in the above online advertising example, \mfucbs would use the lower fidelities to quickly eliminate suboptimal ads and reserve the larger expensive experiments on a small set of promising candidates. We complement this result with a lower bound and show that \mfucbs is nearly optimal under certain conditions.
Author Information
Kirthevasan Kandasamy (CMU)
Gautam Dasarathy (Carnegie Mellon University)
Barnabas Poczos (Carnegie Mellon University)
Jeff Schneider (CMU)
More from the Same Authors
-
2020 Poster: Modeling Task Effects on Meaning Representation in the Brain via Zero-Shot MEG Prediction »
Mariya Toneva · Otilia Stretcu · Barnabas Poczos · Leila Wehbe · Tom Mitchell -
2020 Poster: Robust Density Estimation under Besov IPM Losses »
Ananya Uppal · Shashank Singh · Barnabas Poczos -
2020 Spotlight: Robust Density Estimation under Besov IPM Losses »
Ananya Uppal · Shashank Singh · Barnabas Poczos -
2019 Workshop: Sets and Partitions »
Nicholas Monath · Manzil Zaheer · Andrew McCallum · Ari Kobren · Junier Oliva · Barnabas Poczos · Ruslan Salakhutdinov -
2019 Poster: Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses »
Ananya Uppal · Shashank Singh · Barnabas Poczos -
2019 Oral: Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses »
Ananya Uppal · Shashank Singh · Barnabas Poczos -
2019 Poster: Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels »
Simon Du · Kangcheng Hou · Russ Salakhutdinov · Barnabas Poczos · Ruosong Wang · Keyulu Xu -
2019 Poster: Offline Contextual Bayesian Optimization »
Ian Char · Youngseog Chung · Willie Neiswanger · Kirthevasan Kandasamy · Oak Nelson · Mark Boyer · Egemen Kolemen · Jeff Schneider -
2019 Poster: Learning Local Search Heuristics for Boolean Satisfiability »
Emre Yolcu · Barnabas Poczos -
2018 Poster: Nonparametric Density Estimation under Adversarial Losses »
Shashank Singh · Ananya Uppal · Boyue Li · Chun-Liang Li · Manzil Zaheer · Barnabas Poczos -
2018 Poster: Neural Architecture Search with Bayesian Optimisation and Optimal Transport »
Kirthevasan Kandasamy · Willie Neiswanger · Jeff Schneider · Barnabas Poczos · Eric Xing -
2018 Spotlight: Neural Architecture Search with Bayesian Optimisation and Optimal Transport »
Kirthevasan Kandasamy · Willie Neiswanger · Jeff Schneider · Barnabas Poczos · Eric Xing -
2017 Oral: Deep Sets »
Manzil Zaheer · Satwik Kottur · Siamak Ravanbakhsh · Barnabas Poczos · Ruslan Salakhutdinov · Alexander Smola -
2017 Poster: Hypothesis Transfer Learning via Transformation Functions »
Simon Du · Jayanth Koushik · Aarti Singh · Barnabas Poczos -
2017 Poster: MMD GAN: Towards Deeper Understanding of Moment Matching Network »
Chun-Liang Li · Wei-Cheng Chang · Yu Cheng · Yiming Yang · Barnabas Poczos -
2017 Poster: Deep Sets »
Manzil Zaheer · Satwik Kottur · Siamak Ravanbakhsh · Barnabas Poczos · Ruslan Salakhutdinov · Alexander Smola -
2017 Poster: Gradient Descent Can Take Exponential Time to Escape Saddle Points »
Simon Du · Chi Jin · Jason D Lee · Michael Jordan · Aarti Singh · Barnabas Poczos -
2017 Spotlight: Gradient Descent Can Take Exponential Time to Escape Saddle Points »
Simon Du · Chi Jin · Jason D Lee · Michael Jordan · Aarti Singh · Barnabas Poczos -
2016 Poster: Variance Reduction in Stochastic Gradient Langevin Dynamics »
Kumar Avinava Dubey · Sashank J. Reddi · Sinead Williamson · Barnabas Poczos · Alexander Smola · Eric Xing -
2016 Poster: Finite-Sample Analysis of Fixed-k Nearest Neighbor Density Functional Estimators »
Shashank Singh · Barnabas Poczos -
2016 Poster: Learning HMMs with Nonparametric Emissions via Spectral Decompositions of Continuous Matrices »
Kirthevasan Kandasamy · Maruan Al-Shedivat · Eric Xing -
2016 Poster: Proximal Stochastic Methods for Nonsmooth Nonconvex Finite-Sum Optimization »
Sashank J. Reddi · Suvrit Sra · Barnabas Poczos · Alexander Smola -
2016 Poster: Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations »
Kirthevasan Kandasamy · Gautam Dasarathy · Junier B Oliva · Jeff Schneider · Barnabas Poczos -
2016 Poster: Efficient Nonparametric Smoothness Estimation »
Shashank Singh · Simon Du · Barnabas Poczos -
2015 Poster: Nonparametric von Mises Estimators for Entropies, Divergences and Mutual Informations »
Kirthevasan Kandasamy · Akshay Krishnamurthy · Barnabas Poczos · Larry Wasserman · james m robins -
2015 Poster: On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants »
Sashank J. Reddi · Ahmed Hefny · Suvrit Sra · Barnabas Poczos · Alexander Smola -
2014 Workshop: Modern Nonparametrics 3: Automating the Learning Pipeline »
Eric Xing · Mladen Kolar · Arthur Gretton · Samory Kpotufe · Han Liu · Zoltán Szabó · Alan L Yuille · Andrew G Wilson · Ryan Tibshirani · Sasha Rakhlin · Damian Kozbur · Bharath Sriperumbudur · David Lopez-Paz · Kirthevasan Kandasamy · Francesco Orabona · Andreas Damianou · Wacha Bounliphone · Yanshuai Cao · Arijit Das · Yingzhen Yang · Giulia DeSalvo · Dmitry Storcheus · Roberto Valerio -
2014 Poster: Flexible Transfer Learning under Support and Model Shift »
Xuezhi Wang · Jeff Schneider -
2014 Poster: Exponential Concentration of a Density Functional Estimator »
Shashank Singh · Barnabas Poczos -
2013 Poster: Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition »
Tzu-Kuo Huang · Jeff Schneider -
2013 Poster: Σ-Optimality for Active Learning on Gaussian Random Fields »
Yifei Ma · Roman Garnett · Jeff Schneider -
2011 Poster: Group Anomaly Detection using Flexible Genre Models »
Liang Xiong · Barnabas Poczos · Jeff Schneider -
2011 Poster: Learning Auto-regressive Models from Sequence and Non-sequence Data »
Tzu-Kuo Huang · Jeff Schneider -
2010 Poster: Learning Multiple Tasks with a Sparse Matrix-Normal Penalty »
Yi Zhang · Jeff Schneider -
2010 Poster: Estimation of Renyi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs »
David Pal · Barnabas Poczos · Csaba Szepesvari -
2008 Poster: Learning the Semantic Correlation: An Alternative Way to Gain from Unlabeled Text »
Yi Zhang · Jeff Schneider · Artur Dubrawski