Source-linked AI summary
Joint Entropy Search for Maximally-Informed Bayesian Optimization
Carl Hvarfner, Frank Hutter, Luigi Nardi
TL;DR
Information-theoretic Bayesian optimization methods quantify uncertainty about the optimum, but ES/PES require complex, expensive approximations, while MES focuses only on the optimal value and has an assumption that fails with noise. JES conditions on sampled optimal input/value pairs to measure joint information using standard GP machinery. It reports strong results across synthetic and hyperparameter-optimization tasks, with limitations under model misspecification and in zero-noise settings.
Problem
Method
JES measures entropy reduction for the joint optimum and noiseless optimal value by conditioning on sampled optimal input/value pairs, primarily using standard GP machinery.
Source: §3 · p. 3Results
Across GP-prior samples, synthetic test functions, and six noisy MLP hyperparameter tasks, JES reports strong performance, including substantial gains over PES and MES on GP-prior tasks and performance at least comparable to MES on all six MLP tasks.
Source: §4.1 · p. 7, §4.2 · p. 9, §4.3 · p. 9Takeaways & Limitations
JES combines information about the optimum and its value with minimal computational overhead, and the authors present it as a lightweight acquisition function for Bayesian optimization.
Source: §5 · p. 10Information-theoretic methods may be susceptible to model misspecification, which the proposed γ-exploit approach detects and adjusts for but does not inherently fix; JES also relies on some objective noise.
Source: §6 · p. 10
Abstract
from arXiv · showhide
Information-theoretic Bayesian optimization techniques have become popular for optimizing expensive-to-evaluate black-box functions due to their non-myopic qualities. Entropy Search and Predictive Entropy Search both consider the entropy over the optimum in the input space, while the recent Max-value Entropy Search considers the entropy over the optimal value in the output space. We propose Joint Entropy Search (JES), a novel information-theoretic acquisition function that considers an entirely new quantity, namely the entropy over the joint optimal probability density over both input and output space. To incorporate this information, we consider the reduction in entropy from conditioning on fantasized optimal input/output pairs. The resulting approach primarily relies on standard GP machinery and removes complex approximations typically associated with information-theoretic methods. With minimal computational overhead, JES shows superior decision-making, and yields state-of-the-art performance for information-theoretic approaches across a wide suite of tasks. As a light-weight approach with superior results, JES provides a new go-to acquisition function for Bayesian optimization.
1 Introduction
Bayesian optimization uses a surrogate and acquisition function to choose evaluations of expensive black-box objectives. JES combines information about the optimum and its value while aiming to avoid the computational burden and limitations of earlier information-theoretic approaches.
1 Introduction
- Bayesian optimization uses a probabilistic surrogate and an acquisition function that draws on uncertainty to select the next query for an expensive black-box objective.The approach is used across applications including hyperparameter optimization, robotics, hardware design, and reinforcement learning.Source: §1 · p. 1
- Entropy Search and Predictive Entropy Search select queries using expected information about the optimum’s location, but require costly computation and complex approximations.The computational burden affects their performance and practical use.Source: §1 · p. 1
- MES considers information about the optimal objective value and is computationally efficient, but its convergence rate has been disputed and its assumptions do not hold with noise.The passage notes that MES does not distinguish the unobserved maximal objective value from the observed noisy maximum.Source: §1 · p. 2
- JES combines the ES/PES and MES lines of work to provide a broader perspective on information gain about optimality.It uses information about both the optimum and the noiseless optimal value.Source: §1 · p. 2
- JES uses the full optimal observation to rely primarily on standard GP computations rather than complex approximations, with minimal pre-computation relative to input-space information-theoretic approaches.A related JES acquisition function was independently proposed for multi-objective and batch evaluations; this work focuses on single-objective optimization with large output noise.Source: §1 · p. 2
2 Background and related work
This section introduces Bayesian optimization, its surrogate models and acquisition functions, then contrasts information-theoretic methods that quantify information about the optimum or its value. ES/PES require costly approximations, while MES simplifies computation but relies on an assumption that fails with noise.
2 Background and related work
- Bayesian optimization sequentially selects evaluations using a probabilistic surrogate and acquisition function, aiming to maximize an expensive objective within an evaluation budget.Observations update the surrogate, and after the budget is exhausted a best configuration is returned.Source: §2 · p. 2
- Gaussian processes characterize the objective posterior through a mean and variance, using a covariance function to encode smoothness and relate observations to predictions.Random forests and Bayesian neural networks are also mentioned as alternative surrogates.Source: §2 · p. 2
- Acquisition functions quantify how attractive a candidate point is, balancing exploration and exploitation; Expected Improvement is a simple, computationally cheap heuristic.Other named approaches include UCB, PI, and Knowledge Gradient.Source: §2 · p. 3
- Information-theoretic acquisition functions select queries by expected information gain, expressed as entropy reduction about the optimum’s input location.ES expresses this as current entropy over the optimum minus expected entropy after observing a query.Source: §2 · p. 3
- PES gives an equivalent information-gain expression over query output and the optimum location, but its entropy computation requires expensive approximations and Monte Carlo calculations.For n observations in dimension d, the described PES calculation uses Cholesky decompositions of size O(n + d^2/2)^3 and approximates the optimum’s Hessian for each sample.Source: §2 · p. 3
- MES computes information gain about the optimal value through a one-dimensional output density, but its truncated-Gaussian assumption holds only in a strictly noiseless setting.For noisy applications, that assumption leads to an overestimation of entropy reduction.Source: §2 · p. 3
3 Joint Entropy Search
JES measures information about the joint optimal pair (x*, f*) and estimates its acquisition value by conditioning on sampled pairs and locally truncating the posterior. Its procedure combines GP conditioning with approximations and a safeguard for surrogate-model misspecification.
3.2 The Joint Entropy Search acquisition function
- JES conditions on sampled optimal input/value pairs and locally truncates the posterior to estimate information gained about the joint optimum.The conditioning reduction is exact, while the truncation reduction requires approximation.Source: §3 · p. 3, §3.2 · p. 4
3.1 Joint density over the optimum and optimal value: pictorial
- Unlike ES/PES and MES, JES considers the joint density over optimum location and noiseless optimal value, capturing uncertainty in both.In the toy example, JES selects a point uncertain under both measures, while PES and MES each learn about only one.Source: §3.1 · pp. 3–4, Figure 1 · p. 4
3.2 The Joint Entropy Search acquisition function
- Conditioning reduces log variance most near the conditioned point, while truncation mainly reduces it in uncertain regions farther away.The conditioning reduction depends on prior variance at the conditioned point; reductions from multiple optimal pairs accumulate.Source: §3.2 · p. 5, Figure 3 · p. 5
3.3 Incorporating optimal pairs
- Approximate Thompson sampling draws optimal pairs from approximate sample paths, which JES can optimize cheaply because it needs only each pair.Unlike PES, JES does not require each sampled optimum’s inverted Hessian or thorough gradient-based optimization.Source: §3.3 · p. 5
3.4 Approximating the truncated entropy
- Moment matching approximates the entropy after truncation because the predictive observation distribution is an Extended Skew distribution with intractable entropy.The approximation yields a valid lower bound on information gain.Source: §3.4 · p. 6
3.5 Exploitative selection to guard against model misspecification
- With probability γ, JES queries the posterior-mean maximizer to revisit its belief when the surrogate may be misspecified.The paper reports that this can substantially improve performance under misspecification with negligible worst-case impact.Source: §3.5 · p. 6
3.6 Putting it all together: The JES algorithm
- The algorithm averages the entropy reduction over sampled optimal pairs; its baseline observation entropy is available in closed form.The conditioning contribution is exact, while the truncation contribution uses the approximation described in Section 3.4.Source: §3.6 · p. 6
4 Experimental evaluation
The evaluation compares JES with PES, MES, and EI across GP-prior samples, synthetic test functions, and MLP tuning tasks. JES outperforms PES and MES on GP-prior tasks, performs strongly on Hartmann functions, and is superior or comparable to MES across the MLP tasks.
4 Experimental evaluation
- The evaluation uses simple regret for synthetic functions and inference regret for known-hyperparameter GP tasks; inference regret is unavailable for HPOBench tasks.All methods are compared in the same MATLAB framework, with 100 Monte Carlo samples for JES, MES, and PES.Source: §4 · p. 7
4.1 GP prior samples
- On GP-prior tasks with noise standard deviation 0.1 and outputs roughly [−10, 10], JES substantially outperforms PES and MES across 2D, 4D, 6D, and 12D.These tasks are an optimal setting for each algorithm because the surrogate perfectly models the task. The comparison uses 1,000 repetitions each for 2D, 4D, and 6D, and 250 for 12D, displaying mean and 2 standard errors of log regret.Source: §4.1 · p. 7, Figure 5 · p. 8
- On noisy GP samples, JES improves throughout 125D iterations while MES and PES slow approximately halfway through.The noise standard deviation is roughly 10% of the output range.Source: §4.1 · p. 8, Figure 6 · p. 8
- JES runtime is only marginally slower than MES with Gumbel sampling and at least an order of magnitude faster than PES across displayed dimensionalities.Runtime includes acquisition-function pre-computation and optimization, but excludes the black-box query.Source: §4.1 · p. 8, Table 1 · p. 8
4.2 Synthetic test functions
- On Branin, JES reaches MES’s performance by 100 iterations; on both Hartmann functions, it is among the best early and clearly best late.PES had numerical issues on Branin, so its reported performance may be worse than its actual performance.Source: §4.2 · p. 9, Figure 7 · p. 9
4.3 MLP tasks
- Across six MLP tuning tasks, JES is substantially better on two and approximately equal to EI on three; EI is superior on one.JES is superior or equal to MES on all tasks, while PES lags behind.Source: §4.3 · p. 9, Figure 8 · p. 9
5 Conclusions
JES considers the joint density over the optimum and optimal value. Conditioning on fantasized optimal observations yields a simple entropy reduction with minimal computational overhead, and the authors report strong performance and decision-making.
5 Conclusions
- JES considers the joint density over the optimum and optimal value, a quantity distinct from considering either alone.The approach uses entropy reduction from fantasized optimal observations.Source: §5 · p. 10
- Conditioning on fantasized optimal observations gives JES a simple form for joint-distribution entropy reduction.Source: §5 · p. 10
- The authors report minimal computational overhead, avoidance of restrictive objective assumptions, and state-of-the-art performance.Source: §5 · p. 10
6 Limitations and Future Work
JES can be vulnerable to model misspecification, and its γ-exploit strategy detects and adjusts for that issue without fixing the surrogate model. The authors also note a noise requirement and identify several directions for future work.
6 Limitations and Future Work
- Information-theoretic methods may be especially susceptible to model misspecification; γ-exploit can detect and adjust for it, but remedying it requires changing the surrogate model.The authors suggest combining information-theoretic acquisition with advanced modeling, including additive GPs, heterogeneous-noise modeling, and input warping.Source: §6 · p. 10
- JES relies on some objective noise; in a completely noiseless setting, the authors recommend adding a small noise term.With zero noise, every optimal pair yields infinite information gain, making JES equivalent to TS under random tie-breaking.Source: §6 · p. 10
- Future work could adapt JES to multi-fidelity and multi-objective optimization and integrate prior knowledge about the optimum's location.Source: §6 · p. 10
Checklist
The checklist points readers to the paper's limitations, ethics discussion, and experimental details. The broader-impact statement describes possible indirect societal effects through applications, including potential resource savings in machine-learning training.
Checklist
- The authors state that the introduction reflects the paper's contributions and scope, and that limitations and ethics guidelines are discussed elsewhere.The checklist refers readers to Section 6 for limitations and Section A 2 for ethics guidelines.Source: Checklist · p. 14
- The authors describe JES as a heuristic without theoretical results and point to the repository and appendix for reproducibility and experiment details.The checklist also states that experimental error bars are included.Source: Checklist · p. 14
A Broader impact
- The authors say JES may indirectly affect society through its applications and may reduce machine-learning training resource use while improving performance.They identify a possible reduction in machine-learning research's environmental footprint.Source: A Broader impact · p. 15
B Experimental setup
The experimental setup evaluates JES and other acquisition functions on GP samples, synthetic functions, and MLP classification tasks, alongside runtime tests. The appendix also describes ablations of γ and noise variance.
B Experimental setup
- Acquisition-function and posterior-mean optimization uses the original MATLAB PES implementation with GPStuff, dense-grid sampling, and gradient-based refinement.The authors increased the number of grid points for accuracy.Source: B Experimental setup · p. 15
- GP sample tasks use random Fourier features drawn from a squared-exponential kernel's spectral density, with length scales increased by dimension to maintain task difficulty.Task hyperparameters are listed in Table 2, and optima are approximated by dense random search followed by local search.Source: B Experimental setup · p. 15, Table 2 · p. 15
- Runtime tests compare acquisition-function runtimes over 100 seeds on 2D, 4D, and 6D GP samples, using a shared optimization budget and gradient-based refinement.Runtime includes acquisition setup and optimization after GP hyperparameter sampling and covariance inversion; JES, MES, and PES use 10 hyperparameter sets and 10 sampled optima.Source: B Experimental setup · p. 15
- Synthetic-function experiments sample 100 optimal pairs per acquisition function, resample hyperparameters on a fixed schedule, and compute regret from noiseless function values.The sampled maxima are updated at each iteration, and each test function has a fixed noise amount.Source: B Experimental setup · p. 15
- MLP classification experiments report observed accuracy because noiseless objective values are unavailable, and hold network depth fixed because integer hyperparameters are unsupported.Three HPOBench tasks are evaluated with other parameters scaled to [0, 1] and log-transformed where applicable.Source: B Experimental setup · pp. 15–16, Table 3 · p. 16, Table 4 · p. 16
- Experiments used single-core Intel Xeon Gold 6130 CPUs, totaling about 50,000 core hours for the main paper and 20,000 for the appendix.Source: B Experimental setup · p. 16
C Ablation studies and model misspecification
- The appendix describes ablations of the exploitative-selection ratio γ, its effect on inference regret under misspecification, and robustness to noise variance.Source: C Ablation studies and model… · p. 16
C.1 Ablation studies
The ablations show that γ-exploit improves simple regret and can preserve or improve inference regret, including under model misspecification. JES is also reported as more robust than MES and PES as noise increases.
C.2 Model misspecification
- Across test functions under model misspecification, γ-exploit yields comparable or improved inference regret and strictly improved simple regret for JES, PES, and MES.MES is generally the top-performing and most robust method in these misspecified-model tests.Source: §C.2 · p. 16
C.1 Ablation studies
- γ > 0 improves simple regret, while moderate γ values of 0.05 or 0.1 yield comparable or sometimes improved inference regret across tasks.At γ = 0.2, inference regret is slightly worse on Hartmann (6D) but marginally improved on Branin and Hartmann (3D).Source: §C.1 · p. 16, Figure 9 · p. 17, Figure 10 · p. 17
C.3 Ablation study on σ2ϵ
- As noise increases, JES remains robust while MES and PES performance decreases more drastically.The study fixes the GP noise hyperparameter to its correct value before the experiment.Source: §C.3 · p. 17
D Dependence on the number of MC samples
JES shows a modest dependence on the number of Monte Carlo samples, with the effect more pronounced at higher dimensionality. On the 12-D benchmark, however, lower sample counts achieve better final regret, possibly because they over-exploit.
D Dependence on the number of MC samples
- Higher-dimensional tasks show a slower initial start with fewer MC samples, while larger sample counts can marginally improve initial performance.The passage attributes the stronger dependence at higher dimensionality to the need for more sampled optimal pairs to model the density accurately.Source: D Dependence on the number of MC samples · p. 17
- On the 12-D benchmark, final regret is better for lower numbers of GP samples, such as JES-4, although larger sample counts marginally improve initial performance.The authors suggest JES-4 and JES-20 may over-exploit slightly because sampled optimal pairs may cluster near the optimum despite small positive density elsewhere.Source: D Dependence on the number of MC samples · p. 17
- The high-dimensional synthetic-function figures report mean inference regret for vanilla γ-exploit versions and mean simple regret for the same acquisition-function variants.Figure 11 omits error bars for legibility; Figure 12 displays mean and one standard error.Source: Figure 11 · p. 18, Figure 12 · p. 18
E Approximation Quality
The approximation-quality analysis compares moment matching with an asymptotically exact Monte Carlo approach and examines its effects on entropy reduction and regret evaluations. Moment matching underestimates the entropy reduction in some conditions, with a reported exploration consequence.
E Approximation Quality
- Moment matching approximates the entropy of observations conditioned on the data and an optimal pair by matching the truncated distribution's moments.The approximation covers the truncation-related entropy reduction after conditioning on a new observation.Source: E Approximation Quality · p. 18
- Moment matching consistently estimates a lower entropy reduction than the asymptotically exact MC approach, with error seemingly increasing logarithmically with the truncation quantile.The comparison varies noise level and truncation quantile; Fig. 15 visualizes the ratio of the moment-matching truncation reduction to the MC reduction.Source: E Approximation Quality · p. 19, Figure 15 · p. 20
- With little truncation and noise small relative to total variance, the truncation-related entropy reduction is underestimated by approximately 15%, producing a slightly less explorative strategy.Severe truncation with low noise is described as an uncommon practical scenario.Source: E Approximation Quality · pp. 19–20
F Regret Measures
- The regret-measure figures cover GP sample and synthetic test functions, including simple-regret comparisons of JES, MES, PES, and EI on GP prior samples.Figure 16 reports mean and two standard errors of log regret across 2D, 4D, 6D, and 12D tasks.Source: F Regret Measures · p. 20, Figure 16 · p. 20
F.1 GP sample tasks
On GP sample tasks, simple and inference regret are approximately equal for MES but differ substantially for JES; for PES, the difference can be especially pronounced. On synthetic test functions, the relationship varies by method and task, with MES not yet fully locating the optimum on Branin.
F.1 GP sample tasks
- For GP sample tasks, simple and inference regret are approximately equal for MES but differ substantially for JES; for PES, the difference reaches about two orders of magnitude.Figure 16 presents simple regret; the passage compares it with inference regret.Source: §F.1 · p. 20
F.2 Synthetic test functions
- On Branin, MES has significantly better simple than inference regret, implying it has not yet fully located the optimum; on Hartmann-6, its inference regret marginally worsens after about iteration 100.JES has approximately equal simple and inference regret on the synthetic functions, while PES shows a pronounced difference and numerical issues on Branin.Source: §F.2 · p. 21