PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization

Samuel Daulton, Maximilian Balandat, Eytan Bakshy

arXiv:2006.05078v3stat.MLcs.AIcs.LGmath.OC

TL;DR

The paper addresses computationally expensive and often nondifferentiable acquisition functions for parallel, constrained multi-objective Bayesian optimization. It introduces qEHVI with exact Monte Carlo-estimator gradients and SAA-based optimization, achieving state-of-the-art performance at a fraction of competing methods’ wall time.

  • Problem

    Parallel and constrained multi-objective Bayesian optimization lacks acquisition functions that are simultaneously computationally efficient and differentiable, while EHVI computation scales exponentially with the number of objectives.

  • Method

    The paper derives qEHVI, an exact joint EHVI formulation up to Monte Carlo integration error, and optimizes it using auto-differentiated gradients with sample average approximation and higher-order methods.

  • Results

    qEHVI outperforms state-of-the-art multi-objective Bayesian optimization algorithms while using only a fraction of their wall time.

  • Takeaways & Limitations

    Differentiable qEHVI provides a practical acquisition function for parallel, constrained multi-objective Bayesian optimization, with competitive scaling at high parallelism.

  • Takeaways & Limitations

    EHVI computation remains computationally challenging because its time complexity is exponential in the number of objectives, despite the proposed acceleration and parallelization.

Abstract

from arXiv · show

In many real-world scenarios, decision makers seek to efficiently optimize multiple competing objectives in a sample-efficient fashion. Multi-objective Bayesian optimization (BO) is a common approach, but many of the best-performing acquisition functions do not have known analytic gradients and suffer from high computational overhead. We leverage recent advances in programming models and hardware acceleration for multi-objective BO using Expected Hypervolume Improvement (EHVI)---an algorithm notorious for its high computational complexity. We derive a novel formulation of q-Expected Hypervolume Improvement (qEHVI), an acquisition function that extends EHVI to the parallel, constrained evaluation setting. qEHVI is an exact computation of the joint EHVI of q new candidate points (up to Monte-Carlo (MC) integration error). Whereas previous EHVI formulations rely on gradient-free acquisition optimization or approximated gradients, we compute exact gradients of the MC estimator via auto-differentiation, thereby enabling efficient and effective optimization using first-order and quasi-second-order methods. Our empirical evaluation demonstrates that qEHVI is computationally tractable in many practical scenarios and outperforms state-of-the-art multi-objective BO algorithms at a fraction of their wall time.

1 Introduction

Multi-objective BO targets expensive black-box objectives with competing trade-offs, but existing parallel and constrained methods often lack differentiability, scalability, or efficient computation. The paper introduces qEHVI to address these limitations using exact gradients and accelerated computation.

  • 1.1 Background: Multi-objective optimization seeks Pareto-optimal solutions because improving one objective can deteriorate another.
  • 1.1 Background: Bayesian optimization offers a sample-efficient alternative for expensive black-box objectives compared with evolutionary algorithms.
  • 1.2 Limitations of current approaches: Existing constrained and parallel multi-objective BO methods often use scalarizations, expensive acquisitions, non-differentiable functions, or heuristic parallel extensions.
  • 1.2 Limitations of current approaches: EHVI provides strong Pareto-front coverage, but parallel EHVI has received little attention, existing methods are approximate, and computation is exponential in objective count.
  • 1.3 Contributions: qEHVI is a parallel EHVI formulation that is exact up to Monte-Carlo integration error, supports auxiliary constraints, and uses exact auto-differentiated gradients.

2 Related Work

Prior work addressed EHVI gradients, alternative multi-objective acquisitions, and batch selection, but generally lacked a practical combination of exact qEHVI, constraints, and proper posterior integration.

  • EHVI gradients: Prior exact EHVI gradients were limited to unconstrained, two-objective, sequential optimization, while other methods used gradient-free or approximate-gradient optimization.
  • Alternative acquisitions: Alternative methods include scalarized ParEGO and TS-TCH, HV-based SMS-EGO, and PESMO, but their supported settings differ from parallel constrained EHVI.
  • Batch optimization: Sequential greedy batch selection reduces optimization dimension from qd to d per step and integrates over posterior uncertainty at pending points.
  • Paper distinction: qEHVI enables gradient-based joint and sequential greedy optimization with proper posterior integration, unlike prior exact-qEHVI work that substituted an alternative acquisition.

3 Differentiable q-Expected Hypervolume Improvement

The paper computes joint q-point hypervolume improvement by decomposing non-dominated space into boxes, applying inclusion-exclusion across candidate subsets, and averaging over joint posterior samples. The formulation extends naturally to constraints and remains exact apart from MC error.

  • 3.1 Hypervolume improvement: Hypervolume improvement is the additional dominated volume obtained by adding candidate outcomes to a Pareto set relative to a reference point.
  • 3.1 Box decomposition: For one candidate, HVI partitions non-dominated space into disjoint axis-parallel rectangles and integrates the candidate-induced region within each box.
  • 3.2 Parallel HVI: For q candidates, qEHVI computes the union of their improvement regions using inclusion-exclusion over candidate subsets and box intersections.
  • 3.3 Expected q-HVI: qEHVI estimates expected joint HVI from joint posterior samples because no analytic form is known for q > 1 or correlated outcomes.
  • 3.3 Computation: The box decomposition makes the estimator exact up to MC error, whose iid-sample error scales as 1/√N, while computation costs O(MNK(2^q−1)).
  • 3.4 Outcome Constraints: Outcome constraints are incorporated by weighting sample-level HVI with feasibility indicators, yielding feasible expected hypervolume improvement.

4 Optimizing q-Expected Hypervolume Improvement

Exact auto-differentiated gradients make qEHVI amenable to efficient optimization, while sample average approximation enables deterministic higher-order methods. Experiments show substantial optimization-time savings and benefits from proper posterior integration.

  • 4.1 Differentiability: Auto-differentiation computes exact gradients for qEHVI with more than two objectives, constraints, and batches q > 1, where analytic formulas are unavailable.
  • 4.1 Differentiability: Under regular GP mean and covariance functions, the MC gradient is an unbiased estimate of the exact acquisition-function gradient.
  • 4.2 Optimization via Sample Average Approximation: Sample average approximation enables deterministic higher-order optimizers and provides convergence guarantees under stated regularity conditions.
  • 4.2 Optimization via Sample Average Approximation: Exact gradients reduce cumulative acquisition-optimization time by an order of magnitude relative to finite differences and gradient-free CMA-ES.
  • 4.3 Sequential Greedy and Joint Batch Optimization: Properly integrating unobserved pending outcomes improves optimization performance over posterior-mean sequential selection and joint optimization.

5 Benchmarks

The benchmarks evaluate qEHVI against established and parallel multi-objective Bayesian optimization baselines on synthetic and real-world problems. qEHVI outperforms the baselines sequentially and retains favorable parallel scaling and wall-time characteristics.

  • Benchmark setup: qEHVI is evaluated on synthetic and real-world optimization problems against SMS-EGO, PESMO, TS-TCH, analytic EHVI with gradients, qPAREGO, and a scrambled Sobol baseline.The evaluation includes methods supporting parallel evaluation and constraints, including qPAREGO.
  • Benchmark setup: Synthetic benchmarks use log hypervolume difference, or the hypervolume indicator when the true Pareto front is unknown or difficult to approximate.The log hypervolume difference compares the true feasible Pareto-front hypervolume with that of the approximate feasible Pareto front.
  • Benchmark setup: The real-world benchmarks include automobile crash-safety structural optimization and adaptive bitrate-control policy optimization.The vehicle problem reflects trade-offs among lightweight design, fuel economy, manufacturing cost, damage, and occupant injury; ABR considers video quality and streaming stability.
  • Sequential results: qEHVI outperforms all baselines in sequential optimization performance across every evaluated problem.Figure 3 reports means and 2 standard errors across 20 trials for Branin-Currin, C2-DTLZ2, vehicle crash safety, and ABR control.
  • Computational performance: qEHVI achieves CPU wall times an order of magnitude smaller than PESMO and remains competitive with qPAREGO for large q on a GPU.TS-TCH is fastest, but its lower wall time comes with inferior optimization performance.
  • Parallel results: Increasing parallelism accelerates convergence for all algorithms, while qEHVI’s sample complexity does not substantially deteriorate at high batch sizes.Figure 4 reports ABR performance by batch BO iterations and function evaluations across varying q.

7 Statement of Broader Impact

Multi-objective optimization can help decision makers examine trade-offs that are difficult to encode in advance as a single scalar objective. Improved practical performance could support more informed decisions across multiple outcomes.

  • Broader impact: Optimizing one outcome commonly comes at the expense of secondary outcomes, making advance scalarization of competing objectives difficult in many cases.The paper frames multi-objective optimization as a way to retain the set of optimal trade-offs rather than fixing one scalar objective beforehand.
  • Broader impact: More practical multi-objective Bayesian optimization could help decision makers better understand trade-offs across multiple outcomes.The stated potential impact is improved understanding and more informed decision-making.
  • Broader impact: The broader-impact motivation concerns scientific and engineering decisions where competing objectives must be considered together.Examples in the paper include automobile design and other applications involving multiple performance criteria.

A Derivation of q-Expected Hypervolume Improvement

The paper derives joint qEHVI by combining inclusion-exclusion over candidate subsets with hyper-rectangle partitioning, then estimates the posterior expectation using Monte Carlo integration. Constraints are incorporated through feasibility weighting, while differentiability requires a sigmoid relaxation of constraint indicators.

  • Joint hypervolume improvement: qEHVI computes joint hypervolume improvement by applying inclusion-exclusion to the improvement sets of q new candidates.Each candidate contributes a set of newly dominated points, and intersections are summed with alternating signs.
  • Hyper-rectangle partitioning: Intersections are evaluated independently within a disjoint partition of the non-dominated objective space into K hyper-rectangles.This converts intersections with potentially non-rectangular dominated regions into rectangular computations with easily derived bounds.
  • Parallel computation: The resulting computation parallelizes across candidate subsets and hyper-rectangles, making joint HVI computationally tractable when q is small relative to the Pareto set.The inclusion-exclusion formulation is practical because q is typically much smaller than |P|.
  • Posterior integration: For q > 1, qEHVI is obtained by taking the expectation of joint HVI under samples from the joint GP posterior because no analytical formulation is known.For q = 1 with independent outcomes, the acquisition reduces to EHVI, which has a closed form.
  • Outcome constraints: Constraints are handled by zeroing the contribution of subsets containing infeasible candidates and weighting marginal improvement by joint feasibility.The Monte Carlo formulation can estimate correlated objective and constraint outcomes without requiring their independence.
  • Differentiable constraints: A sigmoid replaces constraint indicators to provide differentiable gradients, introducing approximation error when the sigmoid differs from the exact indicator.The exact indicator formulation computes HVI without approximation error when all sigmoid values match their indicators.
  • Complexity: The implementation has single-threaded time complexity T1 = O(MNK(2q −1)) and requires comparable space for maximum parallelism.Memory limits scalability for large M and q; processing rectangles in chunks reduces memory at the cost of additional runtime.

B Error Bound on Sequential Greedy Approximation

Because qEHVI is a normalized submodular set function, sequential greedy candidate selection inherits a theoretical regret guarantee while avoiding joint optimization over all q candidates.

  • Greedy approximation: qEHVI is submodular because HVI is submodular and expectations preserve stochastic submodularity.This establishes the structural condition needed for the sequential greedy guarantee.
  • Greedy approximation: The Monte Carlo approximation of qEHVI receives the same regret bound because HVI is a normalized submodular set function.The result extends the guarantee from the exact acquisition to the MC-based approximation.

C Convergence Results

The convergence analysis establishes almost-sure convergence of the SAA optimizer under regular GP assumptions and shows unbiasedness of sample-average qEHVI gradients. Fixed base samples also reduce gradient-estimator variance without introducing bias.

  • The proof uses reparameterized GP samples and establishes that the hypervolume improvement is almost surely piece-wise differentiable with respect to candidate locations.
  • Under compactness and continuously differentiable GP mean and covariance functions, the SAA optimizer converges almost surely to the true qEHVI maximizer set.
  • The convergence result assumes a compact search space and a multi-output GP with continuously differentiable mean and covariance functions.
  • A convergence-rate result for the optimizer is left to future work, although the theorem may extend to randomized QMC base samples.
  • The averaged sample-level gradient of the MC qEHVI approximation is an unbiased estimator of the true acquisition-function gradient.
  • Using only N = 32 QMC samples, the average sample gradient has very low variance, while fixing base samples further reduces variance without introducing bias.

E.1.1 Reference point specification

Reference-point specification affects how hypervolume weights Pareto-front regions and therefore influences both evaluation and hypervolume-based acquisition functions. A dynamic strategy showed similar average performance but higher variance, with a boundary for discontinuous fronts.

  • Hypervolume is sensitive to the reference point: distant points favor extreme Pareto-front solutions, whereas nearby points give more weight to less-extreme solutions.
  • The reference point affects both multi-objective method evaluation and the utility functions of methods relying on hypervolume.
  • A dynamic reference point set slightly below the current nadir produced similar average performance but higher variance than a known reference point on continuous fronts.
  • For discontinuous Pareto fronts, dynamic reference-point selection may prevent reaching every section of the front.

E.2 Benchmark Problems

The benchmark suite includes constrained and unconstrained synthetic and engineering problems, with acquisition optimization wall time measured on CPU and GPU hardware.

  • Benchmark results assume minimization of all objectives and use reference points specified in Table 2.
  • Branin-Currin: The constrained Branin-Currin benchmark adds a disk constraint to the underlying problem.
  • DTLZ2: DTLZ2 is evaluated as a synthetic multi-objective benchmark with decision variables constrained to [0, 1]^d.
  • Vehicle Crash Safety: The vehicle crash-safety benchmark uses multiple analytic objective functions over design variables.
  • Policy Optimization for Adaptive Bitrate Control: The adaptive-bitrate-control benchmark optimizes four policy parameters evaluated across 400 video streams.
  • Acquisition-optimization wall time is reported in seconds for CPU and GPU implementations, with means and two standard errors.

F.1 Additional Sequential Optimization Results

Additional experiments evaluate qEHVI on DTLZ2, benchmark problems, noisy Branin-Currin, and approximate hypervolume partitioning. Across these settings, qEHVI generally retains strong optimization performance while computational costs depend on approximation fidelity, batch size, and objective count.

  • DTLZ2: qEHVI outperforms all baseline algorithms on sequential DTLZ2 optimization while maintaining competitive wall times.The experiment uses DTLZ2 with d = 6 and M = 2 objectives.
  • Parallel optimization: qEHVI performance does not degrade substantially across batch BO iterations, unlike qPAREGO and TS-TCH on some benchmark problems.
  • Noisy optimization: qEHVI performs favorably on a noisy Branin-Currin problem with additive zero-mean iid Gaussian observation noise.The noise standard deviation is set to 1% of each objective’s range.
  • Approximate partitioning: Larger approximation levels ζ degrade optimization performance but can provide substantial speedups in qEHVI acquisition optimization.ζ = 0 denotes exact partitioning, and the approximation is evaluated on DTLZ2 with 3 and 4 objectives.
  • Approximate partitioning: Even with coarser hypervolume approximations, qEHVI performs better than qPAREGO on log hypervolume difference.
  • Computation time: Acquisition computation time varies with batch size q and objective count M, while large GPU workloads can encounter memory limitations.The timing study uses 512 MC samples, d = 6, 10 Pareto points, and 20 training points.
Loading 2006.05078v3…