Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features

Rahul Mazumder, Xiang Meng, Haoyue Wang

TL;DR

Quant-BnB is a novel branch-and-bound (BnB) algorithm designed to find globally optimal decision trees for both classification and regression tasks. By leveraging a clever quantile-based pruning strategy, it handles continuous features directly and achieves orders-of-magnitude speedups over existing state-of-the-art optimization methods.

The Challenge of Optimal Decision Trees

Decision trees are a staple of interpretable machine learning. However, the standard way we build them—using greedy algorithms like CART—does not guarantee the "best" or most optimal tree. These heuristics make local, short-sighted splits that can lead to suboptimal predictive performance.

While researchers have developed "optimal" methods using Mixed Integer Programming (MIP) or Dynamic Programming (DP), these approaches face two major hurdles:

  1. Scalability: They often struggle with datasets larger than a few thousand observations.
  2. Feature Constraints: Most current optimal algorithms only work with binary features. To handle continuous data, users must "binarize" it, which either loses information (if too few bins are used) or creates a massive number of features that slows the algorithm to a crawl.

The authors of Quant-BnB aim to bridge this gap by creating a method that is both globally optimal and natively supports continuous features at scale for both regression and classification.

Comparison of optimal tree-learning methods. Quant-BnB uniquely supports continuous features and both regression/classification tasks.

The Quant-BnB Approach

The core of the paper is Quant-BnB, a discrete optimization method based on the Branch-and-Bound framework. The "Quant" refers to quantiles.

Instead of an exhaustive search over every possible split point for every feature—which is computationally explosive—the algorithm partitions the search space based on the quantiles of the feature distribution. This allows the researchers to:

  • Generate Bounds: Derive mathematical upper and lower bounds for the training error within specific sub-regions of the search space.
  • Prune Sub-optimal Regions: If the lower bound of a search region is higher than the best tree found so far (the upper bound), that entire region can be safely discarded without further checking.

The authors propose three different lower bounds ($W_0, W_{1,s'}, W_2$) that offer different trade-offs between computational cost and "tightness" (how close they are to the actual minimum error). They found that $W_{1,s'}$, which uses a subset of samples to estimate the loss, provides the best balance for practical use.

Key Insights and Results

The algorithm was evaluated on 27 datasets from the UCI Machine Learning Repository, spanning 16 classification tasks and 11 regression tasks. These datasets vary significantly in size (from hundreds to hundreds of thousands of observations), providing a robust test for the algorithm's scalability.

Continuous is Better than Binary: The paper demonstrates that tailored approaches for continuous features are far more efficient than converting everything to binary. Binarization creates a "curse of dimensionality" that chokes traditional MIP and DP solvers.

Dramatic Speedups: Quant-BnB shows dramatic performance gains over existing optimal methods like BinOCT, MurTree, and DL8.5.

  • For depth-2 trees, Quant-BnB often finds the optimal solution in a few seconds, whereas competing methods might take minutes, hours, or run out of memory (OoM). On the bank dataset, it was over 29,000 times faster than BinOCT.
  • It successfully handled the skin dataset (~196k observations), while many other optimal methods failed.
  • Even as the problem becomes much harder at depth 3, Quant-BnB outperformed competitors on 13 out of 16 classification datasets.
Detailed performance comparison showing Quant-BnB's speed advantage (in seconds) across various datasets for depth 2 and 3 trees.

Limitations and Future Work

While Quant-BnB is a major step forward, it has its limits:

  • Tree Depth: The algorithm is currently optimized for "shallow" trees (depth 2 or 3). As depth increases to 4 or more, the computational cost grows significantly, making it less practical for very deep architectures.
  • Axis-Aligned Splits: Like most standard decision trees, it only considers splits on a single feature at a time (axis-aligned). It does not currently handle "oblique" splits (linear combinations of features).

Future work could involve extending these quantile-based bounds to deeper trees or integrating them into ensemble methods like Random Forests or Boosting to combine global optimality with high-depth predictive power.

Summary updated

Abstract

Decision trees are one of the most useful and popular methods in the machine learning toolbox. In this paper, we consider the problem of learning optimal decision trees, a combinatorial optimization problem that is challenging to solve at scale. A common approach in the literature is to use greedy heuristics, which may not be optimal. Recently there has been significant interest in learning optimal decision trees using various approaches (e.g., based on integer programming, dynamic programming)—to achieve computational scalability, most of these approaches focus on classification tasks with binary features. In this paper, we present a new discrete optimization method based on branch-and-bound (BnB) to obtain optimal decision trees. Different from existing customized approaches, we consider both regression and classification tasks with continuous features. The basic idea underlying our approach is to split the search space based on the quantiles of the feature distribution—leading to upper and lower bounds for the underlying optimization problem along the BnB iterations. Our proposed algorithm Quant-BnB shows significant speedups compared to existing approaches for shallow optimal trees on various real datasets.
BibTeX
@inproceedings{mazumder2022quant,
  author = {Rahul Mazumder and Xiang Meng and Haoyue Wang},
  title = {{Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=PS0QjOxTyb},
}
Figure