PaperlayerView exact revision on arXiv

Source-linked AI summary

Max-value Entropy Search for Efficient Bayesian Optimization

Zi Wang, Stefanie Jegelka

arXiv:1703.01968v3stat.MLcs.LGmath.OC

TL;DR

ES and PES are query-efficient but computationally expensive because they estimate entropy over the unknown argmax, especially in high dimensions. MES instead uses information about the maximum function value and estimates it through a one-dimensional distribution. The method is reported to match or outperform ES/PES while being more efficient and robust to the number of entropy samples.

  • Problem

    ES and PES require expensive, difficult entropy estimation over the argmax distribution, whose computation becomes inefficient in high dimensions.

  • Method

    MES maximizes mutual information between queries and the maximum function value, using Gumbel or random-feature sampling to approximate its one-dimensional distribution.

  • Results

    MES identifies good points as quickly as or better than ES/PES while being more efficient and robust in mutual-information estimation.

  • Takeaways & Limitations

    MES provides an information-theoretic Bayesian optimization criterion that is adaptable to high-dimensional settings through additive Gaussian processes.

  • Takeaways & Limitations

    The equivalence between single-sample MES and related criteria no longer holds when MES uses more than one maximum-value sample.

Abstract

from arXiv · show

Entropy Search (ES) and Predictive Entropy Search (PES) are popular and empirically successful Bayesian Optimization techniques. Both rely on a compelling information-theoretic motivation, and maximize the information gained about the $\arg\max$ of the unknown function; yet, both are plagued by the expensive computation for estimating entropies. We propose a new criterion, Max-value Entropy Search (MES), that instead uses the information about the maximum function value. We show relations of MES to other Bayesian optimization methods, and establish a regret bound. We observe that MES maintains or improves the good empirical performance of ES/PES, while tremendously lightening the computational burden. In particular, MES is much more robust to the number of samples used for computing the entropy, and hence more efficient for higher dimensional problems.

1. Introduction

Bayesian optimization selects expensive black-box evaluations through acquisition functions. MES preserves the information-theoretic and query-efficient motivation of ES/PES while replacing argmax uncertainty with one-dimensional maximum-value uncertainty to reduce computation.

  • Motivation: Bayesian optimization uses posterior uncertainty to guide queries to expensive, nonconvex black-box objectives.The acquisition function is critical because it determines the selected evaluations.
  • Motivation: ES and PES maximize information about the location of the global optimum but require expensive entropy estimation, especially in high dimensions.Their argmax distributions are difficult to estimate from many input-space samples.
  • MES: MES replaces uncertainty about the argmax with uncertainty about the maximum function value, which lies in one dimension.The paper explores Gumbel and random-feature Monte Carlo strategies for efficient entropy estimation.
  • Contributions: MES aims to retain ES/PES query efficiency at much lower computational cost.The contribution includes theoretical connections, a regret bound, high-dimensional extension, and empirical evaluation.

2. Background

The paper models noisy black-box objectives with Gaussian processes and uses additive Gaussian processes for high-dimensional inputs. It evaluates optimization through simple regret and inference regret, distinguishing queried-point quality from the quality of the final inferred maximizer.

  • Gaussian-process model: The objective is a compact-domain black-box function observed with iid Gaussian noise and modeled using Gaussian processes.High-dimensional cases use an additive Gaussian process variant.
  • Gaussian-process model: A Gaussian process is specified by a mean function and covariance kernel, with posterior mean and covariance updated from observations.The posterior variance is obtained from the posterior covariance at each input.
  • Additive Gaussian processes: Additive Gaussian processes represent the objective as a sum of independent components active on disjoint input-dimension groups.This decomposition supports modeling functions whose structure is distributed across lower-dimensional subsets.
  • Evaluation criteria: Simple regret measures the best queried value's gap from the global maximum, whereas inference regret evaluates the final inferred maximizer.The inferred maximizer is usually the posterior-mean maximizer.

3. Max-value Entropy Search

MES selects points using information about the unknown maximum value rather than the argmax location. It estimates this information through a one-dimensional maximum-value distribution, with Gumbel or random-feature sampling, and connects to existing BO criteria while providing a regret bound.

  • Motivation: ES and PES are computationally difficult because the argmax distribution and its entropy are analytically intractable.Nonunique optima add complexity to the argmax distribution.
  • MES objective: MES maximizes mutual information between the next query and the maximum value y∗ instead of the argmax x∗.The acquisition function approximates this information gain using predictive-distribution entropy.
  • MES objective: MES uses the one-dimensional distribution p(y∗|D_n), making sampling computationally easier than using the d-dimensional argmax distribution.The expectation is approximated by sampling function maxima or using an approximate maximum-value distribution.
  • Gumbel sampling: Gumbel sampling approximates the maximum-value distribution after discretizing the domain and applying a mean-field independence approximation.The mean-field approximation can overestimate the maximum, while the Gumbel approximation is motivated by extreme-value theory and works well empirically.
  • Random-feature sampling: Random-feature sampling draws posterior functions and maximizes each sampled function to obtain samples of y∗.The posterior GP is approximated with a one-hidden-layer neural network representation.
  • Theory and connections: With one y∗ sample, MES is equivalent to EST and PI with threshold θ = y∗, and a variant has a simple-regret bound.The stated equivalence does not hold when MES uses more than one maximum-value sample.

4. High Dimensional MES with Add-GP

The paper extends MES to high-dimensional optimization with additive Gaussian processes. Independent component structure permits separate information gains over active dimensions before concatenating the selected componentwise inputs.

  • High-dimensional extension: Add-MES uses additive Gaussian processes to address the statistical and acquisition-optimization challenges of high-dimensional inputs.The additive model assumes the function is a sum of lower-dimensional components.
  • Componentwise acquisition: Because function components are independent, Add-MES maximizes mutual information separately between each active input group and its component maximum.Each component therefore has its own acquisition function.
  • Componentwise acquisition: The final input is formed by selecting componentwise maximizers and concatenating their subvectors.This combines the independently optimized active dimensions into one query.
  • Componentwise sampling: Add-MES applies the same maximum-value sampling idea componentwise, using Gumbel approximations or posterior-function sampling for each function component.The approximation acts only on the active dimensions of the relevant group.

5. Experiments

Across synthetic, neural-network, robotic, and high-dimensional tasks, MES generally matches or improves competing Bayesian optimization methods while reducing sensitivity and runtime costs. Its variants show complementary behavior across dimensionality and exploration–exploitation settings.

  • Experiments: MES remains competitive with ES, PES, and other Bayesian optimization methods across synthetic, neural-network, and robot-pushing tasks.On higher-dimensional synthetic functions, MES methods outperform PES and ES; neural-network and robot-pushing results are also favorable.
  • 5.1. Synthetic Functions: 1, 10, or 100 sampled maxima leave MES performance relatively stable, whereas PES is highly sensitive to the number of sampled argmaxes.With one or ten samples, MES-G and MES-R remain competitive; PES improves substantially with 100 argmax samples.
  • 5.1. Synthetic Functions: MES-G avoids optimization for sampled maxima and has runtime comparable to EI, while PES and MES-R become slower as sample counts increase.The runtime comparison excludes function-evaluation time and uses fixed GP hyper-parameters.
  • 5.2. Optimization Test Functions: On 2-d eggholder, PES finds better function values faster, but on 10-d Shekel and Michalewicz, MES performs much better and MES-G performs best overall.The results confirm PES’s strong performance when sufficiently many argmax samples are used, while favoring MES on the higher-dimensional test functions.
  • 5.4. Active Learning for Robot Pushing: For robot pushing, MES performs better on the 3-D task and converges faster on the 4-D task, although PI achieves lower regret at the very end of the latter.A separate 14-parameter pushing task and 25-parameter bipedal-walker task show both MES methods performing competitively with add-GP-UCB.
  • 5.5. High Dimensional BO with Add-MES: In additive high-dimensional functions, add-MES methods outperform add-GP-UCB except for add-MES-G at d = 100.Add-MES-G is strongest for d = 10, 20, 30, while add-MES-R is strongest for d = 50, 100; MES-G overestimates and MES-R underestimates the maximum under their respective approximations.

6. Conclusion

MES is an information-theoretic approach for optimizing expensive black-box functions that is competitive with or better than entropy-search methods at lower computational cost. The paper also connects MES to several Bayesian optimization methods, extends it to high-dimensional settings with additive GPs, and establishes a simple-regret bound for a variant.

  • MES optimizes expensive black-box functions using information about the maximum function value.
  • MES is competitive with or better than previous entropy-search methods while requiring much lower computational cost.
  • Additive Gaussian processes make MES adaptable to high-dimensional settings.
  • The paper theoretically connects MES to entropy search, GP-UCB, PI, and EST.
  • A variant of MES has a bound on simple regret.

A. Related work

The paper situates MES among Bayesian optimization methods that use posterior uncertainty to guide queries, especially entropy-search methods targeting the global optimum's location. It also addresses the challenge of finding promising points in high-dimensional spaces under an additive-function assumption.

  • Entropy search methods evaluate inputs that are most informative about the arg max of the optimized function.
  • PI, EI, GP-UCB, and related upper-confidence-bound algorithms use heuristics favoring evaluations likely to have good values.
  • Finding points with good values is challenging in high-dimensional spaces.
  • Prior high-dimensional Bayesian optimization methods assume lower-dimensional structure or additive components active on lower-dimensional manifolds.
  • This work shows that MES also works in high dimensions with the additive assumption used in prior work.

B. Using the Gumbel distribution to sample y∗

The method samples the function maximum by approximating correlated Gaussian-process values with independent Gaussians on a discretized search space, then approximating their maximum distribution with a Gumbel distribution. This approximation is useful in practice, although the Fisher-Tippett-Gnedenko theorem does not generally apply to independent, differently distributed Gaussians.

  • The function maximum y* is sampled by approximating correlated f(x) values with independent Gaussians on a discretized search space.The discretization is denoted X̂, unless the search space is already discrete.
  • Slepian's lemma supports using the independent approximation to obtain a distribution for an upper bound on f(x).
  • The maximum over the discretized function values is approximated with a Gumbel distribution.
  • For identically distributed Gaussian variables, the Fisher-Tippett-Gnedenko theorem makes the Gumbel approximation asymptotically correct.
  • For independent differently distributed Gaussians, the Fisher-Tippett-Gnedenko theorem does not hold, but the Gumbel approximation remains useful in practice.Figure 6 illustrates the approximation through percentile matching.

C. Regret bounds

The paper derives a simple-regret bound for MES by connecting it to EST and controlling sampled maximum values and information gain. The analysis also identifies a randomized trade-off in choosing those sampled values and leaves the high-dimensional Add-GP-MES bound unresolved.

  • Theorem and proof strategy: The bound assumes a Gaussian-process prior over a compact search space, bounded kernel, and iid Gaussian observation noise.The theorem defines f* as the maximum of a function sampled from the GP and uses a maximum-value distribution F.
  • Theorem and proof strategy: The regret analysis combines confidence bounds, predictive variances, and maximum information gain to control cumulative learning regret.The proof invokes bounds on immediate regret and information gain, yielding a high-probability result.
  • Theorem and proof strategy: MES obtains a simple-regret bound by adapting EST results when sampled maximum values exceed the true maximum.The proof partitions iterations and uses samples satisfying y*_ti > f* with high probability.
  • Limitations of the bound: The point-estimate bound has a randomized trade-off because overly large or undersized sampled maximum values can worsen the regret upper bound.There is no principled way to set the unknown true maximum directly.
  • Limitations of the bound: A regret guarantee is not established for add-GP-MES because of technical problems in the existing add-GP-UCB proof, although experiments show good practical performance.The authors state that the add-GP-MES bound should follow add-GP-UCB but could not prove it.

D. Experiments

The experiments compare Bayesian optimization methods on three challenging test functions and use a fixed additive decomposition for fair high-dimensional comparisons. PES performs best on the 2-D eggholder function, whereas MES-G performs best on both 10-D functions.

  • Optimization test functions: The experiments compare simple regret on 2-D eggholder, 10-D Shekel, and 10-D Michalewicz functions.These are described as three challenging optimization test functions.
  • Choosing the additive decomposition: The additive decomposition is selected from 10,000 random decompositions with groups of at most two dimensions, using data likelihood on 500 uniformly sampled points.The chosen decomposition remains fixed across all 500 Bayesian optimization iterations for fair comparison.
Loading 1703.01968v3…