On the Sublinear Regret of GP-UCB
Authors: Justin Whitehouse, Aaditya Ramdas, Steven Z. Wu
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we resolve this open question and show that GP-UCB enjoys nearly optimal regret. In particular, our results yield sublinear regret rates for the Mat ern kernel, improving over the state-of-the-art analyses and partially resolving a COLT open problem posed by Vakili et al. Our improvements rely on a key technical contribution regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel k. Applying this key idea together with a largely overlooked concentration result in separable Hilbert spaces (for which we provide an independent, simplified derivation), we are able to provide a tighter analysis of the GP-UCB algorithm. |
| Researcher Affiliation | Academia | Justin Whitehouse Carnegie Mellon University jwhiteho@andrew.cmu.edu Zhiwei Steven Wu Carnegie Mellon University zstevenwu@cmu.edu Aaditya Ramdas Carnegie Mellon University aramdas@cmu.edu |
| Pseudocode | Yes | Algorithm 1 Gaussian Process Upper Confidence Bound (GP-UCB) |
| Open Source Code | No | The paper does not provide any links to open-source code or state that the source code for the described methodology is available. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets, thus it does not provide information about public dataset availability for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies involving dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup requiring specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not discuss specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameter values or training configurations. |