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

Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa, Alan Fern

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.

Introduction

Many high-stakes engineering tasks—such as designing efficient multicore processors or discovering new metal alloys—require optimizing "expensive" black-box functions. These evaluations are costly because they often involve day-long computer simulations or physical lab experiments. While Bayesian Optimization (BO) is the standard tool for continuous spaces, it faces significant hurdles in discrete spaces (sets, sequences, or graphs).

Specifically, the "Acquisition Function Optimization" (AFO) step—where the algorithm decides which design to test next—becomes a grueling combinatorial search problem. Existing methods often rely on overly simplified models or rigid, hand-designed heuristics that fail to adapt to the specific problem landscape. L2S-DISCO addresses this by treating AFO as a "learning-to-search" problem.

The L2S-DISCO Framework

L2S-DISCO (Learning to Search for DIScrete COmbinatorial optimization) integrates machine learning directly into the search process used to solve the AFO. Instead of a static search algorithm, it employs an iterative loop that improves its own search strategy over time.

The L2S-DISCO framework loop, showing how control knowledge H is updated via rank learning from search trajectories to guide future local searches.

The framework consists of four main components:

  1. Search with Control Knowledge: A local search procedure (with multiple restarts) identifies the next structure to evaluate. This search is guided by a heuristic function $H$, representing "control knowledge."
  2. Online Learning: As the algorithm explores the space, it collects data on which search trajectories lead to high-performing regions.
  3. Rank Learning: This data is used to update the heuristic $H$ via a learning-to-rank formulation (specifically RankNet). The heuristic learns to recognize which starting points for a local search are most likely to lead to the global optimum.
  4. Surrogate Modeling: Similar to standard BO, it maintains a Random Forest surrogate model to estimate the expensive function's behavior across the discrete space.

Experimental Evaluation

The authors evaluated L2S-DISCO on five diverse and challenging benchmarks:

  • Contamination: A food supply chain safety problem with 25 stages.
  • Ising Models: A physics-based graph sparsification task.
  • LABS (Low Auto-correlation Binary Sequences): A classic signal processing benchmark.
  • Network Optimization: Placing communication links between 12 cores in a multicore chip under path-existence constraints.
  • Core Placement: Arranging processing elements on a 64-core mesh with strict cardinality constraints.

Key Results and Insights

L2S-DISCO consistently outperformed or matched state-of-the-art baselines like SMAC and BOCS. A primary advantage is its superior scalability. On the Core Placement task, traditional solvers like BOCS became computationally prohibited due to input dimension explosion (from 64 to 192 variables under one-hot encoding), whereas L2S-DISCO remained efficient.

Convergence comparison showing L2S-DISCO achieving significantly lower (better) function values over iterations compared to the BOCS baseline.

Key insights from the evaluation include:

  • Search as a Learnable Skill: By treating AFO as a learning task, the algorithm discovers the "shape" of the discrete landscape and focuses its search budget where it matters most.
  • Natural Constraint Handling: Search-based methods handle complex "validity" constraints (e.g., connectivity requirements) more easily than mathematical solvers by simply restricting moves to valid neighboring states.
  • Heuristic Transfer: The learned heuristic provides useful guidance across multiple iterations of the BO loop, as the general regions of interest in the acquisition function remain relatively stable even as new data points are added.

Conclusion and Future Work

L2S-DISCO demonstrates that learning to search is a powerful paradigm for discrete optimization. While this work focused on local search, the framework is general and could be applied to other procedures like Branch-and-Bound. Future research will explore more advanced combinatorial kernels and apply the framework to complex hardware-software co-design problems.

Summary updated

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.
BibTeX
@inproceedings{deshwal2020optimizing,
  author = {Aryan Deshwal and Syrine Belakaria and Janardhan Rao Doppa and Alan Fern},
  title = {{Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=KQyVv9ja8hH},
}
Figure