Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework
Abstract
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.
Cite
Text
Deshwal et al. "Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I04.5788Markdown
[Deshwal et al. "Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/deshwal2020aaai-optimizing/) doi:10.1609/AAAI.V34I04.5788BibTeX
@inproceedings{deshwal2020aaai-optimizing,
title = {{Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework}},
author = {Deshwal, Aryan and Belakaria, Syrine and Doppa, Janardhan Rao and Fern, Alan},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {3773-3780},
doi = {10.1609/AAAI.V34I04.5788},
url = {https://mlanthology.org/aaai/2020/deshwal2020aaai-optimizing/}
}