PaperlayerView exact revision on arXiv

Source-linked AI summary

Predictive Entropy Search for Efficient Global Optimization of Black-box Functions

José Miguel Hernández-Lobato, Matthew W. Hoffman, Zoubin Ghahramani

arXiv:1406.2541v1stat.MLcs.LG

TL;DR

Bayesian optimization must locate optima of noisy, expensive black-box functions with few evaluations. PES reformulates information gain about the global maximum using predictive entropy, samples posterior maximizers, and marginalizes hyperparameters. Across synthetic and real-world problems, the paper reports more accurate approximations than ES and improved optimization performance, while relying on simplified constraints in its predictive approximation.

  • Problem

    Bayesian optimization seeks global maxima of noisy, expensive black-box functions, but directly evaluating information about the maximizer is infeasible.

  • Method

    PES maximizes expected information about the global maximizer by expressing the objective through predictive-distribution entropies and marginalizing model hyperparameters.

  • Results

    PES produces more accurate approximations than Entropy Search and achieves significant gains in optimization performance on synthetic and real-world functions.

  • Takeaways & Limitations

    PES provides an information-theoretic Bayesian optimization strategy that combines predictive-entropy approximation with fully Bayesian hyperparameter treatment.

  • Takeaways & Limitations

    The predictive approximation uses simplified constraints, and fixing the Hessian constraint can produce poor predictions when the actual function violates it.

Abstract

from arXiv · show

We propose a novel information-theoretic approach for Bayesian optimization called Predictive Entropy Search (PES). At each iteration, PES selects the next evaluation point that maximizes the expected information gained with respect to the global maximum. PES codifies this intractable acquisition function in terms of the expected reduction in the differential entropy of the predictive distribution. This reformulation allows PES to obtain approximations that are both more accurate and efficient than other alternatives such as Entropy Search (ES). Furthermore, PES can easily perform a fully Bayesian treatment of the model hyperparameters while ES cannot. We evaluate PES in both synthetic and real-world applications, including optimization problems in machine learning, finance, biotechnology, and robotics. We show that the increased accuracy of PES leads to significant gains in optimization performance.

1 Introduction

Bayesian optimization addresses expensive, noisy black-box optimization by modeling the unknown function and selecting evaluations through acquisition functions. This section motivates PES as an information-based alternative to optimistic exploration–exploitation strategies.

  • Motivation: Bayesian optimization seeks the global maximizer of a generally nonconvex black-box function whose evaluations may be noisy and expensive.Modeling the unknown function aims to reduce the number of evaluations needed to find the optimum.
  • Applications: Bayesian optimization has applications including robotics, computer graphics, drug discovery, and statistical or machine-learning hyperparameter tuning.These applications involve optimizing parameters through black-box evaluations.
  • Probabilistic modeling: The method uses a probabilistic model of the latent function to guide sequential evaluation choices.The paper uses a zero-mean Gaussian process prior with a kernel-defined covariance structure.
  • Acquisition functions: An acquisition function combines the predictive distribution with a search rule to choose the next evaluation location.The acquisition should favor likely maxima while encouraging exploration so the recommendation is not merely a posterior-mean optimum.
  • PES motivation: PES maximizes expected information about the posterior distribution of the global maximizer rather than relying on optimistic estimates of the latent function.The paper derives a rearrangement and approximation intended to improve accuracy over ES and reports performance gains from that improvement.

2 Predictive entropy search

PES reformulates information gain about the global maximizer as an entropy difference over predictive observations, making the acquisition easier to approximate. It samples candidate maximizers, approximates constrained predictive distributions, and marginalizes model hyperparameters.

  • Information objective: PES selects evaluations by maximizing expected information about the global maximizer through a reduction in its posterior differential entropy.The direct objective is intractable because updated maximizer distributions and their entropies are difficult to compute repeatedly.
  • Predictive entropy reformulation: Mutual-information symmetry rewrites the objective as predictive entropy H[p(y|Dn, x)] minus predictive entropy conditioned on the maximizer.Conditioning on x⋆ raises predictions near the maximizer and lowers them away from it, while predictive entropies are analytic or easier to approximate.
  • Sampling posterior maxima: PES samples approximate posterior maximizers by drawing finite-feature posterior functions and optimizing each sampled function.Random Fourier features convert the Gaussian process into a finite linear model, and maximizing each approximate sample yields x⋆ samples.
  • Approximating predictive entropy: The conditioned predictive distribution is approximated by replacing global-maximality constraints with local-maximum, observed-best-value, and pointwise comparison constraints.These constraints are incorporated as factors or Gaussian approximations to obtain the conditional predictive variance and entropy.
  • Approximation caveats: The approximation modifies dependence when numerical instability occurs and replaces a fixed Hessian constraint with the sampled function’s Hessian estimate.These adjustments address instability near x and x⋆ and poor predictions when the actual function violates the fixed constraint.
  • Hyperparameter learning: PES marginalizes its acquisition approximation over the posterior distribution of model hyperparameters, unlike the cited fixed-hyperparameter alternative.The paper identifies averaging that alternative over multiple hyperparameter samples as computationally infeasible.

3 Experiments

Experiments evaluate PES approximation accuracy and optimization performance on synthetic and real-world functions, comparing it with ES, EI, and PES-NB. PES more closely matches rejection-sampling ground truth and often achieves lower immediate regret, while performance depends on problem characteristics.

  • Approximation accuracy: PES produces an objective approximation more similar to rejection-sampling ground truth than ES.The reported discrepancy near x = (0.572, 0.687) is attributed to rejection-sampling discretization.
  • Synthetic objectives: PES, ES, and EI are compared using immediate regret on synthetic black-box objectives, with recommendations defined by posterior-mean maximizers.The synthetic experiment reports the median immediate regret across 1000 generated objective functions.
  • Synthetic benchmarks: PES outperforms PES-NB and ES overall across Branin-Hoo, cosine-mixture, and Hartmann-6 benchmark functions.PES beats EI on Branin and cosine functions, whereas EI is significantly better on Hartmann.
  • Real-world functions: PES, ES, and PES-NB perform similarly on NNet, Hydrogen, and Portfolio, while EI performs poorly on those functions.On Walker datasets, PES is better than PES-NB and ES, and it beats EI on the noisier Walker B.
  • Real-world functions: EI performs best on Walker A, where its more greedy behavior is advantageous, while entropy-based methods explore more aggressively.The authors associate this difference with the relative simplicity of the Hartmann and Walker A problems and the higher exploration of entropy-based strategies.

4 Conclusions

The paper proposes PES as an information-theoretic Bayesian optimization method for locating global maxima. It reformulates an intractable acquisition function, supports hyperparameter marginalization, and often improves immediate regret over ES and EI.

  • 4 Conclusions: PES greedily maximizes one-step information about the global maximum location using posterior differential entropy.Its acquisition objective is reformulated through entropy in the posterior predictive distribution of function evaluations.
  • 4 Conclusions: PES produces more accurate acquisition approximations than ES and can marginalize over posterior model hyperparameters, unlike ES.The conclusion attributes the approximation to a reparameterization using predictive-distribution entropy.
  • 4 Conclusions: Across synthetic and real-world experiments, PES often outperforms ES in immediate regret and often performs better than EI.The conclusion contrasts PES's greater exploration with EI's more excessively greedy decisions.

A Details on approximating GP sample paths

The appendix explains how random Fourier features approximate Gaussian-process sample paths. A Bayesian linear model over these features recovers the GP predictive quantities through kernel inner products.

  • Kernel approximation: Bochner's theorem connects continuous shift-invariant positive-definite kernels with spectral densities.The kernel's spectral measure is normalized into a probability density used to construct random features.
  • Kernel approximation: Random features use sampled weights and phases to form a finite-dimensional feature map whose expected inner product equals the kernel.The construction averages cosine features and yields k(x, x′) = E[φ(x)^Tφ(x′)].
  • Bayesian linear representation: A Bayesian linear model f(x) = φ(x)^Tθ with Gaussian parameters produces a Gaussian posterior over θ from noisy observations.The posterior parameters are then used to obtain the predictive distribution at test points.
  • Bayesian linear representation: Using the matrix-inversion lemma expresses predictive quantities through feature inner products, whose expectations recover the original GP kernel formulas.This establishes equivalence between the random-feature Bayesian linear model and the GP with kernel k.

B Details on approximating the predictive variance

The appendix provides further details for approximating the GP predictive variance conditional on a proposed global optimizer location. It expands steps omitted from the main presentation.

  • Predictive variance: The appendix details how to approximate the predictive variance v_n(x|x⋆) for inputs x conditioned on the global optimizer x⋆.It explicitly supplies steps omitted from Section 2.2.

B.1 Incorporating the analytic latent constraints (C1.1)

The method begins by introducing random variables for the analytic latent constraint and constructing a kernel matrix over these variables and the constraint variables.

  • B.1 Incorporating the analytic latent constraints (C1.1): The random variables are introduced as the starting point for incorporating analytic latent constraint C1.1.
  • B.1 Incorporating the analytic latent constraints (C1.1): The kernel matrix is built from covariance evaluations on the stacked vector [z; c], including derivative observations and observation-noise variance for terms corresponding to yi.
  • B.1 Incorporating the analytic latent constraints (C1.1): Conditioning on the observed values of c provides the next step for enforcing constraint C1.1.

B.2 Incorporating the non-analytic latent constraints (C1.2 and C2)

The non-analytic constraints are represented with Gaussian and non-Gaussian factors, then approximated using expectation propagation and moment matching.

  • B.2 Incorporating the non-analytic latent constraints (C1.2 and C2): Constraints C1.2 and C2 are introduced as one Gaussian factor together with d + 1 non-Gaussian factors.
  • B.2 Incorporating the non-analytic latent constraints (C1.2 and C2): The resulting distribution is approximated by a single multivariate Gaussian whose non-Gaussian factors are replaced by Gaussian approximations.
  • B.2 Incorporating the non-analytic latent constraints (C1.2 and C2): The Gaussian approximation combines factor parameters into a vector of means and a diagonal matrix of variances.
  • B.2 Incorporating the non-analytic latent constraints (C1.2 and C2): Expectation propagation initializes factor parameters, forms cavity distributions by removing each factor, and iteratively refines the approximations.
  • B.2 Incorporating the non-analytic latent constraints (C1.2 and C2): Each tilted distribution replaces one approximate factor with its corresponding real factor, after which the Gaussian approximation matches the first two moments.
  • B.2 Incorporating the non-analytic latent constraints (C1.2 and C2): For diagonal-Hessian constraints, the relevant factors are truncated Gaussians, whose moments are used in the subsequent updates.
  • B.2 Incorporating the non-analytic latent constraints (C1.2 and C2): The moment updates include revised means and a parameter α that depends on the approximate mean, observation, variance, and noise variance.

B.3 Incorporating the prediction constraint (C3)

Prediction combines the latent function values at a test input and the global maximizer, then uses Gaussian conditioning and precomputed terms to obtain the constrained predictive variance.

  • B.3 Incorporating the prediction constraint (C3): Prior terms and EP factors are independent of the test input x and can be precomputed for prediction.
  • B.3 Incorporating the prediction constraint (C3): The prediction vector concatenates the latent function values f(x) and f(x⋆).
  • B.3 Incorporating the prediction constraint (C3): Conditioning uses the cross-covariance between the prediction vector and [z; c], producing a Gaussian posterior with computable mean and variance.
  • B.3 Incorporating the prediction constraint (C3): The resulting quantities are inserted into the predictive equations to obtain vn(x|x⋆).
Loading 1406.2541v1…