Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings

• URL: http://arxiv.org/abs/2303.01774v1
• Date: Fri, 3 Mar 2023 08:31:42 GMT
• Title: Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings
• Authors: Aryan Deshwal, Sebastian Ament, Maximilian Balandat, Eytan Bakshy, Janardhan Rao Doppa, David Eriksson
• Abstract summary: We consider the problem of optimizing black-box functions over high-dimensional spaces in science, engineering, and ML applications. Key idea is to select a number of discrete structures from the input space and use them to define an ordinal embedding for high-dimensional structures. We develop a principled approach based on binary wavelets to construct dictionaries for binary spaces, and propose a randomized construction method that generalizes to categorical spaces.
• Score: 36.60636056219264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of optimizing expensive black-box functions over high-dimensional combinatorial spaces which arises in many science, engineering, and ML applications. We use Bayesian Optimization (BO) and propose a novel surrogate modeling approach for efficiently handling a large number of binary and categorical parameters. The key idea is to select a number of discrete structures from the input space (the dictionary) and use them to define an ordinal embedding for high-dimensional combinatorial structures. This allows us to use existing Gaussian process models for continuous spaces. We develop a principled approach based on binary wavelets to construct dictionaries for binary spaces, and propose a randomized construction method that generalizes to categorical spaces. We provide theoretical justification to support the effectiveness of the dictionary-based embeddings. Our experiments on diverse real-world benchmarks demonstrate the effectiveness of our proposed surrogate modeling approach over state-of-the-art BO methods.

Related papers

• Diffusion Model for Data-Driven Black-Box Optimization [54.25693582870226]
  We focus on diffusion models, a powerful generative AI technology, and investigate their potential for black-box optimization. We study two practical types of labels: 1) noisy measurements of a real-valued reward function and 2) human preference based on pairwise comparisons. Our proposed method reformulates the design optimization problem into a conditional sampling problem, which allows us to leverage the power of diffusion models.
  arXiv  Detail & Related papers  (2024-03-20T00:41:12Z)
• 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)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• 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)
• High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces [14.03847432040056]
  We argue that a surrogate model defined on sparse axis-aligned subspaces offer an attractive compromise between flexibility and parsimony. We demonstrate that our approach, which relies on Hamiltonian Monte Carlo for inference, can rapidly identify sparse subspaces relevant to modeling the unknown objective function.
  arXiv  Detail & Related papers  (2021-02-27T23:06:24Z)
• Combinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytopes [43.19936635161588]
  We present a method for Bayesian optimization in a space which can operate well in a large space. Our algorithm shows satisfactory performance compared to existing methods.
  arXiv  Detail & Related papers  (2020-11-26T02:22:41Z)
• High-Dimensional Bayesian Optimization via Nested Riemannian Manifolds [0.0]
  We propose to exploit the geometry of non-Euclidean search spaces, which often arise in a variety of domains, to learn structure-preserving mappings. Our approach features geometry-aware Gaussian processes that jointly learn a nested-manifold embedding and a representation of the objective function in the latent space.
  arXiv  Detail & Related papers  (2020-10-21T11:24:11Z)
• BOSS: Bayesian Optimization over String Spaces [15.630421177117634]
  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.
  arXiv  Detail & Related papers  (2020-10-02T13:18:27Z)
• 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)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  We study clustering methods for binary data, first defining aggregation criteria that measure the compactness of clusters. Five new and original methods are introduced, using neighborhoods and population behavior optimization metaheuristics. From a set of 16 data tables generated by a quasi-Monte Carlo experiment, a comparison is performed for one of the aggregations using L1 dissimilarity, with hierarchical clustering, and a version of k-means: partitioning around medoids or PAM.
  arXiv  Detail & Related papers  (2020-01-06T23:33:31Z)

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.