A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees
Abstract
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.
Related
- Kurdyka-Łojasiewicz-based convergence analysis with approximate weakly convex subdifferentials: bundle, quadratic penalty, and moving balls approximation methods
- Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce
- Exact linearisation of the nonlinear shallow-water equations over a moving bottom: classification, wave generation and run-up
- Approximate Transitivity of Young Translation on Rough Paths
- Foundations of Geometric Approximate Group Theory
BibTeX
@misc{zou2026movinghorizon,
title = {{A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees}},
author = {Chenxuanyin Zou and Jiayang Ren and Qiangqiang Mao and Jing Liu and Marcus Lai and Yankai Cao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38194},
eprint = {2609.38194},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38194},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees
AU - Chenxuanyin Zou
AU - Jiayang Ren
AU - Qiangqiang Mao
AU - Jing Liu
AU - Marcus Lai
AU - Yankai Cao
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.38194
UR - https://arxiv.org/abs/2609.38194
AB - 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.
ER -