# Combinatorial Black-Box Optimization with Expert Advice

arXiv: https://arxiv.org/abs/2006.03963 · HTML: https://mlsanity.com/paper/2006.03963/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2020.

## Built on by (most cited first, 8 of 8)

- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Bayesian Optimization over Permutation Spaces](https://mlsanity.com/paper/2112.01049/) (2021)
- [AntBO: Towards Real-World Automated Antibody Design with Combinatorial Bayesian Optimisation](https://mlsanity.com/paper/2201.12570/) (2022)
- [Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel](https://mlsanity.com/paper/2102.13382/) (2021)
- [Fourier Representations for Black-Box Optimization over Categorical Variables](https://mlsanity.com/paper/2202.03712/) (2022)
- [Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design](https://mlsanity.com/paper/2409.18582/) (2024)
- [A Generative Neural Annealer for Black-Box Combinatorial Optimization](https://mlsanity.com/paper/2505.09742/) (2025)
- [Tight L_∞ Sample Complexity for Low-Degree and Sparse Boolean Polynomials](https://mlsanity.com/paper/2606.17319/) (2026)

## Abstract (arXiv)

We consider the problem of black-box function optimization over the boolean hypercube. Despite the vast literature on black-box function optimization over continuous domains, not much attention has been paid to learning models for optimization over combinatorial domains until recently. However, the computational complexity of the recently devised algorithms are prohibitive even for moderate numbers of variables; drawing one sample using the existing algorithms is more expensive than a function evaluation for many black-box functions of interest. To address this problem, we propose a computationally efficient model learning algorithm based on multilinear polynomials and exponential weight updates. In the proposed algorithm, we alternate between simulated annealing with respect to the current polynomial representation and updating the weights using monomial experts' advice. Numerical experiments on various datasets in both unconstrained and sum-constrained boolean optimization indicate the competitive performance of the proposed algorithm, while improving the computational time up to several orders of magnitude compared to state-of-the-art algorithms in the literature.