Bayesian optimization

Short description: Sequential model-based optimization of expensive black-box functions

Bayesian optimization is a sequential model-based strategy for global optimization of black-box objective functions whose evaluations are costly.[1][2][3] It is commonly used when a single observation requires an experiment, engineering computation, numerical simulation, or machine-learning run, and when derivatives are unavailable or unreliable. The objective need not have a closed-form expression.

The method constructs a probabilistic model of the unknown function, often a Gaussian process (GP), and uses the resulting predictive distribution to choose the next evaluation point. This choice is made by optimizing a sampling criterion, also called an acquisition function.[3][2]

Common applications include hyperparameter optimization in machine learning, where each trial may require training and validating a model,[4][5] and engineering design problems driven by expensive numerical simulations.[6][2]

## Contents

* 1 History
* 2 Problem setting
* 3 Basic method
* 4 Probabilistic models
* 5 Variants and problem classes
* 6 Sampling criteria
* 6.1 Expected improvement
* 7 Solution methods
* 8 Related methods
* 9 Applications
* 10 See also
* 11 References

## History

Early Bayesian approaches to global optimization include work by Harold J. Kushner on locating extrema of noisy functions and work by Jonas Mockus on Bayesian methods for seeking extrema.[7][8][9][1]

Expected improvement is a prominent sampling criterion in this line of work. In 1998, Donald R. Jones, Matthias Schonlau, and William J. Welch introduced the efficient global optimization (EGO) algorithm, which used a kriging or Gaussian-process model with expected improvement for expensive black-box functions.[6]

Later work extended Bayesian optimization to noisy observations, constraints, batch and parallel evaluations, multiple objectives, and mixed or high-dimensional search spaces.[3][10]

## Problem setting

In a standard single-objective setting, Bayesian optimization seeks a point

x⋆∈argminx∈𝒳f(x)

where 𝒳 is a search space and f is an unknown objective function. A maximization problem can be written in the same form by minimizing −f. Although the search space may in principle be continuous, discrete, categorical, or mixed, the standard formulation is most directly applicable to continuous, low- to moderate-dimensional domains. Later methods attempt to relax these restrictions by addressing mixed variables, high-dimensional spaces, constraints, parallel evaluations, and multiple objectives.[3][10]

A useful distinction is between noiseless and noisy optimization. Many real applications also involve constraints, parallel evaluations, or multiple objectives. These variants change how the probabilistic model, incumbent solution, and sampling criterion are defined.[3][10]

## Basic method

Bayesian optimization of a one-dimensional function. A probabilistic model is updated after observations, and sampling criteria guide the selection of future evaluation points.

A typical Bayesian optimization procedure builds a sequence of evaluation points.[3][2] Starting from an initial design X0, the algorithm produces additional evaluation points x1,x2,…. After n sequential evaluations, Xn=X0∪{x1,…,xn} denotes the evaluated points and 𝒟n denotes the corresponding observations. The next point xn+1, or a batch of points, is selected by optimizing a sampling criterion computed from the current probabilistic model.

The procedure has the following form:

1. Choose an initial design X0, often by a space-filling design or random sampling.
2. Evaluate the objective function, and any constraints if present, at the initial design points.
3. Construct or update a probabilistic model using the observed data 𝒟n.
4. Define a sampling criterion, also called an acquisition function or infill criterion, from the probabilistic model.
5. Optimize the sampling criterion to select xn+1, or a batch of points, for evaluation.
6. Evaluate the selected point or points and update the data set.
7. Repeat until an evaluation budget, convergence criterion, or stopping rule is reached.

The Bayesian strategy treats the unknown objective as a random function and places a prior over it. The prior captures assumptions about the behavior of the function. After observations are collected, the prior is updated to form a posterior distribution over the objective function. The posterior distribution is then used to construct the sampling criterion that determines the next query point.

## Probabilistic models

Bayesian optimization requires a probabilistic model of the unknown objective function and, when present, of unknown constraints. Given the evaluations observed so far, the model gives a predictive distribution for unevaluated points in the search space. Sampling criteria are defined from this predictive distribution, so the model provides both predicted objective values and uncertainty estimates.[3][2] Such probabilistic models are often called surrogate models or metamodels because they are used in place of direct evaluations of the expensive objective when choosing candidate points.

Gaussian process regression is the standard probabilistic model in classical presentations of Bayesian optimization and remains common in applications. A Gaussian process prior defines a distribution over functions. After observations are collected, the posterior predictive mean and variance are used by sampling criteria such as expected improvement, probability of improvement, and upper confidence bound criteria.[6][3] Other probabilistic models can be used when the search space, dimensionality, or data size favors another representation.[10][2]

## Variants and problem classes

Bayesian optimization is often described through a noiseless, single-objective problem, but the same model-based loop is adapted to several related settings.

In noisy Bayesian optimization, evaluations return observations such as y=f(x)+ε instead of exact values of the latent objective. The probabilistic model can represent both uncertainty about f and observation noise. Classical expected improvement over the best observed value is a noiseless criterion. In noisy settings, recommendation rules and sampling criteria may be defined for the latent objective, for future noisy observations, or for the value of information. Examples include knowledge-gradient and information-theoretic criteria.[3][11][12][13]

In constrained Bayesian optimization, the objective is optimized subject to feasibility constraints. If the constraints are also unknown black-box functions, separate probabilistic models can be constructed for the objective and constraints, and the sampling criterion can combine predicted improvement with the probability of feasibility.[14]

In batch or parallel Bayesian optimization, the method proposes several candidate points before the corresponding observations are available. Batch methods are useful when experiments, simulations, or machine-learning jobs can be executed concurrently. They may optimize a joint sampling criterion or choose points sequentially while accounting for pending evaluations.[15]

In multi-objective Bayesian optimization, several objective functions are optimized at once and the result is typically an approximation to a Pareto front. Methods include scalarization approaches such as ParEGO, which reduce the problem to a sequence of single-objective subproblems, and indicator-based approaches using criteria such as expected hypervolume improvement.[16][17] Constrained multi-objective Bayesian optimization combines these extensions by modeling objectives and constraints and using sampling criteria based on extended domination rules and expected hypervolume improvement.[18]

## Sampling criteria

A sampling criterion, also called an acquisition function in the machine-learning literature or an infill criterion in surrogate-based optimization, scores candidate points using the current predictive distribution. It is usually inexpensive to evaluate and is optimized instead of the expensive objective function. Sampling criteria express the exploration-exploitation tradeoff by assigning high values to points with a low predicted objective value, high uncertainty, or both.[3][2] A seminal example in the noiseless setting is expected improvement, which scores a candidate point by the posterior expected gain over the best value observed so far.[6][3] Other criteria include probability of improvement,[7] upper- or lower-confidence-bound criteria such as GP-UCB,[19] Thompson sampling,[20] knowledge-gradient criteria,[11] information-theoretic criteria including the IAGO minimizer-entropy criterion, entropy search, and predictive entropy search,[12][13][21] and portfolios or hybrids of several criteria.[22]

### Expected improvement

Expected improvement (EI) was used in the efficient global optimization (EGO) algorithm and remains a standard reference criterion for noiseless Bayesian optimization.[6] In the noiseless minimization setting, let fmin be the best objective value observed so far and let 𝒟 denote the data. The expected improvement at a candidate point x is

EI⁡(x)=𝔼[max⁡(fmin−f(x),0)∣𝒟].

When the model predictive distribution at x is Gaussian, f(x)∣𝒟∼𝒩(μ(x),σ2(x)), and σ(x)>0, EI has the closed form

EI⁡(x)=(fmin−μ(x))Φ(z)+σ(x)ϕ(z),z=fmin−μ(x)σ(x),

where Φ and ϕ are the cumulative distribution function and probability density function of the standard normal distribution. EI is therefore large when the model predicts a low objective value, when uncertainty is high, or both.[3][2]

## Solution methods

The sampling criterion is usually cheap to evaluate relative to the objective, but optimizing it can still be a nonconvex auxiliary problem. Its optimum is often sought by discretization, multi-start local optimization, or deterministic numerical methods such as Newton's method and quasi-Newton methods like the Broyden–Fletcher–Goldfarb–Shanno algorithm. Stochastic methods are also used for this auxiliary search, especially for multimodal or mixed-variable criteria. Examples include genetic algorithms and other evolutionary algorithms, as well as sequential Monte Carlo methods.[3][2][18]

## Related methods

Several derivative-free optimization methods use probability distributions without modeling the unknown objective function itself. Estimation of distribution algorithms build and sample explicit probabilistic models of selected candidate solutions.[23] The cross-entropy method and CMA-ES also update parametric sampling distributions, with CMA-ES adapting the mean, step size, and covariance matrix of a multivariate normal distribution.[24][25] These methods use objective values to update a distribution over candidate points. In Bayesian optimization, the probabilistic model instead represents the objective or constraints, and the next point is chosen by optimizing a criterion derived from that model.

Gaussian-process sequential design is also used in reliability analysis to estimate a probability of failure. For a limit-state function f, random input X, and threshold t, the target may be ℙ(f(X)≤t), or more generally the measure of an excursion set. Stepwise uncertainty reduction strategies choose evaluations to reduce uncertainty about this probability, rather than to locate the minimizer or maximizer of f.[26]

Bayesian optimization is also related to multi-armed bandit problems. Both study sequential decisions that trade off exploration and exploitation, and criteria such as upper confidence bounds and Thompson sampling appear in both settings.[19][20] A common distinction is that bandit algorithms are often formulated to control cumulative regret over a sequence of actions, while Bayesian optimization often emphasizes finding a good optimizer of an expensive function after a small evaluation budget.[3][2]

## Applications

Bayesian optimization is used in applications where objective evaluations are costly. Examples discussed in surveys and textbooks include hyperparameter optimization and algorithm configuration, engineering design and simulation-based optimization,[27] robotics, sensor networks, and experimental design in the physical sciences.[3][2][10]

## See also

* Multi-armed bandit
* Kriging
* Thompson sampling
* Global optimization
* Bayesian experimental design
* Probabilistic numerics
* Pareto optimum
* Active learning (machine learning)
* Multi-objective optimization

## References

1. ↑ 1.0 1.1 Močkus, J. (1989). Bayesian Approach to Global Optimization. Dordrecht: Kluwer Academic. doi:10.1007/978-94-009-0909-0. ISBN 0-7923-0115-3.
2. ↑ 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 Garnett, Roman (2023). Bayesian Optimization. Cambridge University Press. ISBN 978-1-108-42578-0. https://bayesoptbook.com.
3. ↑ 3.00 3.01 3.02 3.03 3.04 3.05 3.06 3.07 3.08 3.09 3.10 3.11 3.12 3.13 3.14 Frazier, Peter I. (2018-07-08). "A Tutorial on Bayesian Optimization". arXiv:1807.02811 [stat.ML].
4. ↑ Snoek, Jasper; Larochelle, Hugo; Adams, Ryan P. (2012). "Practical Bayesian Optimization of Machine Learning Algorithms". 25. pp. 2951–2959. https://proceedings.neurips.cc/paper/2012/hash/05311655a15b75fab86956663e1819cd-Abstract.html.
5. ↑ Klein, Aaron; Falkner, Stefan; Bartels, Simon; Hennig, Philipp; Hutter, Frank (2017). "Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets". 54. PMLR. pp. 528–536. https://proceedings.mlr.press/v54/klein17a.html.
6. ↑ 6.0 6.1 6.2 6.3 6.4 Jones, Donald R.; Schonlau, Matthias; Welch, William J. (1998). "Efficient Global Optimization of Expensive Black-Box Functions". Journal of Global Optimization 13 (4): 455–492. doi:10.1023/A:1008306431147. https://link.springer.com/article/10.1023/A:1008306431147.
7. ↑ 7.0 7.1 Kushner, Harold J. (1964). "A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise". Journal of Basic Engineering 86 (1): 97–106. doi:10.1115/1.3653121. https://asmedigitalcollection.asme.org/fluidsengineering/article/86/1/97/392213/A-New-Method-of-Locating-the-Maximum-Point-of-an.
8. ↑ Močkus, Jonas (1975). "On bayesian methods for seeking the extremum". Optimization Techniques IFIP Technical Conference Novosibirsk, July 1–7, 1974. Lecture Notes in Computer Science. 27. pp. 400–404. doi:10.1007/3-540-07165-2_55. ISBN 978-3-540-07165-5.
9. ↑ Močkus, Jonas (1977). "On Bayesian Methods for Seeking the Extremum and their Application". IFIP Congress: 195–200.
10. ↑ 10.0 10.1 10.2 10.3 10.4 Shahriari, Bobak; Swersky, Kevin; Wang, Ziyu; Adams, Ryan P.; de Freitas, Nando (2016). "Taking the Human Out of the Loop: A Review of Bayesian Optimization". Proceedings of the IEEE 104 (1): 148–175. doi:10.1109/JPROC.2015.2494218.
11. ↑ 11.0 11.1 Frazier, Peter; Powell, Warren; Dayanik, Savas (2009). "The Knowledge-Gradient Policy for Correlated Normal Beliefs". INFORMS Journal on Computing 21 (4): 599–613. doi:10.1287/ijoc.1080.0314.
12. ↑ 12.0 12.1 Villemonteix, Julien; Vazquez, Emmanuel; Walter, Eric (2009). "An informational approach to the global optimization of expensive-to-evaluate functions". Journal of Global Optimization 44 (4): 509–534. doi:10.1007/s10898-008-9354-2.
13. ↑ 13.0 13.1 Hennig, Philipp; Schuler, Christian J. (2012). "Entropy Search for Information-Efficient Global Optimization". Journal of Machine Learning Research 13 (57): 1809–1837. https://jmlr.csail.mit.edu/papers/v13/hennig12a.html.
14. ↑ Gelbart, Michael A.; Snoek, Jasper; Adams, Ryan P. (2014). "Bayesian Optimization with Unknown Constraints". arXiv:1403.5607 [stat.ML].
15. ↑ Gonzalez, Javier; Dai, Zhenwen; Hennig, Philipp; Lawrence, Neil D. (2016). "Batch Bayesian Optimization via Local Penalization". 51. pp. 648–657. https://proceedings.mlr.press/v51/gonzalez16a.html.
16. ↑ Knowles, Joshua (2006). "ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems". IEEE Transactions on Evolutionary Computation 10 (1): 50–66. doi:10.1109/TEVC.2005.851274.
17. ↑ Emmerich, Michael T. M.; Giannakoglou, Kyriakos C.; Naujoks, Boris (2006). "Single- and multiobjective evolutionary optimization assisted by Gaussian random field metamodels". IEEE Transactions on Evolutionary Computation 10 (4): 421–439. doi:10.1109/TEVC.2005.859463.
18. ↑ 18.0 18.1 Feliot, Paul; Bect, Julien; Vazquez, Emmanuel (2017). "A Bayesian approach to constrained single- and multi-objective optimization". Journal of Global Optimization 67 (1): 97–133. doi:10.1007/s10898-016-0427-3.
19. ↑ 19.0 19.1 Srinivas, Niranjan; Krause, Andreas; Kakade, Sham M.; Seeger, Matthias W. (2012). "Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting". IEEE Transactions on Information Theory 58 (5): 3250–3265. doi:10.1109/TIT.2011.2182033.
20. ↑ 20.0 20.1 Thompson, William R. (1933). "On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples". Biometrika 25 (3/4): 285–294. doi:10.1093/biomet/25.3-4.285.
21. ↑ Hernández-Lobato, José Miguel; Hoffman, Matthew W.; Ghahramani, Zoubin (2014). "Predictive Entropy Search for Efficient Global Optimization of Black-box Functions". arXiv:1406.2541 [stat.ML].
22. ↑ Hoffman, Matthew W.; Brochu, Eric; de Freitas, Nando (2011). "Portfolio Allocation for Bayesian Optimization". AUAI Press. pp. 327–336. https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=2214&proceeding_id=27.
23. ↑ Mühlenbein, Heinz; Paaß, Gerhard (1996). "From recombination of genes to the estimation of distributions I. Binary parameters". Parallel Problem Solving from Nature – PPSN IV. Lecture Notes in Computer Science. 1141. pp. 178–187. doi:10.1007/3-540-61723-X_982.
24. ↑ Rubinstein, Reuven Y. (1999). "The Cross-Entropy Method for Combinatorial and Continuous Optimization". Methodology and Computing in Applied Probability 1 (2): 127–190. doi:10.1023/A:1010091220143.
25. ↑ Hansen, Nikolaus; Ostermeier, Andreas (2001). "Completely Derandomized Self-Adaptation in Evolution Strategies". Evolutionary Computation 9 (2): 159–195. doi:10.1162/106365601750190398.
26. ↑ Bect, Julien; Ginsbourger, David; Li, Ling; Picheny, Victor; Vazquez, Emmanuel (2012). "Sequential design of computer experiments for the estimation of a probability of failure". Statistics and Computing 22 (3): 773–793. doi:10.1007/s11222-011-9241-4.
27. ↑ Forrester, Alexander I. J.; Sóbester, András; Keane, Andy J. (2008). Engineering Design via Surrogate Modelling: A Practical Guide. John Wiley & Sons. ISBN 978-0-470-06068-1.

* v
* t
* e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

| … functions|

* Golden-section search
* Interpolation methods
* Line search
* Nelder–Mead method
* Successive parabolic interpolation

|

… and gradients|

| Convergence|

* Trust region
* Wolfe conditions

|

Quasi–Newton|

* Berndt–Hall–Hall–Hausman
* Broyden–Fletcher–Goldfarb–Shanno and L-BFGS
* Davidon–Fletcher–Powell
* Symmetric rank-one (SR1)

Other methods|

* Gauss–Newton
* Gradient
* Levenberg–Marquardt
* Conjugate gradient
* Truncated Newton

… and Hessians|

* Newton's method

Optimization computes maxima and minima.

Constrained nonlinear

| General|

* Barrier methods
* Penalty methods

|

Differentiable|

* Augmented Lagrangian methods
* Sequential quadratic programming
* Successive linear programming

Convex optimization

| Convex
minimization|

* Cutting-plane method
* Reduced gradient (Frank–Wolfe)
* Subgradient method

|

Linear and
quadratic|

| Interior point|

* Affine scaling
* Ellipsoid algorithm of Khachiyan
* Projective algorithm of Karmarkar

|

Basis-exchange|

* Simplex algorithm of Dantzig
* Revised simplex algorithm
* Criss-cross algorithm
* Principal pivoting algorithm of Lemke

Combinatorial

| Paradigms|

* Approximation algorithm
* Dynamic programming
* Greedy algorithm
* Integer programming
* Branch and bound/cut

|

Graph
algorithms|

| Minimum
spanning tree|

* Borůvka
* Prim
* Kruskal

|

* Bellman–Ford
* Dijkstra
* Floyd–Warshall

Network flows|

* Dinic
* Edmonds–Karp
* Ford–Fulkerson
* Push–relabel maximum flow

Metaheuristics

* Evolutionary algorithm
* Hill climbing
* Local search
* Simulated annealing
* Tabu search

* Software

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Bayesian optimization. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Bayesian_optimization&oldid=4569533"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template