Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need
This work addresses a computational bottleneck in Bayesian optimization for researchers and practitioners, offering an incremental improvement in efficiency for nested operations.
The paper tackles the computational inefficiency of multi-step look-ahead Bayesian optimization methods by applying multilevel Monte Carlo (MLMC) to handle nested expectations, achieving the canonical Monte Carlo convergence rate independently of dimension and without smoothness assumptions, as verified numerically on benchmark examples.
We leverage multilevel Monte Carlo (MLMC) to improve the performance of multi-step look-ahead Bayesian optimization (BO) methods that involve nested expectations and maximizations. Often these expectations must be computed by Monte Carlo (MC). The complexity rate of naive MC degrades for nested operations, whereas MLMC is capable of achieving the canonical MC convergence rate for this type of problem, independently of dimension and without any smoothness assumptions. Our theoretical study focuses on the approximation improvements for twoand three-step look-ahead acquisition functions, but, as we discuss, the approach is generalizable in various ways, including beyond the context of BO. Our findings are verified numerically and the benefits of MLMC for BO are illustrated on several benchmark examples. Code is available at https://github.com/Shangda-Yang/MLMCBO .