Acquisition Function

The most widely used acquisition function. It measures the expected amount of improvement over the current best observed value, given the surrogate model's predictive distribution.

• Formula: EI(x) = E[max(0, f(x) - f(x⁺))], where f(x⁺) is the current best observation.
• Behavior: Naturally balances exploration and exploitation. It has a closed-form solution under a Gaussian Process surrogate, making it computationally efficient.
• Use Case: The default choice for most global optimization problems where the goal is to find the single best configuration.

An acquisition function based on the principle of optimism in the face of uncertainty. It selects the point with the highest upper confidence bound of the surrogate model's prediction.

• Formula: UCB(x) = μ(x) + β * σ(x), where μ is the mean prediction, σ is the standard deviation (uncertainty), and β is a parameter controlling the exploration-exploitation trade-off.
• Behavior: Explicitly tunable via β. A higher β encourages more exploration of uncertain regions.
• Use Case: Popular in theoretical analyses and multi-armed bandit problems. Provides provable regret bounds.

A simpler, more exploitative criterion that calculates the probability that a candidate point will yield an improvement over the current best.

• Formula: PI(x) = P(f(x) > f(x⁺) + ξ), where ξ is a small positive margin to prevent over-exploitation.
• Behavior: Tends to be more greedy than EI, often focusing refinement near the current best point. The ξ parameter helps add moderate exploration.
• Use Case: Useful when the optimization budget is very limited and quick, incremental improvement is the goal, though it is often outperformed by EI.

Information-theoretic acquisition functions that seek to maximize the information gain about the location of the optimum.

• Core Idea: They measure the reduction in entropy (uncertainty) of the posterior distribution over the optimal input x* (PES) or the optimal value f* (MES) after evaluating a candidate point.
• Behavior: Often provides a superior exploration-exploitation balance by directly targeting the reduction of uncertainty about the optimum itself.
• Use Case: State-of-the-art choice for problems where the surrogate model is highly accurate and evaluations are extremely expensive. MES is often preferred for its computational tractability.

A one-step lookahead acquisition function that considers the value of information after the surrogate model is updated with the new observation, not just the immediate improvement.

• Core Idea: It measures the expected improvement in the posterior mean of the optimum after a hypothetical evaluation, rather than the improvement in the observed best value.
• Behavior: More computationally intensive but can make better global decisions, especially in batch settings or when the final recommendation is the point with the best posterior mean, not the best observation.
• Use Case: Important in closed-loop experimental design and when the final solution is based on the fully updated model, not just sampled points.

A probabilistic algorithm that selects the next point to evaluate by sampling a random function from the posterior surrogate model and optimizing the sampled function.

• Mechanism: 1) Draw a sample from the Gaussian Process posterior. 2) Find the point that maximizes this sample function. 3) Evaluate the true objective at that point.
• Behavior: Provides a natural, randomized balance between exploration and exploitation. It is asymptotically optimal for certain bandit problems.
• Use Case: Highly effective in parallel/batch Bayesian optimization settings, as multiple independent samples can be optimized to select a diverse batch of points in a single iteration.

Expected Improvement (EI) is the most widely used acquisition function. It calculates the expected amount by which a candidate point's performance will improve upon the current best observed value, given the surrogate model's predictive distribution.

• Mechanism: EI integrates over the probability distribution of possible outcomes above the current best, favoring points with high mean predictions, high uncertainty, or both.
• Formula: (EI(\mathbf{x}) = \mathbb{E}[\max(f(\mathbf{x}) - f(\mathbf{x}^+), 0)]), where (f(\mathbf{x}^+)) is the best observed value.
• Use Case: The default choice for most global optimization problems where the primary goal is to find the single best configuration.

Upper Confidence Bound (UCB), often GP-UCB when using a Gaussian Process surrogate, selects the point that maximizes an optimistic bound on the possible function value. It explicitly balances the surrogate's mean prediction ((\mu(\mathbf{x}))) and its uncertainty ((\sigma(\mathbf{x}))).

• Formula: (UCB(\mathbf{x}) = \mu(\mathbf{x}) + \kappa \sigma(\mathbf{x})), where (\kappa) is a tunable parameter controlling the exploration-exploitation trade-off.
• Deterministic: Unlike EI, UCB is deterministic for a given (\kappa) and surrogate state, simplifying analysis.
• Use Case: Particularly effective in bandit problems and when a predictable, tunable level of optimism is desired for exploration.

Probability of Improvement (PI) is a simpler, earlier acquisition function that selects the point with the highest probability of exceeding the current best observed value by a small margin.

• Mechanism: PI is calculated as the cumulative density of the surrogate's predictive distribution above a target threshold.
• Limitation: It is purely exploitative in its basic form, as it favors points with high probability of even marginal improvement, often getting stuck in local optima.
• Use Case: Less common than EI or UCB, but can be useful in contexts where any improvement is valuable and computational budget is very high, or when modified with a trade-off parameter.

Entropy Search and Predictive Entropy Search (PES) are information-theoretic acquisition functions. Instead of optimizing the function directly, they aim to reduce the uncertainty about the location of the global optimum within the search space.

• Objective: They select the point that is expected to provide the greatest reduction in the entropy (i.e., uncertainty) of the posterior distribution over the optimum's location.
• Computational Cost: More computationally intensive to evaluate than EI or UCB, as they require approximating complex integrals.
• Use Case: Ideal when the precise identification of the optimum is more critical than simply finding a high-performing point, or when the evaluation budget is very limited.

Knowledge Gradient (KG) is a one-step lookahead acquisition function. It evaluates the expected value of the best point we could select after observing the outcome at a candidate location, not just the improvement at that location itself.

• Global Perspective: KG considers how a new observation will improve our overall belief about the entire function, leading to better global decisions. It is less myopic than EI.
• Computational Complexity: Computing the KG is often more expensive, as it requires reasoning about the updated surrogate model post-observation.
• Use Case: Superior performance in sequential decision-making where each evaluation is extremely costly, justifying the extra computation for better long-term search efficiency.

Acquisition functions extend to complex optimization scenarios beyond single-objective maximization.

• Multi-Objective Optimization: Functions like Expected Hypervolume Improvement (EHVI) are used when optimizing for multiple, competing objectives (e.g., accuracy and latency). EHVI measures the expected increase in the dominated volume of the objective space.
• Constrained Optimization: Modified acquisition functions, such as Constrained Expected Improvement, incorporate probabilistic constraints (e.g., model size < 100MB). They only propose points that have a high probability of satisfying all constraints.
• Use Case: Essential for Hardware-Aware NAS and real-world AutoML where models must satisfy practical deployment constraints.