From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spaces

The article presents a novel framework for Bayesian Optimization (BO) in high-dimensional permutation spaces, introducing the Merge Kernel, which utilizes a divide-and-conquer approach from merge sort to achieve a compact representation with a complexity of $\Theta(n\log n)$. This new kernel outperforms the traditional Mallows kernel in both optimization performance and computational efficiency as dimensionality increases, making it a scalable solution for complex tasks like feature ordering and neural architecture search. The findings provide a significant advancement for practitioners seeking effective methods in high-dimensional optimization scenarios.