# Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

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

- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings](https://mlsanity.com/paper/2303.01774/) (2023)
- [Bayesian Optimization over Hybrid Spaces](https://mlsanity.com/paper/2106.04682/) (2021)
- [Bayesian Optimization over Permutation Spaces](https://mlsanity.com/paper/2112.01049/) (2021)
- [Output Space Entropy Search Framework for Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2110.06980/) (2021)
- [Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel](https://mlsanity.com/paper/2102.13382/) (2021)
- [Fourier Representations for Black-Box Optimization over Categorical Variables](https://mlsanity.com/paper/2202.03712/) (2022)
- [Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design](https://mlsanity.com/paper/2409.18582/) (2024)
- [Grey-box Bayesian Optimization for Sensor Placement in Assisted Living Environments](https://mlsanity.com/paper/2309.05784/) (2023)

## Abstract (arXiv)

We consider the problem of optimizing expensive black-box functions over discrete spaces (e.g., sets, sequences, graphs). The key challenge is to select a sequence of combinatorial structures to evaluate, in order to identify high-performing structures as quickly as possible. Our main contribution is to introduce and evaluate a new learning-to-search framework for this problem called L2S-DISCO. The key insight is to employ search procedures guided by control knowledge at each step to select the next structure and to improve the control knowledge as new function evaluations are observed. We provide a concrete instantiation of L2S-DISCO for local search procedure and empirically evaluate it on diverse real-world benchmarks. Results show the efficacy of L2S-DISCO over state-of-the-art algorithms in solving complex optimization problems.