# Bayesian Optimization over Permutation Spaces

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 2 Dec 2021.

## Builds on (most cited first, 25 of 25)

- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Max-value Entropy Search for Multi-Objective Bayesian Optimization with Constraints](https://mlsanity.com/paper/2009.01721/) (2020)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [BOCK : Bayesian Optimization with Cylindrical Kernels](https://mlsanity.com/paper/1806.01619/) (2018)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Molecular Hypergraph Grammar with its Application to Molecular Optimization](https://mlsanity.com/paper/1809.02745/) (2018)
- [BOSS: Bayesian Optimization over String Spaces](https://mlsanity.com/paper/2010.00979/) (2020)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Population-Based Black-Box Optimization for Biological Sequence Design](https://mlsanity.com/paper/2006.03227/) (2020)
- [Mercer Features for Efficient Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2012.07762/) (2020)
- [Constrained Bayesian Optimization for Automatic Chemical Design](https://mlsanity.com/paper/1709.05501/) (2017)
- [Kernels over Sets of Finite Sets using RKHS Embeddings, with Application to Bayesian (Combinatorial) Optimization](https://mlsanity.com/paper/1910.04086/) (2019)
- [Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework](https://mlsanity.com/paper/2012.07320/) (2020)
- [On kernel methods for covariates that are rankings](https://mlsanity.com/paper/1603.08035/) (2016)
- [Combinatorial Black-Box Optimization with Expert Advice](https://mlsanity.com/paper/2006.03963/) (2020)
- [Scalable Combinatorial Bayesian Optimization with Tractable Statistical models](https://mlsanity.com/paper/2008.08177/) (2020)
- [Semidefinite Programming Approach for the Quadratic Assignment Problem with a Sparse Graph](https://mlsanity.com/paper/1703.09339/) (2017)
- [The Weighted Kendall and High-order Kernels for Permutations](https://mlsanity.com/paper/1802.08526/) (2018)

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

- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [Offline Multi-Objective Optimization](https://mlsanity.com/paper/2406.03722/) (2024)
- [Language Model Embeddings Can Be Sufficient for Bayesian Optimization](https://mlsanity.com/paper/2410.10190/) (2024)
- [Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/2306.01276/) (2023)
- [Bayesian Optimization For Multi-Objective Mixed-Variable Problems](https://mlsanity.com/paper/2201.12767/) (2022)
- [Practical First-Order Bayesian Optimization Algorithms](https://mlsanity.com/paper/2306.10815/) (2023)
- [Random Postprocessing for Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2309.02842/) (2023)
- [CATBench: A Compiler Autotuning Benchmarking Suite for Black-box Optimization](https://mlsanity.com/paper/2406.17811/) (2024)
- [Machine Learning for Combinatorial Optimisation of Partially-Specified Problems: Regret Minimisation as a Unifying Lens](https://mlsanity.com/paper/2205.10157/) (2022)
- [Bayesian Optimization for Macro Placement](https://mlsanity.com/paper/2207.08398/) (2022)
- [From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spaces](https://mlsanity.com/paper/2507.13263/) (2025)
- [SpecBPP: A Self-Supervised Learning Approach for Hyperspectral Representation and Soil Organic Carbon Estimation](https://mlsanity.com/paper/2507.19781/) (2025)
- [Grey-box Bayesian Optimization for Sensor Placement in Assisted Living Environments](https://mlsanity.com/paper/2309.05784/) (2023)
- [Non-Myopic Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2412.08085/) (2024)
- [Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric](https://mlsanity.com/paper/2509.04089/) (2025)
- [Black-Box Optimization From Small Offline Datasets via Meta Learning with Synthetic Tasks](https://mlsanity.com/paper/2604.12325/) (2026)
- [Optimal Transport-based Permutation-Invariant Bayesian Optimization of Offshore Wind Farm Layouts](https://mlsanity.com/paper/2606.00009/) (2026)

## Abstract (arXiv)

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.