PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Information Source Optimization

Matthias Poloczek, Jialei Wang, Peter I. Frazier

arXiv:1603.00389v2stat.ML

TL;DR

The paper addresses Bayesian optimization when cheap approximations are biased and noisy rather than reliable surrogates. It combines a joint Gaussian-process model with a cost-sensitive Knowledge Gradient, and reports higher-quality solutions at lower exploration cost than competing methods.

  • Problem

    The problem is how to optimize an expensive black-box objective using cheaper approximations whose bias can vary across the domain.

  • Method

    The method jointly models the objective and information sources with a Gaussian process and selects queries using Knowledge Gradient benefit per unit cost.

  • Results

    The method consistently finds considerably higher objective values while incurring less exploration cost than other state-of-the-art techniques.

  • Takeaways & Limitations

    The framework supports rigorous uncertainty handling for model discrepancies and noisy observations while exploiting correlations across information sources.

  • Takeaways & Limitations

    The model assumes known, continuously differentiable cost and variance functions and offers correlated-discrepancy modeling through source groups, deferred to the online supplement.

Abstract

from arXiv · show

We consider Bayesian optimization of an expensive-to-evaluate black-box objective function, where we also have access to cheaper approximations of the objective. In general, such approximations arise in applications such as reinforcement learning, engineering, and the natural sciences, and are subject to an inherent, unknown bias. This model discrepancy is caused by an inadequate internal model that deviates from reality and can vary over the domain, making the utilization of these approximations a non-trivial task. We present a novel algorithm that provides a rigorous mathematical treatment of the uncertainties arising from model discrepancies and noisy observations. Its optimization decisions rely on a value of information analysis that extends the Knowledge Gradient factor to the setting of multiple information sources that vary in cost: each sampling decision maximizes the predicted benefit per unit cost. We conduct an experimental evaluation that demonstrates that the method consistently outperforms other state-of-the-art techniques: it finds designs of considerably higher objective value and additionally inflicts less cost in the exploration process.

1. Introduction

The paper formulates optimization with expensive true evaluations and cheaper, potentially biased approximations as MISO, then introduces a unified Bayesian model and cost-sensitive acquisition strategy.

  • Problem: MISO optimizes an expensive black-box objective while using cheaper information sources that may differ from reality through domain-varying model discrepancy.This discrepancy is distinct from observational noise and can make approximations difficult to exploit safely.
  • Related work: Existing multifidelity approaches often impose hierarchical, unbiased, or independently noisy information-source assumptions that restrict correlations and applicability.A hierarchy can prevent lower-fidelity queries from adding knowledge after a high-fidelity evaluation at the same point.
  • Contributions: The proposed model jointly represents the objective and information sources, enabling rigorous uncertainty updates across sources and explicit quantification of source bias.A new observation can reduce uncertainty about other sources, including when it comes from a lower-fidelity source.
  • Contributions: The acquisition function extends the Knowledge Gradient to multiple sources with differing costs and selects samples by predicted benefit per unit cost.The policy is described as one-step Bayes optimal for this trade-off, and its cost-sensitive KG factor is analytically computable.
  • Contributions: The framework also models correlated discrepancies among groups of information sources, such as simulations sharing approximations or data.This extends the model beyond independent source discrepancies.

2. The Model

The model treats the true objective and multiple noisy, possibly biased information sources within a Gaussian-process framework, with source-specific discrepancy, cost, and noise functions.

  • Problem setup: The objective g is optimized over a compact feasible design set D, while information sources provide potentially biased or noisy observations about it.The unbiased objective is designated IS0, and each source has a query cost function.
  • Problem setup: Each source observation has mean f(ℓ, x), variance λℓ(x), and model discrepancy δℓ(x) = g(x) − f(ℓ, x).The discrepancy represents systematic deviation from the objective, not merely sampling noise.
  • Gaussian-process model: A single Gaussian process is placed on f across the objective and information sources, providing a uniform Bayesian treatment of their joint behavior.The framework permits arbitrary mean functions and positive semidefinite covariance kernels, with parameterized classes supplied for MISO.
  • Discrepancy models: The independent-discrepancy model uses separate Gaussian processes for source discrepancies and adds each discrepancy to the shared objective process.Zero-mean discrepancy priors are used when there is no strong prior belief about bias direction.
  • Discrepancy models: A more general model represents correlated discrepancies within groups of related information sources, while the main text defers this class to the online supplement.The grouping assumption is intended for sources whose approximations tend to deviate from truth in related ways.

3. The Value of Information Analysis

The algorithm chooses both an information source and design by maximizing expected value of information relative to query cost, then updates its posterior iteratively.

  • Sequential decision: At each round, the algorithm selects a design x and information source ISℓ to improve the estimate of the objective maximum over D.The current best solution is represented by the maximum posterior mean of the unbiased objective source.
  • Value of information: For uniform costs, the value of information is the expected gain over the current posterior optimum, expressed through the Knowledge Gradient factor.The current posterior optimum is maxx′∈D µ(n)(0, x′).
  • Cost-sensitive Knowledge Gradient: With variable costs, the cost-sensitive Knowledge Gradient maximizes expected gain divided by the corresponding query cost.The resulting nested optimization computes (ℓ(n+1), x(n+1)) ∈ argmax CKG(ℓ, x).
  • Optimization: The Knowledge Gradient factor is computed using h(µ̄n, σ̄n(ℓ,x)), then divided by cℓ(x) and optimized over source-design pairs.Gradients with respect to x permit multi-start gradient-based optimization when costs are differentiable.
  • Algorithm: misoKG estimates hyperparameters, forms the posterior, repeatedly selects and observes a source-design pair, updates the posterior, and returns the best estimated objective point.The domain inner maximization can be discretized using a Latin Hypercube design.

4. Numerical Experiments

The experiments compare misoKG with state-of-the-art MISO methods across Rosenbrock, image classification, and assemble-to-order benchmarks. Across these settings, misoKG generally achieves strong objective performance while using information sources cost-effectively, including under model discrepancy and observational noise.

  • Experimental Setups: The evaluation compares misoKG with MTBO+ and misoEI on Rosenbrock, image classification, and assemble-to-order MISO benchmarks.All methods receive identical initial datasets drawn via Latin Hypercube designs.
  • The Rosenbrock Benchmarks: misoKG typically finds an almost optimal Rosenbrock solution within 5-10 samples while achieving better gain per unit cost than its competitors.It relies primarily on cheap samples, whereas misoEI queries the expensive truth and accumulates considerably higher cost.
  • The Rosenbrock Benchmarks: Under larger observational noise and smaller source-cost differences, misoKG outperforms the other Rosenbrock methods and has an even larger relative performance difference.The alternative setup uses λ0(x) = 1 and c0(x) = 50 for IS0.
  • The Image Classification Benchmark: After about 80 information-source queries, misoKG achieves an MNIST test error of about 7.1% and has better late-iteration performance than MTBO+ at the same costs.MTBO+ is reported to converge to the optimum eventually.
  • The Assemble-To-Order Benchmark: On the assemble-to-order benchmark, misoKG averages a gain of 26.1 at an average query cost of 54.6, or 6.3% of the cost misoEI requires for a comparable score.misoKG and MTBO+ mostly use the cheap, biased source, while misoEI almost always selects the most expensive simulation.
  • The Assemble-To-Order Benchmark: misoKG generally exploits the cheap biased source first and switches to the unbiased noisy source later when needed to identify the optimum more exactly.Its first call to IS2 typically occurs after about 60-80 steps, with about ten IS2 queries during the first 150 steps.

A.1. Correlated Model Discrepancies

The model allows information sources to have correlated model discrepancies by grouping sources into partitions and assigning one Gaussian process to each group. These processes are incorporated into a single Gaussian-process prior over the objective and all sources.

  • Correlated model discrepancies: Information sources are partitioned so sources in the same group share a model-discrepancy Gaussian process.The partition function k maps each source to its group, with one independent process ε(k(ℓ), x) per partition.
  • Correlated model discrepancies: The unified model represents each source as the objective plus shared discrepancy and source-specific discrepancy.For every source ℓ, f(ℓ, x) = f(0, x) + ε(k(ℓ), x) + δℓ(x), with f(0, x) equal to the objective g(x).
  • Correlated model discrepancies: All discrepancy processes are incorporated into one Gaussian-process prior over the objective and information sources.The composite covariance function is then defined over source-design pairs.

A.2. Estimation of Hyper-Parameters

The paper estimates model hyper-parameters by maximum a posteriori inference, motivated by the limited data typical of multi-information source optimization. It specifies priors and constructs discrepancy observations from paired source evaluations.

  • Estimation of Hyper-Parameters: Hyper-parameters are fit using maximum a posteriori estimation, with a prior selected for the application.The method section introduces MAP estimation and a specific prior.
  • Estimation of Hyper-Parameters: MAP estimates are suggested because typical MISO scenarios provide little data and may make them more robust than maximum likelihood estimates.The benchmarks showed essentially the same algorithm performance with maximum likelihood estimates.
  • Estimation of Hyper-Parameters: For Matérn kernels, each information source requires estimating d length scales and one signal variance.These are the d + 1 hyper-parameters identified for each source.
  • Estimation of Hyper-Parameters: The procedure evaluates all information sources on shared design points and uses source-output differences to estimate discrepancy-process hyper-parameters.The discrepancy observations are Δi = {ISi(x) − IS0(x) | x ∈ D}.
  • Estimation of Hyper-Parameters: Prior means for length scales are set to the corresponding parameter-interval lengths, while prior variances are assigned for all hyper-parameters.The supplied passage specifies this prior construction but truncates the final variance expression.

A.3. How to Express Beliefs on Fidelities of Information Sources

The model can encode beliefs about information-source fidelity through source-specific coefficients that alter covariance without changing the mean. Increasing a coefficient makes that source less influential in regression.

  • Expressing beliefs on fidelities: A coefficient αℓ can represent beliefs about the relative accuracy of information source ℓ.It may be fitted from data or set by a domain expert when sources are not unbiased estimators.
  • Expressing beliefs on fidelities: The coefficient changes the covariance contribution of source ℓ while leaving the model mean unchanged.For uncorrelated sources, the additional term is 1ℓ,m · αℓ · Σℓ(x, x′).
  • Expressing beliefs on fidelities: Larger αℓ encodes greater uncertainty, so observations from that source have less influence in Gaussian-process regression.Even a noiseless deterministic source can leave nonzero uncertainty about the true objective when its source uncertainty is large.

B. Parallel Computation of the Cost-Sensitive Knowledge Gradient

The paper develops parallel computation for the cost-sensitive Knowledge Gradient by exploiting independent candidate evaluations and parallelizing value-of-information calculations. It also discusses enumeration-based outer optimization when gradient methods may miss good locations.

  • Parallel computation: The cost-sensitive Knowledge Gradient can use gradients to select the next sample point and information source by expected gain per unit cost.The inner optimization is discretized for computation.
  • Parallel computation: Discretizing the outer maximization over sources and design points can help when the CKG surface has many local maxima.The alternative enumerates all CKG factors over a discrete set A.
  • Parallel computation: The enumeration approach has runtime O(M · |A|^2 · log(|A|)), which may bottleneck high-accuracy domain probing.A sorting method can remove the logarithmic factor, while parallelization provides essentially linear speedup.
  • Parallel computation: Computations for different next-sample decisions are independent, requiring only data scattering and selection of the best sample.This yields essentially linear speedup across cores.
  • Parallel computation: The method provides two separately usable or combinable parallelization levels for multi-core cluster CPUs.They parallelize candidate decisions and value-of-information computation within each iteration.
  • Parallel computation: The implementation sorts candidate means and standard deviations, removes dominated entries, and scans the remaining intervals to compute the value function.The interval sequence determines which candidate maximizes the linear form for each z.
Loading 1603.00389v2…