PaperlayerView exact revision on arXiv

Source-linked AI summary

Recent Advances in Bayesian Optimization

Xilu Wang, Yaochu Jin, Sebastian Schmitt, Markus Olhofer

arXiv:2206.03301v2cs.LGcs.DCcs.NEmath.OC

TL;DR

Bayesian optimization addresses expensive black-box problems, including noisy objectives and settings lacking closed-form expressions or gradients. This paper systematically reviews recent advances by organizing methods into nine categories focused on surrogate models and acquisition functions, and identifies open challenges for future research.

  • Problem

    Many applications require optimizing noisy, expensive, or gradient-free black-box objectives, motivating data-efficient Bayesian optimization methods.

  • Method

    The paper conducts a systematic literature review, dividing Bayesian optimization work into nine categories and examining Gaussian process models and acquisition functions.

  • Results

    The survey presents recent Bayesian optimization techniques across diverse optimization scenarios and identifies open problems and future research directions.

  • Takeaways & Limitations

    Bayesian optimization remains an active approach for expensive black-box optimization, with further development needed as new scientific and technological applications pose additional challenges.

  • Takeaways & Limitations

    Distributed Bayesian optimization still lacks rigorous convergence guarantees and must address communication costs, asynchronous settings, and complex network constraints.

Abstract

from arXiv · show

Bayesian optimization has emerged at the forefront of expensive black-box optimization due to its data efficiency. Recent years have witnessed a proliferation of studies on the development of new Bayesian optimization algorithms and their applications. Hence, this paper attempts to provide a comprehensive and updated survey of recent advances in Bayesian optimization and identify interesting open problems. We categorize the existing work on Bayesian optimization into nine main groups according to the motivations and focus of the proposed algorithms. For each category, we present the main advances with respect to the construction of surrogate models and adaptation of the acquisition functions. Finally, we discuss the open questions and suggest promising future research directions, in particular with regard to heterogeneity, privacy preservation, and fairness in distributed and federated optimization systems.

1 INTRODUCTION

Bayesian optimization addresses expensive, noisy, derivative-free black-box problems by using probabilistic surrogates and acquisition functions to guide data-efficient sampling. This survey updates earlier reviews with a taxonomy of nine groups and emerging topics.

  • Motivation: Bayesian optimization targets noisy, expensive, or derivative-free objectives where metaheuristics may require many evaluations.Its data efficiency comes from incorporating prior beliefs and balancing exploration with exploitation.
  • Fundamentals: A Bayesian optimization model combines a prior over the objective with posterior updating after new observations.The surrogate defines a distribution over the objective and is refined using Bayes’ rule.
  • History and applications: Earlier work established probability of improvement, expected improvement, and extensions from one-dimensional to high-dimensional optimization.Engineering applications helped popularize Bayesian optimization, which later spread to materials, finance, reinforcement learning, and hyperparameter tuning.
  • Survey motivation: Earlier reviews did not comprehensively cover the field’s abundant extensions or advances published since the major foundational survey.The paper motivates an updated synthesis for researchers and practitioners.
  • Survey scope: The survey organizes Bayesian optimization algorithms into nine groups according to optimization-problem characteristics and highlights surrogate, acquisition-function, or combined emphases.It also discusses Bayesian dynamic, distributed, federated, heterogeneous, and fair optimization.

2 FUNDAMENTALS OF BAYESIAN OPTIMIZATION

Bayesian optimization uses a Gaussian-process surrogate and an acquisition function to choose informative evaluations of an expensive black-box objective. Common acquisition functions trade off exploration and exploitation, while newer information-theoretic criteria target computational efficiency or broader application settings.

  • Gaussian-process surrogate: Gaussian processes model noisy objective observations with a mean function, covariance kernel, and predictive mean and variance.Kernel hyperparameters can be inferred by maximizing the log marginal likelihood.
  • Acquisition-function role: Acquisition functions identify the next sample by balancing exploration of uncertain regions with exploitation of high predicted objective values.The standard Bayesian optimization loop repeatedly evaluates an acquisition function, samples the objective, and updates the surrogate.
  • Classical acquisition functions: Probability of improvement, expected improvement, knowledge gradient, and confidence bounds use different criteria for selecting evaluations.EI has been extended to parallel, multi-objective, constrained, noisy, multifidelity, and high-dimensional optimization.
  • Acquisition-function caveat: Expected improvement tends to explore around the initial best point before searching more globally.This behavior follows because points close to the current best point receive high EI values.
  • Sampling-based acquisition: Thompson sampling draws candidate arms from the posterior and selects the arm with the highest simulated reward.Its full parallelization and distribution have driven increased interest for bandit problems.
  • Information-theoretic acquisition: Entropy-based acquisition functions seek information about either the global optimum location or its maximum value.MES uses one-dimensional p(y*|D_n), making it computationally simpler than ES and PES while performing at least as well empirically.

3 RECENT ADVANCES IN BAYESIAN OPTIMIZATION

The survey structures the expanding Bayesian optimization literature around optimization-problem characteristics. It focuses on advances in surrogate construction and acquisition-function design across these categories.

  • Taxonomy: The paper categorizes state-of-the-art Bayesian optimization research according to the characteristics of the optimization problems addressed.This organization is intended to clarify the abundant literature.
  • Research focus: The review focuses on major advances in Gaussian-process surrogates and acquisition functions for diverse optimization scenarios.The taxonomy provides a structured overview of existing work.
  • Scope: The survey presents recent Bayesian optimization developments beyond standard black-box single-objective optimization.The preceding fundamentals establish the standard problem before the state-of-the-art review.

3.1 High-dimensional optimization

High-dimensional Bayesian optimization is difficult because dimensionality complicates surrogate construction, acquisition optimization, and data requirements. Recent methods address this through structural assumptions, dimensionality reduction, embeddings, geometry-aware models, additive decompositions, and scalable alternatives.

  • Challenge: High-dimensional Bayesian optimization remains an open challenge because dimension affects both Gaussian-process construction and acquisition-function optimization.The difficulty arises in applications such as hyperparameter optimization as model complexity increases.
  • Structural assumptions: Many methods assume low effective dimensionality or additive structure to make high-dimensional objectives tractable.These assumptions are common but can restrict applicability when all variables contribute or interactions are complex.
  • Dimensionality reduction: Random-embedding methods optimize a high-dimensional objective in a lower-dimensional latent space before projecting selected points back to the original domain.REMBO randomly generates an embedding, fits a GP, optimizes an acquisition function, and inverse-projects the selected point.
  • Learned representations: Learned latent spaces use PCA, VAEs, supervised learning, or semi-supervised learning to identify lower-dimensional representations.VAE-based approaches map high-dimensional inputs to a low-dimensional latent space, though unsupervised representations can have disadvantages.
  • Geometry-aware methods: Nonlinear and geometry-aware embeddings model manifolds and non-Euclidean search spaces more expressively than linear embeddings.HD-GaBO jointly learns a structure-preserving mapping and latent objective with a manifold Gaussian process.
  • Additive structure: Projected-additive models relax disjoint-group restrictions by allowing overlapping groups represented through dependency or sparse factor graphs.Add-GP-UCB exemplifies additive modeling with sums of functions over small variable subsets.

3.2 Combinatorial optimization

Combinatorial Bayesian optimization addresses expensive black-box objectives over discrete, categorical, integer, set, or graph-structured spaces, where continuous-space assumptions and combinatorial explosion hinder efficient search. Recent approaches modify surrogate models, representations, kernels, and acquisition-function optimization, while mixed-variable settings remain relatively underexplored.

  • Combinatorial Bayesian optimization targets expensive black-box objectives over integer, set, categorical, or graph-structured search spaces.
  • Continuous-space Gaussian process methods scale poorly in combinatorial domains, whose solution counts grow exponentially with the parameters.Treating discrete variables as continuous can ignore the search-space structure and repeatedly select identical samples.
  • Variational autoencoders map high-dimensional discrete inputs into lower-dimensional continuous latent spaces for Gaussian-process-based optimization.The reported molecular-space approach uses a SMILES encoder, although the decoder can generate invalid structures.
  • Inherently discrete surrogates include neural networks, random forests, and tree-structured Parzen estimators, while BOCS uses sparse Bayesian linear models and semidefinite programming.Random forests can extrapolate undesirably, and BOCS can become prohibitive with many one-hot-encoded binary or categorical variables; submodular relaxation addresses this issue.
  • Kernel-based methods capture discrete similarity using measures such as Hamming distance, graph kernels, and combinations of kernels for different variable types.Very few studies have considered mixed-variable combinatorial problems involving both continuous and discrete inputs.

3.3 Noisy and robust optimization

Noisy and robust Bayesian optimization adapts surrogate noise models and acquisition functions to measurement noise, outliers, heteroscedasticity, input uncertainty, and robust worst-case objectives. The survey covers modified improvement criteria, heavy-tailed likelihoods, noise propagation, and robust formulations for uncertain queries.

  • Standard Gaussian-process Bayesian optimization assumptions of noise-free inputs and constant-variance Gaussian observation noise may fail in practice.The survey therefore considers noisy observations, outliers, and input-dependent uncertainty.
  • For output noise, methods modify expected improvement using plug-in incumbents, penalties, quantiles, knowledge gradients, or reinterpolation.Expected quantile improvement accounts for heterogeneous noise by measuring improvement relative to a GP β-quantile.
  • Robust Gaussian processes replace Gaussian noise with heavier-tailed models, especially Student-t likelihoods, requiring approximate posterior inference.Expectation propagation, Markov chain Monte Carlo, and factorizing variational approximations are used because the posterior is not analytically tractable.
  • Student-t likelihoods can produce multimodal posteriors because their likelihood is non-log-concave, motivating Laplace and flat-topped t alternatives.
  • Heteroscedastic Gaussian processes model noise variance as input-dependent, while noisy-input methods propagate input uncertainty into output variance or acquisition functions.Unscented expected improvement and unscented incumbents use the unscented transformation to account for input noise throughout model and query evaluation.
  • Robust Bayesian optimization treats uncertain query locations through probabilistic or worst-case formulations, including distributionally robust and adversarial settings.Worst-case objectives search for solutions robust to the worst realization of uncertain parameters, although iterative relaxation may be inefficient when observations are not reused.

3.4 Expensive constrained optimization

Expensive constrained optimization combines Bayesian optimization with constraint-handling techniques when objective and constraint evaluations are costly. The survey organizes methods into constrained acquisition functions and surrogate-assisted constraint handling, including feasibility, uncertainty-reduction, look-ahead, and evolutionary approaches.

  • Expensive constrained optimization involves costly objective and constraint evaluations, with only points satisfying the constraints considered valid solutions.The setting includes applications such as PID-controller tuning subject to stability and safety requirements.
  • Bayesian optimization for expensive constrained problems is divided into constrained Bayesian optimization and surrogate-assisted constraint-handling methods.Constrained Bayesian optimization develops acquisition functions within Gaussian-process frameworks, while the second group supports existing constraint-handling methods such as evolutionary algorithms.
  • Augmented Lagrangian relaxation: Augmented Lagrangian relaxation converts constrained problems into unconstrained subproblems, enabling expected improvement to use the current best augmented-Lagrangian value.Separately modeling objectives and constraints avoids the nonstationary surrogate difficulties of directly modeling the augmented Lagrangian.
  • Probability of feasibility: Feasibility-aware acquisition functions combine improvement with constraint satisfaction, as in expected improvement with constraints and constraint-weighted expected improvement.These methods commonly assume independent constraints and independent Gaussian processes; cEI can be brittle for highly constrained problems and requires a current best observation.
  • Stepwise uncertainty reduction: Stepwise uncertainty-reduction methods select evaluations by reducing uncertainty about quantities such as feasible improvement, expected improvement, or entropy.Related constrained criteria include IECI, feasible-improvement variance, and predictive entropy search for unknown constraints.
  • Surrogate-assisted constraint handling: Non-myopic acquisition functions use multi-step look-ahead to maximize long-term reward, while evolutionary methods can optimize acquisition functions or search for feasible regions.

3.5 Multi-objective optimization

Multi-objective Bayesian optimization addresses expensive problems with multiple conflicting objectives by combining surrogate models and acquisition functions with multi-objective evolutionary algorithms and performance or information-based criteria.

  • Problem formulation: Multi-objective optimization seeks Pareto-optimal solution sets for multiple conflicting objectives, but expensive evaluations make plain MOEAs impractical.The objective vector contains at least two objectives, and only a small number of costly fitness evaluations may be affordable.
  • Combinations with MOEAs: Bayesian optimization can be combined with MOEAs by applying Gaussian-process surrogates and single-objective acquisition functions to each objective.This combination adapts Bayesian optimization to multi-objective settings while leveraging the established success of MOEAs.
  • Combinations with MOEAs: EBO uses Bayesian optimization as the main framework and evolutionary algorithms to optimize the acquisition function, whereas BEO uses an evolutionary framework and acquisition functions to select offspring.In BEO, environmental-selection fitness functions may differ from the acquisition function used for infilling samples.
  • Combinations with MOEAs: MOEA-based methods differ in their evolutionary algorithms and sample-selection strategies, including decomposition, clustering, non-dominated sorting, and uncertainty selection.MOEA/D-EGO clusters training samples before constructing a GP for each cluster, while Multi-EGO maximizes expected improvements for all objectives simultaneously.
  • Performance-indicator-based AFs: Performance indicators such as IGD and HV assess solution sets, with HV measuring the objective-space volume dominated by non-dominated solutions.Larger HV values indicate better algorithmic performance.
  • Performance-indicator-based AFs: EHVI combines expected improvement with hypervolume and is widely used for expensive multi-objective optimization, but its integral-based computation can become intensive.Monte Carlo integration, direct interval-box computation, and interval-box reduction have been studied to improve EHVI efficiency.
  • Information-theory-based AFs: Information-based methods include PESMO, MESMO, and PFES, with PFES designed to capture trade-offs across the entire Pareto front.The survey notes that MESMO can fail when no Pareto-front points lie near the maximum of each objective, motivating PFES.

3.6 Multi-task Optimization

Multi-task Bayesian optimization jointly optimizes related tasks by transferring shared information through task-aware surrogate models and acquisition functions, while computational complexity and task-relatedness constrain applicability.

  • Problem formulation: Multi-task optimization concurrently addresses multiple tasks by leveraging correlated information, whereas multi-objective optimization handles conflicting objectives within one task.Tasks in multi-task optimization may themselves be single- or multi-objective problems.
  • Method: Multi-task Bayesian optimization requires surrogate models that learn transferable task knowledge and acquisition functions that account for both exploration-exploitation and inter-task correlation.These components are intended to speed optimization by exploiting common information across related tasks.
  • Multi-task models: Linear models of coregionalization represent correlated outputs as linear combinations of independent latent processes.Bayesian multi-task models can be viewed as LMC variations with different parameterizations and constraints.
  • Multi-task models: Multi-task Gaussian processes introduce a task covariance matrix alongside input covariance to model inter-task similarities through a product kernel.The task covariance matrix is positive semi-definite, with validity guaranteed by Cholesky decomposition.
  • Limitations and scalability: Multi-task Gaussian processes suffer from computational complexity O(Tn^3), motivating scalable covariance-learning approaches.One proposed improvement uses self-measuring similarity to construct covariance matrices more efficiently.
  • Limitations and scalability: Instantaneous mixing in LMC models is limited to cases where one output process is a blurred version of another, while convolution processes increase computational and storage complexity.The choice of multi-task model therefore depends on the form of cross-output correlation and available computational resources.
  • Applications: Early multi-task Bayesian optimization applications emphasize hyperparameter optimization, using multi-task Gaussian processes and acquisition functions that trade information gain against cost.Collaborative tuning has also selected new samples by maximizing expected improvement on individual datasets.

3.7 Multi-fidelity optimization

Multi-fidelity Bayesian optimization accelerates expensive target optimization by jointly modeling evaluations with different accuracies and costs, then selecting both input locations and fidelity levels.

  • Problem formulation: Multi-fidelity optimization uses evaluations whose accuracy and cost increase with fidelity to accelerate optimization of an expensive target objective.The approach exploits lower-cost, less accurate evaluations alongside higher-cost, more accurate ones.
  • Multi-fidelity models: Multi-fidelity Bayesian optimization builds independent or jointly correlated surrogate models across fidelity levels, with Co-Kriging among the most popular models.Multi-output Gaussian processes and deep neural networks are also used to model multi-fidelity data.
  • Multi-fidelity models: The autoregressive Co-Kriging model represents a high-fidelity prediction as a scaled low-fidelity prediction plus a discrepancy term.The scaling factor minimizes discrepancy between the scaled low-fidelity and high-fidelity models at common sampling points.
  • Applications: Multi-fidelity Kriging has been applied to aerodynamics, engineering design, bandit optimization, multi-objective optimization, and hyperparameter tuning.In bandit and multi-objective settings, research often focuses on designing new acquisition functions.
  • Acquisition functions: Multi-fidelity acquisition functions select both locations and fidelity levels, with early approaches adapting expected improvement to account for fidelity-specific information.An augmented EI can combine expected improvement, low- and high-fidelity correlation, and cost-related reduction terms.
  • Acquisition functions: UCB-based methods formulate fidelity-specific bounds and use thresholds to decide which fidelity to query after selecting a new point.MF-GP-UCB has also been extended from discrete to continuous fidelity spaces.
  • Acquisition functions: Information-based methods divide multi-fidelity optimization into exploration at lower fidelities and optimization or exploitation at the target fidelity.This pattern appears in MF-MI-Greedy and related information-theoretic approaches.

3.8 Transfer/Meta Learning

Transfer and meta-learning in Bayesian optimization address cold starts by reusing knowledge from related source tasks, but their success depends on source-target similarity and appropriate knowledge-transfer models.

  • Motivation: Transfer/meta learning targets Bayesian optimization’s cold-start problem by reusing information from auxiliary domains and related optimization tasks.Without transferred knowledge, optimization may require many expensive evaluations before reaching high-performing solutions.
  • Scope and assumptions: Negative transfer can degrade target-task performance, so successful transfer depends heavily on similarity between source and target tasks.This distinguishes transfer/meta learning from multi-task optimization, which optimizes all tasks simultaneously.
  • Meta-initialization: Meta-initialization speeds hyperparameter search by starting from configurations that performed well on similar datasets.Negative Spearman correlation has been used to measure dataset similarity.
  • Hierarchical models: Hierarchical models can pool knowledge across source datasets, but ranking surrogates may incur high computational complexity.Ranking is motivated by differing loss scales across datasets.
  • Multi-task transfer models: Multi-task Gaussian processes transfer knowledge by modeling source-target similarity, while modified task-covariance matrices can improve computational efficiency.Other models treat source data as noisy observations of the target task.
  • Ensemble transfer: Weighted combinations of Gaussian processes learn one expert per dataset and combine their predictions for target-task inference.The product-of-experts approach avoids training one surrogate on the entire historical dataset.
  • Transfer acquisition functions: Transfer can also enter the acquisition function through TAF, which averages expected improvement across target and source datasets with weights.Reinforcement learning has been explored as a later extension of this direction.

3.9 Parallel/Batch Bayesian optimization

Parallel or batch Bayesian optimization addresses the inefficiency of selecting one point per iteration by extending acquisition functions to choose multiple points. Key approaches trade off information quality, computational tractability, scalability, and similarity to sequential recommendations.

  • Parallel/Batch Bayesian optimization: Batch Bayesian optimization selects multiple query points per iteration, avoiding the sequential process that can be inefficient when evaluations run in parallel.Sequential methods benefit from immediately updated models, making simultaneous point selection more challenging.
  • Parallel/Batch Bayesian optimization: q-EI extends expected improvement to batches, but its q-dimensional Gaussian integral becomes intractable and computationally intensive as q increases.Kriging believer and constant liar strategies sequentially identify points by substituting unknown outputs at previously selected points.
  • Parallel/Batch Bayesian optimization: Parallel GP-UCB methods have been widely studied because of theoretical guarantees including sublinear cumulative regret growth.GP-BUCB uses updated variance to encourage exploration, while related extensions address multi-agent and pure-exploration settings.
  • Parallel/Batch Bayesian optimization: Parallelized PES and q-KG jointly select batches, while TES improves information-based acquisition-function scalability through trusted maximizers.The passage contrasts these approaches with TES’s improved scalability to batch size.
  • Parallel/Batch Bayesian optimization: Batch acquisition functions can be designed to approximate sequential recommendations by minimizing selection loss, yielding a weighted k-means formulation.This direction reformulates parallel acquisition-function optimization around agreement with sequential selection.

4 CHALLENGES AND FUTURE DIRECTIONS

The survey identifies distributed, federated, dynamic, heterogeneous-cost, and fairness-aware Bayesian optimization as active areas with substantial unresolved challenges. These challenges concern communication, privacy, model suitability, acquisition-function quality, changing objectives, unequal costs, and discrimination constraints.

  • Distributed Bayesian optimization: Most distributed or batch Bayesian optimization methods rely on a central server, although HyperSpace and fully distributed Thompson sampling provide notable alternatives.HyperSpace partitions the search space into overlapping hyperspaces with separate GP models; distributed Thompson sampling supports asynchronous parallelism but can perform poorly because of randomness.
  • Distributed Bayesian optimization: Distributed Bayesian optimization must balance convergence rate against communication cost, while addressing latency, asynchronous execution, heterogeneous evaluation times, and complex network constraints.The survey calls for more rigorous convergence theory and practical treatment of time-varying communication and computation capabilities.
  • Federated Bayesian optimization: Federated Bayesian optimization keeps raw client data local while aggregating models, but federated Thompson sampling lacks a rigorous privacy guarantee.Federated Thompson sampling combines server and client GP sampling with probability p and 1 − p, respectively.
  • Federated Bayesian optimization: Federated optimization faces model, acquisition, and privacy challenges because Gaussian processes are nonparametric, Thompson sampling can underperform, and threat models remain insufficiently defined.Proposed directions include random Fourier feature approximations, new acquisition methods, and more rigorous privacy definitions.
  • Dynamic optimization: Dynamic optimization requires Bayesian optimization methods that account for time-varying objectives rather than assuming stationary reward functions.Existing approaches include Markov GP models, resetting, temporal kernels, sliding windows, and weighted GP models to manage forgetting and remembering.
  • Heterogeneous and fairness-aware optimization: Cost-aware Bayesian optimization addresses heterogeneous evaluation costs across search and objective spaces, including settings where different objectives have substantially different computational complexity.Methods include EI per second, cost-cooling, interleaving, and transferring experience from cheaper objectives to expensive ones, but the area remains relatively new.
  • Heterogeneous and fairness-aware optimization: Fairness-aware Bayesian optimization remains largely unexplored, with FairBO using a separate GP fairness model and constrained EI to select feasible queries.The motivation is to address discrimination and bias concerns in applications such as finance, healthcare, hiring, and criminal justice.

5 CONCLUSION

The paper systematically reviews recent Bayesian optimization advances across nine optimization scenarios, emphasizing surrogate-model construction and acquisition-function design. It also highlights distributed data, privacy, fairness, dynamism, and heterogeneity as areas with sporadic research and many open questions.

  • Conclusion: The survey organizes Bayesian optimization research into nine categories spanning optimization challenges and efficiency techniques, including high-dimensionality, noise, constraints, multitask, multifidelity, knowledge transfer, and parallelization.It also summarizes developments addressing distributed data, privacy, fairness, dynamism, and heterogeneous objectives.
  • Conclusion: The paper concludes that distributed data, privacy, fairness, dynamism, and objective heterogeneity remain underexplored, with many open questions requiring further research.The authors aim to clarify the research landscape, including Bayesian optimization’s motivation, strengths, limitations, and future directions.
Loading 2206.03301v2…