PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces

Samuel Daulton, David Eriksson, Maximilian Balandat, Eytan Bakshy

arXiv:2109.10964v4cs.LGcs.AImath.OCstat.ML

TL;DR

Existing multi-objective BO methods struggle with high-dimensional search spaces, expensive evaluations, and global surrogate models whose inference scales cubically with observations. MORBO addresses this with coordinated local trust regions that optimize diverse Pareto-frontier regions in parallel. It scales to hundreds of parameters and thousands of evaluations, with reported order-of-magnitude savings in time and resources over state-of-the-art methods.

  • Problem

    Existing multi-objective BO methods perform poorly beyond a few dozen parameters and rely on global surrogate models with cubic scaling in observations.

  • Method

    MORBO performs coordinated multi-objective BO in parallel local trust regions, sharing observations and managing regions through a global policy.

  • Results

    MORBO scales to hundreds of tunable parameters and thousands of evaluations, achieving order-of-magnitude savings in time and resources over state-of-the-art methods.

  • Takeaways & Limitations

    MORBO enables multi-objective BO on high-dimensional, high-throughput problems previously out of reach for existing BO methods.

  • Takeaways & Limitations

    Hypervolume-based acquisition scales poorly with the number of objectives, and other methods may perform better on low-dimensional problems with small evaluation budgets.

Abstract

from arXiv · show

Many real world scientific and industrial applications require optimizing multiple competing black-box objectives. When the objectives are expensive-to-evaluate, multi-objective Bayesian optimization (BO) is a popular approach because of its high sample efficiency. However, even with recent methodological advances, most existing multi-objective BO methods perform poorly on search spaces with more than a few dozen parameters and rely on global surrogate models that scale cubically with the number of observations. In this work we propose MORBO, a scalable method for multi-objective BO over high-dimensional search spaces. MORBO identifies diverse globally optimal solutions by performing BO in multiple local regions of the design space in parallel using a coordinated strategy. We show that MORBO significantly advances the state-of-the-art in sample efficiency for several high-dimensional synthetic problems and real world applications, including an optical display design problem and a vehicle design problem with 146 and 222 parameters, respectively. On these problems, where existing BO algorithms fail to scale and perform well, MORBO provides practitioners with order-of-magnitude improvements in sample efficiency over the current approach.

1 INTRODUCTION

Multi-objective BO must address expensive evaluations, high-dimensional designs, and surrogate-model scaling limits. MORBO uses coordinated local trust regions to optimize diverse Pareto-frontier regions in parallel and achieves strong sample-efficiency improvements.

  • Motivation: 222 structural-part widths and 54 black-box constraints define a vehicle design problem whose evaluations require crash tests or demanding simulations.The original computation took around 3,000 CPU years on the world’s fastest supercomputer.
  • Motivation: Standard BO applications typically use fewer than 20 tunable parameters, while GP inference scales cubically with the number of data points.These limitations make basic BO poorly suited to high-dimensional, large-budget settings.
  • MORBO: MORBO optimizes diverse parts of the global Pareto frontier in parallel using coordinated local trust regions.Local BO mitigates over-exploration in high-dimensional settings.
  • MORBO: MORBO shares observations across trust regions and collaboratively selects batches to maximize a global utility.It also terminates under-performing regions and allocates new ones using a policy with a theoretical performance guarantee.
  • Results: MORBO scales to hundreds of tunable parameters and thousands of evaluations, where practitioners previously used less sample-efficient alternatives such as NSGA-II.The evaluation reports order-of-magnitude savings in time and resources compared with state-of-the-art methods.

2 BACKGROUND

The background defines Pareto trade-offs, feasibility, hypervolume, and Bayesian optimization, then reviews scalable and trust-region alternatives. It motivates MORBO by highlighting limitations in dimensionality, global modeling, information sharing, and scalarized coverage.

  • Multi-Objective Optimization: Multi-objective optimization seeks a vector of objectives subject to black-box constraints, typically without one solution that simultaneously maximizes every objective.Solutions are compared through Pareto domination, and the feasible Pareto frontier contains optimal trade-offs among feasible designs.
  • Multi-Objective Optimization: The goal is to identify an approximate Pareto frontier within a fixed evaluation budget, commonly assessed with the hypervolume indicator.Hypervolume measures the region dominated by the frontier and bounded by a reference point.
  • Related Methods: Evolutionary algorithms such as NSGA-II generally have high sample complexity, limiting their applicability under small evaluation budgets.This motivates BO when evaluations are expensive and sample efficiency matters.
  • Bayesian Optimization: Bayesian optimization combines a probabilistic surrogate with an acquisition function that balances exploration and exploitation.Multi-objective methods may use random scalarizations or directly maximize expected hypervolume improvement or hypervolume improvement through Thompson sampling.
  • Related Methods: Existing multi-objective BO methods are usually evaluated in low dimensions, rely on global GPs, and rarely address high-dimensional problems with large evaluation budgets.The largest reported search space in the cited literature contains 27 parameters.
  • Related Methods: LaMOO uses good and bad regions but remains limited by global GPs and rejection sampling in high-dimensional spaces.Random embeddings and additive models likewise require strong structural assumptions, while one multi-objective extension needs MCMC feasible only in the small-data regime.
  • Trust Region Bayesian Optimization: TuRBO uses local hyperrectangular trust regions without strong objective assumptions, but does not share information between regions and fits models to each region’s full history.These properties can waste evaluations and impair scalability when regions restart infrequently.
  • Issues with Scalarized TuRBO: Using one persistent random scalarization per trust region can produce poor Pareto-frontier coverage because only a small number of trade-offs may be explored.MORBO instead coordinates regions to improve coverage and global-frontier optimization.

3 MORBO

MORBO coordinates multiple local trust regions to optimize diverse parts of a global Pareto frontier while improving scalability through local modeling and information sharing.

  • Collaborative optimization: MORBO shares observations across trust regions, coordinates their centers, and uses a shared global utility to collaboratively optimize the Pareto frontier.Under-performing trust regions are terminated and new regions are allocated according to a global policy.
  • Collaborative optimization: Hypervolume improvement provides diverse set-level utility, while Thompson sampling approximates expected hypervolume improvement for scalable batch selection.Candidates are selected sequentially, conditioning on earlier selections in the batch.
  • Trust-region center selection: MORBO centers each trust region at a feasible Pareto-front point with maximum hypervolume contribution, or at the point with smallest total constraint violation when none is feasible.Sequential greedy center selection avoids reusing points and favors less crowded regions of the frontier.
  • Local modeling: Local Gaussian-process models use observations within a hypercube of edge length 2L, reducing inference cost compared with fitting models to all observations.MORBO also shares data across trust regions, unlike independent trust-region approaches.
  • Local modeling: Under limited assumptions, local modeling yields speedups of O(n_TR/η^3), and experiments report two orders of magnitude speedups relative to global modeling.Here η is the average number of trust-region modeling spaces containing a data point.
  • Trust-region reinitialization: Hypervolume-scalarization-based reinitialization places new trust regions in diverse objective-space regions and provides a global optimization performance guarantee.The new center maximizes a random hypervolume scalarization under a posterior sample from a global Gaussian process.

4 THEORETICAL ANALYSIS

The theoretical analysis establishes finite sampling before trust-region restarts and bounds MORBO’s cumulative hypervolume regret under stated assumptions. The guarantee is expressed in terms of restarts rather than evaluations, reflecting the method’s large-scale setting.

  • Finite trust-region sampling: Each trust region evaluates only finitely many samples when improvements require at least δ hypervolume increase and objective values lie in [0, B]^M.This result supports subsequent regret analysis over trust-region restarts.
  • Hypervolume regret: MORBO’s regret analysis uses the kernel-dependent maximum information gain γ_T to bound cumulative hypervolume regret after T trust-region restarts.The theorem assumes bounded objectives, Gaussian-distributed objective components, independent Gaussian observation noise, and the finite-sampling conditions.
  • Theoretical significance: The analysis presents MORBO as the first sample-efficient large-scale multi-objective optimization algorithm with bounded regret, up to logarithmic terms.The paper positions this result as extending hypervolume-regret analysis to a large-scale multi-objective BO method.
  • Scope of the guarantee: The regret bound is measured by the number of trust-region restart points rather than evaluations.The paper identifies this distinction as a cost of focusing on problems that global Gaussian-process BO cannot address.

5 EXPERIMENTS

MORBO is evaluated across synthetic and real-world high-dimensional multi-objective problems, including trajectory planning, optical design, and constrained vehicle design. Across these experiments, it outperforms competing methods, while ablations identify multiple trust regions, data sharing, and hypervolume acquisition as important components.

  • Experimental setup: MORBO is evaluated on benchmarks spanning input dimensions, objectives, and constraints, including trajectory planning, optical design, and Mazda vehicle design.The real-world problems have 60, 146, and 222 parameters, respectively.
  • Optical design problem: NSGA-II outperforms BO baselines but remains noncompetitive with MORBO on the 146-parameter optical design problem.Each optical-design evaluation requires a computationally intensive physics simulation taking several hours.
  • Trajectory Planning: MORBO performs best on trajectory planning after 2,000 evaluations, while qNEHVI does not outperform NSGA-II.The experiment uses batch size q = 50 and 200 initial points.
  • Mazda vehicle design problem: MORBO clearly outperforms the other methods on the Mazda vehicle design problem with 222 variables and 54 black-box constraints.NSGA-II improves from the initial feasible solution but is not competitive with MORBO; Sobol finds no subsequent feasible design.
  • Sensitivity analysis: Multiple trust regions and hypervolume acquisition are important: single-region and Chebyshev-scalarization variants perform worse.Performance is generally robust to failure tolerance, except that a value of 10 degrades optical-design performance by shrinking trust regions too quickly.
  • Sensitivity analysis: The default hypervolume-scalarization restart strategy and random restart points both show strong performance, while the default strategy provides a regret bound.MORBO uses five trust regions in the reported experiments.

6 DISCUSSION

The discussion presents MORBO as a scalable multi-objective BO method for high-dimensional and high-throughput settings, while identifying objective-count and budget-dimensionality boundaries.

  • Discussion: MORBO uses coordinated multiple trust regions with scalable local modeling to address high-dimensional and high-throughput multi-objective optimization.The paper reports that this approach tackles real-world problems previously out of reach for existing BO methods.
  • Limitations: Hypervolume-based acquisition scales poorly with the number of objectives, limiting MORBO when objective count becomes large.This limitation remains despite MORBO handling many black-box constraints.
  • Limitations: MORBO is optimized for large-batch, high-throughput settings, whereas other methods may perform better on low-dimensional problems with small evaluation budgets.

A.1 RFFS FOR FAST POSTERIOR SAMPLING

The appendix studies Random Fourier Features as an approximation for fast posterior sampling and compares discrete and continuous optimization across dimensions. Approximation quality and optimization behavior vary with dimensionality.

  • RFFs for fast posterior sampling: RFFs approximate GP function samples as linear combinations of basis functions, offering an alternative to exact posterior sampling.The comparison includes 1,024- and 4,096-basis-function approximations on discrete candidate sets.
  • RFF optimization: Direct gradient optimization of RFF samples placed many parameters on boundaries, causing over-exploration and poor BO performance.The revised procedure first selects top candidates and then optimizes only perturbed dimensions.
  • RFF optimization: Continuous RFF optimization works well at d = 10 but degrades as dimensionality increases.The continuous approach optimizes RFF draws over axis-aligned subspaces using gradient-based optimization.
  • RFF optimization: At higher dimensions, discrete-set RFF optimization outperforms continuous optimization, while 4,096 basis functions outperform 1,024.The paper hypothesizes that RFF approximation quality degrades in higher dimensions.

C PROOFS

The proofs establish finite evaluation of each trust region under a minimum hypervolume-improvement rule and derive a cumulative hypervolume-regret bound under Gaussian-process assumptions.

  • Finite trust-region evaluations: A trust region evaluates only finitely many samples when improvements require at least δ hypervolume gain and its success threshold is τsucc = ∞.The proof uses bounded Pareto-frontier hypervolume and shows that infinitely many evaluations would imply infinitely many δ-sized improvements.
  • Regret bound: Theorem 4.1 bounds MORBO’s cumulative hypervolume regret after T trust-region restarts under bounded objectives and Gaussian-distribution assumptions.The regret is expressed in terms of the number of restart points.
  • Regret bound: The hypervolume-regret analysis scales with the number of objectives through the Lipschitz and hypervolume-scalarization factors.The proof relates the bound to scalarized Bayes regret and an objective-dependent factor.
  • Regret bound: The displayed cumulative-regret expression contains a dimension-dependent factor and the information-gain term [γ_T T ln(T)]^1/2.The supplied proof passages state the cumulative-regret form but do not provide a complete readable derivation of every displayed factor.

D DETAILS ON EXPERIMENTS

The experiments specify MORBO’s trust-region settings, benchmark suite, objective transformations, and local-model fitting procedure. These choices support scalable evaluation across synthetic, low-dimensional, and high-dimensional design problems.

  • MORBO uses five trust regions with Linit = 0.8, Lmax = 1.6, and Lmin = 0.01.
  • MORBO fits local models using data inside a hypercube around each trust-region center and limits the fitting set to nearby points when necessary.The fitting hypercube has edge length 2L, with Nm := min{250, 2^d} used when fewer points are available locally.
  • Synthetic objectives and reference points are multiplied by −1 so the experiments maximize the resulting objectives.
  • The benchmark suite includes DTLZ problems, MW7, welded beam, vehicle safety, trajectory planning, optical design, and Mazda vehicle design.
  • Local modeling has total fitting complexity governed by the average overlap η, and empirical η < 1 yields substantial speedups as trust regions shrink.

E.1 MODEL FITTING TIMES

MORBO reduces model-fitting cost by fitting local models in shrinking trust regions rather than one global model. The reported experiments show much lower fitting time, including on the 146-dimensional optical design problem.

  • MORBO’s local modeling requires far less fitting time than global-model methods, while TSEMO spends almost an hour fitting models after 2,000 trajectory-planning evaluations.
  • The initial overlap η depends on the initial trust-region edge length and the search-space dimension.
  • Trust regions contain a few hundred points on average, enabling computationally efficient local modeling.
  • As optimization proceeds, trust regions shrink and the average number of trust regions containing a design becomes less than one.
  • On the 146-dimensional optical design problem, fitting a global model takes almost 20 minutes near the run’s end compared with 10 seconds for MORBO.

F.1 LOW-DIMENSIONAL PROBLEMS

On low-dimensional vehicle-safety and welded-beam problems, MORBO remains competitive despite being designed for harder settings. Its results also show efficient constraint handling and weak NSGA-II performance in these comparisons.

  • MORBO is competitive with TS-TCH and qParEGO on vehicle safety but does not match qNEHVI and TSEMO.
  • MORBO’s welded-beam results illustrate efficient handling of four black-box constraints.
  • NSGA-II performs barely better than Sobol on vehicle safety and worse than Sobol on welded beam.
  • Candidate generation for MORBO is two orders of magnitude faster than qParEGO and qNEHVI on trajectory planning after all methods complete 2,000 evaluations.
  • The candidate-generation comparison reports batch-selection wall times on DTLZ problems with two and four objectives at d = 100.

F.3 PARETO FRONTIERS

MORBO generally finds well-covered Pareto frontiers across welded-beam, trajectory-planning, optical-design, and Mazda problems. Multiple trust regions support coverage of diverse trade-offs and large final hypervolumes.

  • MORBO achieves much better Pareto-frontier coverage than baseline methods on the 4D welded-beam problem.
  • On trajectory planning, MORBO finds rewards close to the maximum possible reward of 5, while other methods struggle with high-reward trajectories.
  • MORBO explores objective trade-offs better than NSGA-II and Sobol on the optical-design and Mazda problems.
  • Across the displayed replications, multiple trust regions consistently provide good Pareto-frontier coverage alongside large hypervolumes.

F.4 ADDITIONAL BENCHMARK PROBLEMS

MORBO is evaluated on two- and four-objective DTLZ3, DTLZ5, and DTLZ7 problems with 100 dimensions, where it achieves strong final hypervolume performance and ranks among the leading methods.

  • Benchmark setup: MORBO is evaluated on two-objective and four-objective DTLZ3, DTLZ5, and DTLZ7 problems with d = 100.The benchmark uses batches of q = 50 evaluations.
  • Four-objective results: MORBO performs best on four-objective DTLZ7 and achieves the best final hypervolume on four-objective DTLZ3.
  • Two-objective results: On the two-objective problems, MORBO always ranks in the top 4 methods.
  • Efficiency comparison: DGEMO, MOEA/D-EGO, and qNEHVI perform competitively in the two-objective setting, but all are significantly slower than MORBO.
Loading 2109.10964v4…