# A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees

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

## Key facts

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

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

- [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)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Breiman meets Bellman: Non-Greedy Decision Trees with MDPs](https://mlsanity.com/paper/2309.12701/) (2023)
- [Optimal Survival Trees: A Dynamic Programming Approach](https://mlsanity.com/paper/2401.04489/) (2024)
- [Tree in Tree: from Decision Trees to Decision Graphs](https://mlsanity.com/paper/2110.00392/) (2021)
- [Interpretable Decision Trees Through MaxSAT](https://mlsanity.com/paper/2110.13854/) (2021)

## Abstract (arXiv)

Despite the importance for interpretability, decision trees face severe scalability challenges. Existing global optimal methods are often limited by binary feature selection and shallow tree depths, whereas traditional heuristic approaches frequently sacrifice predictive accuracy. To overcome these limitations, this paper proposes a moving-horizon approximate branch-and-reduce method to train near-optimal deep classification trees on large-scale datasets with continuous features. Built on a hierarchical root-subtree optimization framework, the method solves the root-level problem via branch-and-reduce while approximating the induced subtree problem using greedy heuristics. Although the underlying framework is capable of guaranteeing global optimality, the approximation, which functions as a lookahead rollout in a reinforcement learning context, significantly boosts efficiency for deeper structures. A low-cost moving-horizon strategy is then employed to iteratively refine model accuracy. Extensive numerical results demonstrate that our method exceeds the testing accuracy of existing heuristic baselines while offering significantly greater scalability, in terms of both dataset size and tree depth, than global optimal solvers.