Uncertainty-Aware Search Framework for Multi-Objective Bayesian Optimization

Syrine Belakaria, Aryan Deshwal, Nitthilan Kannappan Jayakodi, Janardhan Rao Doppa

Abstract

We consider the problem of multi-objective (MO) blackbox optimization using expensive function evaluations, where the goal is to approximate the true Pareto set of solutions while minimizing the number of function evaluations. For example, in hardware design optimization, we need to find the designs that trade-off performance, energy, and area overhead using expensive simulations. We propose a novel uncertainty-aware search framework referred to as USeMO to efficiently select the sequence of inputs for evaluation to solve this problem. The selection method of USeMO consists of solving a cheap MO optimization problem via surrogate models of the true functions to identify the most promising candidates and picking the best candidate based on a measure of uncertainty. We also provide theoretical analysis to characterize the efficacy of our approach. Our experiments on several synthetic and six diverse real-world benchmark problems show that USeMO consistently outperforms the state-of-the-art algorithms.

Introduction

In many engineering and scientific domains, researchers must optimize multiple conflicting objectives simultaneously. For instance, designing a computer chip requires balancing speed against energy efficiency. These "blackbox" functions are typically expensive to evaluate, requiring hours of simulation or costly physical experiments. The goal of Multi-Objective Bayesian Optimization (MOBO) is to approximate the Pareto front—the set of optimal trade-offs where no objective can be improved without degrading another—using a minimal number of evaluations.

Existing MOBO methods often face significant hurdles. Scalarization techniques can oversimplify complex trade-offs, while information-theoretic approaches like PESMO are computationally intensive, often requiring complex approximations that can degrade accuracy. Furthermore, many algorithms do not scale well as the number of objectives or input dimensions increases. To address these challenges, we introduce the Uncertainty-Aware Search Framework (USeMO).

Methodology

USeMO employs a two-stage search framework designed to balance exploration and exploitation more effectively than previous methods. The process is decoupled into identifying promising candidates and then selecting the most informative one based on uncertainty.

  1. Stage 1: Identifying Promising Candidates. Instead of evaluating expensive real-world functions directly, USeMO constructs "cheap" surrogate models (Gaussian Processes) for each objective. It then solves a multi-objective optimization problem using standard Acquisition Functions (AF), such as Expected Improvement (EI) or Upper Confidence Bound (UCB), derived from these surrogates. This stage identifies a set of promising candidate points ($X_p$) that represent the best predicted trade-offs.
  2. Stage 2: Maximizing Uncertainty. From the set of promising candidates, USeMO selects the single point where the model's uncertainty is highest. Uncertainty is quantified as the volume of the hyper-rectangle formed by the confidence intervals (Lower and Upper Confidence Bounds) across all objectives.
The USeMO framework: a two-stage process involving surrogate model construction and uncertainty maximization.

By selecting the most uncertain point from the most promising region, USeMO intelligently directs evaluations to areas that yield the most information about the true Pareto front.

Experimental Setup

We evaluated USeMO against five major baselines: ParEGO, PESMO, SMSego, EHI, and SUR. The evaluation covered two main categories:

  • Synthetic Benchmarks: Eight standard mathematical functions (e.g., ZDT1, DTLZ1, Ackley-Sphere) with up to 6 dimensions and 6 objectives.
  • Real-World Benchmarks: Diverse applications including Neural Network hyperparameter tuning (accuracy vs. prediction time), Compiler Optimization (memory vs. performance), Hardware Design (area, throughput, energy, and runtime), and Materials Science (designing alloys and piezo-electric materials).

Results and Discussion

USeMO consistently outperformed state-of-the-art algorithms across nearly all synthetic and real-world tests, reaching a better approximation of the Pareto front in fewer iterations.

Performance comparison of USeMO against state-of-the-art baselines on real-world benchmark problems.

Key findings include:

  • Computational Efficiency: USeMO is significantly faster than information-theoretic methods. In complex benchmarks like PRDZPS-6,6, USeMO's acquisition optimization took approximately 14 seconds, compared to 110 seconds for PESMO and 300 seconds for SMSego.
  • Theoretical Guarantees: This work provides the first theoretical analysis characterizing the efficacy of a MOBO approach in terms of asymptotic regret bounds. We prove "sub-linear regret," which guarantees that the algorithm will converge to the true Pareto front as evaluations increase.
  • Robustness: The framework is highly flexible, performing consistently well regardless of the underlying acquisition function (e.g., EI or Thompson Sampling) used in the first stage.

Conclusion

USeMO offers a scalable and efficient solution for multi-objective optimization of expensive blackbox functions. By decoupling the search process and prioritizing uncertainty within promising regions, it achieves superior performance with lower computational overhead. Future work will explore the application of USeMO to higher-stakes engineering problems and investigate alternative measures for multi-objective uncertainty.

Summary updated

Abstract

We consider the problem of multi-objective (MO) blackbox optimization using expensive function evaluations, where the goal is to approximate the true Pareto set of solutions while minimizing the number of function evaluations. For example, in hardware design optimization, we need to find the designs that trade-off performance, energy, and area overhead using expensive simulations. We propose a novel uncertainty-aware search framework referred to as USeMO to efficiently select the sequence of inputs for evaluation to solve this problem. The selection method of USeMO consists of solving a cheap MO optimization problem via surrogate models of the true functions to identify the most promising candidates and picking the best candidate based on a measure of uncertainty. We also provide theoretical analysis to characterize the efficacy of our approach. Our experiments on several synthetic and six diverse real-world benchmark problems show that USeMO consistently outperforms the state-of-the-art algorithms.
BibTeX
@inproceedings{belakaria2020uncertainty,
  author = {Syrine Belakaria and Aryan Deshwal and Nitthilan Kannappan Jayakodi and Janardhan Rao Doppa},
  title = {{Uncertainty-Aware Search Framework for Multi-Objective Bayesian Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=Pt6puJi24U9},
}
Figure