Research map / Learning theory and algorithms / Combinatorial and search optimization
Expected Hypervolume Improvement Is a Particular Hypervolume Improvement
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows EHVI equals a particular hypervolume improvement via a coordinate transformation using EI values, yielding NP-hardness proof, faster exact algorithms, and the first analytic expression of qEHVI for q>1.
Problem
Computing expected hypervolume improvement (EHVI) and its batch variant qEHVI for multi-objective Bayesian optimization is expensive and grows exponentially with the number of objectives; no exact analytic method existed for qEHVI with q>1.
Approach
Rewrites EHVI as the hypervolume improvement of a single point after transforming the coordinates with EI values of the Pareto front and reference point; qEHVI is then written as an inclusion-exclusion sum of a constant number of hypervolume improvements using qMinEI.
Key results
- EHVI computed by the proposed formulation matches DBB to relative error below 1e-13, and is hundreds of times faster than DBB and qDBB-MC for m>=7 with n=10.
- Theory gives EHVI and qEHVI an O~(n^{m/3}) time complexity for m>=4, improving on KMAC's O(n^{floor(m/2)}).
- Proves EHVI is #P-hard and cannot be approximated within 2^{m(1-eps)} unless P=NP-type hardness holds (NP-hard).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the hypervolume improvement formulation with QHV-II to compute EHVI | qEHVI-HVI · Random point sets (n=10, m=2) | runtime (EHVI): 0.0027 -> 0.0023 | No clear effect |
| Use the hypervolume improvement formulation with QHV-II to compute EHVI | qEHVI-HVI · Random point sets (n=10, m=4) | runtime (EHVI): 0.058 -> 0.010 | Helped |
| Use the hypervolume improvement formulation with QHV-II to compute EHVI | qEHVI-HVI · Random point sets (n=10, m=7) | runtime (EHVI): 6.98 -> 0.038 | Helped |
| Use the hypervolume improvement formulation with QHV-II to compute EHVI | qEHVI-HVI · Random point sets (n=10, m=2) | relative error (EHVI): 0.2120 -> <2e-14 | Helped |
| Use the hypervolume improvement formulation to compute the EHVI gradient | qEHVI-HVI · Random point sets (n=10, m=4) | runtime (gradient of EHVI): 0.083 -> 0.034 | Helped |
| Use the hypervolume improvement formulation to compute qEHVI | qEHVI-HVI · Random point sets; q = 2 | runtime (qEHVI) | Mixed |
| Use the hypervolume improvement formulation to compute qEHVI | qEHVI-HVI · Random point sets; q = 4 or 6 | runtime (qEHVI) | Mixed |
| Use 128 samples in qDBB-MC | qDBB-MC · Random point sets (n=10), m ≤ 4 | relative approximation error (EHVI): 0.2120; 0.0660; 0.060 | Mixed |
| Use 1280 samples instead of 128 in qDBB-MC | qDBB-MC · Random point sets (n=10) | approximation error (EHVI and gradient) | Helped |
Surprising findings
- qDBB-MC with 128 samples has unstable approximation errors for m<=4, and 128 samples are insufficient for qEHVI approximation.
- For q>=4 the proposed qEHVI method is slow at small m, and only becomes competitive when the number of objectives is large.
Limitations
- qEHVI cost grows with q through multivariate normal CDF evaluations, making it slow for large q at small m.
- Assumes mutually independent objective GPs; correlated objectives not covered.
- Exact HV computation remains #P-hard, so worst-case cost stays exponential in m.
Experimental setup
Datasets: randomly generated point sets (n in 10, 20, 40, 80; m in 2 to 8)
Benchmarks: randomly generated point sets for EHVI and qEHVI computation
Metrics: running time relative error vs exact DBB approximation error of qDBB-MC
Baselines: KMAC DBB qDBB-MC
Builds on: KMAC qEHVI (Monte-Carlo, BoTorch) qEI (Chevalier and Ginsbourger) QHV-II
Closest papers by meaning
- Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization (NeurIPS 2020 · similarity 0.95)
- Probability Distribution of Hypervolume Improvement in Bi-objective Bayesian Optimization (ICML 2024 · similarity 0.92)
- Simple Extensions of Single-Objective Acquisition Functions and Hedge Strategies for Multi-Objective Bayesian Optimization (NeurIPS 2026 · similarity 0.88)
- BOtied: Multi-objective Bayesian optimization with tied multivariate ranks (ICML 2024 · similarity 0.87)
- MOBO-OSD: Batch Multi-Objective Bayesian Optimization via Orthogonal Search Directions (NeurIPS 2025 · similarity 0.87)
- Trading Off Quality and Uncertainty Through Multi-Objective Optimisation in Batch Bayesian Optimisation (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.