Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo
  is All you Need
Shangda Yang Vitaly Zankin Maximilian Balandat Stefan Scherer Kevin Carlberg Neil Walton Kody J. H. Law
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. The complexity rate of naive Monte Carlo
degrades for nested operations, whereas MLMC is capable of achieving the
canonical Monte Carlo convergence rate for this type of problem, independently
of dimension and without any smoothness assumptions. Our theoretical study
focuses on the approximation improvements for one- and two-step look-ahead
acquisition functions, but, as we discuss, the approach is generalizable in
various ways, including beyond the context of BO. Findings are verified
numerically and the benefits of MLMC for BO are illustrated on several
benchmark examples. Code is available here
https://github.com/Shangda-Yang/MLMCBO.