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. 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 fields, from hardware design to materials science, engineers face "blackbox" optimization problems where they must balance multiple conflicting objectives—such as maximizing a processor's performance while minimizing its energy consumption. These problems present two primary challenges: evaluations are often prohibitively expensive, and there is rarely a single optimal solution. Instead, the goal is to identify a Pareto set, a collection of solutions where no objective can be improved without degrading another.
Existing Bayesian Optimization (BO) tools often struggle in this multi-objective setting. Scalarization methods can lose critical nuance, while information-theoretic approaches like PESMO, though mathematically elegant, are computationally heavy and require complex approximations that can hurt accuracy as the number of objectives grows. This paper introduces USeMO (Uncertainty-aware Search framework for Multi-Objective Bayesian Optimization), a novel framework designed to find these trade-offs efficiently.
The USeMO Framework
USeMO decouples the selection of the next design to test into two distinct stages, effectively balancing exploitation and exploration:
- Promising Candidate Identification: Instead of solving the expensive problem directly, USeMO builds "cheap" surrogate models (Gaussian Processes) for each objective. It treats the acquisition functions (mathematical proxies for utility) of these surrogates as a new, easy-to-solve multi-objective problem. It uses a standard evolutionary algorithm (NSGA-II) to find a set of promising candidate points representing different trade-offs.
- Uncertainty Maximization: From the pool of promising candidates, USeMO selects the one where the surrogate models are most uncertain. Uncertainty is measured as the volume of a hyper-rectangle formed by the confidence intervals (Lower and Upper Confidence Bounds) of all objectives.
By picking the most uncertain point from a pool of high-utility candidates, the algorithm avoids aggressive exploitation. Furthermore, the paper provides a rigorous proof that USeMO achieves sub-linear regret, the first such theoretical guarantee for a multi-objective BO framework.
Experimental Evaluation
The authors evaluated USeMO against five major baselines (ParEGO, PESMO, SMSego, EHI, and SUR) using eight synthetic benchmarks and six diverse real-world benchmarks, including:
- Neural Network Tuning: Optimizing accuracy vs. prediction time on MNIST.
- Compiler Optimization: Tuning SW-LLVM settings for memory and performance.
- Hardware Design: Optimizing FPGA sorting networks (SNW) and Network-on-Chip (NoC) configurations.
- Materials Science: Designing Shape Memory Alloys (SMA) and Piezo-electric materials (PEM).
Results and Discussion
Across almost all benchmarks, USeMO reached a better approximation of the Pareto front faster than its competitors, as measured by Hypervolume Difference and the $R_2$ indicator.
Beyond accuracy, USeMO is significantly more computationally efficient than information-theoretic methods. For instance, on the 6-objective PRDZPS benchmark, USeMO’s selection step took approximately 14 seconds, while PESMO required 110 seconds. This scalability makes USeMO robust even as the number of objectives increases.
Conclusion
USeMO offers a powerful and efficient framework for multi-objective optimization by cleverly treating acquisition functions as a "cheap" MO problem. While it relies on Gaussian Processes, which can scale cubically with the number of points, its two-stage search process provides a significant leap in both practical performance and theoretical reliability for complex engineering tasks.
Summary updated