Optimistic Tree Searches for Combinatorial Black-Box Optimization

Cédric Malherbe, Antoine Grosnit, Rasul Tutunov, Haitham Bou-Ammar, Jun WangNeurIPS 2022 · OpenReview

Introduction

In the realm of computer science and engineering, optimizing "black-box" functions is a pervasive challenge. These are functions where you can observe the output for a given input, but the underlying mathematical structure—gradients, linearity, or submodularity—remains completely unknown.

When the inputs to these functions are combinatorial (such as a discrete string of bits representing a circuit design, a schedule, or a graph), two major hurdles arise:

  1. Combinatorial Explosion: The number of possible configurations grows exponentially with the number of variables.
  2. Lack of Ordering: Unlike continuous spaces where numerical proximity implies structural similarity (e.g., 0.5 is "near" 0.51), discrete bitstrings lack a natural "flow." This makes it incredibly difficult for an algorithm to deduce where to search next based on past evaluations.

Historically, researchers have relied on two main approaches. Bayesian Optimization is powerful but computationally heavy, often limiting it to a few hundred evaluations. Conversely, Heuristics (like Genetic Algorithms or Simulated Annealing) are fast but prone to getting stuck in local optima and lack rigorous theoretical guarantees.

Recent research bridges this gap by introducing the first provable black-box solvers for combinatorial optimization that utilize optimistic tree searches. By cleverly partitioning the search space into a hierarchical tree, these new algorithms achieve linear convergence rates, offering an exponential performance gain over traditional naïve search methods.

The core strategy proposed by the authors is to represent the entire combinatorial search space as a hierarchical tree. The algorithm navigates this tree by being "optimistic in the face of uncertainty"—prioritizing branches that have the highest potential to contain the global maximum based on the data gathered so far.

Combinatorial Tree Representation

To make tree search viable, the researchers designed a specific method to partition the Boolean hypercube (the set of all possible 0 and 1 combinations) into a fully-balanced binary tree.

Combinatorial Tree Partitioning

This tree satisfies a crucial "decreasing diameter" property: as the search descends deeper into the tree, the maximum Hamming distance (the number of differing bits) between any two points in a given node shrinks. This structure effectively simulates the "smoothness" found in continuous spaces, allowing for sophisticated, mathematically grounded search strategies.

Two Novel Algorithms: OLTS and OCTS

Building on this tree structure, the paper introduces two primary algorithms:

  • OLTS (Optimistic Lipschitz Tree Search): This algorithm is designed for scenarios where the "smoothness" of the function (its Lipschitz constant, $k$) is known. It uses an upper confidence bound to systematically decide which branch of the tree to prune and which to explore further.
  • OCTS (Optimistic Combinatorial Tree Search): Because the smoothness of a true black-box function is rarely known in practice, OCTS adapts on the fly. It identifies a Pareto-optimal set of "potentially optimal nodes" to explore, effectively learning the function's behavior and smoothness without prior knowledge.

Key Insights and Performance

Conditioning Matters

The speed at which these algorithms converge is heavily dictated by a "conditioning number." If a function is "well-conditioned"—meaning the global peak is distinct and the surrounding values drop off predictably relative to the distance from the optimum—the algorithm can discard suboptimal branches rapidly.

Lipschitz Smoothness and Conditioning

Linear vs. Logarithmic Convergence

Most naïve search methods, such as random search, converge at a painfully slow logarithmic rate. The theoretical breakthrough of this paper is proving that, by leveraging the combinatorial tree structure, OLTS and OCTS can achieve linear convergence.

In practical terms, this translates to an exponential gain in efficiency. On synthetic benchmark problems (like OneMax and LeadingOnes), OCTS identified the global optimum in roughly $O(d^2 \ln d)$ evaluations, whereas a random search would require an exponential $O(2^d)$ evaluations.

Real-World Efficacy

The researchers didn't just stop at mathematical proofs; they evaluated OCTS on notoriously difficult real-world combinatorial problems, including:

  • LABS (Low Autocorrelation Binary Sequences): A complex non-linear problem used in radar engineering.
  • MaxSAT: A fundamental logic satisfiability problem.
  • Ising Model: A physics-based model for magnetism.

In benchmarks like LABS and Concatenated Trap, OCTS outperformed all baselines, including Simulated Annealing and Genetic Algorithms. In several instances, it discovered high-quality solutions that none of the competing methods could reach. Furthermore, because the "inner loop" math of OCTS is lightweight compared to Bayesian methods, it is highly scalable for functions that are cheap to evaluate but require thousands of trials to solve.

Limitations and Future Work

While optimistic tree searches represent a major step forward for combinatorial optimization, the authors note a few areas for future refinement:

  • Budget Awareness: The current node selection mechanism does not explicitly account for a fixed evaluation budget (e.g., optimizing the search strategy when only 1,000 evaluations remain).
  • Dimension-Specific Smoothness: The model currently assumes a single smoothness constant for the entire problem. In reality, some variables might be significantly more sensitive than others.
  • Mixed Spaces: Extending this framework from purely binary spaces to "mixed" spaces (containing both continuous and discrete variables) or noisy environments is a promising next step for the field.

Summary updated

Abstract

The optimization of combinatorial black-box functions is pervasive in computer science and engineering. However, the combinatorial explosion of the search space and lack of natural ordering pose significant challenges for current techniques from a theoretical and practical perspective, and require new algorithmic ideas. In this paper, we propose to adapt the recent advances in tree searches and partitioning techniques to design and analyze novel black-box combinatorial solvers. A first contribution is the analysis of a first tree-search algorithm called Optimistic Lipschitz Tree Search (OLTS) which assumes the Lipschitz constant of the function to be known. Linear convergence rates are provided for this algorithm under specific conditions, improving upon the logarithmic rates of baselines. An adaptive version, called Optimistic Combinatorial Tree Search (OCTS), is then introduced for the more realistic setup where we do not have any information on the Lipschitz constant of the function. Similar theoretical guarantees are shown to hold for OCTS and a numerical assessment is provided to illustrate the potential of tree searches with respect to state-of-the-art methods over typical benchmarks.
BibTeX
@inproceedings{malherbe2022optimistic,
  author = {Cédric Malherbe and Antoine Grosnit and Rasul Tutunov and Haitham Bou-Ammar and Jun Wang},
  title = {{Optimistic Tree Searches for Combinatorial Black-Box Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=a-3RSZFqdSP},
}
Figure