PaperlayerView exact revision on arXiv

Source-linked AI summary

Entropy Search for Information-Efficient Global Optimization

Philipp Hennig, Christian J. Schuler

arXiv:1112.1217v1stat.MLcs.AI

TL;DR

Global optimization must learn an unknown function and infer its minimum from expensive evaluations, but the corresponding probabilistic inference and planning problems are intractable. The paper develops Entropy Search, combining Gaussian-process priors with approximations for the minimum distribution and information-based evaluation selection. It reports that the resulting algorithm outperforms directly and distantly related competitors, while relying on assumptions and approximations whose scope includes limitations of the Gaussian-process model.

  • Problem

    Global optimization seeks to infer the minimum of an unknown function from expensive, noisy evaluations, but probability-based inference over the minimum is computationally intractable.

  • Method

    Entropy Search uses Gaussian-process priors, discretization, Expectation Propagation, analytic predictions of future belief changes, and greedy information-based evaluation selection.

  • Results

    Entropy Search outperforms directly and distantly related competitors through its probabilistic description of the optimization problem.

  • Takeaways & Limitations

    The paper presents global optimization as inference about the minimum rather than iterative collection of lower function values.

  • Takeaways & Limitations

    The approach depends on Gaussian-process prior assumptions, and additional prior information about the minimum's location is generally intractable and left for future work.

Abstract

from arXiv · show

Contemporary global optimization algorithms are based on local measures of utility, rather than a probability measure over location and value of the optimum. They thus attempt to collect low function values, not to learn about the optimum. The reason for the absence of probabilistic global optimizers is that the corresponding inference problem is intractable in several ways. This paper develops desiderata for probabilistic optimization algorithms, then presents a concrete algorithm which addresses each of the computational intractabilities with a sequence of approximations and explicitly adresses the decision problem of maximizing information gain from each evaluation.

1. Introduction

This paper addresses global optimization when the function must be learned through expensive, noisy evaluations in a bounded, often low-dimensional domain. It defines optimization probabilistically around inferring the minimum and choosing evaluations that reduce expected loss or increase knowledge about it.

  • Problem setting: Global optimization here learns an unknown function while searching for its minimum in a usually bounded, relatively low-dimensional domain.Evaluations may involve expensive physical processes, nontrivial noise, and unavailable derivatives.
  • Problem definition: The paper defines probabilistic optimization using a measure over functions and the induced probability measure pmin over the minimum's location.The objective is to reduce expected loss after a finite number of evaluations.
  • Decision objective: The optimal evaluation locations minimize expected change in loss over the evaluation horizon, but exact planning is generally exponential in the horizon.The paper later addresses this planning difficulty with a greedy approximation.
  • Problem definition: After finitely many evaluations, inference about minima on continuous domains requires prior assumptions because function space lacks a natural measure.Probability theory supplies relative size to competing sets of functions consistent with the observations.
  • Relation to prior approaches: Unlike bandit regret and heuristic improvement utilities, probabilistic optimization targets inference about the global minimum rather than collecting low function values.Local utilities do not capture how evaluations change knowledge about the minimum.

2. Entropy Search

Entropy Search constructs a probabilistic global optimizer by combining Gaussian-process beliefs with approximations for representing and updating the minimum distribution. It selects evaluations by approximating expected information gain while using greedy planning to control computational cost.

  • Model and representation: Entropy Search uses a Gaussian process prior over functions and approximates the induced probability distribution pmin over the minimum's location.The paper notes that Gaussian processes provide descriptive generality and convenient analytic properties.
  • Model and representation: The algorithm discretizes pmin on finitely many non-uniformly sampled representer points to address the infinite-dimensional calculation and the curse of dimensionality.The discretization's artefacts are studied in a tractable one-dimensional setting.
  • Approximate inference: Expectation Propagation supplies an efficient analytic approximation to pmin because its defining integral is not analytically tractable even for finite-dimensional Gaussian measures.The approximation is compared with an asymptotically exact but more expensive Monte Carlo solution.
  • Information-based decisions: Gaussian-process predictions provide an analytic formulation for how future evaluations change the function belief and therefore the minimum distribution.This enables prediction of the expected change in loss for candidate evaluation points.
  • Information-based decisions: Entropy Search uses relative entropy from a uniform distribution as an information-based loss, approximates expected information gain to first order, and chooses evaluations greedily.Greedy planning replaces an exact dynamic program whose cost is exponential in the horizon.

2.2 Discrete Representations for Continuous Distributions

The paper approximates the minimum distribution by representing regular stochastic functions on finitely many points and weighting those points according to a non-uniform quadrature measure. This representation can preserve boundary probability mass and supports efficient inference.

  • Motivation: The minimum distribution pmin is difficult to compute because it requires an integral over an infinite-dimensional function space.Even finite-dimensional versions may remain analytically difficult for a particular p(f).
  • Finite representation: For sufficiently regular stochastic processes, pmin can be approximated arbitrarily well using finitely many representer points sampled from a suitable distribution.The grid need not be regular.
  • Finite representation: A non-uniform quadrature measure gives each representer point a step width approximately proportional to (u(x̃i)N)^-1 as N grows.The discretized probability at a point is combined with the quadrature measure and normalized to approximate pmin.
  • Sampling and comparison: The resulting representation is asymptotically exact on a regular grid and uses probability-of-improvement or expected-improvement measures to sample relevant representer points.These heuristics are used as unnormalized sampling measures, not as the optimizer's final objective.
  • Sampling and comparison: The minimum can have nonzero probability of lying exactly at a domain boundary because the smoothness prior permits appropriate boundary derivatives.This boundary mass is a feature of pmin that local interior reasoning may miss.

2.3 Approximating pmin with Expectation Propagation

The paper approximates the distribution over the location of the minimum by discretizing the domain and applying Expectation Propagation, while Monte Carlo provides an asymptotically exact alternative. These approximations support prediction of how future observations change the minimum distribution and expected loss.

  • Discretization: A finite set of representer points reduces the continuous minimum distribution to a discrete probability distribution over locations.The Gaussian-process belief restricted to the representer points becomes a multivariate Gaussian.
  • Expectation Propagation: The resulting Gaussian integral is intractable, so Expectation Propagation constructs an approximate Gaussian marginal whose normalization constants estimate the minimum-location probabilities.EP treats the prior and minimum constraints as messages in a graphical model.
  • Computational cost: EP has computational cost O(N^4), with the implementation using N = 50 and calculating next evaluation points in approximately 10 seconds.Each minimum-probability computation requires N rank-1 updates costing O(N^2).
  • Monte Carlo alternative: Monte Carlo samples exact functions, finds each sample minimum, and costs O(SN^3), but lacks analytic derivatives because its minimum operation is strongly discontinuous.The method is asymptotically exact and considerably faster per evaluation than EP.
  • Predicting innovation: Future-observation innovations can be sampled jointly, and the resulting innovated minimum distributions can be used to predict changes in loss.Gaussian-process posterior mean changes stochastically, whereas covariance changes deterministically.
  • Validation: EP achieves good agreement with the asymptotically exact Monte Carlo approximation, including point masses at the domain boundaries.

2.5 Information Gain – the Log Loss

The paper defines information gain through a relative-entropy loss on the probability distribution of the minimum. Using a uniform base measure, Entropy Search selects evaluations expected to move belief toward a concentrated minimum distribution.

  • Approximation comparison: Different approximations produce similar next evaluation points despite nonidentical predicted loss-improvement curves.The plotted scales are arbitrary because each approximation is tractable only up to a multiplicative constant.
  • Loss function: Relative entropy, or Kullback–Leibler divergence, is used because ordinary entropy does not directly generalize to probability densities.The paper uses its negative value as a loss function emphasizing information gain.
  • Base measure: The uniform measure over the bounded domain serves as the base measure for evaluating information about the minimum location.This measure is well-defined because the domain is bounded.
  • Decision rule: Entropy Search chooses evaluation points expected to move belief away from the uniform base measure toward a Dirac distribution as quickly as possible.The loss is maximized for a uniform belief and tends toward negative infinity as the belief approaches a point mass.
  • Why the base measure matters: Maximizing entropy relative to the current minimum belief could favor evaluations that merely change belief, rather than evaluations expected to change it in the correct direction.
  • Discrete approximation: The loss is approximated on representer points whose step widths are proportional, up to stochastic error, to an unnormalized sampling measure.The resulting discrete distribution approximates the minimum-location density.

2.6 First-Order Approximation to ⟨L⟩

The first-order approximation predicts expected loss changes by propagating future evaluations through changes in the Gaussian-process belief, the minimum distribution, and finally the loss. Monte Carlo samples make the stochastic component reusable and differentiable.

  • Derivation: Analytic derivatives of the EP minimum distribution enable a first-order expansion of expected loss change with respect to evaluation locations.The derivation applies Itô’s Lemma because the mean change is Gaussian stochastic.
  • Stochastic integration: The approximation separates deterministic effects from stochastic effects and estimates the latter by Monte Carlo integration over a small sample set.
  • Reuse: The samples are drawn once at the initial calculation so the differentiable expected-loss function can be reused during subsequent optimization steps.
  • Limitation: The formulation is loss-function agnostic in principle, but the paper is limited to relative entropy because suitable discretization measures were difficult to find for other losses.Generalization to other loss functions is left for future work.

2.7 Greedy Planning, and its Defects

The paper optimizes evaluation locations using a numerical inner problem, then adopts greedy planning because full-horizon optimization is exponentially costly. Evidence suggests greedy information gathering is not catastrophically wrong, although multi-step evaluation structure can be complex.

  • Inner optimization: Optimizing evaluation locations is a numerical optimization problem with noiseless function evaluations, available derivatives, and lower cost than the physical experiment.
  • Planning difficulty: Optimizing all H evaluations jointly is a dynamic-programming problem whose general cost is exponential in H.
  • Multi-step behavior: The structure of expected two-step loss reduction illustrates the complexity of finding optimal multi-step evaluation locations.The plot is symmetric because Gaussian-process evaluations are exchangeable, with diagonal elements excluded for numerical reasons.
  • Greedy planning: Information gain over function values is submodular, while the paper notes that extending this guarantee to learning the minimum is not immediate.
  • Greedy planning: Greedy selection of the location with the largest immediate expected loss reduction is described as guaranteed never to be catastrophically wrong.

2.8 Further Issues

The paper extends Gaussian-process optimization through prior, likelihood, and inference choices, while identifying scope limits and approximation conditions. These extensions alter posterior beliefs and support settings that standard stationary or polynomial models represent poorly.

  • Extensions: Derivative and integral observations extend Gaussian-process inference when the required kernel derivatives or integrals exist.The same optimization results can then use function, derivative, or combined observations.
  • Learning Hyperparameters: Hyperparameters can be learned by maximum likelihood or Bayesian inference, but the optimizer conditions on fixed hyperparameters for tractability.Approximating the resulting mixture of Gaussian processes with one Gaussian process preserves use of the derived algorithm.
  • Parametric Means: Parametric means and radial basis functions encode structure such as boundary-associated large values without imposing the strong long-range correlations of quadratic means.Quadratic means create an explicit center and correlate opposite ends of the domain, whereas radial basis functions can localize boundary effects.
  • Composite Kernels: Composite kernels combine large-scale curvature with short-scale local variation, producing flexible “rough trough” priors without unwanted global correlations.The paper notes that this prior treats “domes” and “bowls” as equally likely.
  • Nonlinear Likelihoods: Nonlinear likelihoods can encode positivity by learning a latent g with f = exp(g), but Laplace inference is reliable when σ ≪ y.The approximation incorporates (y, σ²) as (log(y), (σ/y)²), yielding heteroscedastic noise.
  • Limitations and Extensions: Different priors produce substantially different posteriors, and additional prior information over the minimum’s location remains generally intractable and outside this paper’s scope.The paper presents location priors as future work and notes that each posterior may suit different situations.
  • Algorithm: Entropy Search pseudocode samples discretization points, infers the Gaussian-process belief and derivatives, evaluates a selected point, and updates recursively until the horizon.At the horizon, it returns the belief over the minimum for the final decision.

2.9 Summary – the Entire Algorithm

Entropy Search chooses evaluations by approximating the posterior over functions and the induced minimum distribution on a discretized domain. It uses that belief, together with the horizon and prior observations, to select the next information-gathering location.

  • Inputs: Entropy Search takes a Gaussian-process prior, likelihood, discretization measure, evaluation horizon, and previously collected observations as inputs.The discretization measure may itself depend on previous data.
  • Inference: The algorithm samples discretization points, infers the current function belief and derivatives, and constructs an approximate belief over the global minimum.That minimum belief guides the choice of where to evaluate next.
  • Sequential Decision: After evaluating the selected point, Entropy Search incorporates the new observation and repeats the selection process until the evaluation horizon is exhausted.The final output is the belief used for the optimization decision.

3. Experiments

Entropy Search is evaluated against GP heuristics and GP-UCB on within-model and out-of-model synthetic tasks, measuring optimizer guesses, regret, and robustness to model mismatch.

  • Experimental design: The experiments compare Entropy Search with Expected Improvement, Probability of Improvement, and GP-UCB on functions sampled from generative models.Within-model tests remove model mismatch; out-of-model tests use rational quadratic-kernel functions beyond the algorithms’ prior class.
  • Within-model comparison: Entropy Search shows a clear advantage in estimating the global minimum’s value and location, although its error eventually flattens because of evaluation noise.The evaluation noise has standard deviation 10^-3.
  • Evaluation limitations: Entropy Search cannot be fairly compared on entropy loss because estimating that loss would require the algorithm introduced in the paper, making the experiment circular.Local optimizers also lack probabilistic function models needed to provide the entropy loss.
  • Regret comparison: Probability of Improvement achieves the lowest regret while performing worst among the global optimizers on function-value and location measures.Its low regret reflects focus on evaluating regions already known to have low function values.
  • Within-model comparison: GP-UCB performs worst in the comparison despite being explicitly designed to achieve low regret.The reported GP-UCB results use the best performance across four settings of δ, whose choice strongly influences performance.
  • Out-of-model comparison: Under model mismatch, all three algorithms perform worse and become more similar, while Entropy Search still barely outperforms the competitors.The off-model functions use a rational quadratic kernel with an infinite mixture of length scales.

4. Conclusion

The paper reframes global optimization as probabilistic inference about a function’s minimum and implements that paradigm as Entropy Search. The method outperforms the cited competitors at increased computational cost, making it most suitable when function evaluations are expensive.

  • Conclusion: The paper’s central contribution is a probabilistic global-optimization paradigm focused on inferring the function minimum rather than collecting progressively lower function values.The conclusion positions this formulation closer to practitioners’ requirements than heuristic and bandit alternatives.
  • Conclusion: Entropy Search combines Gaussian-process priors, a discretized belief p_min over the minimum location, Expectation Propagation, and an approximation to expected information gain.The belief is represented on an irregular grid to address the curse of dimensionality.
  • Conclusion: Entropy Search outperforms directly and distantly related competitors through a more elaborate probabilistic description of the optimization problem.The supplied conclusion references function-value error, location error, and regret in the evaluation figures.
  • Conclusion: The performance increase comes with somewhat increased computational cost, estimated as a constant multiple of classic Gaussian-process global optimizers.The conclusion therefore identifies expensive function evaluations as the setting where the method is most suited.

Appendix A. Mathematical Appendix

The appendix gives a precise interpretation of the minimum-location belief on a continuous domain and explains how it can be approximated using finitely many representer points.

  • Appendix A. Mathematical Appendix: p_min is interpreted through a sequence of increasingly dense finite location sets whose point density converges to a measure positive on every open neighborhood.This construction gives meaning to the probability that a location is the global minimum on a continuous domain.
  • Appendix A. Mathematical Appendix: The infinite-dimensional definition is treated as a limit of finite-dimensional integrals with increasing numbers of factors and dimensions.The appendix notes that existence of this limit for every Gaussian-process kernel is not established there.
Loading 1112.1217v1…