Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds

• URL: http://arxiv.org/abs/2302.01511v2
• Date: Mon, 12 Jun 2023 02:27:53 GMT
• Title: Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds
• Authors: Shion Takeno, Yu Inatsu, Masayuki Karasuyama
• Abstract summary: This study first generalizes the regret analysis of RGP-UCB to a wider class of distributions, including the Gamma distribution. We propose improved RGP-UCB based on a two- parameter exponential distribution, which achieves tighter Bayesian regret bounds. We demonstrate the effectiveness of IRGP-UCB through extensive experiments.
• Score: 9.89553853547974
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Gaussian process upper confidence bound (GP-UCB) is a theoretically promising approach for black-box optimization; however, the confidence parameter $\beta$ is considerably large in the theorem and chosen heuristically in practice. Then, randomized GP-UCB (RGP-UCB) uses a randomized confidence parameter, which follows the Gamma distribution, to mitigate the impact of manually specifying $\beta$. This study first generalizes the regret analysis of RGP-UCB to a wider class of distributions, including the Gamma distribution. Furthermore, we propose improved RGP-UCB (IRGP-UCB) based on a two-parameter exponential distribution, which achieves tighter Bayesian regret bounds. IRGP-UCB does not require an increase in the confidence parameter in terms of the number of iterations, which avoids over-exploration in the later iterations. Finally, we demonstrate the effectiveness of IRGP-UCB through extensive experiments.

Related papers

• Regret Analysis for Randomized Gaussian Process Upper Confidence Bound [9.967062483758632]
  This paper analyzes the randomized variant of GP-UCB called improved randomized GP-UCB. In both regret analyses, IRGP-UCB achieves a sub-linear regret upper bound without increasing the confidence parameter if the input domain is finite.
  arXiv  Detail & Related papers  (2024-09-02T06:49:29Z)
• Regret Optimality of GP-UCB [12.323109084902228]
  Gaussian Process Upper Confidence Bound (GP-UCB) is one of the most popular methods for optimizing black-box functions with noisy observations. We establish new upper bounds on both the simple and cumulative regret of GP-UCB when the objective function to optimize admits certain smoothness property. With the same level of exploration, GP-UCB can simultaneously achieve optimality in both simple and cumulative regret.
  arXiv  Detail & Related papers  (2023-12-03T13:20:08Z)
• Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds [22.752728853701083]
  Gaussian process upper confidence bound (GP-UCB) and Thompson sampling (TS) are well-known options with established theoretical properties regarding Bayesian cumulative regret (BCR) We show that PIMS achieves the tighter BCR bound and avoids the hyper parameter tuning, unlike GP-UCB. We demonstrate a wide range of experiments, focusing on the effectiveness of PIMS that mitigates the practical issues of GP-UCB and TS.
  arXiv  Detail & Related papers  (2023-11-07T06:54:40Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
  arXiv  Detail & Related papers  (2023-07-14T13:56:11Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• Likelihood-Free Inference with Deep Gaussian Processes [70.74203794847344]
  Surrogate models have been successfully used in likelihood-free inference to decrease the number of simulator evaluations. We propose a Deep Gaussian Process (DGP) surrogate model that can handle more irregularly behaved target distributions. Our experiments show how DGPs can outperform GPs on objective functions with multimodal distributions and maintain a comparable performance in unimodal cases.
  arXiv  Detail & Related papers  (2020-06-18T14:24:05Z)
• Uncertainty quantification using martingales for misspecified Gaussian processes [52.22233158357913]
  We address uncertainty quantification for Gaussian processes (GPs) under misspecified priors. We construct a confidence sequence (CS) for the unknown function using martingale techniques. Our CS is statistically valid and empirically outperforms standard GP methods.
  arXiv  Detail & Related papers  (2020-06-12T17:58:59Z)
• Randomised Gaussian Process Upper Confidence Bound for Bayesian Optimisation [60.93091603232817]
  We develop a modified Gaussian process upper confidence bound (GP-UCB) acquisition function. This is done by sampling the exploration-exploitation trade-off parameter from a distribution. We prove that this allows the expected trade-off parameter to be altered to better suit the problem without compromising a bound on the function's Bayesian regret.
  arXiv  Detail & Related papers  (2020-06-08T00:28:41Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.