Uncertainty-Aware Search Framework for Multi-Objective Bayesian Optimization

1 Introduction

• The goal is to approximate the true Pareto set while minimizing costly evaluations of unknown, conflicting objectives.A Pareto-optimal solution cannot improve one objective without compromising another.Source: §1 · p. 1
• Bayesian optimization uses cheap surrogate models learned from evaluations and acquisition functions to select evaluations for expensive black-box problems.The introduction notes that multi-objective Bayesian optimization has received relatively less attention than its single-objective counterpart.Source: §1 · p. 1
• Prior multi-objective methods can struggle with trade-offs, scale poorly, or incur computationally expensive acquisition optimization.Single-objective reductions can encourage aggressive exploitation, while Pareto-hypervolume acquisition optimization scales poorly and PESMO optimization is expensive.Source: §1 · p. 1
• USeMO first finds promising candidates through cheap multi-objective optimization of acquisition functions, then selects one using an uncertainty measure.The framework is presented as a two-stage procedure for sequential decision-making under uncertainty.Source: §1 · p. 1
• USeMO does not reduce the task to one objective, can use varied single-objective acquisition functions, and is designed for many-objective efficiency.The introduction also highlights uncertainty management through its two-stage selection procedure.Source: §1 · p. 2
• The paper contributes a principled search-based framework, asymptotic regret analysis, and experiments on synthetic and six real-world benchmarks.The experiments are described as showing accuracy and efficiency improvements over existing methods.Source: §1 · p. 2

2 Background and Problem Setup

• Bayesian optimization learns a cheap surrogate from past costly evaluations and uses it to choose subsequent inputs.Its search trades off exploration and exploitation to direct evaluations toward optimal inputs.Source: §2 · p. 2
• A Gaussian Process models an unknown function using a mean function and covariance or kernel function.For finite input sets, function values are normally distributed under the specified GP.Source: §2 · p. 2
• Acquisition functions score candidate inputs; examples include EI, UCB, LCB, and Thompson sampling, and USeMO can use other acquisition functions.The model's mean and standard deviation correspond to exploitation and exploration scores, respectively.Source: §2 · p. 2
• An optimization procedure selects the highest-scoring candidate according to the acquisition function and statistical model.DIRECT is given as an example procedure.Source: §2 · p. 2
• The multi-objective problem minimizes at least two real-valued functions and seeks a Pareto set that no outside point dominates.The objective is to approximate that set while minimizing the number of evaluations.Source: §2 · p. 2

3 Related work

• Scalarization methods such as ParEGO combine objectives using sampled weights, while hypervolume-based acquisition methods can scale poorly beyond two objectives.Reducing to a single objective can make trade-offs difficult to capture and may encourage exploitation.Source: §3 · p. 2
• PAL classifies inputs as Pareto-optimal, non-Pareto-optimal, or uncertain but applies only to finite discrete spaces; PESMO targets information about the true Pareto set.PESMO's acquisition optimization is expensive, and efficiency approximations may degrade accuracy or lose information-theoretic advantage; MESMO is described as improving over PESMO.Source: §3 · pp. 2–3
• An analog-circuit method optimizes GP posterior means with LCB, whereas USeMO is evaluated across six diverse application domains and multiple acquisition functions.The passage names neural-network hyperparameter tuning, compiler settings, network-on-chip, and materials design among those domains.Source: §3 · p. 3

4.1 Overview of USeMO Framework

• USeMO builds one statistical model per objective, solves a cheap multi-objective problem to form a Pareto set of candidates, and evaluates the most uncertain candidate.After evaluation, the models are updated with the new input and objective values.Source: §4.1 · p. 3, Figure 1 · p. 3

4.2 Key Algorithmic Components of USeMO

• The candidate Pareto set captures trade-offs among objective-specific acquisition functions, and USeMO selects the candidate with the largest uncertainty volume for evaluation.The volume uses lower and upper confidence bounds; its parameter βt trades off exploitation and exploration.Source: §4.2 · pp. 3–4
• USeMO uses the same acquisition function across objectives to avoid differing acquisition ranges that could unbalance trade-offs in the cheap and final Pareto fronts.The framework allows single-objective acquisition functions such as EI, TS, and LCB.Source: §4.1 · p. 3, §4.2 · p. 4

4.3 Theoretical Analysis

• The GP-LCB analysis establishes asymptotically sublinear cumulative regret for multi-objective Bayesian optimization when the same acquisition function is used across objectives.The analysis considers distance-based regret and states that the result extends to epsilon and R2 metrics.Source: §4.3 · pp. 4–5

5.1 Experimental Setup

• The setup uses GP models with squared-exponential kernels, NSGA-II for cheap MO optimization, and USeMO with EI and TS acquisition functions.NSGA-II was fixed at 1,500 function calls after increasing that number showed no USeMO performance improvement.Source: §5.1 · p. 5
• The synthetic benchmark table specifies each benchmark’s functions, objective count, and input dimension.Figure 2 plots the log hypervolume difference and log R2 Indicator over evaluations, with means and variances from 10 runs.Source: Table 1 · p. 5, Figure 2 · p. 6
• The experiments used six diverse real-world benchmarks, including MNIST neural-network tuning, SW-LLVM optimization over 1024 settings (d=10), SNW sorting-network optimization over 206 designs, and NoC optimization over 259 implementations.Source: §5.1 · pp. 5–6
• Evaluation uses Pareto hypervolume difference and the R2 Indicator to assess estimated Pareto-front quality.The R2 Indicator is the average distance from the ideal to estimated Pareto front and degenerates to the regret metric used in the theoretical analysis.Source: §5.1 · p. 7

5.2 Results and Discussion

• USeMO consistently outperforms all baselines and converges faster on synthetic and real-world benchmarks.Both TS and EI variants outperform the baselines, although their convergence rates differ.Source: Figure 2 · p. 6, Figure 3 · p. 7, §5.2 · p. 8
• USeMO’s acquisition-optimization time scales significantly better than PESMO’s and is comparable to ParEGO’s.PESMO and SMSego times rise significantly when the number of objectives exceeds two.Source: §5.2 · p. 8, Table 2 · p. 8
• Uncertainty maximization performs better than random selection for choosing among candidates from the cheap MO solver, though random selection is competitive in some cases.Figure 4 compares log hypervolume difference against evaluation count across synthetic benchmarks.Source: §5.2 · p. 8

6 Summary and Future Work

• USeMO is a framework for solving multi-objective Bayesian optimization problems through a two-stage search procedure.The procedure aims to improve accuracy and efficiency in sequential decision-making under uncertainty when selecting inputs for evaluation.Source: §6 · p. 8
• Figure 4 compares uncertainty maximization and random selection for choosing an input from the cheap solver’s Pareto set.It plots log hypervolume difference against evaluation count for synthetic benchmarks.Source: Figure 4 · p. 8
• Experiments on diverse benchmarks show USeMO consistently outperforms state-of-the-art methods and scales gracefully to large-scale multi-objective problems..Source: §6 · p. 8

A Theoretical Analysis

• For δ ∈ (0, 1), Lemma 1 sets β_t = 2 log(|X|π²t²/6δ) and states that its ensuing result holds with probability 1−δ.The proof models F_i(x) as N(µ_i,t−1(x), σ_i,t−1(x)) and applies a union bound.Source: A Theoretical Analysis · p. 10
• Theorem 1 states that, for the Pareto set Xt generated by cheap multi-objective optimization at iteration t, the following result holds with probability 1 − δ.Source: A Theoretical Analysis · p. 10
• Tmax denotes the maximum information gain about an objective after Tmax iterations.The proof applies the cited single-objective GP-optimization lemmas to each objective.Source: A Theoretical Analysis · p. 10

• Figure 5 depicts estimated-front points, their hypervolume, the optimal front, and the area representing hypervolume difference.Source: Figure 5 · p. 10, B Additional Experimental Results · p. 10
• Figure 6 compares USeMO-LCB with baseline algorithms on synthetic and real-world benchmarks using log hypervolume difference over evaluation counts.Source: B Additional Experimental Results · p. 10, Figure 6 · p. 11
• Figure 6 plots the mean and variance across 10 runs for each benchmark.Source: Figure 6 · p. 11