Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation

• URL: http://arxiv.org/abs/2410.16893v1
• Date: Tue, 22 Oct 2024 10:56:52 GMT
• Title: Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation
• Authors: Yilin Xie, Shiqiang Zhang, Joel Paulson, Calvin Tsay,
• Abstract summary: We introduce a piecewise approximation for process kernels and a corresponding MIQP representation for acquisition functions. We empirically demonstrate the framework on synthetic functions, constrained benchmarks, and hyper tuning tasks.
• Score: 2.3342885570554652
• License:
• Abstract: Bayesian optimization relies on iteratively constructing and optimizing an acquisition function. The latter turns out to be a challenging, non-convex optimization problem itself. Despite the relative importance of this step, most algorithms employ sampling- or gradient-based methods, which do not provably converge to global optima. This work investigates mixed-integer programming (MIP) as a paradigm for \textit{global} acquisition function optimization. Specifically, our Piecewise-linear Kernel Mixed Integer Quadratic Programming (PK-MIQP) formulation introduces a piecewise-linear approximation for Gaussian process kernels and admits a corresponding MIQP representation for acquisition functions. We analyze the theoretical regret bounds of the proposed approximation, and empirically demonstrate the framework on synthetic functions, constrained benchmarks, and a hyperparameter tuning task.

Related papers

• 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)
• ProGO: Probabilistic Global Optimizer [9.772380490791635]
  In this paper we develop an algorithm that converges to the global optima under some mild conditions. We show that the proposed algorithm outperforms, by order of magnitude, many existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-10-04T22:23:40Z)
• Extrinsic Bayesian Optimizations on Manifolds [1.3477333339913569]
  We propose an extrinsic Bayesian optimization (eBO) framework for general optimization problems on Euclid manifold. Our approach is to employ extrinsic Gaussian processes by first embedding the manifold onto some higher dimensionalean space. This leads to efficient and scalable algorithms for optimization over complex manifold.
  arXiv  Detail & Related papers  (2022-12-21T06:10:12Z)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  We study the effectiveness of various ZO optimization methods for optimizing molecular objectives. We show the advantages of ZO sign-based gradient descent (ZO-signGD) We demonstrate the potential effectiveness of ZO optimization methods on widely used benchmark tasks from the Guacamol suite.
  arXiv  Detail & Related papers  (2022-10-27T01:58:10Z)
• Surrogate modeling for Bayesian optimization beyond a single Gaussian process [62.294228304646516]
  We propose a novel Bayesian surrogate model to balance exploration with exploitation of the search space. To endow function sampling with scalability, random feature-based kernel approximation is leveraged per GP model. To further establish convergence of the proposed EGP-TS to the global optimum, analysis is conducted based on the notion of Bayesian regret.
  arXiv  Detail & Related papers  (2022-05-27T16:43:10Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  We consider potentially non- optimized approximation problems. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
  arXiv  Detail & Related papers  (2022-04-11T09:37:04Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds [9.632674803757475]
  We propose a scheme for solving convex and non- optimization problems on distance. Our proposed algorithm adapts to the level of complexity in the objective function.
  arXiv  Detail & Related papers  (2020-10-18T02:48:22Z)
• 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)
• 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)

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.