Source-linked AI summary
Portfolio Allocation for Bayesian Optimization
Eric Brochu, Matthew W. Hoffman, Nando de Freitas
TL;DR
Bayesian optimization lacks a universally best acquisition function, complicating efficient optimization of expensive objectives. The paper uses an online bandit-managed portfolio of acquisition functions, with GP-Hedge as its leading strategy. Experiments show adaptive portfolios generally outperform the best individual acquisition function, while the paper also derives a regret bound whose convergence guarantee is limited.
Problem
No single acquisition function is guaranteed to perform best across arbitrary unknown objectives, creating a selection problem in Bayesian optimization.
Method
The paper manages a portfolio of acquisition functions with online multi-armed bandit hedging, using Gaussian-process modeling and GP-Hedge as the best-performing strategy.
Results
Adaptive acquisition-function portfolios often perform substantially better—and almost never worse—than the best-performing individual acquisition function.
Takeaways & Limitations
Portfolio strategies can adapt acquisition-function selection to the optimization problem, with full-information methods often outperforming partial-information methods.
Takeaways & Limitations
The regret theorem does not guarantee convergence, and hedging regret cannot be directly compared with the best underlying strategy because actions alter future problem states and rewards.
Abstract
from arXiv · showhide
Bayesian optimization with Gaussian processes has become an increasingly popular tool in the machine learning community. It is efficient and can be used when very little is known about the objective function, making it popular in expensive black-box optimization scenarios. It uses Bayesian methods to sample the objective efficiently using an acquisition function which incorporates the model's estimate of the objective and the uncertainty at any given point. However, there are several different parameterized acquisition functions in the literature, and it is often unclear which one to use. Instead of using a single acquisition function, we adopt a portfolio of acquisition functions governed by an online multi-armed bandit strategy. We propose several portfolio strategies, the best of which we call GP-Hedge, and show that this method outperforms the best individual acquisition function. We also provide a theoretical bound on the algorithm's performance.
1 Introduction
Bayesian optimization efficiently optimizes expensive, noisy black-box objectives, but selecting an acquisition function is difficult because no single method works best across all function classes. The paper addresses this with an adaptive portfolio managed by hierarchical hedging.
- Motivation: Bayesian optimization uses a posterior over the unknown objective and an acquisition function to balance exploration and exploitation when selecting samples.It is useful when evaluations are costly, derivatives are unavailable, or the objective is non-convex.
- Motivation: The method targets expensive objectives that lack closed-form expressions but can be evaluated noisily at sampled points.The paper lists applications including robot gait design, path planning, algorithm configuration, and reinforcement learning.
- Problem: No acquisition function works well for every class of objective function, making the choice among proposed methods nontrivial.The paper frames this as the problem its portfolio strategy is designed to address.
- Approach: The paper proposes a hierarchical hedging approach that manages an adaptive portfolio of acquisition functions.Its experiments compare hedging approaches with individual acquisition functions, and the paper also presents a performance bound.
2 Bayesian optimization
Bayesian optimization alternates between updating a Gaussian-process surrogate from noisy observations and maximizing an acquisition function to choose the next evaluation. The section reviews the GP model and common acquisition functions, including their exploration parameters and regret properties.
- Gaussian-process model: Bayesian optimization models the unknown objective with a GP posterior updated from accumulated observations D1:t.The posterior is obtained by combining a GP prior with the likelihood of the observed data and serves as a surrogate response surface.
- Bayesian-optimization procedure: At each iteration, the procedure maximizes the acquisition function over the GP, samples the selected point, and augments the dataset with its noisy observation.The observation model is yt = f(xt) + ϵt.
- Gaussian-process model: The objective is assigned a GP prior with mean m(x) and covariance k(xi, xj), commonly using a squared-exponential kernel with ARD hyperparameters.The presentation assumes a zero prior mean and notes that hyperparameter choice is difficult when data are scarce.
- Acquisition functions: Acquisition functions assign high values to points with high predicted objectives, high uncertainty, or both, and their maxima determine the next evaluation location.The auxiliary acquisition maximization is treated as an easier numerical optimization problem than evaluating the objective.
- Acquisition functions: PI favors improvement probability, EI also accounts for improvement magnitude, and UCB combines posterior mean with weighted uncertainty.PI uses ξ as a trade-off parameter, while UCB uses κ to weight variance.
- Regret: GP-UCB has cumulative regret bounded by O(√TβTγT), whose sublinear form supports a no-regret interpretation under the stated conditions.The bound depends on the learning rate, information gain, and kernel choice.
- Regret: The reviewed GP-UCB regret bound can be quite loose in practice.This caveat is stated after relating average regret to the optimization gap.
3 Portfolio strategies
The paper treats acquisition-function selection as a hierarchical multi-armed bandit problem and evaluates hedging strategies that adaptively combine acquisition functions. GP-Hedge uses full-information rewards from the GP model, while portfolio size and information availability affect which strategy is suitable.
- Portfolio formulation: Because no acquisition function is guaranteed to be best on an arbitrary unknown objective, a portfolio may outperform every single acquisition function.The portfolio is formulated as a hierarchical bandit whose arms are acquisition functions with their own point-selection problems.
- GP-Hedge: Hedge selects acquisition functions using probabilities based on cumulative rewards, then updates gains for the candidate actions.In Bayesian optimization, each arm nominates a point by maximizing its acquisition function.
- GP-Hedge: GP-Hedge defines each nominee’s reward from the expected value of the GP model at that nominee, enabling full-information updates for every acquisition function.The reward definition is considered reasonable when the objective is smooth.
- Alternative strategies: Exp3 adapts hedging to partial information by using the selected action’s reward and mixing the hedging distribution with uniform exploration.This reduces the risk of overlooking actions whose initial rewards were low.
- Alternative strategies: NormalHedge is designed for many arms and may be poorly matched to problems with relatively small portfolios.The paper distinguishes strategy suitability by the number of acquisition-function arms.
- Computational considerations: GP-Hedge requires optimizing all N acquisition functions each iteration, but objective evaluations usually dominate costs when N is small.Fast approximate acquisition optimization is also reported as generally sufficient.
- Empirical comparison: With N = 3, GP-Hedge beats the best individual acquisition function in almost all cases; with N = 9, adding individually weaker parameter settings improves long-run performance.The figure compares three literature test functions and shows portfolio probabilities over iterations.
4 Experiments
The experiments evaluate GP-Hedge and related acquisition portfolios on standard, synthetic, and control problems. Across these settings, mixed strategies generally outperform individual acquisition functions, especially as optimization difficulty and dimensionality increase.
- Experimental settings: GP-Hedge was evaluated on standard Bayesian-optimization functions, synthetic functions sampled from GP priors, and a nonlinear particle-control task.The standard functions were Branin, Hartman 3, and Hartman 6; the synthetic experiments varied dimensionality, and the control task used a 9D repeller-parameter optimization.
- 4.1 Standard test functions: The 9-function GP-Hedge variant was almost always the best method across function and time-step combinations in the standard-function experiments.The authors suggest that additional acquisition functions help exploration early, while exploitative methods receive more probability later as exploitation becomes more rewarding.
- 4.1 Standard test functions: Under the gap measure, GP-Hedge outperformed other mixed strategies as problem difficulty and dimensionality increased.The uniform portfolio performed well on easier functions but degraded on Hartman 6, while NormalHedge could collapse to an exclusively exploitative portfolio.
- 4.1 Standard test functions: Under average regret, hedging strategies performed comparably to GP-UCB, whereas the gap measure provided a more direct comparison of optimization performance.Average regret was included to enable comparison with previous work, but the authors note that its bound can be loose and that final incumbent regret is often the more relevant quantity.
- 4.2 Sampled test functions: In sampled GP-prior functions, GP-Hedge with N = 9 was best overall, while GP-UCB performed well at 10D and 20D but poorly at 40D.The authors attribute the 40D behavior to GP-UCB favoring high-variance regions in an extremely sparse search space.
- 4.3 Control of a particle simulation: On the particle-control task, GP-Hedge outperformed each constituent method, while PI performed particularly poorly on the plateau-heavy objective.The control problem used trajectories of falling particles and a finite, large time horizon; PI struggled to explore after locking onto a mode.
5 Convergence behaviour
The paper cannot directly relate GP-Hedge’s regret to that of the best acquisition strategy because each strategy selects different points and changes future rewards. A bound is obtained only under simplifying assumptions, but it does not guarantee convergence.
- Convergence limitations: Directly comparing GP-Hedge with the best underlying acquisition strategy is problematic because their decisions produce different future points and rewards.The algorithm’s choices affect the state of the optimization problem at every later iteration.
- Proof assumptions: The analysis assumes rewards equal the posterior mean µ_t−1(x_t) and that GP-UCB is included among the candidate acquisition functions.These assumptions simplify the proof and enable use of GP-UCB convergence results.
- Theorem 1: Theorem 1 bounds cumulative regret with high probability when GP-Hedge includes GP-UCB and the information gain after T iterations is bounded by γ_T.The theorem is stated under a collection of acquisition strategies and a suitable information-gain bound.
- Interpretation of the bound: The bound contains two sub-linear terms and an additional term depending on information gained at points proposed by GP-UCB but not necessarily selected.The extra term reflects the relation between proposed points and previously selected points.
6 Conclusions and future work
The paper concludes that adaptive portfolios of acquisition functions usually match or exceed the best individual function, while full-information strategies often outperform partial-information strategies. It also presents a regret bound that offers intuition but not a convergence guarantee.
- Conclusions: Adaptive portfolios of acquisition functions perform substantially better—and almost never worse—than the best-performing individual acquisition function.This conclusion is based on the paper’s experiments.
- Strategy tradeoffs: Full-information hedging strategies outperform partial-information strategies in many situations, while partial-information methods can help when N is high or advice conflicts strongly.The paper identifies these conditions as tradeoffs for future study.
- Theory: The paper gives a regret bound for its hedging strategy by relating performance to existing GP-UCB bounds, although the bound does not guarantee convergence.The bound nevertheless provides intuition for hedging methods’ empirical success.
A Proof of Theorem 1
The appendix proves the GP-Hedge regret theorem by combining Hedge regret with Gaussian-process concentration, information-gain, variance, and GP-UCB bounds. The proof retains a term for GP-UCB points that Hedge proposes but does not select.
- Proof setup: The proof models portfolio selection with Hedge using rewards r_t = µ_t−1(x_t), where rewards depend on the actions actually taken by Hedge.The gain of each strategy is considered in hindsight over T steps.
- Hedging bound: Hedge’s regret lemma applies for rewards in [0,1] and extends to arbitrary ranges, unknown horizons, and the partial-information strategy Exp3.The parameter η can be made time-varying to remove the requirement that T be known.
- Gaussian-process bounds: The Gaussian-process lemmas bound posterior-mean deviations, information gain, and sums of variances for points selected by the algorithm.The information-gain bound applies to many common kernels, including the squared-exponential kernel.
- GP-UCB component: A separate GP-UCB lemma bounds the relevant terms for points proposed by GP-UCB, without requiring those points to have been selected previously by GP-UCB.This lets the proof use GP-UCB guarantees inside the Hedge analysis.
- Proof boundary: The variance-sum lemma cannot simplify terms for GP-UCB-proposed points because it applies only to points sampled by the algorithm.Hedge may propose GP-UCB points without selecting them.
B Synthetic test functions
The experiments construct synthetic objectives from Gaussian-process priors because no generally agreed test-function suite exists for higher-dimensional Bayesian optimization. Performance is evaluated against an approximate optimum, with repeller-control results averaged over 25 runs.
- Synthetic objectives: Synthetic functions are sampled from a known Gaussian-process prior to address the lack of a generally agreed higher-dimensional Bayesian-optimization test suite.The practical construction samples points and uses the posterior mean as the synthetic objective.
- Objective construction: Each trial draws ARD-kernel parameters uniformly from [0, 2]^d, samples 100d points, and draws function values from N(0, K).The resulting predictive posterior mean µ(x) serves as the test function.
- Evaluation: The objective maximum f(x⋆) is approximated with conventional global optimization so the gap metric can be computed.The sampled construction points are not revealed to the Bayesian-optimization methods.
- Repeller control: Figure 5 averages the progress of each Bayesian-optimization method over 25 runs, alongside 10 sample trajectories over 100 time-steps for one repeller configuration.The displayed repeller configuration is not necessarily optimal.