PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-fidelity Bayesian Optimisation with Continuous Approximations

Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, Barnabas Poczos

arXiv:1703.06240v1stat.ML

TL;DR

Expensive black-box optimisation motivates methods that exploit cheaper approximations, yet most existing multi-fidelity approaches use only finitely many fidelities. The paper introduces BOCA for continuous fidelity spaces, gives theoretical regret guarantees, and reports stronger performance than several alternatives in synthetic and real experiments.

  • Problem

    Expensive function evaluations create a need for optimisation methods that exploit cheaper, less accurate approximations.

  • Method

    BOCA models multi-fidelity optimisation over a continuous fidelity space using Gaussian processes and a fidelity-selection strategy.

  • Results

    BOCA has a regret bound and achieves better simple regret than methods such as GP-UCB that ignore approximations.

  • Takeaways & Limitations

    Continuous-fidelity modelling lets BOCA share information across fidelities with fewer hyper-parameters than existing multi-fidelity methods.

  • Takeaways & Limitations

    The analysis is currently limited in its treatment of more general fidelity spaces and stronger regret bounds for finite-dimensional kernels.

Abstract

from arXiv · show

Bandit methods for black-box optimisation, such as Bayesian optimisation, are used in a variety of applications including hyper-parameter tuning and experiment design. Recently, \emph{multi-fidelity} methods have garnered considerable attention since function evaluations have become increasingly expensive in such applications. Multi-fidelity methods use cheap approximations to the function of interest to speed up the overall optimisation process. However, most multi-fidelity methods assume only a finite number of approximations. In many practical applications however, a continuous spectrum of approximations might be available. For instance, when tuning an expensive neural network, one might choose to approximate the cross validation performance using less data $N$ and/or few training iterations $T$. Here, the approximations are best viewed as arising out of a continuous two dimensional space $(N,T)$. In this work, we develop a Bayesian optimisation method, BOCA, for this setting. We characterise its theoretical properties and show that it achieves better regret than than strategies which ignore the approximations. BOCA outperforms several other baselines in synthetic and real experiments.

1. Introduction

Multi-fidelity optimisation uses cheaper, less accurate approximations to guide expensive black-box optimisation, but existing approaches largely assume finitely many fidelities. This paper introduces BOCA for continuous fidelity spaces and reports theoretical and empirical advantages.

  • Motivation: Multi-fidelity methods trade evaluation cost against approximation accuracy to make expensive black-box optimisation more tractable.Cheap approximations can guide search before expensive evaluations of the target function.
  • Continuous approximations: Continuous fidelity spaces arise naturally when approximation quality varies with data size, training iterations, simulation granularity, or other continuous controls.Hyper-parameter tuning can use fewer data points N and fewer iterations T to approximate validation accuracy.
  • Contribution: Theorem 1 shows that BOCA uses cheap low-fidelity evaluations to discard poor configurations and reserves high-fidelity evaluations for promising regions.This behaviour is supported when cross-validation performance varies smoothly with data size and training iterations.
  • Contribution: BOCA is designed for Bayesian optimisation with continuous approximations rather than a finite set of fidelities.The method uses Gaussian-process assumptions and targets general bandit optimisation tasks.
  • Contribution: BOCA combines a regret analysis with empirical comparisons on synthetic problems and real hyper-parameter-tuning and astrophysics examples.The reported experiments compare BOCA with both multi-fidelity and non-multi-fidelity alternatives.

2. Preliminaries

The paper formulates the target objective as a high-fidelity slice of a function over domain and fidelity spaces, then models their relationship with Gaussian processes. Its setup accounts for noisy observations, fidelity costs, information gaps, and simple regret.

  • Gaussian processes: A Gaussian process is a random function characterised by a mean function and covariance kernel, with observations corrupted by Gaussian noise.The posterior after observations remains a Gaussian process.
  • Gaussian processes: Radial kernels make covariance depend on distance, and the squared-exponential bandwidth controls prior smoothness across the domain.Larger bandwidths produce smoother sampled functions.
  • Bayesian optimisation: GP-UCB selects evaluations by maximising a posterior upper confidence bound that balances exploitation and exploration.The posterior mean favours high predicted values, while posterior uncertainty favours poorly known regions.
  • Problem setup: The target function is the high-fidelity slice f(·) = g(z•, ·) of a function defined jointly over fidelity space Z and search domain X.The optimisation target is the maximiser of this slice, not of a cheaper fidelity.
  • Problem setup: Queries select both a fidelity z and domain point x, observe noisy g(z, x), and incur a known fidelity-dependent cost λ(z).In the hyper-parameter example, the cost is λ(N,T) = O(N^2T).
  • Regret: Multi-fidelity simple regret measures optimisation error at the target fidelity after spending a resource budget Λ.Cheap evaluations help guide search, but reward is defined only through the optimum of g(z•, ·).
  • Problem setup: The product kernel separates fidelity and domain similarity, while φZ determines how informative cheaper fidelities are about the target slice.For a squared-exponential fidelity kernel, larger bandwidth hZ implies greater smoothness and a smaller information gap.

3. BOCA: Bayesian Optimisation with Continuous Approximations

BOCA selects both domain points and fidelities sequentially, using lower-cost approximations when their uncertainty and informativeness justify them. Its analysis shows that informative approximations concentrate high-fidelity queries near the optimum, improving regret relative to GP-UCB, while retaining comparable guarantees when approximations are less informative.

  • Fidelity and point selection: BOCA selects the domain point by maximizing an upper confidence bound, then chooses the cheapest fidelity passing its selection criteria, defaulting to the target fidelity otherwise.The criteria balance fidelity cost, posterior uncertainty, and the information gap from the target fidelity.
  • Fidelity and point selection: The fidelity threshold increases with both evaluation cost and information gap, favoring cheap, informative fidelities while discouraging queries far from the target.The information gap increases with distance from the target fidelity, making distant fidelities less likely to qualify.
  • Theoretical results: BOCA’s analysis shows that, after capital Λ, fewer than n^α target-fidelity queries occur outside a subset Xρ containing the optimum x⋆.This concentration result underpins the method’s use of lower-fidelity information during high-fidelity optimization.
  • Theoretical results: For smooth fidelity dependence, Xρ is small and BOCA improves over GP-UCB by a factor proportional to vol(Xρ)/vol(X) asymptotically.With a squared-exponential fidelity kernel, larger bandwidth hZ makes approximations smoother and Xρ smaller.
  • Theoretical results: When fidelity dependence is less smooth, BOCA’s advantage diminishes but its regret remains no worse than GP-UCB up to constant factors.The paper also states that the latter term in the regret bound vanishes rapidly with its n−(1−α/2) dependence.
  • Empirical scope and limitations: The method’s experiments compare BOCA with multi-fidelity and non-multi-fidelity alternatives on synthetic problems and real hyper-parameter-tuning and astrophysics examples.The theoretical presentation suppresses constants and polylogarithmic terms, with a rigorous treatment given in Appendix B.

4. Experiments

The experiments evaluate BOCA against single-fidelity and finite-fidelity baselines on synthetic, astrophysical, and hyperparameter-tuning problems. BOCA generally performs strongly, adapting to fidelity smoothness and outperforming alternatives on most synthetic problems.

  • Experimental setup: BOCA is compared with GP-UCB, GP-EI, MF-GP-UCB, and MF-SKO across synthetic and real optimisation problems.GP-UCB and GP-EI ignore fidelity information, whereas MF-GP-UCB and MF-SKO use finite fidelity sets.
  • Synthetic experiments: BOCA outperforms other baselines when the fidelity function is smooth and remains robust when fidelity smoothness is low.The two sanity checks use fidelity-space SE bandwidths 1.0 and 0.01; the latter produces highly unsmooth variation.
  • Synthetic experiments: BOCA outperforms all methods on every modified global-optimisation benchmark except Borehole, where MF-GP-UCB performs better.The experiments add Gaussian observation noise and learn unknown GP hyperparameters by marginal likelihood every 25 iterations.
  • Real experiments: The astrophysics task optimises average log likelihood over three cosmological parameters using dataset size and integration-grid size as continuous fidelity choices.The maximum-fidelity setting uses N = 192 and G = 10^6, with cost λ(N, G) = NG.
  • Real experiments: The news-group task tunes an RBF support-vector classifier while varying dataset size N and training iterations T, with cost λ(N, T) = NT.The hyperparameters are the regularisation penalty and kernel temperature, each ranging from 10^-2 to 10^3.
  • Evaluation protocol: The synthetic and real evaluations use simple regret or maximum value as outcomes, with repeated runs and standard-error bars.Figure 3 averages 20 experiments; Figure 4 averages 20 Branin experiments and 10 experiments each for supernova and news groups.

5. Conclusion

The paper presents BOCA for Bayesian optimisation with continuous fidelity spaces, establishes theoretical regret guarantees, and evaluates it against competing methods. Its conclusion emphasizes information sharing across fidelities and identifies broader theoretical and modelling extensions as future work.

  • 5. Conclusion: BOCA treats approximations as arising from a continuous fidelity space rather than a finite set of fidelities.The paper states that this setting can potentially be extended to arbitrary fidelity spaces.
  • 5. Conclusion: The paper bounds BOCA’s simple regret and reports that its regret is better than GP-UCB, which ignores approximations.The reported gains are determined by the smoothness of the fidelity space.
  • 5. Conclusion: BOCA shares information across fidelities effectively and uses more natural modelling assumptions with fewer hyperparameters than existing multi-fidelity methods.The conclusion contrasts BOCA with existing finite-fidelity approaches.
  • 5. Conclusion: Empirically, BOCA is competitive with other baselines on synthetic and real problems.The empirical scope includes the experiments described in the paper’s synthetic and application sections.
  • Future work: Future work includes extending the regret analysis to finite-dimensional kernels and developing theory for more general fidelity spaces with suitable kernels.The paper notes that its current analysis techniques do not carry over straightforwardly to finite-dimensional non-radial kernels.
  • Theoretical scope: The theoretical analysis assumes stationary radial kernels and regularity conditions satisfied by sufficiently smooth kernels such as SE and Matérn kernels with ν > 2.The cited assumptions concern kernel structure and partial derivatives.

A.2. Some Technical Results

This appendix collects technical tools used in the theoretical analysis, including Gaussian concentration, GP mutual-information results, and posterior-variance control. These lemmas support bounds on uncertainty in the Gaussian-process models.

  • Technical lemmas: The GP mutual-information lemma relates noisy observations to latent function values on a finite queried set.It is stated for observations y = f(x) + ε with Gaussian noise variance η^2.
  • Role in analysis: The appendix uses these results to control posterior variance for the f and g Gaussian processes.The posterior-variance bound is identified as a technical ingredient for the analysis.
  • Technical lemmas: The posterior-variance lemma controls uncertainty after repeated observations at one point when the kernel is radial.It bounds the posterior variance at all domain points after s observations at a single location.
  • Provenance: The cited posterior-variance result is proved in earlier work as part of a larger proof.The appendix reproduces the result for use in its analysis.

B. Analysis

The analysis formalizes BOCA’s query behavior around a dilated near-optimal set and establishes a high-probability theorem under GP and regularity assumptions.

  • Query localization: BOCA’s analysis shows that most evaluations at the target fidelity z• lie inside Xρ,n after n queries.Xρ,n is a dilation of Xρ arising from the covering argument.
  • Query localization: Xρ,n approaches Xρ at a polynomial rate as n →∞ for every α > 0.The dilation has radius proportional to d/n^(α/2d).
  • Main theorem: Theorem 8 gives a high-probability regret guarantee for BOCA on Z = [0, 1]^p and X = [0, 1]^d under GP and fidelity regularity assumptions.For every α ∈ (0, 1), suitable ρ and Λ0 yield the guarantee with probability at least 1 −δ for all Λ ≥Λ0.
  • Proof strategy: The proof partitions queries into target-fidelity queries in Xρ,n, queries outside that set, and queries at other fidelities.The analysis bounds these components separately using coverings, information gaps, and posterior-variance arguments.
  • Proof strategy: The technical setup controls query counts through dilated sets, fidelity thresholds, and coverings of the domain X.These constructions are used to show that the latter query classes are small and target-fidelity queries dominate.

B.2. Some Technical Lemmas

These technical lemmas establish high-probability confidence and discretisation guarantees, then relate information gaps to posterior uncertainty. Together, they provide the ingredients for controlling BOCA’s continuous-domain analysis.

  • The first lemma shows that the UCB ϕ_t upper bounds f(x_t) at every evaluated domain point.
  • With probability greater than 1 − δ/6, discretisation error satisfies |f(x) − f([x]_t)| ≤ 1/t^2 for every t ≥ 1 and x ∈ X.
  • With probability greater than 1 − δ/3, posterior deviations on every discretisation point satisfy |f(a) − µ_{t−1}(a)| ≤ β_t^1/2 σ_{t−1}(a).
  • The discretisation lemma uses the regularity condition and a time-dependent finite grid whose size is controlled through β_t.
  • Lemma 11 relates the information-gap quantity τ_{t−1}(z,x) to the posterior standard deviation σ_{t−1}(x), using radial-kernel variance comparisons.

B.3. Proof of Theorem 8

Theorem 8 is proved by bounding queries in nonoptimal-fidelity and nonoptimal-region sets, controlling random plays, and then applying information-gain arguments to simple regret. The proof also develops covering-number bounds for continuous fidelity and domain spaces.

  • Queries in the fidelity-exclusion set satisfy T_n(F_n) ≤ n^α with probability at least 1 − δ/6.
  • 47?
  • Covering arguments show that posterior variance becomes small inside sufficiently sampled balls, yielding T_n(H_n) ≤ C_2 Ω_n(H_n) β_n poly(λ_r).
  • For sufficiently large Λ, the number of random queries is bounded by N ≤ 2Λ/λ(z•), after establishing that more than half of the plays occur at the target fidelity.
  • The proof bounds plays at fidelities z ≠ z• and outside X_{ρ,n} at z• before controlling simple regret through maximum information gain.
  • For squared-exponential kernels, the covering construction is polylogarithmic in n; analogous Matérn constructions have a worse logarithmic exponent.
  • The choice q = 1/(p + d + 2) makes capital density across fidelities with λ(z) < λ(θ_t(A)) roughly uniform, although its optimality for GP optimisation is left unclear.

B.3.1. PROOF OF LEMMA 12

The proof of Lemma 12 uses UCB maximisation, posterior-variance thresholds, and the definition of Q_t(A) to bound how often BOCA queries a suboptimal region. The resulting argument converts persistent UCB optimism into a query-count bound.

  • For A excluding the optimum, the UCB maximiser b satisfies ϕ_t(b) > f⋆ − 1/t^2 whenever BOCA queries A.
  • The proof identifies a time t between u + 1 and n where b remains above the near-optimal UCB threshold while τ_{t−1}(b) < γ(θ).
  • The definition of Q_t(A) supplies a lower bound on f⋆ − f(x), linking suboptimality in A to the variance threshold γ(θ).
  • The remaining inequalities use Lemma 5, the theorem’s conditions on β_t, and an integral bound on the resulting sum.

B.3.2. PROOF OF LEMMA 14

The proof bounds posterior-variance terms using queries restricted to a fidelity slice and invokes mutual-information maximization to complete the result.

  • Queries outside the fidelity slice can only decrease GP variance, so the first sum is bounded using only slice queries.
  • The proof applies u2/v2 ≤ log(1+u2)/log(1+v2) to obtain the stated intermediate bound.
  • The result follows because Ψs(A) maximizes mutual information among all subsets of size s.

C.1. Implementation Details

The implementation maps domains to unit hypercubes, initializes Gaussian-process methods with random queries, and updates model and fidelity-selection settings during optimization.

  • The domain and fidelity coordinates are linearly transformed to [0, 1]^d and [0, 1]^p.
  • GP methods receive uniform random initialization using Λ/10 capital; single-fidelity methods start at z•, while multi-fidelity methods sample available fidelities randomly.
  • Except in the first two Figure 3 experiments, GP hyper-parameters are learned by marginal likelihood after initialization and updated every 25 iterations.The implementation uses a squared-exponential kernel with separate learned bandwidths for each dimension.
  • βt is set to 0.5d log(2ℓt+1), using an effective L1 diameter scaled by inverse kernel bandwidths.
  • The DiRect algorithm is used to maximize ϕt.
  • The practical fidelity set is formed from a finely sampled grid filtered by the three conditions in (7), with the threshold factor updated during optimization.The factor starts at c = 1 and is updated every 20 iterations.

C.2. Description of Synthetic Functions

The experiments use synthetic Gaussian-process samples and standard benchmark functions with continuous fidelity spaces, specified domains, costs, and noise levels.

  • Synthetic Gaussian-process functions are interpolated from values on a 50×50 grid over the two-dimensional Z×X space.The experiments use squared-exponential kernels, η2 = 0.05, and λ(z) = 0.2 + 6z2.
  • The Currin exponential function uses X = [0, 1]^2, Z = [0, 1], z• = 1, λ(z) = 0.1 + z2, and η2 = 0.5.
  • The Hartmann constructions use p = 4 for the 3-dimensional case and p = 2 for the 6-dimensional case, reducing to standard Hartmann functions at z = z• = 1p.
  • The paper also includes a Borehole function taken from Xiong et al. (2013).
  • A synthetic function is defined by g(z, x) = zf2(x) + (1 − z)f1(x) over Z = [0, 1] with z• = 1.Its cost is λ(z) = 0.1 + z1.5 and its noise variance is η2 = 5.
  • The Branin benchmark uses X = [[−5, 10], [0, 15]]2 and a three-dimensional fidelity space Z = [0, 1]3.At z = z• = 1p, the construction becomes the standard Branin function.
Loading 1703.06240v1…