Source-linked AI summary
Bayesian Optimization of Combinatorial Structures
Ricardo Baptista, Matthias Poloczek
TL;DR
The paper addresses expensive black-box optimization over combinatorial structures, where combinatorial explosion and costly evaluations challenge existing methods. It proposes BOCS, combining an adaptive model of structural interactions with a scalable acquisition procedure based on semidefinite programming, and reports that BOCS outperforms state-of-the-art methods across evaluated problems.
Problem
Expensive black-box optimization over combinatorial structures is important across applications, but combinatorial search spaces and costly evaluations challenge existing optimization methods.
Method
BOCS uses an interpretable model of interactions among structural elements, restricted in practice to second-order terms, together with an acquisition procedure that uses semidefinite programming for scalable optimization.
Results
BOCS outperforms state-of-the-art methods from combinatorial optimization and machine learning across the paper's evaluated benchmark problems.
Takeaways & Limitations
The proposed approach provides a scalable and sample-efficient algorithm for optimizing expensive black-box functions over combinatorial structures.
Takeaways & Limitations
The quadratic-form acquisition problem is computationally hard, and the paper identifies efficient optimization of other acquisition criteria and tailored models as future work.
Abstract
from arXiv · showhide
The optimization of expensive-to-evaluate black-box functions over combinatorial structures is an ubiquitous task in machine learning, engineering and the natural sciences. The combinatorial explosion of the search space and costly evaluations pose challenges for current techniques in discrete optimization and machine learning, and critically require new algorithmic ideas. This article proposes, to the best of our knowledge, the first algorithm to overcome these challenges, based on an adaptive, scalable model that identifies useful combinatorial structure even when data is scarce. Our acquisition function pioneers the use of semidefinite programming to achieve efficiency and scalability. Experimental evaluations demonstrate that this algorithm consistently outperforms other methods from combinatorial and Bayesian optimization.
1. Introduction
The paper introduces BOCS for expensive black-box optimization over combinatorial structures, targeting scalability and sample efficiency where existing methods face domain and evaluation-cost challenges.
- BOCS addresses expensive black-box optimization over combinatorial structures arising in machine learning, engineering, and natural sciences.Applications include image object location, drug discovery, solver hyper-parameter cross-validation, food safety control, model sparsification, and bike-station placement.
- BOCS is designed to tame combinatorial search-space explosion while improving sample efficiency over existing methods.
- Its acquisition-function optimizer uses convex-optimization ideas to improve scalability and efficiency in large combinatorial domains.
- The model captures interactions among structural elements and infers them when data is expensive and scarce.The paper also demonstrates the model's interpretability on experimental data.
- The evaluation compares BOCS with machine-learning and discrete-optimization methods across benchmarks in machine learning, aerospace engineering, and food safety control.
- Related Work: Prior Bayesian-optimization methods mainly target box-constrained or specially structured continuous domains, while structured combinatorial domains have received little attention.Existing categorical approaches trade off dimensionality or use random forests and local search to handle higher-dimensional problems.
2. Problem Formulation
The problem is to find a global optimizer of an expensive black-box function over a discrete structured domain, with observations modeled as noisy evaluations.
- The objective is to find a global optimizer argmax_x∈D f(x) over a discrete structured domain D.
- Each evaluation provides an independent, conditionally normally distributed observation with mean f(x) and finite variance σ2.
- The paper focuses on binary domains D = {0, 1}^d, where x_i indicates whether a design element is present.Examples include bike-station locations, chemical side-chains, component couplings, and graph edges.
3. The BOCS Algorithm
BOCS combines an interaction-aware sparse Bayesian model with Thompson-sampling-style acquisition and semidefinite-programming relaxations to optimize expensive black-box functions over combinatorial domains. It iteratively samples model coefficients, approximately solves the resulting binary quadratic program, evaluates the selected design, and updates its posterior.
- 3.1. Statistical Model: BOCS models combinatorial objective functions with interaction terms while restricting monomial order to control the exponential model size.Second-order models provide an empirical trade-off between expressiveness and prediction accuracy when data is limited.
- 3.1. Statistical Model: A sparsity-inducing horseshoe prior shrinks regression coefficients to support inference when second-order models have Θ(d2) coefficients and evaluations are scarce.Posterior sampling uses an exact algorithm with complexity O(N 2p), nearly linear in p when N ≪ p.
- 3.2. Acquisition Function: BOCS samples coefficients from their posterior and uses the resulting model to select the next point, preserving uncertainty-driven exploration rather than relying only on maximum-likelihood estimates.The acquisition step is inspired by Thompson sampling and optimizes a regularized sampled objective.
- 3.2. Acquisition Function: BOCS converts the sampled binary quadratic program into a semidefinite relaxation, solves it to a prescribed precision, and rounds the solution back to a feasible binary design.The relaxation replaces binary variables with vectors on a unit sphere before randomized geometric rounding recovers a hypercube solution.
- 3.3. BOCS Algorithm: Each iteration samples posterior coefficients, approximately optimizes the regularized model, evaluates the selected point, and updates the posterior until the sample budget is exhausted.This procedure starts from an initial dataset and returns the best observed or modeled feasible design according to the algorithmic loop.
- 3.4. BOCS-SA: A Low-Complexity Variant of BOCS: BOCS-SA replaces semidefinite programming with stochastic local search, while BOCS-SDP has per-iteration running time bounded by O(N 2d2 + poly(d, 1.The paper reports that the semidefinite-program solver takes only a few seconds in the evaluated setting and is expected to scale to a few hundred dimensions.
4. Numerical Results
Across four combinatorial benchmarks, BOCS variants generally achieve strong performance, with BOCS-SDP leading on binary quadratic programming, Ising sparsification, and contamination control, while aero-structural results are more closely matched.
- Benchmark setup: The evaluation covers binary quadratic programming, Ising-model sparsification, contamination control, and aero-structural complexity reduction, alongside Bayesian and discrete-optimization baselines.The first three problems use repeated evaluations and shared initial datasets for BOCS and EI; reported results use averages with uncertainty intervals.
- Binary quadratic programming: Both BOCS variants significantly outperform competitors on random binary quadratic programming instances with Lc = 10 and λ = 0.BOCS-SDP and BOCS-SA are close to each other, while EI and SA progress more slowly and OLS eventually becomes trapped in a local optimum.
- Binary quadratic programming: For binary quadratic programming with Lc=100 and λ=1, BOCS-SDP performs substantially better than other algorithms, followed by BOCS-SA.The results also associate posterior sampling of regression weights with exploration of the model space and better performance than a maximum-likelihood variant.
- Sparsification of Ising models: BOCS-SDP obtains the best function values for all three Ising-sparsification settings after 150 iterations and has the lowest variability across 10 random models.The Ising objective is expensive because computing the partition-function ratio grows exponentially in the number of nodes; the problem uses 24 edges and 20 initial points.
- Aero-structural multi-component problem: In the aero-structural problem, SA performs best overall, followed closely by EI, BOCS-SDP, and BOCS-SA with similar convergence profiles.The task seeks a sparsified model preserving the output distribution while reducing coupling variables; one reported BOCS solution retains 5 of 21 variables.
5. Conclusion
BOCS is presented as the first algorithm for optimizing expensive black-box functions over combinatorial structures, addressing combinatorial explosion through scalable acquisition optimization. The authors report that it outperforms state-of-the-art methods, while future work targets other acquisition criteria and application-specific models.
- Its acquisition algorithm uses convex-optimization techniques to improve scalability and efficiency in large combinatorial domains.
- The method handles sparse data and applies to a wide range of combinatorial structures.
- Future work includes optimizing other acquisition criteria and developing models tailored to specific applications.
Supplementary Material
The supplementary material extends BOCS beyond binary, second-order settings to categorical and integer-valued variables and higher-order models. Simulated annealing searches the acquisition criterion while preserving feasible categorical assignments.
- BOCS supports models of order larger than two and categorical and integer-valued variables.
- Categorical variables are expanded into binary indicators, with exactly one indicator active for each categorical variable.
- For categorical optimization, simulated annealing operates on original-domain tuples so proposed solutions remain feasible assignments.
- Integer-valued variables use the regression model directly, while acquisition optimization uses the same neighborhood definition as categorical variables.
- Higher-order models use monomials up to a chosen order, trading greater expressiveness against lower predictive accuracy with limited data.
B. Evaluation of Higher Order Models
Higher-order models can capture interactions that second-order models miss, but their benefits depend on available data. Across the evaluated benchmarks, third-order models improve as samples increase, while second-order models offer a good limited-data trade-off.
- Second-order BOCS-SA performs better initially on the aero-structural benchmark, whereas the third-order model performs better as samples grow.Second-order models estimate fewer coefficients with lower variance from few samples; higher-order models capture more interactions but may require more data.
- With λ = 0, Ising results are averaged over 100 instances, while λ = 10^-2 results are summarized separately.
- For the Ising benchmark, third-order BOCS-SA achieves better results than lower-order models as the number of samples increases.
- Second-order models provide a good trade-off between model expressiveness and accuracy when data is limited.
C. Wall-clock Time Performance
BOCS requires less wall-clock time than expected improvement on the 24-dimensional Ising benchmark. BOCS-SA is at least seven times faster and BOCS-SDP four times faster, while EI’s acquisition optimization is prohibitively costly.
- The comparison measures time to first reach objective value 0.01 for λ = 0 and 10^-4 across 100 runs with 95% confidence intervals.
- BOCS-SA is at least seven times faster than EI, while BOCS-SDP is four times faster.
- For a 24-dimensional Ising problem, finding an acquisition-function optimizer is prohibitively costly for EI.
D. Descriptions of Benchmark Problems
The Ising objective measures divergence between an original model and a subgraph-based approximation, but evaluating its partition-function term is generally expensive.
- Ising model: The Ising objective computes KL divergence between models p(z) and qx(z) using interaction matrices Jp and Jq.Precomputed second moments from the original model contribute to the first KL term.
- Computational limitation: Because the model class is not restricted to efficiently normalizable subgraphs, computing Zq generally requires exponentially many terms in n.This makes both the partition-function term and the KL divergence expensive to evaluate.
- Ising model: The objective measures distance to a subgraph approximation while retaining the corresponding parameters from the original interaction matrix.A nonzero Jq_ij uses the same value as the corresponding Jp_ij entry.
D.2. Contamination Control
The contamination-control objective minimizes prevention cost while constraining contamination exceedance probabilities, using Monte Carlo estimates and regression-based optimization models.
- Objective and constraints: The objective minimizes prevention cost while requiring contamination levels to remain below specified thresholds with sufficiently high probability.Constraints are evaluated by counting threshold exceedances across T Monte Carlo simulations.
- Regression models: The study compares maximum likelihood, standard Bayesian linear, and sparse Bayesian linear regression models.These order-two models are evaluated by average absolute approximation error on M = 50 test points while varying training-set size.
- Regression models: The MLE uses an additive normally distributed error model and least-squares estimation of regression coefficients.Its variance treatment is uniform across coefficient estimates.
- Regression models: Bayesian models characterize joint uncertainty in α and σ2, which BOCS uses by sampling regression coefficients from their posterior.This contrasts with the MLE’s uniform variance estimate.
F.1. Validation on Binary Quadratic Programming.
Validation on binary quadratic problems compares MLE, standard Bayesian, and sparse Bayesian estimators, with sparse modeling improving prediction in limited-data and higher-dimensional settings.
- Binary quadratic validation: With N = 40 training samples, the sparsity-inducing regression prior achieves the best prediction of the true quadratic function values.The comparison includes MLE, Bayesian linear regression, and sparse regression predictions.
- Optimization implications: Posterior uncertainty matters for Bayesian optimization because replacing posterior coefficient samples with MLE estimates drastically impairs the optimization process.The MLE does not reflect uncertainty in the model.
- Binary quadratic validation: As the training set grows, test errors converge across estimators for binary quadratic problems.With sufficient training points, the quadratic model closely interpolates the objective, producing low MLE test error.
- Ising validation: The sparse estimator provides lower test errors than standard Bayesian linear regression for the d = 24-edge Ising model.The reduction is attributed to shrinking near-zero coefficients through the sparsity-inducing prior.
F.3. Validation on the Contamination Control Problem.
For contamination control, sparse regression reduces small-sample error, while the aero-structural problem shows similar estimator performance and exposes bias in the second-order model.
- Contamination control: As N increases, coefficient variance and test-set error decrease for MLE, Bayesian, and sparse estimators in contamination control.The sparse estimator shows a large reduction in error offset for small N.
- Contamination control: The contamination objective appears well approximated by a model with a sparse set of interaction terms.The sparsity-inducing prior learns the relevant interaction structure as training data increases.
- Aero-structural validation: The aero-structural problem has similar performance across four estimators as the number of training samples increases.Its test error begins to plateau for large N.
- Aero-structural validation: The aero-structural error plateau indicates bias in the order-two statistical model and motivates higher-order modeling when enough data are available.The authors identify adaptive switching to a higher-order model as future work.