Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization

By Sam Daulton, Maximilian Balandat, Eytan Bakshy. Neural Information Processing Systems, 2020

381 citations recorded by the source corpus.

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 existing 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 ($q$EHVI), an acquisition function that extends EHVI to the parallel, constrained evaluation setting. $q$EHVI 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. Lastly, our empirical evaluation demonstrates that $q$EHVI is computationally tractable in many practical scenarios and outperforms state-of-the-art multi-objective BO algorithms at a fraction of their wall time.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/1c55f470a8273788d82f05500d507b408a5722b8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Ganesh Venkatesh
2. M. McCourt
3. Akshat Shrivastava
4. David Eriksson
5. Isabelle M Guyon
6. Zhen Xu
7. Eero Laaksonen
8. Ahmed Aly

In Computational Theory and Mathematics

1. M. McCourt
2. David Eriksson
3. Isabelle M Guyon
4. Zhen Xu
5. Eero Laaksonen
6. Ryan D. Turner
7. J. Kiili
8. Shuhei Watanabe

In Management Science and Operations Research

1. David Eriksson
2. Isabelle M Guyon
3. Ahmed Aly
4. Ryan D. Turner
5. Arun Babu

Citations in the corpus

• Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020 (2021, background): “Additionally, while we only focused on unconstrained single-objective optimization performance, many relevant problems have additional black-box constraints that need to be satisfied or are more naturally phrased as multi-objective optimization problems [12, 13, 21, 32, 40].”
• Latency-Aware Neural Architecture Search with Multi-Objective Bayesian Optimization (2021, background): “…include the expected improvement (EI) with respect to a scalarized objective (Knowles, 2006), expected hypervolume improvement (EHVI) (Emmerich et al., 2006; Daulton et al., 2020), and information gain with respect to the Pareto frontier (Hernandez-Lobato et al., 2016; Suzuki et al., 2020).”