PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Aryan Deshwal, Sebastian Ament, Maximilian Balandat, Eytan Bakshy, Janardhan Rao Doppa, David Eriksson

arXiv:2303.01774v1cs.LGstat.ML

TL;DR

The paper targets sample-efficient optimization of expensive black-box functions over high-dimensional combinatorial spaces, where suitable probabilistic surrogates are needed. It introduces dictionary-based Hamming embeddings for GP modeling, with binary-wavelet and randomized dictionary constructions, and reports strong performance across diverse benchmarks, including improvement over CASMOPOLITAN and COMBO.

  • Problem

    High-dimensional combinatorial and mixed optimization requires accurate probabilistic models and uncertainty estimates despite limited evaluations.

    Source: §1 · p. 1, §2 · p. 2

  • Method

    HED embeds discrete inputs by their Hamming distances to dictionary structures, using binary wavelets for binary spaces and a randomized construction for categorical inputs and arbitrary sizes.

    Source: §1 · pp. 1–2, §4 · p. 4

  • Results

    BODi showed strong performance across diverse problems and outperformed strong baselines such as CASMOPOLITAN and COMBO.

    Source: §1 · p. 2, §8 · p. 9

  • Takeaways & Limitations

    The dictionary kernel is applicable beyond BO to kernel-based methods and can support multi-objective, multi-fidelity, and trust-region optimization.

    Source: §8 · p. 8

    Binary-wavelet construction is nontrivial for non-power-of-two dimensions, so the experiments use sub-sampled columns of power-of-two wavelets in those cases.

    Source: §4 · p. 4

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper addresses sample-efficient modeling and optimization in high-dimensional combinatorial and mixed spaces by introducing dictionary-based embeddings for Gaussian processes. Its theoretical analysis and experiments support compressed search spaces, improved regret bounds, and strong benchmark performance.

1 INTRODUCTION

  • The motivating applications include calibration, AutoML feature selection, microbiome analysis, compiler-flag tuning, and database configuration.These settings involve expensive evaluations and, in some cases, both discrete and continuous parameters.Source: §1 · p. 1
  • HED embeds combinatorial inputs through Hamming distances to dictionary structures, enabling GP kernels with ARD for high-dimensional discrete and mixed spaces.The approach extends to mixed inputs through a product kernel combining HED for discrete variables with a continuous kernel.Source: §1 · p. 1
  • Binary wavelets optimize dictionary orthogonality in power-of-two dimensions, while diverse random dictionaries support categorical inputs and arbitrary dictionary sizes.The two constructions are motivated by the theoretical role of dictionary orthogonality and search-space cardinality.Source: §1 · p. 2
  • BODi outperforms strong baselines including CASMOPOLITAN and COMBO across a diverse set of combinatorial and mixed Bayesian-optimization benchmarks.The evaluation attributes BODi’s strong performance to its dictionary-based surrogate model.Source: §1 · p. 2
  • Compressed input-space cardinality yields improved regret bounds for GP bandits with binary inputs under the paper’s stated conditions.The theoretical analysis also shows data-dependent compression when ARD is used.Source: §1 · p. 2

2 BACKGROUND

The paper formulates Bayesian optimization over large discrete spaces as black-box optimization under limited evaluations. Its central modeling challenge is constructing accurate probabilistic surrogates with useful uncertainty estimates for combinatorial inputs.

Combinatorial and mixed spaces

  • A combinatorial space contains discrete structures represented by d variables, with cardinality equal to the product of their numbers of possible values; binary spaces have size 2^d.Combining the discrete space with a continuous domain forms a mixed space.Source: §2 · p. 2

Problem definition

  • The objective is to approximately optimize a black-box function over a high-dimensional combinatorial space using a small number of function evaluations.A binary feature-selection problem is given as an example.Source: §2 · p. 2

Bayesian optimization

  • Bayesian optimization fits a probabilistic surrogate from previous evaluations and selects new inputs by maximizing an acquisition function over the surrogate posterior.For high-dimensional combinatorial spaces, building an accurate surrogate is identified as the central challenge.Source: §2 · p. 2

Gaussian processes

  • Gaussian processes provide flexible probabilistic models with uncertainty quantification through a mean function and covariance kernel.ARD lengthscales allow relevance to vary across input dimensions in the standard continuous formulation.Source: §2 · p. 2

3 RELATED WORK

Prior work offers diverse surrogate models and embeddings for discrete, mixed, and continuous optimization, but high-dimensional combinatorial spaces remain comparatively underexplored. The paper positions BODi as an approach designed for this setting and reports improvement over CASMOPOLITAN.

Discrete and mixed spaces

  • Existing discrete-space approaches include Bayesian linear regression, diffusion-kernel GPs, continuous embeddings, latent-space BO, random forests, and density estimators.The cited methods differ in scalability, representation, and surrogate assumptions.Source: §3 · p. 3
  • BOCS can scale poorly with input dimension, while continuous-embedding methods may require reconstructing discrete inputs after acquisition optimization.The paper contrasts these properties with its dictionary-based embeddings.Source: §3 · p. 3

High-dimensional continuous spaces

  • Many methods for high-dimensional continuous BO rely on low-dimensional structure, additivity, or trust-region and line-search strategies.These methods are presented as categories of related continuous-space approaches.Source: §3 · p. 3
  • High-dimensional combinatorial and mixed search spaces remain less studied than continuous spaces, despite arising in many real-world applications.CASMOPOLITAN is identified as an exception using adaptive Hamming-distance trust regions.Source: §3 · p. 3
  • The paper reports that BODi and its dictionary-based kernel improve over CASMOPOLITAN in the high-dimensional setting.Source: §3 · p. 3

4 DICTIONARY EMBEDDINGS

HED embeds high-dimensional binary or categorical inputs by their Hamming distances to a fixed dictionary, enabling GP modeling in an ordinal feature space. Dictionary construction controls modeling flexibility: binary wavelets perform well in suitable dimensions, while diverse random dictionaries extend construction across arbitrary dimensions and categorical inputs.

Hamming embedding via dictionaries

  • HED maps each input to its Hamming distances from m dictionary structures, producing an ordinal embedding for GP modeling.The embedding has one feature per dictionary element, with [φA(z)]i = h(ai, z).Source: §4 · p. 3
  • ARD on the embedding can prune redundant dimensions, reducing search-space cardinality and improving the theoretical sample-efficiency of GP bandits.The embedding also supports GP kernels developed for continuous spaces and extends to mixed inputs through a product kernel.Source: §4 · pp. 3, 5

Dictionary construction

  • Uniformly random dictionaries show poor predictive performance on the 60-variable MaxSAT problem, whereas sub-sampled binary wavelet dictionaries perform well.Figure 2 compares mean predictions and 95% predictive intervals using 50 training and 50 test points.Source: §4 · p. 4, Figure 2 · p. 4
  • Binary wavelet construction is difficult for non-power-of-two dimensions, so the experiments sub-sample columns from power-of-two wavelets in those cases.The existence of suitable binary wavelets for arbitrary dimensions remains an open problem.Source: §4 · p. 4
  • The diverse-random procedure varies Bernoulli bias parameters across dictionary rows, creating a broad range of sparsity levels instead of concentrating near d/2 nonzeros.This construction generalizes to categorical inputs and can produce dictionaries of arbitrary size and dimension.Source: §4 · pp. 4–5

5 BODi: BAYESIAN OPTIMIZATION WITH DICTIONARY EMBEDDINGS

BODi fits a Matérn-5/2 GP with ARD on the HED embedding and selects evaluations by optimizing Expected Improvement over the discrete search space. For mixed spaces, it alternates local search over discrete variables with gradient-based optimization over continuous variables.

BODi algorithm

  • BODi uses a Matérn-5/2 GP with ARD on HED and Expected Improvement to choose evaluations in the discrete space.Acquisition optimization uses local search from randomly generated initial conditions.Source: §5 · p. 5
  • Each BO iteration constructs a dictionary, embeds the training inputs, refits the GP, optimizes the acquisition function, evaluates the selected structure, and updates the data.The process repeats until the query budget is exhausted, returning the best input found.Source: §5 · p. 5

Mixed-space optimization

  • For mixed search spaces, BODi alternates search over continuous and discrete subspaces, using local search for discrete parameters and gradient-based optimization for continuous parameters.This is presented as a common approach for BO over mixed spaces.Source: §5 · p. 5

6 THEORETICAL ANALYSIS OF BODi

Theoretical analysis shows that dictionary-based Hamming embeddings can compress the cardinality of binary search spaces, improving GP-bandit regret bounds while balancing computational simplicity against model expressiveness.

6 THEORETICAL ANALYSIS OF BODi

  • Dictionary-based embeddings can reduce binary search-space cardinality and thereby improve GP-bandit regret bounds under stated conditions.The improvement depends on compressed cardinality rather than merely reduced embedding dimensionality.Source: §6 · pp. 5–7
  • The Hamming embedding is equivalent to an affine transformation of ±1-encoded inputs and, for the wavelet dictionary, to a shifted sub-sampled Hadamard transform.The embedded distance depends on a linear projection of the difference between encoded binary inputs.Source: §6 · pp. 5–6
  • Unlike Gaussian random projections, the dictionary construction can reduce embedded-space cardinality, whereas even one-dimensional Gaussian projections preserve the full binary cardinality almost surely.This distinction explains why dimensionality reduction alone does not guarantee the cardinality reduction needed for finite-space BO bounds.Source: §6 · p. 6
  • The embedding-cardinality bound depends on dictionary-row variability µA and grows polynomially with d rather than exponentially under the stated construction.The binary wavelet dictionary achieves the lowest possible coherence d/2 in power-of-two dimensions, while duplicate dictionary elements yield µA=d.Source: §6 · p. 6
  • ARD can prune redundant dictionary dimensions, allowing larger dictionaries to preserve modeling flexibility while reducing the effective search-space complexity.The paper notes that larger embedding dimensions tend to improve performance and that ARD removes most embedding dimensions.Source: §6 · p. 7

7 EXPERIMENTS

Experiments evaluate BODi across combinatorial, categorical, mixed, and ablation settings, finding consistently strong optimization and predictive performance against established BO baselines.

7.1 Combinatorial test problems

  • BODi finds significantly better LABS solutions than the baselines and substantially outperforms them on the pest-control problem, reaching an objective value around ≈12.On weighted MaxSAT, BODi quickly finds a close-to-optimal solution in a space of up to 2^60 configurations.Source: §7.1 · pp. 7–8
  • BODi consistently performs best among the compared methods on three high-dimensional combinatorial test problems.The comparison includes CASMOPOLITAN, COMBO, SMAC, and random search.Source: Figure 3 · p. 8

7.2 Model performance

  • HED with diverse random dictionary elements gives accurate predictions, while overlap, diffusion, and Gaussian-random dictionaries perform poorly on the evaluated MaxSAT task.With m = 128, ARD assigns lengthscale below 10 to only 4 dictionary elements, pruning most dimensions.Source: §7.2 · p. 8

7.3 Mixed test problems

  • On mixed Ackley with 50 binary and 3 continuous variables, BODi quickly approaches the global optimum of 0, while most baselines perform poorly.The subsampled binary wavelet dictionary also performs particularly well on this problem.Source: §7.3 · p. 8
  • BODi performs slightly better than CASMOPOLITAN for joint feature selection and SVM hyperparameter optimization on the UCI slice dataset.The task optimizes inclusion of 50 features together with the C, ϵ, and γ hyperparameters to minimize held-out RMSE.Source: §7.3 · p. 8

7.4 Ablation study

  • Dictionary sizes m = 128 and m = 256 perform best in the LABS ablation, while m = 16 or m = 32 performs worse and larger dictionaries increase runtime.The experiments therefore use m = 128 as a performance-runtime compromise.Source: §7.4 · p. 8

8 DISCUSSION

The discussion presents BODi’s dictionary kernel as broadly applicable beyond Bayesian optimization and reports strong performance across diverse problems. It also identifies single-objective evaluation and dictionary design as limitations and opportunities for further work.

  • BODi’s dictionary kernel is suitable for high-dimensional combinatorial and mixed search spaces and can be used beyond Bayesian optimization.The approach is described as relevant to kernel-based methods more generally.Source: §8 · p. 8
  • The kernel is agnostic to acquisition-function choice, supporting extensions to multi-objective, multi-fidelity, and trust-region optimization.Source: §8 · p. 8
  • BODi showed strong performance across diverse problems and outperformed strong baselines including CASMOPOLITAN and COMBO.Source: §8 · p. 9
  • The evaluation covered only single-objective problems, leaving multi-objective performance untested.Source: §8 · p. 9
  • Future work could optimize dictionaries during model fitting, use historical data, or design dictionaries specifically for locating optima rather than globally accurate modeling.Source: §8 · p. 9

A Affine Representation of the Hamming Embedding

The affine representation shows that Hamming embeddings of binary vectors can be expressed through transformed ±1 encodings. This connects the dictionary embedding to linear projections, RBF-style kernels, and efficient Hadamard-transform computation.

B Search Space Cardinality Reduction

The analysis bounds the cardinality of the dictionary-embedded search space and uses that bound to derive improved Bayesian-optimization regret guarantees. It shows why generic random projections may preserve the full binary search-space cardinality.

C Dictionary Construction Approach via Binary Wavelets

The paper develops binary-wavelet and diverse-parameter dictionaries, then uses local search to optimize acquisition functions over combinatorial inputs. Experiments report robust dictionary choices, sub-10-second iteration times, and a categorical extension.

C Dictionary Construction Approach via Binary Wavelets

  • C Dictionary Construction Approach via Binary Wavelets: Binary-wavelet dictionaries sample diverse basis vectors spanning a range of sequencies.Sequency counts transitions between 0 and 1, analogous to frequency in Fourier analysis.Source: C Dictionary Construction Approach via… · p. 15
  • C Dictionary Construction Approach via Binary Wavelets: The binary-wavelet dictionary corresponds to a subsampled randomized Hadamard transform and minimizes the coherence-like measure µA.Source: C Dictionary Construction Approach via… · p. 15

D Local Search for Optimizing Acquisition Function over Combinatorial Spaces

  • D Local Search for Optimizing Acquisition Function over Combinatorial Spaces: BODi starts from random and spray candidates, greedily climbs one-Hamming-distance neighbors, and evaluates the best trajectory endpoint.Source: D Local Search for Optimizing… · p. 16

E Runtimes

  • E Runtimes: On a 60-variable MaxSAT problem, BODi and CASMOPOLITAN each average less than 10 seconds per BO iteration and are significantly faster than COMBO.Source: E Runtimes · p. 17

F Societal Impact

  • F Societal Impact: The authors describe BODi’s intended benefit as better optimization or comparable models with fewer computational resources, while noting minimal additional risk.Source: F Societal Impact · p. 17

G Dictionary construction for dictionaries with binary and categorical variables

Related papers

Loading 2303.01774v1…