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

• URL: http://arxiv.org/abs/2402.02111v2
• Date: Tue, 25 Jun 2024 13:11:33 GMT
• Title: Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need
• Authors: Shangda Yang, Vitaly Zankin, Maximilian Balandat, Stefan Scherer, Kevin Carlberg, Neil Walton, Kody J. H. Law,
• Abstract summary: Multilevel Monte Carlo (MLCBOC) is capable of achieving the canonical MC convergence rate. Our theoretical study focuses on the approximation improvements for twoand three-step look-ahead acquisition functions. Our findings are verified numerically and the benefits ofCBOC for BO are illustrated on several benchmark examples.
• Score: 5.283807323380133
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 .

Related papers

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Learning to Explore for Stochastic Gradient MCMC [15.286308920219446]
  We propose a meta-learning strategy to build glssgmcmc which can efficiently explore the multi-modal target distributions. Our algorithm allows the learned SGMCMC to quickly explore the high-density region of the posterior landscape.
  arXiv  Detail & Related papers  (2024-08-17T08:36:42Z)
• Large Language Models to Enhance Bayesian Optimization [57.474613739645605]
  We present LLAMBO, a novel approach that integrates the capabilities of Large Language Models (LLM) within Bayesian optimization. At a high level, we frame the BO problem in natural language, enabling LLMs to iteratively propose and evaluate promising solutions conditioned on historical evaluations. Our findings illustrate that LLAMBO is effective at zero-shot warmstarting, and enhances surrogate modeling and candidate sampling, especially in the early stages of search when observations are sparse.
  arXiv  Detail & Related papers  (2024-02-06T11:44:06Z)
• Reverse Diffusion Monte Carlo [19.35592726471155]
  We propose a novel Monte Carlo sampling algorithm called reverse diffusion Monte Carlo (rdMC) rdMC is distinct from the Markov chain Monte Carlo (MCMC) methods.
  arXiv  Detail & Related papers  (2023-07-05T05:42:03Z)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  We propose a replacement of the Markov Chain Monte Carlo (MCMC) with an inherently parallel algorithm, the Sequential Monte Carlo (SMC) Experiments show that SMC combined with the Evolutionary Algorithms (EA) can produce more accurate results compared to MCMC in 100 times fewer iterations.
  arXiv  Detail & Related papers  (2023-05-30T06:17:35Z)
• Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processes [8.198195852439946]
  We study preferential Bayesian optimization (BO) where reliable feedback is limited to pairwise comparison called duels. An important challenge in preferential BO, which uses the preferential Gaussian process (GP) model to represent flexible preference structure, is that the posterior distribution is a computationally intractable skew GP. We develop a new method that achieves both high computational efficiency and low sample complexity, and then demonstrate its effectiveness through extensive numerical experiments.
  arXiv  Detail & Related papers  (2023-02-03T03:02:38Z)
• Parallel Approaches to Accelerate Bayesian Decision Trees [1.9728521995447947]
  We propose two methods for exploiting parallelism in the MCMC. In the first, we replace the MCMC with another numerical Bayesian approach. In the second, we consider data partitioning.
  arXiv  Detail & Related papers  (2023-01-22T09:56:26Z)
• Low-variance estimation in the Plackett-Luce model via quasi-Monte Carlo sampling [58.14878401145309]
  We develop a novel approach to producing more sample-efficient estimators of expectations in the PL model. We illustrate our findings both theoretically and empirically using real-world recommendation data from Amazon Music and the Yahoo learning-to-rank challenge.
  arXiv  Detail & Related papers  (2022-05-12T11:15:47Z)
• Continual Repeated Annealed Flow Transport Monte Carlo [93.98285297760671]
  We propose Continual Repeated Annealed Flow Transport Monte Carlo (CRAFT) It combines a sequential Monte Carlo sampler with variational inference using normalizing flows. We show that CRAFT can achieve impressively accurate results on a lattice field example.
  arXiv  Detail & Related papers  (2022-01-31T10:58:31Z)
• Variational Combinatorial Sequential Monte Carlo Methods for Bayesian Phylogenetic Inference [4.339931151475307]
  We introduce Vari Combinatorial Monte Carlo (VCSMC), a powerful framework that establishes variational search to learn over intricate structures. We show that VCSMC and CSMC are efficient and explore higher probability spaces than existing methods on a range of tasks.
  arXiv  Detail & Related papers  (2021-05-31T19:44:24Z)
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning [63.64636047748605]
  We develop a new theoretical framework to provide convergence guarantee for the general multi-step MAML algorithm. In particular, our results suggest that an inner-stage step needs to be chosen inversely proportional to $N$ of inner-stage steps in order for $N$ MAML to have guaranteed convergence.
  arXiv  Detail & Related papers  (2020-02-18T19:17:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.