On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
Authors: Xu Cai, Jonathan Scarlett
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm is some Reproducing Kernel Hilbert Space (RKHS), which can be viewed as a non-Bayesian Gaussian process bandit problem. In the standard noisy setting, we provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability. In a robust setting in which every sampled point may be perturbed by a suitablyconstrained adversary, we provide a novel lower bound for deterministic strategies, demonstrating an inevitable joint dependence of the cumulative regret on the corruption level and the time horizon, in contrast with existing lower bounds that only characterize the individual dependencies. Furthermore, in a distinct robust setting in which the final point is perturbed by an adversary, we strengthen an existing lower bound that only holds for target success probabilities very close to one, by allowing for arbitrary success probabilities above 2 |
| Researcher Affiliation | Academia | 1Department of Computer Science, National University of Singapore 2Department of Mathematics & Institute of Data Science, National University of Singapore. Correspondence to: Xu Cai <caix@u.nus.edu>, Jonathan Scarlett <scarlett@comp.nus.edu.sg>. |
| Pseudocode | No | The paper presents mathematical analyses and proofs, but does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any specific links or statements about the availability of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve experiments on datasets, so there is no mention of public or open datasets for training. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments. Therefore, there is no discussion of dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper and does not involve running experiments on specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper and does not involve running experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that provides mathematical proofs and analyses, not empirical experiments. Therefore, there are no experimental setup details like hyperparameters or training configurations. |