Timezone: »
Poster
Optimal Order Simple Regret for Gaussian Process Bandits
Sattar Vakili · Nacime Bouziani · Sepehr Jalali · Alberto Bernacchia · Da-shan Shiu
Consider the sequential optimization of a continuous, possibly non-convex, and expensive to evaluate objective function $f$. The problem can be cast as a Gaussian Process (GP) bandit where $f$ lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows a significant gap between the lower and upper bounds on the simple regret performance. When $N$ is the number of exploration trials and $\gamma_N$ is the maximal information gain, we prove an $\tilde{\mathcal{O}}(\sqrt{\gamma_N/N})$ bound on the simple regret performance of a pure exploration algorithm that is significantly tighter than the existing bounds. We show that this bound is order optimal up to logarithmic factors for the cases where a lower bound on regret is known. To establish these results, we prove novel and sharp confidence intervals for GP models applicable to RKHS elements which may be of broader interest.
Author Information
Sattar Vakili (MediaTek Research)
Nacime Bouziani (Imperial College London)
Sepehr Jalali (Mediatek Research)
Alberto Bernacchia (MediaTek Research)
Da-shan Shiu (University of California Berkeley)
More from the Same Authors
-
2021 : How to distribute data across tasks for meta-learning? »
Alexandru Cioba · Michael Bromberg · Qian Wang · RITWIK NIYOGI · Georgios Batzolis · Jezabel Garcia · Da-shan Shiu · Alberto Bernacchia -
2022 : Gradient Descent: Robustness to Adversarial Corruption »
Fu-Chieh Chang · Farhang Nabiei · Pei-Yuan Wu · Alexandru Cioba · Sattar Vakili · Alberto Bernacchia -
2023 Poster: Kerenlized Reinforcement Learning with Order Optimal Regret Bounds »
Sattar Vakili · Iuliia Olkhovskaia -
2022 : Poster Session 2 »
Jinwuk Seok · Bo Liu · Ryotaro Mitsuboshi · David Martinez-Rubio · Weiqiang Zheng · Ilgee Hong · Chen Fan · Kazusato Oko · Bo Tang · Miao Cheng · Aaron Defazio · Tim G. J. Rudner · Gabriele Farina · Vishwak Srinivasan · Ruichen Jiang · Peng Wang · Jane Lee · Nathan Wycoff · Nikhil Ghosh · Yinbin Han · David Mueller · Liu Yang · Amrutha Varshini Ramesh · Siqi Zhang · Kaifeng Lyu · David Yunis · Kumar Kshitij Patel · Fangshuo Liao · Dmitrii Avdiukhin · Xiang Li · Sattar Vakili · Jiaxin Shi -
2022 Poster: Near-Optimal Collaborative Learning in Bandits »
Clémence Réda · Sattar Vakili · Emilie Kaufmann -
2021 : Escaping the abstraction: a foreign function interface for the Unified Form Language [UFL] »
Nacime Bouziani -
2021 : Cyclic orthogonal convolutions for long-range integration of features »
Federica Freddi · Jezabel Garcia · Michael Bromberg · Sepehr Jalali · Da-shan Shiu · Alvin Chua · Alberto Bernacchia -
2021 Poster: Natural continual learning: success is a journey, not (just) a destination »
Ta-Chu Kao · Kristopher Jensen · Gido van de Ven · Alberto Bernacchia · Guillaume Hennequin -
2021 Poster: A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance »
Sudeep Salgia · Sattar Vakili · Qing Zhao -
2021 Poster: Scalable Thompson Sampling using Sparse Gaussian Process Models »
Sattar Vakili · Henry Moss · Artem Artemev · Vincent Dutordoir · Victor Picheny -
2020 Poster: Non-reversible Gaussian processes for identifying latent dynamical structure in neural data »
Virginia Rutten · Alberto Bernacchia · Maneesh Sahani · Guillaume Hennequin -
2020 Oral: Non-reversible Gaussian processes for identifying latent dynamical structure in neural data »
Virginia Rutten · Alberto Bernacchia · Maneesh Sahani · Guillaume Hennequin -
2018 Poster: Exact natural gradient in deep linear networks and its application to the nonlinear case »
Alberto Bernacchia · Mate Lengyel · Guillaume Hennequin