GIBBON: General-purpose Information-Based Bayesian OptimisatioN

1. Introduction

• Information-theoretic BO reduces uncertainty about high-performing regions, with MES targeting the one-dimensional maximum value rather than the maximiser location targeted by ES and PES.The lower-dimensional target contributes to MES’s broader applicability and lower approximation burden.Source: §1 · p. 2
• Existing MES extensions for multi-fidelity and batch BO require additional numerical approximations, while synchronous batch MES can require prohibitively expensive B-dimensional Gaussian cumulative density calculations.These extensions therefore lose the simplicity and low cost of vanilla MES, and existing generic batch heuristics support only Euclidean spaces.Source: §1 · pp. 2–3
• GIBBON provides one generalisation of MES for combinations of noisy, batch, single-fidelity, and multi-fidelity optimisation, including synchronous batches over discrete structures.Unlike existing MES extensions, it retains the computational cost of vanilla MES without numerical integration.Source: §1 · p. 3
• GIBBON’s analysis connects information-theoretic search with determinantal point processes and local penalisation, theoretically justifying attributes previously selected heuristically.This connection provides an interpretation of popular batch BO heuristics.Source: §1 · p. 3
• The paper also analyses GIBBON’s computational complexity within the broader class of information-theoretic acquisition functions.The stated aim is a comprehensive evaluation of information-theoretic BO overheads.Source: §1 · p. 3
• The paper evaluates GIBBON on benchmark optimisation tasks, high-cost string optimisation, and synchronous batch multi-fidelity BO with controllable observation noise.These experiments include the first application of information-theoretic acquisition functions to high-cost string optimisation tasks.Source: §1 · p. 3

2. Max-value Entropy Search for Black-Box Function Optimisation

• Bayesian optimisation chooses locations, and possibly fidelity levels, for expensive black-box evaluations using a probabilistic surrogate and an acquisition function.The general framework selects batches of B location-fidelity pairs, with standard and batch BO recovered as special cases.Source: §2 · pp. 4–5
• MES measures the utility of an evaluation by its mutual-information reduction in uncertainty about the objective’s maximum value g∗.GMES extends this idea to the joint mutual information of a batch of fidelity evaluations with g∗.Source: §2 · p. 5
• The full GMES calculation is challenging because g∗ lacks a closed-form distribution, making a practically viable approximation its central computational challenge.The framework must handle standard, noisy, multi-fidelity, and batch cases within this difficulty.Source: §2 · p. 5

2.1 Max-value Entropy Search for noiseless standard BO

• For noiseless standard BO, MES combines closed-form Gaussian and truncated-Gaussian entropies with Monte Carlo samples of g∗, obtained efficiently using a Gumbel approximation.This formulation has achieved strong empirical performance with substantially lower overhead than other information-theoretic methods in its supported setting.Source: §2.1 · p. 6

2.2 Max-value Entropy Search for multi-fidelity BO

• Multi-fidelity MES loses the truncated-Gaussian closed form because fidelity evaluations conditional on g∗ follow an extended skew Gaussian distribution, requiring numerical integration.The same formulation can cover noisy single-fidelity observations by treating them as a single-fidelity special case.Source: §2.2 · pp. 6–7

2.3 Max-value Entropy Search for Batch BO

• Synchronous batch MES is difficult because conditional interactions among B evaluations prevent inexpensive asynchronous-batch approximations, motivating GIBBON’s integration-free strategy.A naive extension requires prohibitively expensive B-dimensional multivariate Gaussian cumulative density approximations.Source: §2.3 · p. 7

2.4 Alternatives to Max-value Entropy Search

• ES and PES target entropy reduction over the d-dimensional maximiser, making them more expensive and restricting PES to Euclidean search spaces, while EI, UCB, KG, and batch heuristics trade cost, guarantees, or performance differently.Local penalisation and DPP-based approaches are popular batch heuristics, but the introduction characterises them as supporting only Euclidean spaces.Source: §2.4 · pp. 7–8

3.1 GMES as a Function of Information Gain

• GMES can be expressed as information gain: the entropy reduction in candidate evaluations obtained by observing the objective function’s maximum value.This reformulation makes efficient information-gain calculation the central target of the section.Source: §3.1 · p. 8

3.2 Required Predictive Quantities

• Under a GP surrogate, each candidate evaluation is conditionally independent of other fidelities given its paired objective value, enabling a closed-form density for A|C*<m.The assumption holds trivially for noisy single-fidelity BO and corresponds to the multi-fidelity Markov property; the resulting density contains a multivariate Gaussian cumulative density.Source: §3.2 · pp. 9–10

3.3 Approximating Information Gain

• The information-gain approximation replaces the intractable conditional-entropy calculation with a lower bound derived from information-theoretic inequalities.The bound uses the predictive correlation matrix and closed-form marginal conditional variances, while the exact conditional entropy is unavailable beyond limited cases.Source: §3.3 · p. 10, Proof · p. 11

3.4 GIBBON: General-purpose Information-Based Bayesian OptimisatioN

• GIBBON combines the information-gain bound with Monte Carlo sampling of the maximum value using a Gumbel-based sampler to approximate GMES.The resulting acquisition function is given in closed form and can be implemented with simple algebraic operations; continuous spaces also admit accessible gradients.Source: §3.4 · p. 12
• GIBBON closely approximates MES in a two-dimensional task, sharing all acquisition-function modes and differing only in regions with very low utility.The comparison uses exact MES entropy reductions as ground truth.Source: §3.4 · p. 12, Figure 2 · p. 13

4. Relationship Between GIBBON and Heuristics for Batch Bayesian Optimisation

• GIBBON's batch acquisition decomposes into individual information terms plus a determinant of predictive correlations, balancing informative evaluations with within-batch diversity.The individual terms favour locations providing information about g*, while the determinant favours points with low predictive correlation.Source: §4 · p. 14

4.1 Relationship with Determinantal Point Processes

• GIBBON is equivalent to a DPP whose quality function derives from single-point GIBBON and whose similarity kernel is the surrogate's predictive correlation.This establishes a theoretical basis for using DPPs in batch BO and replaces arbitrary quality and similarity choices with information-theoretic ones.Source: §4.1 · pp. 14–15
• Greedy GIBBON batch selection corresponds to approximate DPP MAP inference, whose submodularity explains the effectiveness of greedy batch filling despite MAP inference being NP-hard.The equivalence follows from allocating the batch with maximal determinant under the DPP formulation.Source: §4.1 · p. 15
• The DPP formulation supports multi-fidelity and structured search spaces, unlike existing DPP-based BO applications limited to single-fidelity Euclidean settings.Its quality and similarity choices reportedly improve over existing DPP heuristics in the experiments.Source: §4.1 · p. 15

4.2 Relationship with Local Penalisation

• GIBBON can also be recast as local penalisation, with predictive-correlation penalties replacing Lipschitz-based penalisation functions.The resulting correlation-based penalty avoids estimating L and is reported to outperform existing local-penalisation methods.Source: §4.2 · pp. 15–16
• Existing soft and hard local penalisation methods depend on a carefully estimated Lipschitz constant, which is defined only for Euclidean search spaces.This constrains their direct applicability to non-Euclidean structured domains.Source: §4.2 · pp. 15–16

5. The Computational Complexity of Information-theoretic Bayesian Optimisation

• The analysis treats one-off initialisation and per-query evaluation as the two acquisition-specific costs, while omitting GP fitting shared by all BO routines.Fitting a GP on n observations costs O(n^3), and predictive means and covariances cost O(n) and O(n^2), respectively.Source: §5 · pp. 16–17, §5.1 · p. 17

5.1 Acquisition Function Initialisation Costs

• Approximation sample sizes for d-dimensional quantities must grow as O(e^d) to preserve accuracy, whereas single-dimensional quantities can use O(1) samples independently of d.The complexity comparison therefore focuses on scaling with search-space dimension d, batch size B, and observations n.Source: §5.1 · pp. 17–18
• GIBBON's initialisation cost is O(n^2e^d), substantially below ES and PES, because it samples maximum values rather than d-dimensional maximiser locations.Only FITBO has a lower initialisation cost, but it supports only noiseless standard BO and uses a complicated construction.Source: §5.1 · p. 18

5.2 Acquisition Function Query Costs

• GIBBON matches the lowest query costs among information-theoretic acquisition functions while supporting standard, stochastic, multi-fidelity, and batch optimisation.Its practical cost is substantially lower than MUMBO and MF-MES because those methods incur additional numerical-integration overhead.Source: §5.2 · pp. 18–19
• GIBBON's acquisition-query complexity is O(B^2n^2 + B^3), from accessing batch predictive covariances and computing their determinant.MF-MES has a similar construction but adds a B-dimensional integral, whose numerical evaluation introduces substantial overhead.Source: §5.2 · p. 18
• ES and PES have larger query costs than GIBBON because they repeatedly process O(e^d) samples of the objective maximiser x* or associated kernel matrices.PPES additionally performs determinant calculations for each precomputed kernel matrix in batch settings.Source: §5.2 · p. 19

6. Experiments

• GIBBON at least matches and often exceeds existing high-performance acquisition functions while incurring orders-of-magnitude lower computational overhead across the experiments.The experiments cover batch and multi-fidelity synthetic benchmarks, molecular design, and a real-world batch multi-task BO framework.Source: §6 · p. 19

6.1 Standard and Batch Optimisation

• GIBBON achieves small regret in competitively few iterations for sequential and batch synthetic optimisation, outperforming standard MES in the noiseless sequential task.Its overhead is at least ten times lower than batch KG, remains nearly fixed as optimisation progresses, and is lower than other high-performing batch methods.Source: §6.1 · pp. 20, 22, Figure 3 · p. 21, Figure 4 · p. 22

6.2.1 GIBBON FOR LARGE BATCH OPTIMISATION

• GIBBON performs effectively for small-to-moderate batches but fails to leverage large parallel batches, with performance dropping significantly at batch size 25.LPEI achieves lower regret with batches of 50 than GIBBON with batches of 10, because the lower-bound approximation becomes dominated by repulsion and produces repeated edge queries.Source: §6.2.1 · p. 24, Figure 6 · p. 24

6.2.2 GIBBON WITH THOMPSON-SAMPLED MAXIMUM VALUES

• Exact Thompson-sampled maximum values provide only small, inconsistent batch improvements over Gumbel sampling while increasing overhead fivefold for B = 1 and threefold for B = 5.The sampler change has no effect on sequential optimisation, so the experiments retain the computationally light Gumbel sampler.Source: §6.2.2 · pp. 25–26, Figure 7 · p. 25

6.3 Multi-fidelity Optimisation

• GIBBON provides at least as effective multi-fidelity optimisation as MUMBO while achieving significantly lower computational overhead across synthetic benchmarks.The regret advantage over MUMBO increases with search-space dimensionality, although their overhead difference narrows because both use the Gumbel sampler.Source: §6.3 · p. 26, Table 3 · p. 26, Figure 8 · p. 27

6.4 Batch Molecular Search

• GIBBON extends molecular BO to effective batch optimisation over non-Euclidean SMILES spaces, providing a modest sequential improvement over EI and supporting batch sizes 5 and 10.It requires only B surrogate predictions per candidate batch and makes no assumptions about the search space, enabling parallel molecular synthesis.Source: §6.4 · p. 28, Figure 9 · p. 29

6.5 Bayesian Optimisation by Sampling Hierarchically

• Replacing KG-CRN with GIBBON yields BOSH, a hierarchical BO framework with small computational overheads and natural batch support for more efficient, higher-precision optimisation.BOSH chooses both evaluation locations and objective realisations through a growing pool modelled with a Hierarchical Gaussian Process.Source: §6.5 · p. 29

6.5.1 REINFORCEMENT LEARNING

• In the lunar-lander task, fixed small collections of initial conditions fail to deliver good true performance, while FASTCV is hampered by updating a large between-realisation correlation matrix.The supplied results describe BOSH’s adaptive realisation selection, including consideration of up to 15 random conditions.Source: Figure 10 · p. 30, §6.5.1 · p. 31

6.5.2 HYPER-PARAMETER TUNING

• BOSH finds reasonably well-performing hyper-parameter configurations using a fraction of the computation required by standard BO and BOSH.FABOLAS fails to improve upon the chosen configuration even when allowed significantly longer runtime.Source: §6.5.2 · p. 32
• BOSH adaptively considers up to four train-test splits, enabling higher-precision tuning than single-split BO and faster tuning than BO with 5-fold or 10-fold cross-validation.These comparisons are shown in Figures 11a–11c.Source: §6.5.2 · p. 32

7. Discussion

• GIBBON extends max-value entropy search with a lightweight approximation for a wide range of Bayesian optimisation problems.Its derivation also connects information-theoretic search, determinantal point processes, and local penalisation.Source: §7 · p. 32
• GIBBON supports batch and multi-fidelity optimisation in highly structured search spaces, demonstrated through a molecular design loop.The framework is intended for settings beyond Euclidean domains.Source: §7 · p. 32

7.1 Limitations and Future Work

• GIBBON performs poorly for large batch sizes, despite its low-cost greedy batch construction.The authors identify improving the diversity-quality trade-off as an important direction for future work.Source: §7.1 · p. 32
• GIBBON has no theoretical guarantees because the tightness and approximation error of its information-theoretic lower bound remain unanalyzed.The authors state that such analysis could clarify performance degradation for large batches and support convergence guarantees.Source: §7.1 · pp. 32–33
• The method could extend to batch multi-objective, constrained, and non-myopic Bayesian optimisation frameworks.These possibilities are presented as future applications beyond the demonstrated settings.Source: §7.1 · p. 33

Appendix A. Extracting The Required Predictive Quantities from a Gaussian Process Surrogate Model

• A Gaussian-process surrogate supplies the predictive quantities required by GIBBON using observations, kernel matrices, kernel vectors, and fidelity information.The multi-fidelity construction assumes that the true objective can be queried, at least noisily, and includes observation-noise terms.Source: Appendix A · p. 34

Appendix B. Proof of Theorem 2

• Theorem 2 characterizes the distribution of A conditioned on C* < m for jointly Gaussian B-dimensional variables.Each pair {A_j, C_j} is jointly Gaussian, with conditional independence across the other components given C_j.Source: Appendix B · p. 34
• The conditional-density expression uses a threshold vector m and multivariate Gaussian density and cumulative-density functions.The covariance construction combines the covariance of C with diagonal correlation and residual terms.Source: Appendix B · p. 34

Proof

• The proof factorizes the conditional density, applies bivariate Gaussian conditioning, and rewrites the integrand as a product of Gaussian densities.A standard Gaussian-product formula then allows one factor to be taken outside the integral, yielding the claimed expression.Source: Proof · pp. 35–36

Appendix C. Experimental Details for Synthetic Benchmarks.

• The appendix provides detailed information about each synthetic benchmark.Source: Appendix C · p. 36
• The synthetic benchmark appendix documents the functions used in the experiments.Source: Appendix C · p. 36
• These benchmark descriptions support the paper’s experimental evaluation of optimisation methods.Source: Appendix C · p. 36

C.1 Standard BO benchmarks

• The Shekel benchmark is four-dimensional, has ten local minima and one global minimum, and is defined on [0, 10]^4.Source: §C.1 · p. 36
• The Ackley benchmark is four-dimensional, has many local minima and a nearly flat outer region surrounding one global minimum, and is defined on [−32.768, 32.768]^4.Source: §C.1 · p. 37
• The Hartmann 6 benchmark is six-dimensional, has six local minima and one global minimum, and is defined on [0, 1]^6.Source: §C.1 · p. 37

• The benchmark suite spans Currin exponential, Hartmann 3, Hartmann 6, and Borehole functions in discrete fidelity spaces.Source: §C.2 · pp. 37–38
• Currin exponential uses two fidelities with query costs 10 and 1.Source: §C.2 · pp. 37–38
• Hartmann 3 uses three fidelities with query costs 100, 10, and 1.Source: §C.2 · p. 37
• Hartmann 6 uses four fidelities with query costs 1000, 100, 10, and 1.Source: §C.2 · p. 38
• Borehole uses two fidelities with query costs 10 and 1.Source: §C.2 · p. 38

Appendix D. A modified GIBBON for BO with large batches

• Down-weighting GIBBON’s diversity term by B^2 addresses its hypothesised dominance over the quality term for large batches.The scaling reflects the B^2 elements in a candidate batch’s predictive covariance.Source: Appendix D · pp. 38–39
• B = 50 batches converge faster with modified GIBBON as batch size increases, whereas standard GIBBON fails for B > 10.Source: Figure 12 · p. 39
• The simple rescaling allows GIBBON to control large parallel resources in the repeated noisy Hartmann experiment.Source: Appendix D · p. 39, Figure 12 · p. 39

Appendix E. Comparing GIBBON with MES

• GIBBON and MES induce different exploration–exploitation trade-offs because their analytical expressions differ, with behavior varying across benchmark functions.GIBBON is particularly suited to Shekel and Ackley but not Hartmann functions.Source: Appendix E · p. 39
• With one max-value sample, GIBBON and MES always choose the same query points, unlike practical implementations using 5 or 10 samples.Source: Appendix E · p. 39

E.1 Equivalence of the degenerate forms of MES and GIBBON

• In the degenerate noiseless setting, both acquisition functions decrease strictly with u, and GIBBON is a strict lower bound on MES.Source: §E.1 · pp. 39–40, Figure 13 · p. 40
• Exact inner-loop maximisation therefore makes degenerate GIBBON and MES select identical points.Source: §E.1 · p. 40
• Degenerate GIBBON inherits degenerate MES’s simple-regret bound, but this guarantee does not extend to multiple samples, batch BO, or multi-fidelity BO.Source: §E.1 · p. 40

F.1 Hierarchical Gaussian Process

• A hierarchical Gaussian process models a shared objective g with an upper kernel and realization-specific deviations with a lower kernel.Each realization is conditionally independent given the shared mean function g.Source: §F.1 · pp. 40–41

F.1.1 PREDICTIVE DISTRIBUTION OF AN HGP

• The HGP uses a compound kernel over locations and realizations and Gaussian observation noise, yielding the joint predictive quantities required by GIBBON.Source: §F.1.1 · p. 41
• HGP prediction requires inversion of an n × n matrix, giving computational cost comparable to standard GP prediction.Source: §F.1.1 · p. 41

F.1.2 BOSH’S KERNEL STRUCTURE

• Tying upper- and lower-kernel length scales leaves BOSH with d + 4 parameters, only two more than a standard Matérn 5/2 GP.Source: §F.1.2 · pp. 41–42

F.2 Initialisation Costs

• BOSH initializes each of two seed-pool elements with d + 5 evaluations, while FASTCV requires at least d + 3 evaluations for each of B seeds.Using fewer initial points severely limited the initial performance of all methods, while BOSH’s seed modeling lowers initialization costs.Source: §F.2 · p. 42

F.3 Reinforcement Learning: Lunar Lander

• The Lunar Lander experiment tunes seven controller thresholds to maximize average reward over 100 random initial conditions in a stochastic environment.Rewards include fuel-use penalties, crash penalties, landing bonuses, and a landing-zone bonus.Source: §F.3 · p. 42

F.4 Hyper-parameter Tuning: IMDB SVM

• The IMDB SVM experiment tunes C and gamma for sentiment classification on 50,000 reviews using a bag-of-words tf-idf representation.Optimization uses 1,000 reviews for fitting and tuning, with 49,000 held out to measure true performance.Source: §F.4 · pp. 42–43