Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization
By: Shuhei Watanabe
Hypervolume (HV)-based Bayesian optimization (BO) is one of the standard approaches for multi-objective decision-making. However, the computational cost of optimizing the acquisition function remains a significant bottleneck, primarily due to the expense of HV improvement calculations. While HV box-decomposition offers an efficient way to cope with the frequent exact improvement calculations, it suffers from super-polynomial memory complexity $O(MN^{\lfloor \frac{M + 1}{2} \rfloor})$ in the worst case as proposed by Lacour et al. (2017). To tackle this problem, Couckuyt et al. (2012) employed an approximation algorithm. However, a rigorous algorithmic description is currently absent from the literature. This paper bridges this gap by providing comprehensive mathematical and algorithmic details of this approximation algorithm.
Similar Papers
HiBBO: HiPPO-based Space Consistency for High-dimensional Bayesian Optimisation
Machine Learning (CS)
Finds best answers faster in complex problems.
Scalable Neural Network-based Blackbox Optimization
Machine Learning (CS)
Finds best answers faster, even with many choices.
We Still Don't Understand High-Dimensional Bayesian Optimization
Machine Learning (CS)
Finds best solutions in huge, complex problems.