BOSS: Bayesian Optimization over String Spaces

• URL: http://arxiv.org/abs/2010.00979v1
• Date: Fri, 2 Oct 2020 13:18:27 GMT
• Title: BOSS: Bayesian Optimization over String Spaces
• Authors: Henry B. Moss, Daniel Beck, Javier Gonzalez, David S. Leslie, Paul Rayson
• Abstract summary: This article develops a Bayesian optimization (BO) method which acts directly over raw strings. It proposes the first uses of string kernels and genetic algorithms within BO loops.
• Score: 15.630421177117634
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This article develops a Bayesian optimization (BO) method which acts directly over raw strings, proposing the first uses of string kernels and genetic algorithms within BO loops. Recent applications of BO over strings have been hindered by the need to map inputs into a smooth and unconstrained latent space. Learning this projection is computationally and data-intensive. Our approach instead builds a powerful Gaussian process surrogate model based on string kernels, naturally supporting variable length inputs, and performs efficient acquisition function maximization for spaces with syntactical constraints. Experiments demonstrate considerably improved optimization over existing approaches across a broad range of constraints, including the popular setting where syntax is governed by a context-free grammar.

Related papers

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment. We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• Sample-efficient Bayesian Optimisation Using Known Invariances [56.34916328814857]
  We show that vanilla and constrained BO algorithms are inefficient when optimising invariant objectives. We derive a bound on the maximum information gain of these invariant kernels. We use our method to design a current drive system for a nuclear fusion reactor, finding a high-performance solution.
  arXiv  Detail & Related papers  (2024-10-22T12:51:46Z)
• Predicting from Strings: Language Model Embeddings for Bayesian Optimization [21.370382766970877]
  We propose Embed-then-Regress, a paradigm for applying in-context regression over string inputs. By expressing all inputs as strings we are able to perform general-purpose regression for Optimization over various domains.
  arXiv  Detail & Related papers  (2024-10-14T06:22:11Z)
• High dimensional Bayesian Optimization via Condensing-Expansion Projection [1.6355174910200032]
  In high-dimensional settings, Bayesian optimization (BO) can be expensive and infeasible. We introduce a novel random projection-based approach for high-dimensional BO that does not reply on the effective subspace assumption. Experimental results demonstrate that both algorithms outperform existing random embedding-based algorithms in most cases.
  arXiv  Detail & Related papers  (2024-08-09T04:47:38Z)
• Reinforced In-Context Black-Box Optimization [64.25546325063272]
  RIBBO is a method to reinforce-learn a BBO algorithm from offline data in an end-to-end fashion. RIBBO employs expressive sequence models to learn the optimization histories produced by multiple behavior algorithms and tasks. Central to our method is to augment the optimization histories with textitregret-to-go tokens, which are designed to represent the performance of an algorithm based on cumulative regret over the future part of the histories.
  arXiv  Detail & Related papers  (2024-02-27T11:32:14Z)
• Voronoi Candidates for Bayesian Optimization [2.7309692684728617]
  Many practical BO methods, particularly in high dimension, eschew a formal, continuous optimization of the acquisition function. We propose to use candidates which lie on the boundary of the Voronoi tessellation of the current design points, so they are equidistant to two or more of them. We discuss strategies for efficient implementation by directly sampling the Voronoi boundary without explicitly generating the tessellation.
  arXiv  Detail & Related papers  (2024-02-07T14:47:13Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces [27.989924313988016]
  We consider the problem of optimizing spaces (e.g., sequences, trees, and graphs) using expensive black-box function evaluations. A recent BO approach for spaces is through a reduction to BO over continuous spaces by learning a latent representation of structures. This paper proposes a principled approach referred as LADDER to overcome this drawback.
  arXiv  Detail & Related papers  (2021-11-01T18:26:22Z)
• LinEasyBO: Scalable Bayesian Optimization Approach for Analog Circuit Synthesis via One-Dimensional Subspaces [11.64233949999656]
  We propose a fast and robust Bayesian optimization approach via one-dimensional subspaces for analog circuit synthesis. Our proposed algorithm can accelerate the optimization procedure by up to 9x and 38x compared to LP-EI and REMBOpBO respectively when the batch size is 15.
  arXiv  Detail & Related papers  (2021-09-01T21:25:25Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces [63.22864716473051]
  We propose a novel BO algorithm which expands (and shifts) the search space over iterations. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates.
  arXiv  Detail & Related papers  (2020-09-05T14:24:40Z)

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.