Source-linked AI summary
Maximizing acquisition functions for Bayesian optimization
James T. Wilson, Frank Hutter, Marc Peter Deisenroth
TL;DR
Bayesian optimization depends on difficult inner maximization of acquisition functions, especially for parallel, non-convex, high-dimensional, and intractable objectives. The paper develops gradient-based optimization for Monte Carlo acquisitions and greedy maximization for a submodular family, finding reliable and often substantial performance gains as acquisition dimensionality increases. Its guarantees and setup remain bounded by assumptions including finite ground sets and parallel-query modeling.
Problem
Acquisition-function maximization is difficult in BO, particularly when parallel query optimization makes objectives non-convex, high-dimensional, and intractable.
Method
The paper uses reparameterization and differentiation under the expectation for Monte Carlo acquisitions, and exploits submodularity to justify greedy maximization.
Results
Gradient-based and submodular maximization improve outer-loop performance, with gains becoming more pronounced as acquisition dimensionality increases.
Takeaways & Limitations
Gradient information and greedy submodular strategies provide practical techniques for finite-time parallel Bayesian optimization.
Takeaways & Limitations
The submodular-maximization guarantee requires a finite ground set, while extensions to infinite ground sets were not undertaken.
Abstract
from arXiv · showhide
Bayesian optimization is a sample-efficient approach to global optimization that relies on theoretically motivated value heuristics (acquisition functions) to guide its search process. Fully maximizing acquisition functions produces the Bayes' decision rule, but this ideal is difficult to achieve since these functions are frequently non-trivial to optimize. This statement is especially true when evaluating queries in parallel, where acquisition functions are routinely non-convex, high-dimensional, and intractable. We first show that acquisition functions estimated via Monte Carlo integration are consistently amenable to gradient-based optimization. Subsequently, we identify a common family of acquisition functions, including EI and UCB, whose properties not only facilitate but justify use of greedy approaches for their maximization.
1 Introduction
Bayesian optimization applies Bayesian decision theory to costly black-box global optimization, but maximizing its acquisition function is difficult in practice. The paper addresses this gap with gradient-based Monte Carlo optimization and greedy maximization of submodular acquisitions.
- Bayesian optimization seeks global maximizers of costly black-box functions while minimizing incurred evaluation costs.
- Acquisition maximization implements Bayes’ decision rule but is difficult enough that treating it as a black box causes systematic departure from BO’s premise.
- The paper optimizes Monte Carlo acquisition functions using sample-path derivatives and identifies submodular acquisitions suitable for greedy maximization.
- Submodular acquisition properties support efficient greedy maximization with guaranteed near-optimal results.
2 Background
Bayesian optimization combines a probabilistic surrogate with an acquisition function to select query sets, yet the resulting inner optimization is often non-convex, high-dimensional, and intractable. These difficulties intensify with parallelism and costly acquisition proxies.
- Parallelism: Parallel BO evaluates q designs in X ∈ Rq×d, with q = 1 recovering sequential decision-making.
- Surrogate models: A surrogate model represents plausible explanations for the black-box function and produces a probabilistic belief over outcomes.
- Acquisition functions: An acquisition function combines the surrogate belief with utility to assign expected value to evaluating query sets.
- Inner optimization problem: Maximizing the acquisition function converts surrogate-based machinery into concrete query decisions in BO’s outer loop.
- Inner optimization problem: Acquisition optimization becomes harder as input dimension d and parallelism q increase because functions are non-convex and acquisition dimensionality scales with q.
- Acquisition functions: Acquisition functions are often analytically intractable, and evaluating their proxies can become increasingly costly over time.
3 Maximizing acquisition functions
The paper develops two complementary ways to optimize Bayesian-optimization acquisition functions: differentiating Monte Carlo estimators and greedily maximizing myopic maximal acquisitions. Reparameterization supports unbiased gradient estimation, while submodularity provides theoretical justification for greedy query selection.
- Overview: The section addresses gradient-based optimization of Monte Carlo acquisitions and greedy maximization of myopic maximal acquisitions.These are presented as the paper’s two complementary technical contributions.
- 3.1 Differentiating Monte Carlo acquisitions: Reparameterization expresses samples as deterministic mappings of simpler random variables, making their dependence on distribution parameters differentiable.For a multivariate normal, the mapping is φ(z; θ) = µ + Lz, with L the Cholesky factor of Σ.
- 3.1 Differentiating Monte Carlo acquisitions: Differentiable sample paths and justified interchange of differentiation and expectation yield unbiased Monte Carlo gradient estimators under stated regularity conditions.For Gaussian processes with twice differentiable kernels and unique query locations, these conditions establish an unbiased gradient estimator for parallel q-EI.
- 3.1 Differentiating Monte Carlo acquisitions: Concrete continuous-to-discrete approximations make discontinuous utilities such as Probability of Improvement and Entropy Search amenable to differentiation.The sigmoid approximation uses temperature τ and becomes exact as τ → 0.
- 3.2 Maximizing myopic maximal acquisitions: Myopic maximal acquisitions include EI, PI, SR, and UCB, and their expected-max structure makes them particularly suitable for greedy maximization.The expected-max formulation is L(X) = E_y[max ˆℓ(y)].
- 3.2 Maximizing myopic maximal acquisitions: The myopic maximal family is submodular, so greedy maximization produces near-optimal query sets at each Bayesian-optimization outer-loop step.The result applies the submodular structure directly to the acquisition functions rather than using submodularity only for outer-loop regret analysis.
- 3.2 Maximizing myopic maximal acquisitions: Incremental forms are particularly efficient because their marginal gains often admit closed-form solutions, while Monte Carlo integration estimates otherwise intractable fantasy-based integrals.Incremental approaches also reduce Monte Carlo sample variance and can reuse cached expensive computations.
4 Experiments
Experiments compare acquisition maximizers under synthetic and black-box tasks, varying dimensionality, parallelism, runtime budgets, and Monte Carlo estimation choices. Gradient-based and submodular strategies generally improve Bayesian optimization performance, with larger benefits as acquisition dimensionality grows.
- Experimental settings: Synthetic and black-box experiments varied input dimensionality, parallelism, and inner runtime budgets while evaluating acquisition maximizers.Synthetic tasks used a known GP prior; black-box tasks withheld knowledge of the function prior and used online MAP estimation.
- Acquisition functions: The experiments focused on parallel Monte Carlo EI and UCB, with incremental q-EI results reserved for extended results to avoid confounding comparisons.Trials used Gaussian measurement noise with variance 1e−3 and averaged results over 32 independent trials.
- Maximizer comparisons: Gradient-based maximizers consistently outperformed gradient-free and naïve alternatives across the evaluated settings.The comparison used stochastic gradient ascent, CMA-ES, and Random Search under CPU-runtime constraints.
- Maximizer comparisons: Submodular maximizers generally surpassed their joint counterparts, although their advantage declined in lower-dimensional cases where gradients alone could optimize the estimator.The benefits of combining gradients with submodular maximization increased with acquisition dimensionality q × d.
- Black-box results: The same maximizer trends largely held on black-box tasks with an unknown GP prior, indicating that model mismatch did not eliminate their influence.On Hartmann-6, performance improved with greater parallelism when the inner optimization budget increased correspondingly.
5 Conclusion
The paper develops practical approaches for optimizing Monte Carlo acquisition functions and submodular acquisition functions in Bayesian optimization. Empirical evidence indicates that these techniques can improve performance when parallel queries must be selected within finite time.
- Monte Carlo acquisition functions provide unbiased gradient estimates that can be exploited during optimization.
- Many of the same acquisition functions form submodular set functions that can be efficiently optimized greedily.
- The proposed techniques are presented as general-purpose practices for practical Bayesian optimization.
- Empirical evidence reports substantial performance gains in real-world scenarios where queries must be chosen in finite time.
A.1 Concrete approximations
Concrete relaxations replace discontinuous discrete events with temperature-controlled continuous mappings, enabling differentiation through Monte Carlo acquisition estimates. As temperature approaches zero, the approximations converge to the corresponding true acquisition functions.
- Discrete events derived from continuous outcomes are typically discontinuous, preventing direct interchange of differentiation and expectation.
- A concrete approximation introduces a temperature parameter τ and relaxes one-hot categorical events into continuous mappings for τ > 0.
- The relaxed event satisfies the conditions needed to interchange differentiation and expectation.
- For multivariate normal beliefs, reparameterized samples use φ(z; θ) = µ + L g(z), allowing concrete approximations for Entropy Search and Probability of Improvement integrands.
- As τ →0, the Monte Carlo approximations converge to the corresponding true functions, whereas high temperatures wash them out.
A.2 Parallel Upper Confidence Bound (q-UCB)
The paper derives a parallel UCB representation whose marginalization recovers q′-UCB and whose q-dimensional integral can be estimated without heuristic approximations.
- Parallel UCB: The derivation rewrites parallel UCB using Gaussian integrals and rescaled covariance parameters.The representation uses ˆΣ = (βπ/2)Σ and an integrand involving µ and |ˆLz|.
- Marginal consistency: For any subset of q′ ≤ q queries, marginalizing the remaining terms recovers the corresponding q′-UCB value.
- Estimation: Directly addressing the q-dimensional integral avoids the heuristic approximations used by sequentially imitating parallel-UCB methods.The resulting estimator is unbiased for the true value.
- Interpretation: The integral form gives an intuitive interpretation as the expectation of a Gaussian variable above its mean.
A.3 Normalizing utility functions
The paper establishes normalization conditions for submodular acquisition utilities, showing that EI, PI, and UCB can be normalized under explicit assumptions while Simple Regret is technically harder.
- Expected Improvement: EI becomes normalized and submodular when improvement is rectified before taking the maximum.The integrand is ℓEI(y; α) = max(ReLU(y −α)).
- Probability of Improvement: PI is already normalized because its Heaviside-valued integrand maps outcomes to {0, 1}.
- Simple Regret: Simple Regret requires a finite lower bound on the utility, making its submodular maximization the hardest case to justify.The earlier assumption vmin = 0 is insufficient for the more general normalization argument.
- Upper Confidence Bound: UCB can be normalized when the minimum predictive mean vmin is finite.For a zero-mean GP with a twice differentiable kernel, this condition is guaranteed for bounded functions f.
- LEI: For LEI, the expected-improvement-of-improvement integrand simplifies using the initial improvement threshold α.
B.1 Experiment Details
Experiments use synthetic functions drawn from a known GP prior and compare gradient-based, gradient-free, and naïve acquisition maximizers under practical initialization and runtime strategies.
- Synthetic tasks: Synthetic tasks eliminate model error by drawing functions from a known prior.The functions are constructed from weighted Fourier-basis samples for a GP with a continuous stationary kernel.
- Maximizers: ADAM consistently outperformed the other tested gradient-based approaches, while CMA-ES repeatedly outperformed DIRECT.
- Initialization: Gradient-based optimization is sensitive to initialization because acquisition functions are non-convex and contain low-utility plateaus.
- Initialization: Sampling initial query points from the marginal acquisition function avoids excluded regions and produced consistent gains with most optimizers.Initialization consumed the first tenth of the allocated runtime.
- Asynchronous optimization: Pending queries are handled by fantasizing predictive-mean observations, which promotes query diversity but produced only modest performance changes.
B.3 Extended Results
Extended experiments compare acquisition maximizers across q-UCB and q-EI settings, showing broad advantages for gradient-based and submodular approaches alongside a higher-dimensional exception for incremental q-EI.
- Extended experiments: Additional q-UCB and incremental q-EI experiments use conditions identical to those in Section 4.
- Parallel UCB: Except on Levy, q-UCB outperformed q-EI, including on Branin-Hoo and Hartmann-3.The confidence parameter was β = 2.
- Incremental q-EI: CMA-ES with incremental q-EI outperformed gradient-based optimization on higher-dimensional acquisition surfaces.This contrasts with the larger body of results.
- Incremental q-EI: Figure 8 compares greedy incremental q-EI with m = 16 against greedy joint q-EI.
- q-UCB evaluation: Figures 6 and 7 report log10 immediate regret while varying runtime for Monte Carlo q-UCB on known-prior synthetic and unknown-prior black-box tasks.