Improving sample efficiency of high dimensional Bayesian optimization with MCMC

• URL: http://arxiv.org/abs/2401.02650v1
• Date: Fri, 5 Jan 2024 05:56:42 GMT
• Title: Improving sample efficiency of high dimensional Bayesian optimization with MCMC
• Authors: Zeji Yi, Yunyue Wei, Chu Xin Cheng, Kaibo He, and Yanan Sui
• Abstract summary: We propose a new method based on Markov Chain Monte Carlo to efficiently sample from an approximated posterior. We show experimentally that both the Metropolis-Hastings and the Langevin Dynamics version of our algorithm outperform state-of-the-art methods in high-dimensional sequential optimization and reinforcement learning benchmarks.
• Score: 7.241485121318798
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sequential optimization methods are often confronted with the curse of dimensionality in high-dimensional spaces. Current approaches under the Gaussian process framework are still burdened by the computational complexity of tracking Gaussian process posteriors and need to partition the optimization problem into small regions to ensure exploration or assume an underlying low-dimensional structure. With the idea of transiting the candidate points towards more promising positions, we propose a new method based on Markov Chain Monte Carlo to efficiently sample from an approximated posterior. We provide theoretical guarantees of its convergence in the Gaussian process Thompson sampling setting. We also show experimentally that both the Metropolis-Hastings and the Langevin Dynamics version of our algorithm outperform state-of-the-art methods in high-dimensional sequential optimization and reinforcement learning benchmarks.

Related papers

• An Adaptive Dimension Reduction Estimation Method for High-dimensional Bayesian Optimization [6.79843988450982]
  We propose a two-step optimization framework to extend BO to high-dimensional settings. Our algorithm offers the flexibility to operate these steps either concurrently or in sequence. Numerical experiments validate the efficacy of our method in challenging scenarios.
  arXiv  Detail & Related papers  (2024-03-08T16:21:08Z)
• Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration [2.984929040246293]
  novel noise-free Bayesian optimization strategies that rely on a random exploration step to enhance the accuracy of Gaussian process surrogate models. New algorithms retain the ease of implementation of the classical GP-UCB, but an additional exploration step facilitates their convergence.
  arXiv  Detail & Related papers  (2024-01-30T14:16:06Z)
• A Particle-based Sparse Gaussian Process Optimizer [5.672919245950197]
  We present a new swarm-swarm-based framework utilizing the underlying dynamical process of descent. The biggest advantage of this approach is greater exploration around the current state before deciding descent descent.
  arXiv  Detail & Related papers  (2022-11-26T09:06:15Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• High dimensional Bayesian Optimization Algorithm for Complex System in Time Series [1.9371782627708491]
  This paper presents a novel high dimensional Bayesian optimization algorithm. Based on the time-dependent or dimension-dependent characteristics of the model, the proposed algorithm can reduce the dimension evenly. To increase the final accuracy of the optimal solution, the proposed algorithm adds a local search based on a series of Adam-based steps at the final stage.
  arXiv  Detail & Related papers  (2021-08-04T21:21:17Z)
• High-Dimensional Simulation Optimization via Brownian Fields and Sparse Grids [14.15772050249329]
  High-dimensional simulation optimization is notoriously challenging. We propose a new sampling algorithm that converges to a global optimal solution. We show that the proposed algorithm dramatically outperforms typical alternatives in practice.
  arXiv  Detail & Related papers  (2021-07-19T03:03:27Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  Our algorithm generates a sequence of finite-dimensional random subspaces of functional space spanned by a set of draws from the experimenter's Gaussian Process. Standard Bayesian optimisation is applied on each subspace, and the best solution found used as a starting point (origin) for the next subspace. We test our algorithm in simulated and real-world experiments, namely blind function matching, finding the optimal precipitation-strengthening function for an aluminium alloy, and learning rate schedule optimisation for deep networks.
  arXiv  Detail & Related papers  (2020-09-08T06:54:11Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  We propose a reduced-space formulation with trained Gaussian processes trained on few data points. The approach also leads to significantly smaller and computationally cheaper sub solver for lower bounding. In total, we reduce time convergence by orders of orders of the proposed method.
  arXiv  Detail & Related papers  (2020-05-21T20:59:11Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck. We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian. We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
  arXiv  Detail & Related papers  (2020-02-16T09:01:18Z)

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.