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

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

TL;DR

This paper introduces L2S-DISCO, a novel framework that combines machine learning with search algorithms to efficiently optimize expensive black-box functions over discrete spaces. By learning to guide its search process, L2S-DISCO significantly outperforms existing methods on complex real-world problems, finding better solutions faster.

What Problem Does This Paper Address?

Many real-world optimization problems involve searching through vast, discrete spaces (like sets of materials, sequences of operations, or network configurations) where evaluating each possibility is extremely costly, akin to running a complex simulation or a physical experiment. The challenge is to intelligently select which configurations to evaluate to find the best one as quickly as possible. Traditional Bayesian Optimization (BO) methods, which are effective for continuous spaces, struggle with discrete spaces due to difficulties in modeling complex structures and efficiently searching them. This paper tackles the problem of optimizing these expensive black-box functions in discrete spaces, specifically focusing on the challenge of selecting the next candidate structure to evaluate.

Methods

The core innovation is the L2S-DISCO (Learning-to-Search for Discrete Combinatorial Optimization) framework. It's a "learning-to-search" approach, meaning it uses machine learning to improve a search procedure over time.

Here's how it works:

  • Surrogate Model: Like standard BO, L2S-DISCO builds a statistical model (a surrogate) of the expensive objective function based on observed evaluations. This model helps predict the performance of unseen configurations.
  • Acquisition Function Optimization: The crucial step is deciding which configuration to evaluate next. This is done by optimizing an "acquisition function" (AF), which balances exploration (trying new areas) and exploitation (focusing on promising areas).
  • Search-Based AFO: Instead of directly optimizing the AF, L2S-DISCO frames this as a search problem. It uses a combinatorial search procedure (like local search) guided by learned "search control knowledge" (e.g., heuristics).
  • Learning Control Knowledge: The key novelty is that this search control knowledge is continuously improved using machine learning. As the search progresses and new data (function evaluations and the resulting search trajectories) is gathered, the framework retrains its search guidance mechanism. This allows it to adapt and become more efficient over time.
  • Instantiation for Local Search: The paper provides a concrete implementation of L2S-DISCO for local search. Here, the learned heuristic guides the selection of good starting states for the local search, which then uses the acquisition function to find local optima. The learning is done via a "rank learning" formulation, where the system learns to rank starting states based on the quality of the solutions they lead to.

Datasets

The paper evaluates L2S-DISCO on five diverse benchmark domains:

  1. Contamination: A food supply chain problem involving binary decisions to prevent contamination.
  2. Sparsification of zero-field Ising models: Finding a sparse distribution that approximates a given one, often represented by graph structures.
  3. Low auto-correlation binary sequences (LABS): Optimizing binary sequences for signal processing applications.
  4. Network optimization in multicore chips: Optimizing communication link placements in multicore processors, with constraints on valid paths.
  5. Core placement optimization in multicore chips: Optimizing the placement of different types of cores (CPU, GPU, memory) in a mesh network, with categorical variables and cardinality constraints.

These benchmarks represent real-world problems with discrete structures and expensive evaluations, often involving complex constraints.

Key Insights and Ideas

  • Learning to Search is Powerful for Discrete BO: The paper demonstrates that framing the acquisition function optimization as a search problem, and then learning to guide that search, is a highly effective strategy for discrete optimization.
  • Adaptability is Key: By continuously updating its search strategy based on new data, L2S-DISCO can adapt to the specific characteristics of the optimization problem and the evolving surrogate model, leading to better performance over time.
  • Beyond Model Assumptions: Unlike some methods (like BOCS) that rely on specific modeling assumptions (e.g., linear models, binary variables) to enable efficient solvers, L2S-DISCO is more flexible. It can work with complex surrogate models and acquisition functions, making it applicable to a wider range of problems.
  • Handling Constraints Gracefully: The search-based nature of L2S-DISCO makes it naturally amenable to incorporating domain constraints, which is a significant challenge for many existing BO methods in discrete spaces.

Key Results

L2S-DISCO consistently outperformed state-of-the-art baselines (SMAC and BOCS) across most of the evaluated benchmarks.

  • General Superiority: L2S-DISCO variants (using EI and UCB acquisition functions) generally performed better than SMAC.
  • Contamination & Ising: L2S-DISCO showed comparable or better performance than BOCS, especially in the Ising domain where it eventually matched BOCS's performance. The paper notes that BOCS performs well here because the problem aligns with its modeling assumptions, but L2S-DISCO is more robust when these assumptions are not met.
  • LABS: L2S-DISCO significantly outperformed both BOCS and SMAC.
  • Network Optimization: L2S-DISCO showed significantly better performance than BOCS, which struggled with constraints and got stuck for long periods. SMAC was not applicable due to its inability to handle domain constraints.
  • Core Placement Optimization: L2S-DISCO significantly outperformed BOCS. BOCS also scaled very poorly on this non-binary categorical problem due to the overhead of one-hot encoding, making its execution extremely slow.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that for problems that perfectly match the modeling assumptions of methods like BOCS (allowing for specialized solvers like SDP), those methods might perform slightly better initially. However, L2S-DISCO's robustness and adaptability make it superior in more complex scenarios.
  • The scalability of BOCS with one-hot encoding for categorical variables is a significant limitation highlighted by the experiments.
  • Future Work:
    • Investigate instantiations of L2S-DISCO for other search procedures beyond local search to further enhance performance.
  • Apply L2S-DISCO to other important real-world applications, potentially by incorporating specific domain knowledge.
  • Explore more sophisticated machine learning techniques for learning the search control knowledge.

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