Source-linked AI summary
Optimization, fast and slow: optimally switching between local and Bayesian optimization
Mark McLeod, Michael A. Osborne, Stephen J. Roberts
TL;DR
Bayesian optimization often relies on manually fixed evaluation budgets, while local stopping criteria can ignore the full objective model. BLOSSOM switches between Bayesian acquisition functions and local optimization, and stops at a specified expected-regret tolerance. On tested objectives, it improves the final result by several orders of magnitude over existing methods.
Problem
Fixed budgets require manual choices, while existing local stopping criteria do not consider the full model and need user-selected thresholds.
Source: §1.2 · pp. 1–2Method
BLOSSOM switches between multiple acquisition functions and local optimization, using a Bayesian stopping criterion based on a specified expected-regret tolerance.
Source: §1.1 · p. 1Results
BLOSSOM improves the final result by several orders of magnitude over existing methods and has the lowest mean terminal regret and mean product of regret and iterations on five of six test objectives.
Source: §4.2 · p. 7, §5 · p. 9Takeaways & Limitations
The method combines evaluation-efficient Bayesian optimization and local convergence, and can stop once the expected-regret tolerance is achieved.
Source: §1.1 · p. 1Common benchmark functions can be extremely dissimilar to the Matérn 5/2 GP model; the tests use an ad-hoc output transformation, while a better-matched kernel or online transform would be preferable.
Source: §4.2 · p. 6
Abstract
from arXiv · showhide
We develop the first Bayesian Optimization algorithm, BLOSSOM, which selects between multiple alternative acquisition functions and traditional local optimization at each step. This is combined with a novel stopping condition based on expected regret. This pairing allows us to obtain the best characteristics of both local and Bayesian optimization, making efficient use of function evaluations while yielding superior convergence to the global minimum on a selection of optimization problems, and also halting optimization once a principled and intuitive stopping condition has been fulfilled.
1. Introduction
BLOSSOM combines Bayesian and local optimization with a stopping criterion based on expected regret. The introduction motivates this design by the difficulty of choosing stopping budgets and by numerical limits on convergence.
1.1. Bayesian Optimization with Gaussian Processes
- BLOSSOM selects among multiple acquisition functions and local optimization at each iteration, then stops when a specified expected-regret tolerance is achieved.This combines Bayesian optimization’s evaluation efficiency with local optimization’s convergence, without requiring a fixed budget.Source: §1.1 · p. 1
1.2. Requirement for a Stopping Criterion
- Fixed iteration or computational budgets require manual choices that risk either neglecting easy improvements or paying for expensive evaluations with minimal gain.Existing early-stopping criteria based on consecutive evaluations or incumbent improvement are local and require user-selected values, unlike the preferred full-model criterion.Source: §1.2 · pp. 1–2
1.3. Convergence Properties
- Approximate acquisition maximization and diagonal noise limit convergence, while covariance conditioning worsens as evaluations cluster near the minimum.The algorithm is designed to avoid this ineffective exploitation and terminate once a well-defined condition is met.Source: §1.3 · p. 2
- On Hartman-4D, PES achieves good regret quickly, but added jitter yields no further improvement beyond roughly √jitter.The figure reports median and quartiles across 16 repetitions.Source: Figure 1 · p. 2
2. The Algorithm
BLOSSOM separates local from global regret, then switches among Bayesian optimization, global-regret reduction, and local optimization according to candidate-minimum and regret criteria.
2.1. Separating Global and Local Regret
- Total regret is split into a local gap from the candidate to its basin minimum and a global gap from that minimum to the true global minimum.Local exploitation reduces the local component; exploration and exploitation of other minima reduce the global component.Source: §2.1 · p. 3
2.2. Multiple Acquisition Functions
- BLOSSOM uses random initialization, PES by default, Global Regret Reduction when a convex candidate-minimum region is identified, and local optimization after global regret falls below its target.The methods reuse expensive computations shared with PES to limit additional overhead.Source: §2.2 · p. 3
2.2.2. LOCAL OPTIMIZATION
- Under noiseless evaluations, BLOSSOM starts BFGS in a predicted convex region, rescales using the GP Hessian estimate, and stops at gradient <10^-6.The stated local-search condition can be used to bring local regret below a desired target.Source: §2.2 · p. 3, §2.2.2 · pp. 3–4
2.2.1. GLOBAL REGRET REDUCTION
- Global Regret Reduction modifies expected improvement by comparing against the estimated minimum yi obtainable from local optimization, rather than the lowest observed objective value.The acquisition uses the GP posterior mean and variance and the unit Normal cdf and pdf.Source: §2.2.1 · p. 3
2.3. Switching Between Acquisition Functions
- A high-confidence convex region around the posterior-mean minimum triggers Global Regret Reduction; sufficiently low estimated global regret then triggers local exploitation.If the regret target is not met, Bayesian iterations continue with Global Regret Reduction.Source: §2.3 · p. 4
3. Estimating Required Quantities
This section estimates the quantities needed by the switching criteria: pointwise and regional convexity, alongside global regret and expected local minimum value.
3.1. Identifying a Convex Region
- The procedure estimates pointwise Hessian-convexity probabilities and seeks the largest region around the posterior minimum meeting a required probability of convexity throughout.Source: §3.1 · p. 5
3.1.1. CONVEXITY AT A POINT
- At a point, Hessian draws from the GP posterior are tested for positive definiteness using Cholesky decomposition, and a uniform-prior Bernoulli posterior mean sets the pass threshold.Passing corresponds to E(θ) = 1 − 1/(n+2).Source: §3.1.1 · p. 5
3.1.2. RADIUS OF A CONVEX REGION
- The convex region is estimated as a hypersphere centered at the posterior minimum, with radius given by the minimum positive-definite distance across sampled directions.Directions are sampled uniformly, and binary line searches locate their positive-definite radii.Source: §3.1.2 · pp. 5–6
- Global regret is estimated by marginalizing over local and global minima, assuming their values are independent and approximating local-minimum values with a normal distribution.Because the global-minimum distribution lacks an analytic form, its marginalization is approximated by a summation.Source: §3.1.2 · p. 6
- GP support-point draws approximate the global-minimum distribution using McLeod et al. (2017) for half and variance-weighted rejection sampling for the remainder.The same draws estimate the local-minimum distribution using only points within the convex region.Source: §3.1.2 · p. 6
4. Results
BLOSSOM’s results cover GP-drawn objectives, common benchmark functions, and GP hyperparameter optimization. Across the benchmarks, it combines low terminal regret with early stopping, while the target regret affects reliability and evaluation count.
4.2. Common Benchmark Functions
- The common benchmarks use an ad hoc log transform because their flat plains and steep sides differ greatly from the Matérn 5/2 GP’s shape.The authors suggest a more suitable kernel or online output-space transformation as preferable alternatives.Source: §4.2 · p. 6
- Mean steps multiplied by regret, E[nR], is used because neither step count nor regret alone captures stopping performance; lower values indicate improvement.The metric’s equal contours take the form y = a x.Source: §4.2 · p. 6
4.1. In-Model Objectives
- On Matérn 5/2 GP-drawn objectives, the 10^-6 target reached the global minimum in all 35 runs, while no stopping condition had one failure.The experiments use GP-drawn objectives because the target-regret effect may not appear on a single fixed objective; the authors report roughly achieving requested expected-regret values.Source: §4.1 · p. 6, Figure 4 · p. 7
4.2. Common Benchmark Functions
- BLOSSOM achieves the lowest mean terminal regret and mean regret–iteration product on five of six common objectives; a 10^-4 target improves reliability over 10^-2 at the cost of more evaluations.When the GP places the predicted global minimum in the wrong basin, a lower target requires additional exploration and provides more chances to identify the correct basin.Source: §4.2 · p. 7
4.3. GP Hyperparameter Optimization
- For GP hyperparameter log-likelihood, BLOSSOM achieved the best absolute result and several orders of magnitude better terminal convergence than PES or EI, while stopping within a reasonable number of iterations.The test optimized GP input and output scale hyperparameters using UK electricity-demand measurements.Source: §4 · p. 6, §4.3 · p. 7, Figure 6 · p. 7
5. Conclusion
BLOSSOM switches between Bayesian and local optimization and stops when a specified expected-regret tolerance is met. The paper reports improved final results and savings from stopping after convergence rather than continuing for many steps.
5. Conclusion
- BLOSSOM selects among multiple acquisition functions and local optimization, then stops once the specified expected-regret tolerance is achieved.This is intended to retain Bayesian optimization’s evaluation efficiency alongside local optimization’s convergence.Source: §5 · pp. 7, 9
- All stopping criteria save, on average, steps beyond convergence, while BLOSSOM reliably reaches a low regret before stopping.Figure 5 displays median and quartiles of regret and dashed curves for the fraction of optimizations still running.Source: Figure 5 · p. 8
- BLOSSOM achieved the best regret and step-regret product on five of six common objectives.The step-regret product combines final regret with the number of steps taken.Source: Table 1 · p. 8