# Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need

arXiv: https://arxiv.org/abs/2402.02111 · HTML: https://mlsanity.com/paper/2402.02111/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 64 references that are in the map.
- First posted on arXiv 3 Feb 2024.

## Builds on (most cited first, 20 of 20)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Survey of multifidelity methods in uncertainty propagation, inference, and optimization](https://mlsanity.com/paper/1806.10761/) (2018)
- [Parallel Bayesian Global Optimization of Expensive Functions](https://mlsanity.com/paper/1602.05149/) (2016)
- [Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees](https://mlsanity.com/paper/2006.15779/) (2020)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [GLASSES: Relieving The Myopia Of Bayesian Optimisation](https://mlsanity.com/paper/1510.06299/) (2015)
- [BINOCULARS for Efficient, Nonmyopic Sequential Experimental Design](https://mlsanity.com/paper/1909.04568/) (2019)
- [Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? A Study via Rollout](https://mlsanity.com/paper/1911.01004/) (2019)
- [Efficient Rollout Strategies for Bayesian Optimization](https://mlsanity.com/paper/2002.10539/) (2020)
- [Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs](https://mlsanity.com/paper/2005.08414/) (2020)
- [Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs](https://mlsanity.com/paper/2111.06537/) (2021)
- [On Russian Roulette Estimates for Bayesian Inference with Doubly-Intractable Likelihoods](https://mlsanity.com/paper/1306.4032/) (2013)
- [Multilevel Monte Carlo Variational Inference](https://mlsanity.com/paper/1902.00468/) (2019)
- [Multilevel Monte Carlo estimation of expected information gains](https://mlsanity.com/paper/1811.07546/) (2018)
- [Two-step Lookahead Bayesian Optimization with Inequality Constraints](https://mlsanity.com/paper/2112.02833/) (2021)
- [Multi-fidelity Monte Carlo: a pseudo-marginal approach](https://mlsanity.com/paper/2210.01534/) (2022)
- [Unbiased Bayes for Big Data: Paths of Partial Posteriors](https://mlsanity.com/paper/1501.03326/) (2015)
- [Recursive Two-Step Lookahead Expected Payoff for Time-Dependent Bayesian Optimization](https://mlsanity.com/paper/2006.08037/) (2020)

## Built on by (most cited first, 4 of 4)

- [Monte Carlo Tree Search based Space Transfer for Black-box Optimization](https://mlsanity.com/paper/2412.07186/) (2024)
- [Nested Expectations with Kernel Quadrature](https://mlsanity.com/paper/2502.18284/) (2025)
- [Multilevel neural simulation-based inference](https://mlsanity.com/paper/2506.06087/) (2025)
- [Generalization and Optimization of SGD with Lookahead](https://mlsanity.com/paper/2509.15776/) (2025)

## Abstract (arXiv)

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 .