mlsanityData to 7 Oct 2026

Bayesian Optimization of Combinatorial Structures

arXiv 1806.08838 ↗First posted 22 Jun 2018stat.ML cs.LG math.OCcited by 64

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 64 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Jun 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 14; 2023: 10; 2024: 8; 2025: 12; 2026: 5.

64 papers.

Sort:

By area:

  1. 2023Unexpected Improvements to Expected Improvement for Bayesian Optimizationcited by 144
  2. 2021High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspacescited by 139
  3. 2024Vanilla Bayesian Optimization Performs Great in High Dimensionscited by 87
  4. 2021The Out-of-Distribution Problem in Explainability and Search Methods for Feature Importance Explanationscited by 86
  5. 2022Recent Advances in Bayesian Optimizationcited by 74
  6. 2021Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spacescited by 51
  7. 2023Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspacescited by 50
  8. 2021Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spacescited by 45
  9. 2022Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterizationcited by 35
  10. 2024Teach Better or Show Smarter? On Instructions and Exemplars in Automatic Prompt Optimizationcited by 28
  11. 2023Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spacescited by 27
  12. 2023Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddingscited by 24
38 more
  1. 2021Bayesian Optimization over Hybrid Spacescited by 23
  2. 2022Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimizationcited by 22
  3. 2024A survey and benchmark of high-dimensional Bayesian optimization of discrete sequencescited by 22
  4. 2022SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problemscited by 21
  5. 2021Bayesian Optimization over Permutation Spacescited by 17
  6. 2022Application of QUBO solver using black-box optimization to structural design for resonance avoidancecited by 17
  7. 2023Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruningcited by 17
  8. 2021NOMU: Neural Optimization-based Model Uncertaintycited by 16
  9. 2023Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimizationcited by 15
  10. 2022AntBO: Towards Real-World Automated Antibody Design with Combinatorial Bayesian Optimisationcited by 14
  11. 2022Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spacescited by 14
  12. 2021Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functionscited by 10
  13. 2023OpenBox: A Python Toolkit for Generalized Black-box Optimizationcited by 9
  14. 2024Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximationcited by 8
  15. 2023SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spacescited by 7
  16. 2021Batch Multi-Fidelity Bayesian Optimization with Deep Auto-Regressive Networkscited by 6
  17. 2021Retrieving Black-box Optimal Images from External Databasescited by 6
  18. 2022Lossy compression of matrices by black-box optimisation of mixed integer nonlinear programmingcited by 6
  19. 2023Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimizationcited by 6
  20. 2021Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernelcited by 5
  21. 2022Bayesian Optimization For Multi-Objective Mixed-Variable Problemscited by 5
  22. 2021Mixed Variable Bayesian Optimization with Frequency Modulated Kernelscited by 4
  23. 2022Fourier Representations for Black-Box Optimization over Categorical Variablescited by 4
  24. 2022Optimization on Manifolds via Graph Gaussian Processescited by 4
  25. 2024Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Designcited by 4
  26. 2022Black Box Optimization Using QUBO and the Cross Entropy Methodcited by 3
  27. 2024User-Side Realizationcited by 3
  28. 2025Graph-Based Bayesian Optimization for Quantum Circuit Architecture Search with Uncertainty Calibrated Surrogatescited by 3
  29. 2021Explaining Inference Queries with Bayesian Optimizationcited by 2
  30. 2021A Novel Surrogate-assisted Evolutionary Algorithm Applied to Partition-based Ensemble Learningcited by 2
  31. 2025Fine-tuning LLMs with variational Bayesian last layer for high-dimensional Bayesian optimizationcited by 2
  32. 2022Machine Learning for Combinatorial Optimisation of Partially-Specified Problems: Regret Minimisation as a Unifying Lenscited by 1
  33. 2022Bayesian Optimization for Macro Placementcited by 1
  34. 2023Inverse Protein Folding Using Deep Bayesian Optimizationcited by 1
  35. 2024Bayesian Optimization of Functions over Node Subsets in Graphscited by 1
  36. 2025A Generative Neural Annealer for Black-Box Combinatorial Optimizationcited by 1
  37. 2025Subsampling Factorization Machine Annealingcited by 1
  38. 2025Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimizationcited by 1

50 most cited of 64 All 64 (JSON)