Bayesian Optimization

The surrogate model is a probabilistic approximation of the expensive, unknown objective function. It provides a computationally cheap way to model the function's behavior and quantify uncertainty.

• Gaussian Processes (GPs) are the most common choice, as they provide a full posterior distribution (mean and variance) for any input point.
• The model is updated after each new function evaluation, refining its predictions.
• The variance from the surrogate quantifies epistemic uncertainty—regions of the search space where the model is less certain due to lack of data.

The acquisition function is a heuristic that uses the surrogate model's predictions to decide the next point to evaluate. It formalizes the trade-off between exploration (probing uncertain regions) and exploitation (focusing on areas likely to be good).

Common acquisition functions include:

• Expected Improvement (EI): Measures the expected amount of improvement over the current best observation.
• Upper Confidence Bound (UCB): Selects points with a high weighted sum of predicted mean and uncertainty.
• Probability of Improvement (PoI): Measures the probability that a point will yield an improvement. The next evaluation point is chosen by maximizing the acquisition function, a much cheaper optimization problem.

The observation history is the set of input-output pairs {(x₁, y₁), (x₂, y₂), ...} collected from evaluating the true, expensive objective function. This dataset is the empirical evidence upon which the surrogate model is conditioned.

• The initial history often starts with a small set of points from a space-filling design (e.g., Latin Hypercube Sampling) to build a preliminary surrogate model.
• The history grows sequentially, with each new point selected by the acquisition function.
• The quality and diversity of this dataset directly determine the accuracy of the surrogate model and the efficiency of the optimization process.

The optimization loop is the sequential, iterative procedure that defines Bayesian optimization. It typically follows these steps:

1. Build/Update Surrogate: Fit the probabilistic model (e.g., Gaussian Process) to all observed data.
2. Maximize Acquisition: Find the point x_next that maximizes the acquisition function, using the surrogate's predictions.
3. Evaluate Objective: Query the expensive black-box function at x_next to obtain y_next.
4. Augment Data: Add the new observation (x_next, y_next) to the history.
5. Repeat: Continue until a budget (e.g., number of evaluations) is exhausted or convergence is achieved. This loop automates the corrective action planning by using model-based reasoning to select the most informative next experiment.

The prior over functions is the initial probabilistic belief about the shape and properties of the unknown objective function, encoded in the surrogate model before any data is observed.

• In a Gaussian Process, this is defined by the mean function (often assumed to be zero) and the kernel (covariance) function.
• The kernel function (e.g., Matérn, Squared Exponential) encodes assumptions about smoothness, periodicity, and trend.
• This prior allows the model to make sensible predictions and uncertainty estimates from the very first iteration, guiding early exploration. The choice of kernel is a critical hyperparameter.

A global optimizer is required to solve the inner-loop problem of maximizing the acquisition function. Since the acquisition function can be multi-modal, a global search strategy is needed.

Common approaches include:

• Direct search methods like L-BFGS-B or random restarts of gradient-based optimizers.
• Evolutionary algorithms or other derivative-free optimizers.
• In practice, this is often done by evaluating the acquisition function on a large, quasi-random candidate set of points and selecting the best. The efficiency of this inner optimizer impacts the overall computational cost of the Bayesian optimization framework.

BO is the engine behind many AutoML systems. The search space is vastly larger than simple hyperparameter tuning, encompassing model selection, feature preprocessing steps, and their associated hyperparameters simultaneously. The black-box function is the final pipeline's cross-validation score. BO navigates this complex, hierarchical space to find the best combination of components and settings without manual intervention.

• Key Challenge: Designing a search space that can represent diverse pipeline architectures.
• Outcome: A fully configured ML pipeline optimized for a specific dataset.

In physical sciences and engineering, running experiments (e.g., chemical synthesis, alloy composition, drug formulation) is time-consuming and resource-intensive. BO guides the experimental process by modeling the relationship between input parameters (e.g., temperature, pressure, concentration ratios) and the output property of interest (e.g., yield, strength, efficacy). It suggests the next experiment most likely to improve the target, accelerating discovery.

• Real-world impact: Optimizing the recipe for a new battery electrolyte to maximize energy density.
• Advantage: Minimizes the number of costly lab experiments required.

Tuning parameters for controllers (e.g., PID gains) or robotic systems (e.g., gait parameters for walking robots) often relies on expert intuition or brute-force search. BO treats the controller's performance metric (e.g., settling time, energy efficiency, stability) as a black-box function. It efficiently searches the parameter space to find settings that optimize real-world or simulated performance, which may be non-linear and noisy.

• Use Case: Optimizing the proportional, integral, and derivative gains of a drone's flight controller for smooth hovering.
• Consideration: Evaluations may be run in simulation for speed, but the final optimization often requires real-world trials.

When optimizing website layouts, product features, or marketing copy, each variant tested with live users has a business cost (opportunity cost, engineering effort). BO can sequentially test variants by modeling the conversion rate or engagement metric as a function of the design choices. The acquisition function balances exploring new ideas and exploiting currently good ones, leading to faster convergence on the optimal design with less revenue loss than traditional A/B/n testing.

• Example: Optimizing the color, size, and text of a 'Subscribe' button across multiple dimensions simultaneously.
• Framework: Often implemented as Multi-armed Bandit algorithms, a simpler relative of BO.

Many algorithms have tunable parameters that significantly affect runtime or solution quality (e.g., SAT solvers, database query optimizers, compiler flags). BO is used to find the configuration that minimizes runtime or maximizes solution quality for a given benchmark or workload. The evaluation is a single run of the algorithm, which can be expensive for large problem instances.

• Key Benefit: Discovers non-intuitive, high-performance parameter settings that human experts might miss.
• Domain: Widely used in automated algorithm configuration for combinatorial optimization and high-performance computing.

A Gaussian Process is a non-parametric probabilistic model that defines a distribution over functions. It is the most common surrogate model in Bayesian optimization.

• Core Function: It provides a posterior distribution (mean and variance) for the unknown objective function at any point, quantifying uncertainty.
• Key Property: The covariance (kernel) function dictates the smoothness and structure of the modeled function.
• Role in BO: The GP's posterior is used to compute the acquisition function, which guides the search for the optimum.

An acquisition function is a utility function derived from the surrogate model's posterior, used to select the next point to evaluate in the Bayesian optimization loop.

• Purpose: It formalizes the exploration-exploitation trade-off. It suggests points that are either likely to be optimal (high mean) or highly uncertain (high variance).
• Common Types:
  • Expected Improvement (EI): Measures the expected amount by which the evaluation will improve over the current best observation.
  • Upper Confidence Bound (UCB): Selects points with a high weighted sum of the predicted mean and uncertainty.
  • Probability of Improvement (PI): Measures the probability that a new point will be better than the current best.

The Multi-Armed Bandit problem is a sequential decision-making framework where an agent chooses from a set of actions (arms) with unknown reward distributions to maximize cumulative reward.

• Core Dilemma: The exploration-exploitation trade-off—trying new arms to learn their reward vs. pulling the best-known arm.
• Relation to BO: Bayesian optimization can be viewed as a continuum-armed bandit problem, where the set of actions is a continuous, high-dimensional parameter space instead of discrete arms.
• Algorithms: Strategies like Upper Confidence Bound (UCB) and Thompson Sampling are foundational to both fields.

A surrogate model is a computationally inexpensive approximation of a complex, expensive-to-evaluate objective function.

• Purpose in BO: To model the black-box function using the observed data (x, f(x)). The optimizer queries the surrogate instead of the real system for most calculations.
• Common Choices:
  • Gaussian Processes: Provide uncertainty estimates.
  • Random Forests: Can model non-stationary functions.
  • Bayesian Neural Networks: Offer flexible, deep representations.
• Fitting: The model is updated (re-fitted or its posterior updated) after each new observation from the true function.

Expected Improvement is the most widely used acquisition function in Bayesian optimization. It selects the next point to evaluate by calculating the expected amount of improvement over the current best observation (f*).

• Mathematical Definition: EI(x) = E[max(f(x) - f*, 0)], where the expectation is taken over the posterior distribution of f(x) given by the surrogate model (e.g., a Gaussian Process).
• Advantage: It automatically balances exploration and exploitation. Points with high predicted values or high uncertainty can yield high EI.
• Implementation: Has a closed-form solution under a GP surrogate, making it efficient to compute.