PaperlayerView exact revision on arXiv

Source-linked AI summary

Combinatorial Bayesian Optimization using the Graph Cartesian Product

Changyong Oh, Jakub M. Tomczak, Efstratios Gavves, Max Welling

arXiv:1902.00448v2stat.MLcs.LG

TL;DR

Combinatorial Bayesian optimization lacks broadly effective methods for ordinal and categorical search spaces with expensive, noisy, nonlinear objectives. COMBO uses a graph Cartesian product and ARD diffusion-kernel Gaussian process with Horseshoe-based variable selection, and it consistently outperforms competitors across evaluated benchmarks while remaining computationally and statistically efficient.

  • Problem

    Bayesian optimization for ordinal and categorical search spaces remains limited despite applications involving expensive, noisy, nonlinear black-box objectives.

  • Method

    COMBO represents joint assignments with a graph Cartesian product and uses an ARD diffusion-kernel Gaussian process with a Horseshoe prior for high-order interaction modeling and variable selection.

  • Results

    COMBO consistently outperforms all competitors across numerical benchmarks, weighted maximum satisfiability, and neural architecture search.

  • Takeaways & Limitations

    COMBO provides a Gaussian-process Bayesian optimization approach for combinatorial problems with complex high-order interactions and rapidly expanding search spaces.

  • Takeaways & Limitations

    BOCS was excluded from ordinal and multi-categorical experiments because its available open-source implementation did not support those variable types at submission time.

Abstract

from arXiv · show

This paper focuses on Bayesian Optimization (BO) for objectives on combinatorial search spaces, including ordinal and categorical variables. Despite the abundance of potential applications of Combinatorial BO, including chipset configuration search and neural architecture search, only a handful of methods have been proposed. We introduce COMBO, a new Gaussian Process (GP) BO. COMBO quantifies "smoothness" of functions on combinatorial search spaces by utilizing a combinatorial graph. The vertex set of the combinatorial graph consists of all possible joint assignments of the variables, while edges are constructed using the graph Cartesian product of the sub-graphs that represent the individual variables. On this combinatorial graph, we propose an ARD diffusion kernel with which the GP is able to model high-order interactions between variables leading to better performance. Moreover, using the Horseshoe prior for the scale parameter in the ARD diffusion kernel results in an effective variable selection procedure, making COMBO suitable for high dimensional problems. Computationally, in COMBO the graph Cartesian product allows the Graph Fourier Transform calculation to scale linearly instead of exponentially. We validate COMBO in a wide array of realistic benchmarks, including weighted maximum satisfiability problems and neural architecture search. COMBO outperforms consistently the latest state-of-the-art while maintaining computational and statistical efficiency.

1 Introduction

Combinatorial Bayesian Optimization targets black-box, expensive, noisy, and nonlinear objectives over ordinal or categorical spaces, where standard approaches face both modeling and computational challenges. COMBO addresses these challenges with graph-based smoothness, scalable Gaussian-process computation, high-order interaction modeling, and variable selection.

  • Motivation: Combinatorial BO targets black-box objectives over ordinal or categorical variables in applications such as chipset configuration, neural architecture, and compiler optimization.These applications involve objectives that are difficult to optimize directly and require efficient search over discrete configurations.
  • Motivation: Black-box, expensive, noisy, and highly nonlinear evaluations make gradient-based, low-sample-efficient, and simple exact optimization methods unsuitable.The motivating applications combine all three difficulties: unavailable gradients, costly evaluations, and complex noisy objectives.
  • Problem: Most Bayesian optimization methods focus on continuous spaces because Gaussian processes rely on kernel-defined smoothness, which is not straightforward to specify for combinatorial functions.Existing kernels on combinatorial structures do not fully resolve the relationship between graph-signal smoothness and function smoothness.
  • Problem: The number of configurations scales as O(k^M) for M categorical variables with k categories, making Gaussian-process BO computationally difficult on combinatorial spaces.The rapidly expanding configuration space compounds the difficulty of covariance computation at successive BO iterations.
  • COMBO: COMBO represents combinatorial choices with a graph Cartesian product and uses a graph-based ARD diffusion kernel to model arbitrarily high-order interactions efficiently.A Horseshoe prior on ARD parameters additionally enables variable selection for high-dimensional problems.
  • Evaluation: COMBO is evaluated on numerical benchmarks, weighted maximum satisfiability, and neural architecture search, consistently outperforming all competitors.The evaluation covers four numerical benchmarks and two realistic test cases.

2 Method

COMBO builds a combinatorial graph from per-variable sub-graphs and applies graph Fourier methods to define Gaussian-process smoothness. Its ARD diffusion kernel models variable-specific structure and supports scalable eigendecomposition through graph Cartesian products.

  • Bayesian optimization: Bayesian optimization iteratively fits a surrogate to observed evaluations and uses an acquisition function to select the next promising point.The process continues until the evaluation budget is exhausted.
  • Bayesian optimization: A Gaussian-process surrogate provides both a predictive mean and a predictive variance for modeling objective values and uncertainty.The predictive quantities are computed from kernel covariances between candidate and observed points.
  • Combinatorial graphs: COMBO constructs one sub-graph per combinatorial variable, using complete graphs for categorical variables and path graphs for ordinal variables.The graph Cartesian product combines these sub-graphs into a graph containing all joint assignments.
  • Combinatorial graphs: The graph Cartesian product connects assignments that differ in one variable, and with complete categorical sub-graphs its shortest-path distance equals Hamming distance.For non-complete sub-graphs, the shortest path is equal to or greater than Hamming distance.
  • Graph kernels: Graph Fourier Transforms represent graph signals using graph Fourier bases, with high-frequency modes corresponding to larger graph-Laplacian eigenvalues.The diffusion kernel penalizes higher frequencies more strongly, encouraging graph-smooth functions.
  • Scalability: The graph Cartesian product reduces Graph Fourier Transform complexity to O(∑_i |V_i|^3) by decomposing the full kernel into Kronecker products of sub-graph kernels.Direct eigendecomposition instead has cubic complexity in the total number of vertices, which is infeasible for rapidly growing combinatorial spaces.
  • ARD diffusion kernel: The ARD diffusion kernel assigns a separate nonnegative scale β_i to each variable, enabling a more flexible kernel and automatic variable selection.The variable-specific scales are combined with a sparsity-inducing Horseshoe prior in COMBO.

3 Related work

Prior combinatorial BO methods use encodings or sparse Bayesian linear regression, but their handling of discrete structure and interaction order limits applicability. COMBO instead uses a graph-based Gaussian-process formulation designed for complex high-order interactions.

  • Existing approaches: Some combinatorial BO methods one-hot encode categorical variables and treat integer variables as real values before rounding acquisition-function outputs.This approach can repeatedly evaluate the same points because of rounding.
  • Existing approaches: BOCS uses sparse Bayesian linear regression with semidefinite programming or simulated annealing to select subsequent evaluations.Its application is mostly restricted to low-order interactions because users must specify the highest interaction order.
  • COMBO: COMBO uses a Gaussian-process surrogate on a combinatorial graph to support complex high-order interactions without requiring a fixed maximum interaction order.This contrasts with the interaction-order limitation described for BOCS.

4 Experiments

COMBO is evaluated across binary, ordinal, multi-categorical, weighted MaxSAT, and neural architecture search benchmarks, generally outperforming competing methods while remaining computationally efficient.

  • 4.1 Bayesian optimization with binary variables 2: COMBO outperforms all competing methods on contamination control, a 21-variable binary problem with approximately 2.10 × 10^6 configurations.The benchmark contains higher-order interactions arising from the sequential structure of the problem.
  • 4.2 Bayesian optimization with ordinal and multi-categorical variables: On non-binary benchmarks, COMBO converges faster and more stably on Branin and outperforms all methods on Pest control.Pest control has 21 stations with 5 choices each, or approximately 4.77 × 10^14 configurations, and uses a budget of 320 evaluations.
  • 4.3 Weighted maximum satisfiability: COMBO performs best on all weighted MaxSAT cases while modeling arbitrarily high-order interactions without BOCS’s rapidly growing parameter count.For 43 binary variables, BOCS uses 13,288, 136,698, or 1,099,296 parameters for third-, fourth-, or fifth-order interactions, respectively.
  • 4.3 Weighted maximum satisfiability: COMBO is faster than BOCS-SA3 and BOCS-SDP while maintaining superior performance on weighted MaxSAT, including the approximately 1.15 × 10^18-configuration wMaxSAT60 problem.BOCS-SA3 required 168 hours to collect around 200 evaluations, whereas BOCS-SDP is restricted to second-order interactions.
  • 4.4 Neural architecture search: On neural architecture search, COMBO significantly outperforms BOCS, random search, and regularized evolution, reaching its performance with 260 evaluations while evolution does not reach it with 500.The comparison reports mean and standard error over 4 runs.

5 Conclusion

COMBO is a Bayesian Optimization method for combinatorial search spaces that combines graph-based smoothness, scalable computation, and flexible variable selection. It consistently outperforms competitors across diverse problems.

  • COMBO represents combinatorial choices with a graph Cartesian product of variable-specific sub-graphs.The graph contains all possible joint assignments as vertices.
  • COMBO uses the Graph Fourier Transform to define function smoothness and an ARD diffusion kernel with Horseshoe priors.These design choices support high-order interactions and variable selection.
  • COMBO consistently outperforms competitors across a wide range of problems while addressing exponentially increasing combinatorial complexity.The paper attributes this to its graph representation, Fourier-based smoothness, flexible kernel, and variable selection.

1 Graph Cartesian product

The graph Cartesian product gives combinatorial search spaces a structured geometry: shortest paths correspond to Hamming distance, while eigendecompositions can be assembled from smaller variable graphs. This makes Graph Fourier Transform calculations substantially more scalable than direct full-graph computation.

  • Graph geometry: For categorical variables, the shortest path in the Cartesian-product graph equals the Hamming distance between assignments.Each edge changes one categorical variable, contributing one unit to the path length.
  • Graph eigensystems: The Cartesian-product Laplacian combines sub-graph Laplacians through Kronecker products and sums.Its eigensystem is obtained by combining sub-graph eigenvalues and eigenvectors.
  • Computational scaling: Graph Fourier Transform computation uses separate sub-graph eigendecompositions instead of directly decomposing the full combinatorial graph.Direct eigendecomposition has cubic complexity in the number of full-graph vertices, whereas the product structure sums the smaller cubic costs.
  • Computational scaling: The Cartesian-product structure makes ARD diffusion-kernel computation efficient using precomputed sub-graph eigensystems.The resulting overhead is described as marginal relative to direct computation.

2 Surrogate model fitting

COMBO fits its Gaussian-process surrogate by posterior sampling over mean, variance, noise, and variable-specific kernel-scale parameters. Slice sampling and Horseshoe priors provide a practical fitting procedure with sparsity-inducing variable selection.

  • Posterior sampling: COMBO samples Gaussian-process parameters from their posterior using slice sampling.The sampled parameters include the mean, signal variance, noise variance, and variable-specific β_i values.
  • ARD diffusion kernel: The ARD diffusion kernel uses sub-graph Laplacian eigenvalues and eigenvectors to construct the Gram matrix.Each variable contributes its own scale parameter β_i.
  • Posterior sampling: The fitting procedure uses warm-up burn-in followed by additional slice-sampling draws at each new evaluation.COMBO uses 100 burn-in steps and generates 10 more samples at every new evaluation.
  • Sparsity and priors: Horseshoe priors on β_i are used for variable selection and encourage sparsity in the surrogate model.The paper motivates these priors as especially important when Bayesian Optimization data are scarce.

3 Acquisition function maximization

COMBO maximizes its acquisition function through a staged search that combines broad random exploration, local spray points, and breadth-first local search. Simulated annealing provided little improvement over the simpler local-search procedure.

  • Candidate initialization: COMBO begins acquisition optimization with 20,000 random exploration vertices and 20 spray vertices near the best evaluated vertex.The 20 highest-acquisition candidates among the initial 20,020 vertices seed further optimization.
  • Local optimization: Breadth-first local search repeatedly moves to the highest-acquisition adjacent vertex until no improving neighbor remains.This searches the combinatorial graph locally from each selected starting point.
  • Search comparison: The best of three simulated-annealing variants was hardly better than breadth-first local search alone.COMBO therefore uses the simpler procedure without simulated annealing.

4 Experiments

The experiments evaluate COMBO on Ising sparsification, contamination control, discretized Branin, and pest control problems spanning binary, ordinal, and categorical variables. Across these settings, the reported results emphasize COMBO’s optimization performance and stability on combinatorial objectives.

  • Ising sparsification: The Ising sparsification experiments use a 4 × 4 grid of spins, random interactions, three regularization values, and a 170-evaluation budget.Exhaustive search would require enumerating 2^24 configurations.
  • Ordinal variables: discretized Branin: The discretized Branin benchmark contains 2 ordinal variables with 51 values each and a 100-evaluation budget.The search space is formed by discretizing the two-dimensional Branin domain into equally spaced grid points.
  • Ordinal variables: discretized Branin: COMBO converges to a better Branin solution faster and with better stability, maintaining its reported performance through 100 evaluations.The comparison includes SMAC, TPE, and SA.
  • Multi-categorical variables: pest control: The pest-control problem has 25 variables with five categories each, while pesticide price and effectiveness change according to previous choices.The objective minimizes both control expense and the portion of products containing pests.

4.3 Weighted maximum satisfiability(wMaxSAT)

The wMaxSAT experiments evaluate COMBO on three weighted maximum satisfiability benchmarks drawn from the 2018 competition. The benchmarks contain no hard clauses, use up to 100 variables, and are transformed into minimization objectives.

  • Benchmark construction: The study selects three weighted MaxSAT benchmarks with no hard clauses and no more than 100 variables.Weights are normalized by mean subtraction and standard deviation division before negation for minimization.
  • Results: The reported benchmark comparisons include SMAC, TPE, SA, BOCS-SDP, BOCS-SA3, and COMBO/GM.The reported objective values differ across the evaluated instances.
  • Benchmark construction: The evaluated instances contain 28, 43, and 60 variables, named maxcut-johnson8-2-4, maxcut-hamming8-2, and frb-frb10-6-4.The benchmarks come from the MaxSAT Competition 2018.
  • Runtime: BOCS-SA3 ran for 168 hours but did not complete 270 evaluations on the 43-variable wMaxSAT instance.The corresponding runtime is plotted as 168 hours.

4.4 Neural architecture search(NAS)

The neural architecture search experiment encodes architectures as a 31-variable binary search space built from cells with fixed states, connectivity choices, and computation types. Architectures are trained on CIFAR10, evaluated using validation error and normalized FLOPs, and compared with evolutionary search.

  • Search-space design: Each NAS cell has input and output states plus five hidden states, with connectivity specified among the seven states.The computation type of each hidden state is determined by two binary choices.
  • Search-space design: The complete NAS search space contains 31 binary variables, and three cells are stacked to construct a network.The binary encoding supports comparison with BOCS, although COMBO is not restricted to binary choices.
  • Evaluation: Architectures are trained for 20 epochs on CIFAR10, with 30,000 training examples and 10,000 evaluation examples after shuffling.Four training runs are used for each architecture to stabilize noisy evaluations.
  • Evaluation: Invalid architectures receive a validation accuracy of 10%, corresponding to constant prediction.This value is used when binary choices produce an invalid architecture.
  • Evaluation: The final evaluation combines validation error with a FLOPs penalty normalized by the maximum FLOPs in the search space.The coefficient 0.02 encodes an assumption about trading increased error for reduced FLOPs.
Loading 1902.00448v2…