mlsanityData to 7 Oct 2026

Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel

arXiv 2102.13382 ↗First posted 26 Feb 2021stat.ML cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

In this work we propose a batch Bayesian optimization method for combinatorial problems on permutations, which is well suited for expensive-to-evaluate objectives. We first introduce LAW, an efficient batch acquisition method based on determinantal point processes using the acquisition weighted kernel. Relying on multiple parallel evaluations, LAW enables accelerated search on combinatorial spaces. We then apply the framework to permutation problems, which have so far received little attention in the Bayesian Optimization literature, despite their practical importance. We call this method LAW2ORDER. On the theoretical front, we prove that LAW2ORDER has vanishing simple regret by showing that the batch cumulative regret is sublinear. Empirically, we assess the method on several standard combinatorial problems involving permutations such as quadratic assignment, flowshop scheduling and the traveling salesman, as well as on a structure learning task.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 27 of its 98 references that are in the map. First posted on arXiv 26 Feb 2021.

Builds on

27 of 98 references.

References · 27

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2018A Tutorial on Bayesian Optimizationcited by 734
  3. 2015Scalable Bayesian Optimization Using Deep Neural Networkscited by 284
  4. 2014Predictive Entropy Search for Efficient Global Optimization of Black-box Functionscited by 201
  5. 2020pymoo: Multi-objective Optimization in Pythoncited by 196
  6. 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 125
  7. 2017Batched Large-scale Bayesian Optimization in High-dimensional Spacescited by 116
  8. 2015Batch Bayesian Optimization via Local Penalizationcited by 103
  9. 2019Combinatorial Bayesian Optimization using the Graph Cartesian Productcited by 78
  10. 2016The Parallel Knowledge Gradient Method for Batch Bayesian Optimizationcited by 73
  11. 2016Structure Learning in Graphical Modelingcited by 66
  12. 2018Bayesian Optimization of Combinatorial Structurescited by 64
15 more
  1. 2017Batched High-dimensional Bayesian Optimization via Structural Kernel Learningcited by 51
  2. 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
  3. 2016Parallel Bayesian Global Optimization of Expensive Functionscited by 43
  4. 2019Batch Active Learning Using Determinantal Point Processescited by 42
  5. 2019Minimum Description Length Revisitedcited by 36
  6. 2017Guarantees for Greedy Maximization of Non-submodular Functions with Applicationscited by 34
  7. 2016Batched Gaussian Process Bandit Optimization via Determinantal Point Processescited by 33
  8. 2015Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functionscited by 31
  9. 2020Optimal Transport Kernels for Sequential and Parallel Neural Architecture Searchcited by 29
  10. 2016Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processescited by 24
  11. 2018Differentiable Compositional Kernel Learning for Gaussian Processescited by 23
  12. 2015Optimization as Estimation with Gaussian Processes in Bandit Settingscited by 17
  13. 2020Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Frameworkcited by 11
  14. 2020Combinatorial Black-Box Optimization with Expert Advicecited by 8
  15. 2019Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraintcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 3; 2025: 1.

5 papers.

  1. 2024Language Model Embeddings Can Be Sufficient for Bayesian Optimizationcited by 8
  2. 2023SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spacescited by 7
  3. 2024Advancing Deep Active Learning & Data Subset Selection: Unifying Principles with Information-Theory Intuitionscited by 7
  4. 2024CATBench: A Compiler Autotuning Benchmarking Suite for Black-box Optimizationcited by 2
  5. 2025From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spacescited by 1