PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement

Samuel Daulton, Maximilian Balandat, Eytan Bakshy

arXiv:2105.08195v2cs.LGcs.AIstat.ML

TL;DR

Noisy multi-objective black-box optimization requires methods that identify Pareto trade-offs despite corrupted observations and large parallel batches. The paper proposes NEHVI and qNEHVI, Bayesian hypervolume-improvement methods that integrate uncertainty in the Pareto frontier and use scalable computation. Across noisy and parallel benchmarks, qNEHVI is robust, achieves strong hypervolume performance, and has competitive wall times, subject to computational and evaluation-setting limitations.

  • Problem

    Existing MOBO methods often perform poorly with noisy observations, while parallel EHVI has exponential complexity in batch size.

  • Method

    NEHVI applies a Bayesian treatment to EHVI by integrating uncertainty in the Pareto frontier, while qNEHVI provides a scalable parallel variant using CBD and sample average approximation.

  • Results

    qNEHVI and qNEHVI-1 outperform all other methods on the noisy benchmarks across sequential and parallel settings, with qNEHVI achieving the greatest hypervolume for increasingly large batch sizes.

  • Takeaways & Limitations

    qNEHVI provides a one-step Bayes-optimal policy for hypervolume maximization in noisy and noise-free settings while enabling scalable parallel candidate generation.

  • Takeaways & Limitations

    Exact hypervolume computation has super-polynomial complexity in the number of objectives, and information-theoretic methods may support decoupled objective evaluations that qNEHVI does not address.

Abstract

from arXiv · show

Optimizing multiple competing black-box objectives is a challenging problem in many fields, including science, engineering, and machine learning. Multi-objective Bayesian optimization (MOBO) is a sample-efficient approach for identifying the optimal trade-offs between the objectives. However, many existing methods perform poorly when the observations are corrupted by noise. We propose a novel acquisition function, NEHVI, that overcomes this important practical limitation by applying a Bayesian treatment to the popular expected hypervolume improvement (EHVI) criterion and integrating over this uncertainty in the Pareto frontier. We argue that, even in the noiseless setting, generating multiple candidates in parallel is an incarnation of EHVI with uncertainty in the Pareto frontier and therefore can be addressed using the same underlying technique. Through this lens, we derive a natural parallel variant, $q$NEHVI, that reduces computational complexity of parallel EHVI from exponential to polynomial with respect to the batch size. $q$NEHVI is one-step Bayes-optimal for hypervolume maximization in both noisy and noiseless environments, and we show that it can be optimized effectively with gradient-based methods via sample average approximation. Empirically, we demonstrate not only that $q$NEHVI is substantially more robust to observation noise than existing MOBO approaches, but also that it achieves state-of-the-art optimization performance and competitive wall-times in large-batch environments.

1 Introduction

Multi-objective black-box optimization seeks Pareto-optimal trade-offs among competing objectives, but practical observations are often noisy and existing MOBO methods commonly neglect that noise. The paper proposes NEHVI and qNEHVI to address noisy objectives and scalable parallel evaluation.

  • Motivation: Multi-objective optimization seeks a Pareto frontier of optimal trade-offs rather than a single universally best solution.Examples include balancing video quality against latency, locomotive speed against energy, and crop yield against environmental impact.
  • Motivation: Bayesian optimization combines a probabilistic surrogate with an acquisition function to balance exploration and exploitation.
  • Problem Setting: Most available MOBO methods do not account for noisy observations, although noise arises in applications such as A/B testing, agriculture, and robotics.
  • Contributions: NEHVI applies expected hypervolume improvement to noisy multi-objective optimization, while qNEHVI extends it to highly parallel evaluations.
  • Contributions: qNEHVI reduces parallel EHVI time and space complexity from exponential to polynomial in batch size and is one-step Bayes-optimal for hypervolume improvement.

2 Preliminaries

The paper formulates black-box multi-objective optimization as identifying Pareto-optimal trade-offs over a bounded design space without analytical functions or gradients. Bayesian optimization uses probabilistic surrogates and acquisition functions to make sample-efficient evaluations, addressing the high sample complexity of evolutionary alternatives.

  • Problem Formulation: The goal is to optimize multiple objectives over a bounded design space when the black-box function has no known analytical expression or gradients.
  • Pareto Optimality: MOO identifies Pareto-optimal objective trade-offs, commonly approximated by a finite Pareto frontier because the true frontier may be infinite.
  • Pareto Optimality: Hypervolume measures the objective-space region dominated by an approximate Pareto frontier and bounded by a reference point.
  • Bayesian Optimization: Bayesian optimization uses a probabilistic surrogate, typically a Gaussian process, and an acquisition function to balance exploration and exploitation.
  • Bayesian Optimization: MOBO combines Bayesian surrogates with multi-objective acquisition functions to provide a more sample-efficient alternative to evolutionary algorithms.

3 Related Work

Prior MOBO methods use hypervolume improvement, entropy, random scalarization, or evolutionary strategies, but key approaches either assume noise-free observations or face scaling and optimization difficulties. The paper positions noise-aware hypervolume methods as a response to these limitations.

  • Hypervolume-Based Methods: EHVI extends expected improvement to multi-objective optimization, while qEHVI supports batches but scales exponentially with batch size and assumes noise-free observations.
  • Hypervolume-Based Methods: DGEMO scales to large batches but does not account for noisy observations, whereas TSEMO uses Thompson sampling with random Fourier feature approximations and evolutionary optimization.
  • Entropy-Based Methods: PESMO accounts for observation noise, but its entropy computations are intractable and require complex approximations and time-consuming numerical optimization.
  • Scalarization-Based Methods: ParEGO and its batch variants convert MOO into scalarized single-objective problems using random scalarizations and parallel optimization procedures.
  • Noise-Aware Optimization: Earlier simulation studies reported no performance benefit from modeling noise, whereas this work finds that accounting for noise substantially improves performance.
  • Noise-Aware Optimization: Unlike prior work that monitors Pareto-frontier uncertainty, the paper develops a method for performing MOBO directly in noisy settings.

4 Background on Expected Hypervolume Improvement

EHVI estimates expected hypervolume improvement from a probabilistic surrogate and can be computed using box decompositions or Monte Carlo integration. Its standard one-step optimality assumes sequential, noise-free evaluation, motivating more general parallel and uncertain-frontier treatments.

  • Hypervolume Computation: The hypervolume indicator measures the M-dimensional region dominated by a finite approximate Pareto frontier and bounded below by a reference point.
  • Hypervolume Improvement: Hypervolume improvement is the increase in hypervolume obtained by adding a candidate set to an existing approximate Pareto frontier.
  • Hypervolume Computation: Hypervolume is computed by decomposing the dominated region into disjoint axis-aligned hyperrectangles, calculating each volume, and summing them.Exact hypervolume computation has super-polynomial complexity in the number of objectives.
  • Expected Hypervolume Improvement: EHVI uses the surrogate posterior over unknown function values to compute the expected hypervolume improvement of an out-of-sample candidate.
  • Expected Hypervolume Improvement: Monte Carlo integration supports EHVI without assuming conditionally independent objectives or sequential candidate generation.
  • Parallel EHVI: The displayed parallel EHVI estimator uses sampled function realizations and a candidate set of q points to approximate the acquisition value.
  • Expected Hypervolume Improvement: EHVI is one-step Bayes-optimal for hypervolume maximization when one design is evaluated, observations are noise-free, and the final approximate frontier is determined accordingly.

5 Expected Hypervolume Improvement with Noisy Observations

With noisy observations, the observed Pareto frontier can mislead EHVI, whereas NEHVI integrates uncertainty in the unknown function values and retains one-step Bayes-optimality.

  • Noisy observations make the true Pareto frontier unavailable, so EHVI is no longer one-step Bayes-optimal.The observed frontier can differ from the frontier of the underlying noiseless function.
  • Using the observed frontier can make EHVI optimize noise, producing a clumped and insufficiently diverse Pareto frontier.Posterior-mean plug-in EHVI can also produce clustered frontiers.
  • NEHVI integrates EHVI over posterior uncertainty in function values at previously evaluated points.Its integral can be approximated with Monte Carlo samples from the posterior and joint posterior evaluations.
  • NEHVI retains one-step Bayes-optimality in noisy environments and equals EHVI in noiseless environments.The method is designed to account for uncertainty in the Pareto frontier rather than substitute observed or posterior-mean values.
  • qNEHVI extends the approach to asynchronous or batch candidate generation by evaluating hypervolume improvement for q points.A sequential greedy approximation selects candidates through q simpler d-dimensional optimization problems.

6 Efficient Evaluation with Cached Box Decompositions

Cached box decompositions make repeated NEHVI evaluations practical by fixing posterior samples, caching Pareto decompositions, and supporting scalable sequential greedy batch selection.

  • Direct Monte Carlo optimization is prohibitively expensive because it repeatedly recomputes Pareto frontiers and box decompositions inside the acquisition loop.Box decomposition algorithms also have super-polynomial complexity in the number of objectives.
  • CBD computes Pareto frontiers and box decompositions once using fixed posterior samples, then caches them for an entire BO iteration.This is an instance of sample average approximation.
  • Conditional posterior sampling uses reparameterization and low-rank covariance updates to generate joint samples for candidate evaluations.For GP posteriors, samples use a posterior mean, a covariance root decomposition, and Gaussian base samples.
  • Parallel EHVI with the inclusion-exclusion principle has time and space complexity exponential in batch size q.The formulation computes volumes jointly dominated by all 2^q − 1 nonempty subsets of candidates.
  • Sequential greedy batch selection decomposes qNEHVI into contributions from previously selected candidates and the next candidate.This reduces joint optimization over a qd-dimensional domain to a sequence of d-dimensional problems.
  • CBD scales to much larger batch sizes than IEP and avoids GPU out-of-memory failures in the reported wall-time comparison.The comparison uses sequential greedy L-BFGS-B optimization on a two-objective, six-dimensional DTLZ2 problem.

7 Optimizing NEHVI

SAA fixes posterior base samples to create a deterministic NEHVI acquisition function, enabling gradient-based optimization with convergence guarantees that also extend to qNEHVI.

  • NEHVI is differentiable with respect to the candidate x because Pareto-frontier and box-decomposition operations do not depend on x.Automatic differentiation can compute exact sample-path gradients.
  • SAA fixes base samples for observed and candidate points, producing a deterministic acquisition function suitable for higher-order optimization.The deterministic form enables fast convergence rates for acquisition optimization.
  • Theorem 1 provides convergence guarantees for SAA acquisition optimization under compactness and continuously differentiable GP mean and covariance functions.The theorem concerns convergence toward the set of maximizers of the true NEHVI acquisition function.
  • The same theorem holds in the parallel setting, giving qNEHVI the same SAA acquisition-optimization convergence guarantees as NEHVI.
  • The gradient of the full Monte Carlo qNEHVI estimator is an unbiased estimator of the gradient of true joint noisy qNEHVI.This unbiased-gradient result is not required for the SAA approach.

8 Approximation of qNEHVI using Approximate GP Sample Paths

qNEHVI-1 approximates qNEHVI with a single deterministic RFF-based GP sample path, trading the full computation for cheaper evaluations and exact sample-path gradients.

  • CBD gives qNEHVI polynomial rather than exponential complexity in q, but still requires repeated joint-posterior evaluations and N box decompositions.This motivates a cheaper approximate GP sample-path alternative.
  • qNEHVI-1 uses one deterministic RFF GP sample path to approximate the qNEHVI integral during sequential greedy candidate optimization.RFF evaluations are cheaper than evaluating the GP posterior at out-of-sample points.
  • qNEHVI-1 directly optimizes HVI with exact sample-path gradients, whereas TSEMO uses NSGA-II to create a discrete candidate population.The paper reports improved optimization performance and significantly faster execution for qNEHVI-1 in Appendix H.

9 Experiments

The experiments evaluate qNEHVI and related methods on noisy synthetic and real-world multi-objective benchmarks in sequential and parallel settings. qNEHVI performs strongly across noise levels and batch sizes while maintaining competitive optimization wall-times.

  • Evaluation setup: The evaluation compares qNEHVI against established MOBO methods using logarithmic hypervolume difference from the true Pareto frontier.Because evaluations are noisy, hypervolume is computed from the noiseless Pareto frontier across observed points.
  • Benchmarks: Synthetic benchmarks include noisy BraninCurrin and DTLZ2 problems with objective noise ranging from 5% to 10% of each objective’s range.The experiments also cover adaptive bitrate control and vehicle design optimization.
  • Sequential and parallel results: qNEHVI and qNEHVI-1 outperform all other methods on noisy benchmarks in both sequential and parallel settings.This ordering remains consistent across tested noise levels up to 10%, with qNEHVI continuing to perform best up to 30% noise in an appendix study.
  • Sequential and parallel results: qNEHVI generally achieves the greatest hypervolume as batch size increases and scales more elegantly than TS-TCH and ParEGO variants.It also consistently outperforms qEHVI-PM-CBD, while qEHVI is reported only for q = 1 and q = 8 because IEP scales exponentially with q.
  • Dimensionality: qNEHVI-1 is among the top performers on relatively low-dimensional problems, whereas qNEHVI is more robust as search-space dimensionality increases.The authors attribute this observed difference to possible degradation of the Fourier-feature approximation used by qNEHVI-1.
  • Wall time: On a GPU, qNEHVI-1 has the lowest optimization wall time among tested methods on every problem, while qNEHVI is faster than information-theoretic methods on all problems.qNEHVI is often faster than BoTorch’s qNParEGO implementation when using efficient low-rank Cholesky updates.

10 Discussion

The discussion presents NEHVI as a principled approach to noisy and parallel MOBO, enabled by cached box decompositions. It also identifies computational and methodological limitations that motivate further work.

  • 10 Discussion: NEHVI is one-step Bayes-optimal for hypervolume maximization in both noisy and noise-free settings.The method targets hypervolume dominated by the Pareto frontier.
  • 10 Discussion: Cached box decomposition makes joint-hypervolume computations feasible for scalable parallel candidate generation with qNEHVI and qEHVI.The decomposition partitions non-dominated space into disjoint axis-aligned rectangles whose contributions can be summed.
  • Limitations and future work: Exact hypervolume computation remains super-polynomial in the number of objectives, motivating combinations with differentiable approximate hypervolume methods.The authors suggest such combinations could provide further speed-ups.
  • Computational scaling: CBD and IEP are mathematically equivalent under common random numbers, but CBD computes qNEHVI much more efficiently.The asymptotic relative time complexity of CBD over IEP grows without bound with batch size q.
  • Computational scaling: CBD has polynomial space complexity in q, whereas IEP has exponential space complexity in q.The acquisition computation is highly parallelizable, although CPU saturation and GPU memory limits can arise even for relatively small q.

E Theoretical Results

Theoretical results establish qNEHVI's computability and optimization properties, including bounded hyperrectangle decompositions, unbiased Monte Carlo gradients, and submodularity-based approximation guarantees.

  • Posterior sampling: qNEHVI represents posterior objective samples through a GP posterior mean, covariance root decomposition, and reparameterized Gaussian base samples.The sampled objectives include previously evaluated and candidate points, enabling sample-level hypervolume calculations.
  • Computational structure: The box decomposition of the non-dominated space contains finitely many hyperrectangles, with count bounded by O(|P_t|^⌊M/2⌋+1).The decomposition and its size depend on the posterior sample.
  • Theoretical guarantees: Theorem 1 holds for qNEHVI because the required dominating function is integrable under Gaussian base samples.The proof bounds the relevant quantities using finite reference-point coordinates and Gaussian absolute moments.
  • Gradient estimation: The averaged sample-level gradient is an unbiased estimate of the gradient of the true qNEHVI acquisition function.This result assumes continuously differentiable GP mean and covariance functions, no duplicate candidates, and reparameterized sample gradients.
  • Approximation guarantees: qNEHVI is submodular, so sequential greedy batch selection and its Monte Carlo approximation inherit the stated 1/e regret bound.The argument uses that expected stochastic submodular functions remain submodular and that HVI is normalized and submodular.

G.4 Evaluation Details

The evaluation computes log hypervolume difference against an estimated or constructed reference Pareto frontier and uses a heuristic reference point based on noiseless nadir and ideal values.

  • Evaluation metric: Log hypervolume difference uses NSGA-II to estimate the true Pareto frontier, except for ABR and AutoML, where all methods' estimated objectives define it.The resulting frontier determines the dominated hypervolume used in the metric.
  • Reference points: The reference point is r = f_nadir(x) − β(f_ideal(x) − f_nadir(x)) with β = 0.1 for every benchmark problem.The nadir and ideal values are computed component-wise from noiseless objectives.

H.1 Wall Time Results

qNEHVI combines strong optimization performance with competitive acquisition-optimization wall times, while CBD enables scaling to large batches and multiple objectives. Its advantages are especially pronounced under noise and high-dimensional or highly parallel settings, although qNEHVI-1 has narrower strengths.

  • Wall Time Results: qNEHVI is faster to optimize than MESMO and PFES on nearly all benchmark problems except CarSideImpact, with wall times competitive with qNParEGO.On many problems, qNEHVI is also faster than qNParEGO, including VehicleSafety and CarSideImpact with three and four objectives.
  • Scaling to large batch sizes with CBD: CBD scales parallel EHVI to large batch sizes with three or four objectives, whereas IEP wall times grow exponentially and can overflow GPU memory.qEHVI(-PM) ran out of memory for q = 8 on CarSideImpact because its box decomposition produced many hyperrectangles.
  • Additional Empirical Results: qNEHVI-based algorithms are consistently top performers in additional optimization results, while qEHVI is best only in the sequential CarSideImpact case.In parallel vehicle manufacturing settings, qNEHVI is identified as the best choice because it scales to large batches while qEHVI runs out of memory at q = 8.
  • Performance over Higher Dimensional Spaces: qNEHVI-1 performs well on many low-dimensional problems but underperforms qNEHVI in higher-dimensional spaces, likely because its RFF approximation degrades there.The paper notes that further study is needed to determine whether increasing the number of Fourier basis functions improves robustness.
  • Optimization Performance under Increasing Noise Levels: qNEHVI is the top performer in high-noise environments, while qNEHVI-1 is competitive mainly when noise is below 15% of each objective’s range.All methods degrade as noise increases; qNEHVI-1 can achieve the best final hypervolume below that noise level but performs worse earlier in optimization.
  • Optimization Performance on Noiseless Benchmarks: qNEHVI outperforms tested methods across noiseless benchmarks and shows little performance degradation as parallelism increases.qNEHVI-1 is also a top performer on noiseless problems.
  • Performance of qNEHVI-1 on 5-Objective Optimization: qNEHVI-1 extends EHVI-based optimization to five objectives, outperforming qNParEGO and Sobol search but requiring 73.53 seconds per candidate on average.qNParEGO requires 11.37 seconds per candidate on average, making qNEHVI-1 slower in this five-objective experiment.
Loading 2105.08195v2…