Mercer Features for Efficient Combinatorial Bayesian Optimization


  • Aryan Deshwal Washington State University
  • Syrine Belakaria Washington State University
  • Janardhan Rao Doppa Washington State University



Active Learning, Sequential Decision Making, Online Learning & Bandits, Bayesian Learning


Bayesian optimization (BO) is an efficient framework for solving black-box optimization problems with expensive function evaluations. This paper addresses the BO problem setting for combinatorial spaces (e.g., sequences and graphs) that occurs naturally in science and engineering applications. A prototypical example is molecular optimization guided by expensive experiments. The key challenge is to balance the complexity of statistical models and tractability of search to select combinatorial structures for evaluation. In this paper, we propose an efficient approach referred as Mercer Features for Combinatorial Bayesian Optimization (MerCBO). The key idea behind MerCBO is to provide explicit feature maps for diffusion kernels over discrete objects by exploiting the structure of their combinatorial graph representation. These Mercer features combined with Thompson sampling as the acquisition function allows us to employ efficient solvers for finding the next structure for evaluation. Experimental evaluation on diverse real-world benchmarks demonstrates that MerCBO performs similarly or better than prior methods.




How to Cite

Deshwal, A., Belakaria, S., & Doppa, J. R. (2021). Mercer Features for Efficient Combinatorial Bayesian Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 7210-7218.



AAAI Technical Track on Machine Learning I