Tight Regret Bounds for Bayesian Optimization in One Dimension

Jonathan Scarlett
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4500-4508, 2018.

Abstract

We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions on the kernel, the best possible cumulative regret up to time $T$ behaves as $\Omega(\sqrt{T})$ and $O(\sqrt{T\log T})$. This gives a tight characterization up to a $\sqrt{\log T}$ factor, and includes the first non-trivial lower bound for noisy BO. Our assumptions are satisfied, for example, by the squared exponential and Matérn-$\nu$ kernels, with the latter requiring $\nu > 2$. Our results certify the near-optimality of existing bounds (Srinivas et al., 2009) for the SE kernel, while proving them to be strictly suboptimal for the Matérn kernel with $\nu > 2$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-scarlett18a, title = {Tight Regret Bounds for {B}ayesian Optimization in One Dimension}, author = {Scarlett, Jonathan}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4500--4508}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/scarlett18a/scarlett18a.pdf}, url = {https://proceedings.mlr.press/v80/scarlett18a.html}, abstract = {We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions on the kernel, the best possible cumulative regret up to time $T$ behaves as $\Omega(\sqrt{T})$ and $O(\sqrt{T\log T})$. This gives a tight characterization up to a $\sqrt{\log T}$ factor, and includes the first non-trivial lower bound for noisy BO. Our assumptions are satisfied, for example, by the squared exponential and Matérn-$\nu$ kernels, with the latter requiring $\nu > 2$. Our results certify the near-optimality of existing bounds (Srinivas et al., 2009) for the SE kernel, while proving them to be strictly suboptimal for the Matérn kernel with $\nu > 2$.} }
Endnote
%0 Conference Paper %T Tight Regret Bounds for Bayesian Optimization in One Dimension %A Jonathan Scarlett %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-scarlett18a %I PMLR %P 4500--4508 %U https://proceedings.mlr.press/v80/scarlett18a.html %V 80 %X We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions on the kernel, the best possible cumulative regret up to time $T$ behaves as $\Omega(\sqrt{T})$ and $O(\sqrt{T\log T})$. This gives a tight characterization up to a $\sqrt{\log T}$ factor, and includes the first non-trivial lower bound for noisy BO. Our assumptions are satisfied, for example, by the squared exponential and Matérn-$\nu$ kernels, with the latter requiring $\nu > 2$. Our results certify the near-optimality of existing bounds (Srinivas et al., 2009) for the SE kernel, while proving them to be strictly suboptimal for the Matérn kernel with $\nu > 2$.
APA
Scarlett, J.. (2018). Tight Regret Bounds for Bayesian Optimization in One Dimension. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4500-4508 Available from https://proceedings.mlr.press/v80/scarlett18a.html.

Related Material