Optimizing expensive to evaluate black-box functions over an input space
consisting of all permutations of d objects is an important problem with many
real-world applications. For example, placement of functional blocks in
hardware design to optimize performance via simulations. The overall goal is to
minimize the number of function evaluations to find high-performing
permutations. The key challenge in solving this problem using the Bayesian
optimization (BO) framework is to trade-off the complexity of statistical model
and tractability of acquisition function optimization. In this paper, we
propose and evaluate two algorithms for BO over Permutation Spaces (BOPS).
First, BOPS-T employs Gaussian process (GP) surrogate model with Kendall
kernels and a Tractable acquisition function optimization approach based on
Thompson sampling to select the sequence of permutations for evaluation.
Second, BOPS-H employs GP surrogate model with Mallow kernels and a Heuristic
search approach to optimize expected improvement acquisition function. We
theoretically analyze the performance of BOPS-T to show that their regret grows
sub-linearly. Our experiments on multiple synthetic and real-world benchmarks
show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO
algorithm for combinatorial spaces. To drive future research on this important
problem, we make new resources and real-world benchmarks available to the
community.

本研究针对基于贝叶斯优化的排列空间问题，提出了两种算法：BOPS-T 和 BOPS-H。两种算法均采用了高斯过程模型，BOPS-T 采用 Kendall 核函数和可处理的采集函数优化方法，BOPS-H 采用 Mallow 核函数和启发式搜索方法来优化期望改进采集函数。理论分析和实验表明，这两种算法在人工和实际基准测试中均优于同类问题的最先进的 BO 算法。

置换空间上的贝叶斯优化

Bayesian Optimization over Permutation Spaces

We consider the problem of optimizing combinatorial spaces (e.g., sequences,
trees, and graphs) using expensive black-box function evaluations. For example,
optimizing molecules for drug design using physical lab experiments. Bayesian
optimization (BO) is an efficient framework for solving such problems by
intelligently selecting the inputs with high utility guided by a learned
surrogate model. A recent BO approach for combinatorial spaces is through a
reduction to BO over continuous spaces by learning a latent representation of
structures using deep generative models (DGMs). The selected input from the
continuous space is decoded into a discrete structure for performing function
evaluation. However, the surrogate model over the latent space only uses the
information learned by the DGM, which may not have the desired inductive bias
to approximate the target black-box function. To overcome this drawback, this
paper proposes a principled approach referred as LADDER. The key idea is to
define a novel structure-coupled kernel that explicitly integrates the
structural information from decoded structures with the learned latent space
representation for better surrogate modeling. Our experiments on real-world
benchmarks show that LADDER significantly improves over the BO over latent
space method, and performs better or similar to state-of-the-art methods.

本文提出了一种基于结构耦合核的 BO 方法 LADDER，使用深度生成模型的潜在表示来优化组合空间，解决了传统 BO 方法中代理模型只利用深度生成模型学习的信息对黑盒函数进行近似的缺陷，并通过实验验证表现优越。

结合潜空间和结构核的组合空间贝叶斯优化

Combining Latent Space and Structured Kernels for Bayesian Optimization  over Combinatorial Spaces

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 tractable solvers to find next structures for evaluation. Experiments
on diverse real-world benchmarks demonstrate that MerCBO performs similarly or
better than prior methods. The source code is available at
this https URL .

本文介绍了 Mercer Features for Combinatorial Bayesian Optimization（MerCBO）方法，该方法利用离散对象的组合图表示的结构，提供了扩散核的显式特征映射，结合使用 Thompson 采样作为获取函数，使我们能够使用可处理的解算器找到下一个要评估的结构，在各种真实世界基准测试中，MerCBO 表现出类似或更好的结果。

高效组合贝叶斯优化的 Mercer 特征

Mercer Features for Efficient Combinatorial Bayesian Optimization

The Gumbel-Max trick is the basis of many relaxed gradient estimators. These
estimators are easy to implement and low variance, but the goal of scaling them
comprehensively to large combinatorial distributions is still outstanding.
Working within the perturbation model framework, we introduce stochastic
softmax tricks, which generalize the Gumbel-Softmax trick to combinatorial
spaces. Our framework is a unified perspective on existing relaxed estimators
for perturbation models, and it contains many novel relaxations. We design
structured relaxations for subset selection, spanning trees, arborescences, and
others. When compared to less structured baselines, we find that stochastic
softmax tricks can be used to train latent variable models that perform better
and discover more latent structure.

在扰动模型框架下，我们使用随机 softmax 技巧（stochastic softmax tricks）对 Gumbel-Softmax 技巧进行了推广，将其推广到组合空间。与基线相比，我们发现使用随机 softmax 技巧可以训练表现更好、发现更多潜在结构的潜在变量模型。