Source-linked AI summary
Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions
Amar Shah, Zoubin Ghahramani
TL;DR
The paper addresses expensive global optimization when evaluations are noisy and batches must be selected in parallel, a setting with few established non-greedy methods. It develops PPES, which chooses batches to maximize information gain about the global maximizer without greedy batch construction. Experiments on synthetic and real-world objectives report consistently strong optimization performance, while the method relies on approximations with identified limitations.
Problem
Expensive, noisy black-box optimization requires selecting parallel evaluation batches, but existing batch Bayesian optimization methods use greedy construction.
Method
PPES selects a batch by maximizing expected information gain about the location of the global maximizer under a Gaussian-process Bayesian optimization model.
Results
PPES consistently outperforms competing methods on the tested functions and performs close to best or best across the synthetic benchmarks.
Takeaways & Limitations
PPES provides a non-greedy batch Bayesian optimization strategy that can improve optimization performance on synthetic and real-world objectives.
Takeaways & Limitations
The method approximates the global-maximizer posterior with constraints and may perform poorly when a sampled maximizer has a significantly suboptimal posterior mean.
Abstract
from arXiv · showhide
We develop parallel predictive entropy search (PPES), a novel algorithm for Bayesian optimization of expensive black-box objective functions. At each iteration, PPES aims to select a batch of points which will maximize the information gain about the global maximizer of the objective. Well known strategies exist for suggesting a single evaluation point based on previous observations, while far fewer are known for selecting batches of points to evaluate in parallel. The few batch selection schemes that have been studied all resort to greedy methods to compute an optimal batch. To the best of our knowledge, PPES is the first non-greedy batch Bayesian optimization strategy. We demonstrate the benefit of this approach in optimization performance on both synthetic and real world applications, including problems in machine learning, rocket science and robotics.
1 Introduction
Expensive, noisy evaluations make global optimization of unknown, non-concave objectives costly, motivating Bayesian methods and especially non-greedy batch selection. PPES addresses the limited availability of batch strategies by selecting points jointly for information gain about the global maximizer.
- Motivation: Global optimization seeks the maximizer of an unknown, non-concave objective using as few expensive sequential queries as possible.Evaluations may incur computational, economic, or other costs.
- Bayesian optimization: Bayesian optimization models the unknown objective probabilistically and chooses evaluations using a utility function based on posterior beliefs.It has been applied to expensive tasks including robot-controller optimization and chemical discovery.
- Bayesian optimization: Bayesian optimization requires choices about both the model for f and the strategy for selecting the next evaluation location.Gaussian processes are common because they are flexible and support analytic calculations, although other models are also useful.
- Batch selection: Few established methods select evaluation batches, and existing batch strategies use greedy procedures that add points individually until the batch is full.The paper motivates avoiding greedy selection because it can produce severely poor global solutions.
- Contribution: PPES is presented as a non-greedy batch strategy that selects points to maximize expected uncertainty reduction about the objective's maximizer.It extends predictive entropy search to multiple-point batch selection and is evaluated on synthetic and real-world objectives.
2 Problem Statement and Background
The paper formulates parallel Bayesian optimization as noisy batch evaluation under a Gaussian-process model, with decisions aimed at reducing regret. Prior batch methods extend single-point acquisition rules through greedy construction, whereas PPES avoids greedy batch selection.
- Problem formulation: At each decision, the algorithm selects Q points for parallel noisy evaluation over a compact domain, seeking to maximize f while minimizing future regret.The objective is modeled as a Gaussian-process draw with constant mean and differentiable kernel.
- Single-point strategies: Most Bayesian optimization methods focus on selecting one point, commonly by maximizing expected improvement over the current best evaluation.For Q > 1, the corresponding expected-improvement strategy lacks an analytic expression.
- Prior batch methods: EI-MCMC constructs a batch sequentially using Monte Carlo approximations, making it greedy both in one-step improvement and in batch construction.Its batch is populated point by point until it reaches size Q.
- Prior batch methods: GP-BUCB and GP-UCB-PE also populate batches greedily, using predictive variance or information gain to choose successive points.GP-BUCB updates variance while maintaining the same posterior mean within a batch, whereas GP-UCB-PE explores a high-probability relevant region.
- PPES: The paper identifies PPES as a batch Bayesian optimization method that avoids greedy selection of individual points.This addresses the stated gap that existing batch methods resort to greedy batch selection.
3 Parallel Predictive Entropy Search
PPES selects parallel evaluation batches by maximizing expected information about the global maximizer, using entropy reformulations and approximations that make the objective tractable. It combines expectation propagation with MAP or random-feature sampling of the maximizer posterior.
- 3.1 Approximating the Predictive Entropy: PPES chooses a batch of Q points to maximize information about the location of the global maximizer.The objective is formulated through negative differential entropy or mutual information involving the maximizer and predictive observations.
- 3.1 Approximating the Predictive Entropy: The mutual-information formulation replaces intractable entropy calculations over the maximizer with entropies of predictive observation distributions.Predictive-distribution entropies are easier to approximate than entropies over the global maximizer.
- 3.1 Approximating the Predictive Entropy: Expectation propagation approximates the maximizer-conditioned predictive distribution by enforcing that the maximizer exceeds values at queried and previously observed locations.The two constraints require f(x*) to exceed current query values and the largest noisy observation, with noise accounted for in the latter condition.
- 3.1 Approximating the Predictive Entropy: The resulting Gaussian approximation yields analytically computable predictive entropies for the batch observations.Marginalization and Gaussian noise produce an approximate multivariate Gaussian observation distribution whose entropy has a closed-form determinant expression.
- 3.2 Sampling from the Posterior over the Global Maximizer: PPES approximates the posterior over the global maximizer using either a MAP estimate or random-feature function samples optimized with gradient-based methods.MAP is convenient but does not characterize the full posterior; random features provide approximate samples from the function posterior and their maximizers.
- 3.3 Computing and Optimizing the PPES Approximation: Random-feature approximations avoid the O(m^3) cost of repeatedly evaluating an expensive sampled function while locating its optimum.The method samples finite-dimensional features and posterior weights, constructs an analytic function, and optimizes it.
4 Empirical Study
The empirical study evaluates PPES against four batch Bayesian optimization methods on synthetic and real-world objectives, using median immediate regret across repeated experiments. PPES performs close to best on synthetic benchmarks and consistently outperforms competitors on the reported real-world functions, while its approximation is visually similar to the ground-truth acquisition function.
- Acquisition approximation: The EP-based acquisition approximation has a surface similar to the ground truth, with peaks appearing at the same input locations in the reported experiment.The approximation is described as an annealed version, with more pronounced peaks and flatter non-peak areas.
- Synthetic objectives: PPES performs close to best or best on four synthetic benchmarks with batch size Q = 3.It significantly outperforms GP-UCB-PE on 3 of 4 problems, although EI-MCMC performs better on Hartmann-6.
- Real-world objectives: PPES consistently outperforms competing methods on the reported real-world functions with batch sizes Q = 2 and Q = 4.The comparison reports median immediate regret over 200 random initializations.
- Real-world objectives: On hydrogen, PPES has mediocre initial immediate regret but improves rapidly as more batches are evaluated.This pattern is reported alongside PPES’s overall advantage on the real-world functions.
- Real-world objectives: PPES handles the discontinuous rocket objective best, producing fewer zero-valued samples and fewer zero-valued recommendations than competing methods.The rocket objective returns zero when the simulated rocket fails to return to Earth.
5 Conclusions
The paper develops PPES as an information-theoretic batch Bayesian optimization method that maximizes one-step information gain without greedily selecting individual batch points. The authors report that competing methods can under-explore, harming performance on multi-modal, noisy objectives.
- Conclusion: PPES maximizes one-step information gain about x∗ while selecting the batch non-greedily.Previous methods are described as doubly greedy because they look one step ahead and fill batches greedily.
- Conclusion: Competing methods can under-explore, which hurts performance on multi-modal, noisy objective functions.This conclusion is based on the paper’s experiments.
- Conclusion: PPES is presented as an information theoretic approach to batch Bayesian optimization.The method targets information about the location of the global maximizer.
Appendix
The appendix describes an expectation-propagation approximation for a constrained Gaussian-process predictive distribution. It replaces indicator and Gaussian-cdf factors with scaled Gaussian site factors and iteratively updates their parameters until convergence.
- Predictive distribution: The predictive vector f+ follows a multivariate Gaussian distribution N(f+; m+, K+).The vector includes batch function values and the global-maximizer function value.
- Constraints: The approximation imposes that f(x∗) exceeds every queried function value and previous noisy observations.These conditions define the event C being approximated.
- Expectation propagation: Expectation propagation approximates each indicator function and Gaussian cdf with a univariate scaled Gaussian density.The resulting site parameters are optimized through approximate inference updates.
- Expectation propagation: Products of Gaussian factors yield a Gaussian approximation w(f+) = ZN(f+; µ+, Σ+).The approximation is represented through updated mean and covariance parameters.
- Expectation propagation: The EP iterations compute cavity distributions, perform moment matching, update site parameters, and repeat until convergence.The final predictive parameters µ+ and Σ+ are updated after the site updates.