Practical Efficient Global Optimization is No-regret
Authors: Jingyi Wang, Haowei Wang, Nai-Yuan Chiang, Juliane Mueller, Tucker Hartland, Cosmin G. Petra
Organizations: Lawrence Livermore National Laboratory, CA, USA · National University of Singapore, Singapore · National Laboratory of the Rockies, CO, USA
Efficient global optimization (EGO) is one of the most widely used noise-free Bayesian optimization algorithms.It comprises the Gaussian process (GP) surrogate model and expected improvement (EI) acquisition function. In practice, when EGO is applied, a scalar matrix of a small positive value (also called a nugget or jitter) is usually added to the covariance matrix of the deterministic GP to improve numerical stability. We refer to this EGO with a positive nugget as the practical EGO. Despite its wide adoption and empirical success, to date, cumulative regret bounds for practical EGO have yet to be established. In this paper, we present for the first time the cumulative regret upper bound of practical EGO. In particular, we show that practical EGO has sublinear cumulative regret bounds and thus is a no-regret algorithm for commonly used kernels including the squared exponential (SE) and Matérn kernels (ν>21). Moreover, we analyze the effect of the nugget on the regret bound and discuss the theoretical implication on its choice. Numerical experiments are conducted to support and validate our findings.
Figures & tables
Figure 1: Illustrative example of EI contour of the Branin function with 50 samples. From left to right: contour plots for ϵ=10−2 , ϵ=10−6 , ϵ=10−10 , and no nugget. The maximum EI 50 value from left to right: 2.53×10−2 , 1.90×10−4 , 4.72×10−5 , and 4.72×10−5 .
Figure 2: Cumulative regret upper bound with nugget ϵ at different T and selected constants for SE kernel. The case “other” means neither the conditions for case 1 nor those for case 2 are satisfied.
d
kernel
ϵ
t=1
t=50
t=100
t=200
2
SE
10−10
0.596
0.091
0.058
0.040
2
SE
10−6
0.596
0.141
0.101
0.076
2
SE
10−4
0.596
0.153
0.120
0.097
2
Matérn
10−10
0.393
0.061
0.031
0.016
2
Matérn
10−6
0.393
0.055
0.028
0.015
2
Matérn
10−4
0.393
0.054
0.028
0.016
Table 1: The average accumulative regret for different iteration over 20 macro-replications.
Figure 3: Median average cumulative regret bound for practical EGO with ϵ values 10−2 , 10−4 , and 10−6 for five examples. From top to bottom: Rosenbrock, Six-hump camel, Hartmann6, Branin, Michalewicz functions.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Cumulative regret upper bound with nugget ϵ at different T and selected constants for Matérn kernel ( ν=21 ). The case “other” means neither the conditions for case 1 nor those for case 2 are satisfied.
Figure 5: Illustrative example of EI contour of the Branin function with 50 random samples. From left to right: contour plots for ϵ=10−2 , ϵ=10−6 , ϵ=10−10 , and no nugget. The maximum EI 50 value from left to right: 0.40515 , 0.40085 , 0.40085 , and 0.40085 . The maximum level of the colorbar corresponds to the maximum of EI 50 of each plot.
Figure 6: 25th and 75th percentile average cumulative regret for practical EGO with nugget values 10−2 , 10−4 , and 10−6 for five examples.
Existing cumulative regret guarantees for Bayesian optimization (BO) do not necessarily characterize the quality of the algorithm's final output. This gap is critical under noisy evaluations, where the goal is to return a single high-quality recommendation. To address it, we introduce efficient exploration strategies that can be incorporated into any BO procedure by occasionally replacing the acquisition query with an exploration query. To validate this approach, we bound the Gaussian process posterior standard deviation over the search space via the fill distance of the queries, which measures the largest region left unexplored. We then use this result to derive upper bounds on the inference regret, i.e., the gap between the global optimum and the function value at the algorithm's returned point. Empirically, these exploration strategies improve the final recommendations of existing BO algorithms on synthetic benchmarks, hyperparameter optimization, and a control task.
Hwanwoo Kim, Jungwoo Hong, Kyungjae Lee
Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University
We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields γ~T/T=O(ε1/2) and expected average regret O(ε1/4) in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on 1/ε.
Matthias Mandl, Hanne Kekkonen
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
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.