🤖 machine learning

High-dimensional Multi-objective Bayesian Optimization with Learned Variable Interactions

This paper introduces ViaMOBO, a generic framework for high-dimensional multi-objective Bayesian optimization that leverages variable interaction analysis to decompose the decision space into separable subspaces for local optimization, thereby outperforming existing methods in approximating Pareto fronts for expensive black-box problems.

Original authors: Hongyan Wang, Jiayu Huang, Haotian Zheng, Xin Gao, Chi Ding, Ying Liu, Xia Wang, Qing Xu, Keqiang Li

Published 2026-08-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Hongyan Wang, Jiayu Huang, Haotian Zheng, Xin Gao, Chi Ding, Ying Liu, Xia Wang, Qing Xu, Keqiang Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a massive, multi-layered mystery. But instead of clues, you are looking for the perfect recipe. You have a giant cookbook where every page represents a different combination of ingredients, and your goal is to find the "Pareto front"—the ultimate set of recipes that are the tastiest, the cheapest, and the healthiest all at once. The catch? You can't just taste every single page. The book is too thick, and tasting a recipe takes hours of cooking and cleaning. This is the world of Multi-objective Bayesian Optimization (MOBO). It's a smart way to find the best solutions for tricky problems where you have to balance several goals at once, like designing a car that is fast, safe, and fuel-efficient, or tuning a robot's brain to be quick and accurate. The problem is, when the number of ingredients (or variables) gets huge, the number of possible recipes explodes. It's like trying to find a needle in a haystack that keeps growing. Traditional methods get overwhelmed and stop working well when the "haystack" gets too big.

This is where a new detective, named ViaMOBO, steps onto the scene. The researchers behind this paper realized that in many real-world problems, not all ingredients interact with each other. Sometimes, the amount of salt you use doesn't change how the oven temperature affects the cake; they are independent. Other times, they are best friends and always change the outcome together. The paper proposes a clever trick: instead of blindly tasting every possible combination in the giant book, ViaMOBO first asks, "Which ingredients actually talk to each other?" It uses a smart "binary classifier" (think of it as a super-quick taste-tester that guesses the result without actually cooking) to figure out which variables are linked. Once it knows the groups, it breaks the giant problem into smaller, manageable puzzles. It solves each small puzzle separately and then puts the answers back together. The paper shows that this method works incredibly well on high-dimensional problems (like those with 100 variables), finding better solutions faster and with less computing power than previous methods, especially when the problem has these hidden "groups" of interacting variables. However, the authors also note that if the variables are all tangled up in a messy, non-stop chain reaction (strongly coupled), this grouping trick might not work as well, suggesting it's best for problems where some parts can be separated.

The Detective's New Tool: ViaMOBO

So, how does this new detective, ViaMOBO, actually solve the mystery? Imagine you are trying to tune a complex machine with 100 dials. Old methods would try to turn all 100 dials at once, hoping to stumble upon the perfect setting. But with 100 dials, the number of combinations is so huge that you'd be turning dials until the sun burns out.

ViaMOBO takes a different approach. It starts by looking at the dials and asking, "Do these two dials affect each other?" To do this without wasting time, it uses a binary classifier (a type of machine learning model, like a Support Vector Machine or SVM). Instead of actually running the expensive, time-consuming test for every new combination of dials, the classifier predicts the outcome based on patterns it has already learned. It's like having a sous-chef who can guess, "If I add more salt and turn up the heat, the dish will be too salty," without actually cooking it.

By using this prediction tool, ViaMOBO can figure out which dials are "interacting" (they change the result together) and which are independent. Once it knows the relationships, it divides the 100 dials into smaller groups. Maybe dials 1 through 10 are a team, and dials 11 through 20 are another team that doesn't care about the first group. Now, instead of solving one giant, impossible puzzle, the detective solves ten tiny, easy puzzles. This is called additive kernel structure. It's like realizing you can bake the cake, frost it, and decorate it in separate steps rather than trying to do everything in one chaotic motion.

The Results: Faster, Smarter, and Cheaper

The researchers tested this new detective against a bunch of other famous detectives (like ParEGO, MORBO, and DGEMO) on some very tough test cases. They used synthetic problems (made-up math puzzles) and real-world challenges, like designing the shape of an airplane wing (airfoil) and planning a rover's path on a planet.

On the synthetic tests, specifically a problem called DTLZ2 with 100 decision variables (dials), the results were striking. ViaMOBO found a solution that was very close to the best possible, but it did it much faster. While another top contender, DGEMO, eventually found a slightly better final solution (achieving a higher Hypervolume score), it took about 10.5 times longer to get there. ViaMOBO reached a high-quality solution in just 3.99 hours (with a standard deviation of 2.16 hours), whereas DGEMO took 41.90 hours. In fact, for the 100-dimensional problem, ViaMOBO was the only method that consistently found a good solution without timing out or crashing, while others struggled or took days.

When they moved to real-world problems, like optimizing the shape of an airplane wing with 40 variables, the story was similar. ViaMOBO was the most computationally efficient method. It took only 1.35 hours to run, while the next fastest method, MORBO, took 9.37 hours. Although MORBO found a slightly better final result (about 6.84% better in terms of "hypervolume," a score that measures how good the solution is), ViaMOBO offered a much better balance between the quality of the answer and the time it took to get there.

However, the paper also points out a limitation. When they tested ViaMOBO on a 60-dimensional trajectory planning problem (planning a path for a rover), it didn't perform as well as some other methods like MORBO or NSGA-II. The authors suggest this is because the rover's path has "strong sequential coupling"—meaning every step depends heavily on the one before it, and you can't really separate the variables into independent groups. In this case, the "grouping" trick didn't work as well, showing that ViaMOBO is best suited for problems where you can actually find those separable groups.

The Takeaway

The main finding of this paper is that ViaMOBO is a powerful new framework for solving expensive, multi-objective problems with many variables. It works by first learning which variables interact with each other using a smart classifier, then breaking the big problem into smaller, easier pieces. The experiments suggest that this approach significantly reduces the time and computing power needed to find good solutions, especially when the problem has a structure that allows for separation.

The authors are confident in these results based on their simulations and real-world tests, showing that ViaMOBO outperforms existing methods in terms of speed and efficiency for high-dimensional problems. However, they are also clear that this isn't a magic bullet for every problem. If the variables are all tangled up in a way that can't be separated, the method might not be the best choice. But for the vast number of problems where variables do have independent groups, ViaMOBO offers a much faster and smarter way to find the perfect recipe.

Technical Summary: High-dimensional Multi-objective Bayesian Optimization with Learned Variable Interactions (ViaMOBO)

1. Problem Statement

Multi-objective Bayesian Optimization (MOBO) is a powerful technique for approximating Pareto fronts in expensive black-box problems, such as robotics design, circuit optimization, and hyperparameter tuning. However, existing MOBO approaches face a significant bottleneck: exponential sampling complexity as the dimensionality of the decision space increases.

Current state-of-the-art methods for high-dimensional MOBO, such as ReMO and MORBO, suffer from specific limitations:

ReMO relies on random embedding, assuming that only a few dimensions are effective and that the same dimensions are effective across all objectives. This assumption is often irrational for real-world problems where different objectives may depend on different variable subsets.
MORBO utilizes trust regions to manage local models but focuses primarily on reducing the cubic time complexity of data points rather than addressing the exponential complexity of the decision dimension itself. It does not explicitly model the interaction structure between variables.

Furthermore, many real-world high-dimensional problems exhibit variable interactions, where the fluctuation of one variable influences others, jointly affecting objective values. Current MOBO methods often ignore these relationships, leading to severely decreased performance. The core challenge is to determine whether a high-dimensional Multi-Objective Problem (MOP) is separable (variables can be grouped into independent subsets) or non-separable without making strong prior assumptions, and to leverage this structure to reduce sampling complexity.

2. Methodology: ViaMOBO Framework

The paper proposes ViaMOBO, a generic framework designed to alleviate the curse of dimensionality by learning decision variable interactions. The framework operates through the following stages:

A. Redefinition of Separability for MOPs

The authors redefine separability for multi-objective contexts. A MOP is considered separable if every objective function is separable (either fully or partially). Crucially, they introduce a transitive property for variable interactions: if variable $x_i$ interacts with $x_j$ , and $x_j$ interacts with $x_k$ , then all three are interacting. This allows the decision space to be partitioned into disjoint subgroups of interdependent variables.

B. Variable Interaction Learning (Without Expensive Evaluations)

A key innovation is the method for detecting interactions without incurring the cost of additional expensive function evaluations.

Perturbation Strategy: The algorithm selects a decision vector $x$ that maximizes a specific objective. It then perturbs this vector at two dimensions ( $i$ and $j$ ) to create new vectors ( $x'_i, x'_j, x'_{ij}$ ).
Binary Classification: Instead of evaluating the true objective function for these perturbed vectors (which would be expensive), ViaMOBO trains a binary classifier (SVM) on existing data. This classifier learns the magnitude relationship between the objective values of two decision vectors.
Interaction Detection: The trained SVM predicts the relationship between the perturbed vectors. If a dominance relationship exists between the perturbed sets (e.g., $[f(x'_i), f(x'_j)]$ dominates $[f(x), f(x'_{ij})]$ ), the variables $x_i$ and $x_j$ are deemed interacting.
Partitioning: Using the transitivity definition, the algorithm groups all interacting variables into disjoint subspaces ( $\Omega_i$ ). If the MOP is found to be non-separable, the framework defaults to other high-dimensional methods (e.g., MORBO).

C. Additive Kernel Structure and Local Optimization

Once the decision space is partitioned into disjoint subgroups $\Omega_i$ :

Additive GP Modeling: The framework assumes an additive structure for the surrogate model. Each objective $f_i(x)$ is modeled as a sum of sub-functions, each defined over a specific subgroup $\Omega_i$ .
Local Bayesian Optimization: Instead of optimizing in the full $D$ -dimensional space, the acquisition function is optimized independently within each low-dimensional subspace $\Omega_i$ . This drastically reduces the computational complexity of the acquisition function maximization.
Batch Sampling: To select a batch of candidates, the method employs strategies like qUCB, qEI, or qEHVI. It utilizes a "virtual derivative" observation technique to avoid over-exploration at the boundaries of the search space.

3. Key Contributions

ViaMOBO Framework: A general MOBO framework that introduces an additive kernel structure into multi-objective settings, explicitly considering the sample efficiency of the acquisition function in high-dimensional spaces.
Interaction Learning Strategy: A novel strategy that determines the separability of high-dimensional MOPs by learning variable interactions. It avoids expensive function evaluations during the learning phase by utilizing a binary classifier to predict objective value relationships.
Empirical Validation: Comprehensive verification against state-of-the-art MOBO methods (including ReMO, MORBO, ParEGO, DGEMO, etc.) on both synthetic benchmarks (DTLZ2) and real-world problems (airfoil design, trajectory planning).

4. Experimental Results

The authors evaluated ViaMOBO on synthetic problems with dimensions ranging from 10 to 100, and real-world problems with dimensions of 20, 40, and 60.

Synthetic Benchmarks (DTLZ2):
- 10D: ViaMOBO achieved near-optimal Pareto front approximations, with a final Hypervolume (HV) only 0.024% lower than the best performer (DGEMO), but with a runtime approximately 5.6 times faster.
- 30D: ViaMOBO maintained competitive performance, achieving a final HV only 0.118% below DGEMO while requiring roughly one-quarter of the runtime.
- 100D: ViaMOBO demonstrated superior early and intermediate convergence, achieving the highest HV@500 and HV@1000. While DGEMO eventually achieved a slightly higher final HV, it required 10.5 times the runtime. ViaMOBO significantly outperformed MORBO in terms of convergence speed and AUC-HV.
Real-World Problems:
- Airfoil Design (20D & 40D): ViaMOBO was the fastest surrogate-based method. In the 20D case, it required only ~21% of the runtime of TSEMO and ~12% of qParEGO while maintaining competitive final solution quality. In the 40D case, it was the most computationally efficient, requiring ~1/7th the runtime of MORBO for a competitive final HV.
- Trajectory Planning (60D): On this problem with strong sequential coupling, ViaMOBO performed well but was outperformed by MORBO and NSGA-II. The authors note this highlights an applicability boundary: ViaMOBO is best suited for problems with identifiable group structures or weak inter-group coupling, rather than strongly coupled sequential tasks.
Ablation Studies:
- Classifier Accuracy: The binary classifier maintained an overall grouping accuracy above 73% even at 100 dimensions, though accuracy decreased as dimensionality increased.
- Acquisition Functions: For 2-objective problems, EHVI performed best. However, for 3-objective problems, EHVI suffered from numerical instability and high computational cost. EI and UCB provided a better balance of convergence, efficiency, and robustness for the ViaMOBO framework.

5. Significance and Claims

The paper claims that ViaMOBO offers a significant advancement in handling expensive, high-dimensional multi-objective problems by moving away from rigid assumptions (like random embedding) toward data-driven structural learning.

Efficiency: By decomposing the high-dimensional space into smaller, independent subspaces based on learned interactions, ViaMOBO avoids the exponential complexity associated with global optimization in high dimensions.
Cost-Effectiveness: The use of a binary classifier to infer interactions eliminates the need for costly additional function evaluations during the structural analysis phase.
Practicality: The framework provides a favorable trade-off between solution quality and computational cost, making it particularly suitable for real-world engineering applications where computational budgets are limited.

The authors modestly acknowledge that ViaMOBO is primarily tailored to separable or weakly coupled problems. For strongly coupled, non-separable problems, its advantages may diminish, suggesting a direction for future work involving more expressive interaction modeling and adaptive variable grouping.