  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.
