# Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

arXiv: https://arxiv.org/abs/2609.05826 · HTML: https://mlsanity.com/paper/2609.05826/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 55 references that are in the map.
- First posted on arXiv 5 Sep 2026.

## Builds on (most cited first, 19 of 19)

- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (2021)
- [Sparsity in Optimal Randomized Classification Trees](https://mlsanity.com/paper/2002.09191/) (2020)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)
- [Margin Optimal Classification Trees](https://mlsanity.com/paper/2210.10567/) (2022)
- [Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound](https://mlsanity.com/paper/2501.07903/) (2025)
- [MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees](https://mlsanity.com/paper/2309.15312/) (2023)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [An improved column-generation-based matheuristic for learning classification trees](https://mlsanity.com/paper/2308.11477/) (2023)
- [A Generic Complete Anytime Beam Search for Optimal Decision Tree](https://mlsanity.com/paper/2508.06064/) (2025)
- [Acceleration Techniques for Learning Optimal Classification Trees with Integer Programming](https://mlsanity.com/paper/2511.18791/) (2025)
- [Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach](https://mlsanity.com/paper/2602.02173/) (2026)

## Abstract (arXiv)

Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase. We develop a joint feature- and sample-space reduction framework based on STreeD. Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives. This reduces sample-dependent computation without changing the fixed-candidate optimization problem. Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems. Each certified Weighted STreeD solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space. Experiments on five data sets show that Weighted STreeD achieves speedups of up to 121.41 times over standard STreeD. Adaptive STreeD reduces runtime in matched comparisons at depths 2 to 4 and continues to return feasible trees at greater depths where full-feature methods are limited by time or memory. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons. These results show how joint feature- and sample-space reduction can scale dynamic-programming-based optimal-tree learning to more demanding instances.