Regret-Based $(ε,δ)$-optimal Stopping Criteria for Bayesian Optimization

• URL: http://arxiv.org/abs/2605.22561v1
• Date: Thu, 21 May 2026 14:42:31 GMT
• Title: Regret-Based $(ε,δ)$-optimal Stopping Criteria for Bayesian Optimization
• Abstract summary: We present provably tighter instantaneous regret bounds for GP upper confidence bound (GP-UCB) at any given iteration.<n>We then propose stopping criteria for GP-UCB based on this tighter bound that ensures an $$-optimal solution with high probability $1-$ upon termination.
• Score: 6.144270713077559
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bayesian optimization (BO) is a widely used iterative black-box optimization method that utilizes Gaussian process (GP) surrogate models. In practice, BO is typically terminated after a fixed evaluation budget is exhausted, which can incur unnecessary cost and provides no optimality guarantee on solution quality. Recent research in developing a practical stopping criterion has made empirical progress, yet a theoretically sound stopping criterion remains a work in progress. In this work, we present provably tighter instantaneous regret bounds for GP upper confidence bound (GP-UCB) at any given iteration. Then, we propose stopping criteria for GP-UCB based on this tighter bound that ensures an $ε$-optimal solution with high probability $1-δ$ upon termination. Numerical experiments are performed to validate and demonstrate the effectiveness and efficiency of our stopping criteria.

Related papers

• Online Sharp-Calibrated Bayesian Optimization [19.176262090411292]
  We propose Online Sharp-Calibrated Bayesian Optimization (OSCBO), a BO algorithm that adaptively balances GP sharpness and calibration.<n>OSCBO performs competitively across synthetic and real-world benchmarks, ranking among the strongest methods in final simple regret.
  arXiv  Detail & Related papers  (2026-05-11T13:41:42Z)
• Robust Bayesian Optimization via Tempered Posteriors [1.6042394978941517]
  We develop a robust GP-based BO via tempered posterior updates to mitigate overconfidence under local misspecifications.<n>We show that tempering yields sharper worst-case regret guarantees than the standard posterior $(=1)$, with the most favorable guarantees occurring near the classical EI choice.
  arXiv  Detail & Related papers  (2026-01-11T23:34:24Z)
• Principled Algorithms for Optimizing Generalized Metrics in Binary Classification [53.604375124674796]
  We introduce principled algorithms for optimizing generalized metrics, supported by $H$-consistency and finite-sample generalization bounds.<n>Our approach reformulates metric optimization as a generalized cost-sensitive learning problem.<n>We develop new algorithms, METRO, with strong theoretical performance guarantees.
  arXiv  Detail & Related papers  (2025-12-29T01:33:42Z)
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  We study stopping rules for gradient descent (SGD) for convex optimization.<n>We develop an anytime-valid, data-dependent upper confidence sequence for the weighted average suboptimality of projected SGD.<n>These are the first rigorous, time-uniform performance guarantees and finitetime $varepsilon$-optimality certificates.
  arXiv  Detail & Related papers  (2025-12-15T09:26:45Z)
• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference [71.09125259964684]
  Test-time compute (TTC) has become an increasingly prominent paradigm for enhancing large language models (LLMs)<n>We study reward-filtered sequential inference, a simple procedure that selectively incorporates only high-reward generations into the context.<n>On the theoretical side, we show that reward-filtered sequential inference yields strictly stronger guarantees than standard TTC paradigms.
  arXiv  Detail & Related papers  (2025-12-04T08:21:33Z)
• Cost-aware Stopping for Bayesian Optimization [46.95172329282389]
  We propose a cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs and is free of tuning.<n>We prove a theoretical guarantee bounding the expected cumulative evaluation cost incurred by our stopping rule when paired with state-of-the-art acquisition functions.
  arXiv  Detail & Related papers  (2025-07-16T17:54:14Z)
• Bayesian Optimization of Robustness Measures under Input Uncertainty: A Randomized Gaussian Process Upper Confidence Bound Approach [3.8979646385036175]
  Black-box functions often involve input uncertainty.<n>Black-box functions often involve input uncertainty.<n>RRGP-UCB is a novel method that samples $beta$ from a chi-squared-based probability distribution.
  arXiv  Detail & Related papers  (2025-04-04T05:01:54Z)
• Stopping Bayesian Optimization with Probabilistic Regret Bounds [1.4141453107129403]
  We investigate replacing a de facto stopping rule with criteria based on the probability that a point satisfies a given set of conditions.<n>We give a practical algorithm for evaluating Monte Carlo stopping rules in a manner that is both sample efficient and robust to estimation error.
  arXiv  Detail & Related papers  (2024-02-26T18:34:58Z)
• Principled Preferential Bayesian Optimization [22.269732173306192]
  We study the problem of preferential Bayesian optimization (BO) We aim to optimize a black-box function with only preference feedback over a pair of candidate solutions. An optimistic algorithm with an efficient computational method is then developed to solve the problem.
  arXiv  Detail & Related papers  (2024-02-08T02:57:47Z)
• Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimation [44.53678257757108]
  We propose a new BO method that can sub-linearly converge to the objective function's global optimum. Our method uses a multi-armed bandit technique (EXP3) to add random data points to the BO process. We demonstrate empirically that our method outperforms existing approaches on various synthetic and real-world problems.
  arXiv  Detail & Related papers  (2023-06-12T03:35:45Z)
• 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)
• 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)
• Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification [119.41129787351092]
  We introduce BBKB, the first no-regret GP optimization algorithm that provably runs in near-linear time and selects candidates in batches. We show that the same bound can be used to adaptively delay costly updates to the sparse GP approximation, achieving a near-constant per-step amortized cost.
  arXiv  Detail & Related papers  (2020-02-23T17:43:29Z)

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.