  We study the problem of optimizing expensive blackbox functions over
combinatorial spaces (e.g., sets, sequences, trees, and graphs). BOCS (Baptista
and Poloczek, 2018) is a state-of-the-art Bayesian optimization method for
tractable statistical models, which performs semi-definite programming based
acquisition function optimization (AFO) to select the next structure for
evaluation. Unfortunately, BOCS scales poorly for large number of binary and/or
categorical variables. Based on recent advances in submodular relaxation (Ito
and Fujimaki, 2016) for solving Binary Quadratic Programs, we study an approach
referred as Parametrized Submodular Relaxation (PSR) towards the goal of
improving the scalability and accuracy of solving AFO problems for BOCS model.
PSR approach relies on two key ideas. First, reformulation of AFO problem as
submodular relaxation with some unknown parameters, which can be solved
efficiently using minimum graph cut algorithms. Second, construction of an
optimization problem to estimate the unknown parameters with close
approximation to the true objective. Experiments on diverse benchmark problems
show significant improvements with PSR for BOCS model. The source code is
available at https://github.com/aryandeshwal/Submodular_Relaxation_BOCS .
