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

Chenxuanyin Zou; Jiayang Ren; Qiangqiang Mao; Jing Liu; Marcus Lai; Yankai Cao

cs.LGSep 18, 2026

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

Authors: Chenxuanyin Zou, Jiayang Ren, Qiangqiang Mao, Jing Liu, Marcus Lai, Yankai Cao

Organizations: Department of Chemical and Biological Engineering University of British Columbia · Department of Electrical and Computer Engineering University of British Columbia · Department of Computer Science University of British Columbia

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.

Figures & tables

Figure 1: Illustration of the Child-Subtree Approximation via RL (

x

denotes the state).

Figure 2: An example of MH when

d=4

Figure 3: Average training time across 51 small datasets on a logarithmic scale. CART and DPDT remain the fastest methods, whereas Quant-BnB and DL8.5 exhibit sharp runtime growth with depth. MHABR is slower than the heuristic baselines but scales more moderately than the global optimization baselines, requiring

26.99~\mathrm{s}

at depth 8, compared with

167.2~\mathrm{s}

for DL8.5 and

236.7~\mathrm{s}

for LS-OCT .

Figure 4: Training/testing accuracy vs. tree depth/running time on Avila

Figure 5: Training/testing accuracy vs. tree depth/running time on Eeg

Figure 6: Training and testing accuracy of 51 small datasets across

d=2,3,4,8

Figure 7: Theoretical relationships in terms of optimality between our algorithms and other global optimal methods

Panel of Figure 8 — Figure 8: Ablation study of MHABR on Avila using a depth-8 tree. For instance, the depth-8 subtree represents the complete original tree, while the depth-7 subtrees are rooted at nodes 2 and 3. Similarly, the depth-6 subtrees are rooted at nodes 4, 5, 6, and 7, and this pattern continues for the other depths. (a) layer-wise improvements in training accuracy from MH refinement; (b) runtime with and without the reduction strategy across subtree depths; (c) effect of the termination tolerance $\epsilon$ ; and (d) effect of the mini-batch ratio $\theta$ .

Symbol	Description
Data and decision-tree notation
$\{(x_{i},y_{i})\}_{i=1}^{n}$	Dataset of $n$ feature–label pairs.
$\mathcal{Y}$	Set of class labels.
$n$ , $p$ , $n_{c}$	Numbers of samples, features, and classes, respectively.
$[n]$	Index set $\{1,\ldots,n\}$ .
$\mathcal{I}\subseteq[n]$	Index set of samples in a tree or subtree.

Table 7: Summary of notation used in this paper.

Dataset	Depth	Train		Test
Dataset	Depth	TAO	MHABR	TAO	MHABR
Balance-scale	$d=2$	72.5 (1.6)	72.7 (0.7)	69.5 (2.9)	68.5 (2.0)
	$d=3$	76.9 (1.1)	76.8 (1.4)	71.6 (1.9)	74.8 (2.2)
	$d=4$	84.0 (1.5)	84.1 (1.1)	79.8 (3.1)	78.9 (2.7)
Banknote-auth.	$d=2$	91.9 (0.4)	92.8 (0.4)	90.6 (0.9)	91.3 (1.1)
	$d=3$	96.0 (0.5)	98.3 (0.4)	95.7 (1.2)	97.2 (0.6)

Table 8: Performance comparison between TAO and MHABR . Results are reported as mean accuracy with standard deviation in parentheses. Best results for each dataset, depth, and split are highlighted in bold.

Panel of Figure 9 — Figure 9: Illustration of a canonical XOR failure mode. A depth-1 greedy split may fail to separate the classes, whereas a depth-2 lookahead can recover the correct interaction structure.

Decision Tree Learning

Decision tree learning builds hierarchical, rule-based models for prediction, balancing accuracy, computational cost, and interpretability.

See all 69 papers

Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
Sep 5, 2026Jiancheng Tu, Wenqi FanDecision Tree Learning Dynamic Programming
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Search Strategies for Optimal Classification and Regression Trees
Jul 30, 2026Jacobus G. M. van der Linden, Mim van den Bos, Emir DemirovićDecision Tree Learning Classification
Delft University of Technology
Adaptive Multi-Branching for Shallow Decision Tree Induction
Aug 29, 2026Hanul Park, Jeonghoon Choi, Juseong Kim +2Decision Tree Learning Tabular ML
Department of Information Convergence Engineering, Pusan National University, Busan, Rep. of Korea · School of Computer Science and Engineering, Pusan National University, Busan, Rep. of Korea

Sep 5, 2026J/K move · Enter open · S save

Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

Jiancheng Tu, Wenqi Fan

Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University

Decision Tree Learning Dynamic Programming Feature Selection

Open paper AskPDF 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.

Abstract

Decision Tree Learning

Explore similar work

Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

Search Strategies for Optimal Classification and Regression Trees

Adaptive Multi-Branching for Shallow Decision Tree Induction