PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.38194v1cs.LGcs.AImath.OC

TL;DR

Decision-tree learning faces a trade-off: heuristic methods can sacrifice accuracy, while global optimization methods have difficulty scaling to deeper trees and large datasets. MHABR combines root-level branch-and-reduce search with approximate subtree solutions and moving-horizon refinement. It reports higher accuracy than evaluated heuristic baselines and greater scalability than the global methods considered, while retaining exactness for depth-2 trees.

  • Problem

    Heuristic tree methods may sacrifice predictive accuracy, while global optimal methods are often limited by feature binarization, tree depth, and scalability on large datasets.

    Source: §1 · p. 2

  • Method

    MHABR uses branch-and-reduce for the root-level problem, CART-based approximations for child-subtree problems, and moving-horizon refinement.

    Source: §1 · p. 2, §4.1 · p. 8, §4.5 · p. 12

  • Results

    3.01% higher average testing accuracy than DPDT at depth 8 on eight medium- and large-scale datasets, while MHABR remains feasible where compared global optimal methods do not complete.

    Source: §1 · p. 3

  • Takeaways & Limitations

    MHABR offers an empirical trade-off between optimization quality, runtime, and scalability on the benchmark datasets considered, and is exact for depth-2 trees.

    Source: §6 · p. 24

    The study uses an unweighted 0-1 objective, which may favor majority classes on highly imbalanced datasets and may not reflect minority-class performance.

    Source: §5.7 · p. 23

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces MHABR to train deep classification trees on large datasets with continuous features, targeting a balance between heuristic accuracy and global-solver scalability. Experiments report stronger accuracy than evaluated heuristic baselines and feasibility at greater depths and dataset sizes than the global methods considered.

1 Introduction

  • Optimal decision-tree learning is NP-hard; traditional greedy methods are efficient but can fall short of optimality, especially for deeper trees.The paper identifies the need for a method that improves accuracy while scaling to deep trees on large datasets.Source: §1 · p. 2
  • Global solvers face efficiency limits on deeper trees, while many DP- and SAT-based approaches binarize continuous features and struggle beyond depth 5 on large datasets.Some exact methods reach depth 3, while other caching-based DP methods can learn relatively deeper trees.Source: §1 · p. 2
  • MHABR combines a hierarchical root-subtree framework and root-level branch-and-reduce search with CART-approximated child-subtree problems and low-cost moving-horizon refinement.The framework guarantees global optimality when child-subtree problems are solved recursively and exactly.Source: §1 · p. 2
  • 3.01% higher average testing accuracy than DPDT at depth 8 on eight medium- and large-scale datasets; MHABR also remains feasible where compared global methods do not complete.Across 59 UCI datasets, MHABR is reported to train trees up to depth 8 on datasets with as many as 60 million samples.Source: §1 · pp. 2–3

2 Preliminary

The paper formulates supervised classification over feature vectors and class labels, then expresses tree training as loss minimization. It organizes the optimization by separating root splits from the induced child-subtree problems.

2 Preliminary

  • The supervised task uses labeled samples with numerical, categorical, or binary features, which are scaled to [0, 1].The dataset contains feature vectors and corresponding class labels.Source: §2 · p. 3

2.1 Notations for Decision Trees

  • Tree training minimizes the number of misclassified instances, with an optional complexity penalty weighted by α to balance training accuracy and generalization.The penalty is omitted from the paper's initial formulation and later examined in experiments.Source: §2.1 · p. 3

2.2 A Hierarchical Root–Subtree Framework for Decision Tree Training

  • The hierarchical framework isolates the root feature and threshold for a root-level problem, then defines the tree's loss through the optimized left and right child subtrees.The framework treats the root split separately because it processes the entire dataset.Source: §2.2 · pp. 3–4

3 A Branch-and-Reduce Method for Optimal Decision Trees

The branch-and-reduce method searches root split candidates using bounds, reduction, and branching. Under exact child-subtree optimization, the framework converges to a globally optimal tree.

3 A Branch-and-Reduce Method for Optimal Decision Trees

  • The root-level branch-and-reduce search addresses the large split-candidate space that can arise when continuous features have many unique values.The method's optimality analysis assumes child-subtree problems can be solved exactly and efficiently.Source: §3 · p. 4

3.1 Upper Bound, Lower Bound, Reduction, and Branching Strategy

  • A Lipschitz-type bound on loss across split indices supports lower bounds that can rule out candidates unable to improve the incumbent solution.The method also maintains an upper bound from evaluated splits and bisects remaining candidates at their midpoint.Source: §3.1 · pp. 4–6

3.2 The Procedure of Branch-and-Reduce Method

  • The procedure evaluates midpoint splits, updates the incumbent, reduces candidate sets, and branches on the remaining regions until none remain.Its reduction strategy preserves the global optimum, and Algorithm 1 converges to the global optimum under exact child-subtree solutions.Source: §3.2 · p. 6

4 A Moving-Horizon Approximate Method for Deep Trees

The method combines root-level branch-and-reduce with approximate child-subtree values to make deep-tree optimization more efficient, then refines selected subtrees through a moving horizon. Exact child-subtree optimization guarantees global optimality, while the approximate method retains a global-optimality guarantee for depth-2 trees.

4 A Moving-Horizon Approximate Method for Deep Trees

  • The exact hierarchical framework guarantees global optimality when child-subtree problems are solved recursively, but this exact approach incurs an exponential increase in computational time.The approximation is introduced to improve efficiency while maintaining high accuracy; depth-2 global optimality is still guaranteed.Source: §4 · p. 7

4.1 Child-Subtree Approximation

  • For d > 2, CART approximates child-subtree values within ABR; its returned training loss is no greater than CART’s, but reduction is heuristic and global optimality is not claimed.With reduction disabled, ABR exactly minimizes the approximate objective; with reduction enabled, the depth-2 tree remains globally optimal.Source: §4.1 · pp. 8–9

4.2 A Reinforcement Learning Perspective

  • In the RL view, each layer’s sample sets are states, its splitting rules are actions, and loss descent is the reward; CART approximates the cost-to-go for the child subtrees.A 2-step lookahead can improve performance at additional computational cost.Source: §4.2 · p. 10

4.3 A Moving-Horizon Approach

  • Moving-horizon refinement repeatedly re-optimizes selected subtrees with their reaching samples, decreasing subtree depth across steps and potentially improving deep-tree accuracy.It requires at most 2^d−1 − 1 iterations and stops when a subtree reaches optimal loss, including when its depth is 1.Source: §4.3 · p. 10

4.4 Why ABR and MH Can Improve Over CART

  • Unlike CART’s local split criterion, ABR evaluates candidate root splits with approximate downstream subtree costs, allowing a split with little immediate benefit to yield a better full tree.The noiseless XOR example illustrates the lookahead benefit: a depth-2 tree can classify all four patterns even when a one-step greedy split sees no immediate loss reduction.Source: §4.4 · p. 11

4.5 A Moving-Horizon Approximate Branch-and-Reduce Method

  • MHABR initializes with CART and replaces a subtree only when its approximate search finds lower loss, so accepted updates never increase total training loss.The algorithm uses ABR to search selected subtrees and updates the tree only when the proposed subtree loss is lower.Source: §4.5 · pp. 11–12

3. The cost of MHABR is bounded by O

The number of candidate feature-threshold pairs is at most p(n + 1), giving a coarse O(pn) bound.

3. The cost of MHABR is bounded by O

  • p(n + 1) = O(pn) bounds the total number of candidate feature-threshold pairs.The passage identifies this as a coarse bound used in the subsequent worst-case analysis.Source: §3 · p. 12

2. The cost of MHABR is bounded by O

The section bounds CART, exact branch-and-reduce (BR), and moving-horizon approximate branch-and-reduce (MHABR) under repeated sorting assumptions. Exact BR grows exponentially with tree depth, while MHABR uses approximate subtree solves across moving-horizon levels; the bounds are coarse worst-case estimates.

2. The cost of MHABR is bounded by O

  • CART costs O(pnd log n) under repeated sorting, because sorting dominates the linear sweep over candidate thresholds.The analysis assumes samples are sorted with respect to all p features at processed nodes.Source: §2 · p. 13
  • For fixed p and n, exact BR has an exponential-in-depth bound; for fixed depth, its bound is polynomial in n and p, with degree increasing with depth.Its cost grows multiplicatively with the number of candidate splits at each recursive depth.Source: §2 · p. 13
  • Each ABR root candidate is evaluated by approximating its child subtrees with depth-(dsub −1) CART trees, at cost O(pn(dsub −1) log n) per candidate.The bound uses the fact that the two child sample sets partition the parent samples.Source: §2 · p. 14
  • MHABR applies ABR to subtrees with remaining depths d through 2, summing work across same-level subtrees whose sample sets are disjoint.At a fixed remaining depth, the processed subtree sample sizes sum to at most n.Source: §2 · p. 14
  • The bounds are coarse worst-case estimates; observed runtime is reduced by warm-starting, reduction, and early stopping.The theorem ignores implementation-dependent speedups including these effects.Source: §2 · p. 14

5 Numerical Experiments

The numerical experiments assess MHABR’s predictive accuracy and scalability across datasets and tree depths, including comparisons with DPDT and global solvers and evaluation of its refinement and efficiency techniques. They also examine multiclass tasks, class imbalance, real-world safety, and the tradeoff between accuracy gains and training time at prescribed tree depths.

5.1 Performance on Small Datasets

  • MHABR achieves the strongest average testing accuracy at depths d = 2 and d = 3 on small datasets, remains 0.99% ahead of DL8.5 at d = 8, and reaches the global optimum at d = 2.At d = 8, the training–testing gap signals overfitting, so those results warrant the later validation-based tuning context. MHABR also exceeds heuristic baselines in training accuracy, averaging 2.63% above CART.Source: §5.1 · pp. 15–16

5.2 Medium-scale and Large-scale Datasets

  • At depth d = 8, MHABR’s average testing accuracy exceeds CART by 3.66% and DPDT by 3.01% across medium- and large-scale datasets, while remaining feasible for deeper trees.On medium datasets, it exceeds CART by 1.84% at depth 4 and 4.59% at depth 8, and DPDT by 0.66% and 3.49%, respectively; on large datasets the corresponding advantages are 1.14% and 4.13% over CART and 0.63% and 3.89% over DPDT.Source: Table 2 · p. 17, §5.2 · p. 18
  • MHABR’s training cost is driven more by unique split candidates than sample count; on small datasets, its runtime grows nearly linearly with depth while global solvers become sharply more expensive.At depth 8, MHABR takes 26.99 s, compared with 167.2 s for DL8.5 and 236.7 s for LS-OCT; CART and DPDT remain faster heuristic baselines.Source: §5.1 · p. 16, Figure 3 · p. 16, §5.2 · p. 18

5.3 Compared to DPDT

  • At d = 8 across 51 datasets, MHABR strictly outperforms default DPDT on 23 datasets, improving overall by 46.29%, and is 3.93% worse on 7 datasets.The α-tuning comparison uses 25 datasets with more than 500 samples, a shared validation-based procedure, and depths 2–5; Table 3 reports the highest average testing accuracy for MHABR at every depth.Source: §5.3 · pp. 18, 20, Table 3 · p. 20

5.4 Discussion about comparison with global optimal methods

  • MHABR matches Quant-BnB’s training accuracy at d = 2 and is only marginally lower at d = 3, while exceeding DL8.5’s training accuracy on continuous datasets, especially at depth 8.Quant-BnB completes only 42 datasets and is limited to depth 3; DL8.5’s binarization of continuous features introduces approximation error.Source: §5.4 · pp. 20–21, Table 4 · p. 21

5.5 Optimality Gap Evaluation and An Extension

  • Across 10 small datasets, MHABR’s average optimality gap stays within 1%, while MHABR2 consistently reduces it below 1% and attains exact optimality for depth-3 trees.MHABR2 extends the root-level lookahead to the top two layers for d ≥ 3; MHABR is generally recommended as a balance of strong optimality and reasonable computational cost.Source: §5.5 · pp. 21–22, Table 5 · p. 22, Table 6 · p. 22

5.6 Ablation Studies

  • On the depth-8 Avila ablation, MH refinements yield their greatest improvements in the first five layers, while reduction cuts depth-8 subtree runtime by nearly two orders of magnitude.With ε = 10^-2, final accuracy is similar to ε = 10^-3 and 10^-4 while runtime falls 60%; θ values of 0.8 and 0.9 outperform the full-data run, whereas θ = 0.3 reduces accuracy by less than 5%.Source: §5.6 · pp. 22–23, Figure 8 · p. 23

5.7 Practical Considerations and Limitations

  • MHABR handles binary and multiclass classification without class-dependent threshold search, but unweighted 0-1 loss can understate minority-class performance on imbalanced data.A class-weighted objective can replace the unweighted loss without changing the framework. The threshold search space does not grow with the number of classes, but deeper trees may be needed because a depth-d tree has at most 2^d leaves.Source: §5.7 · p. 23
  • A rule-based tree can aid transparency and auditing, but interpretability alone does not ensure fairness, robustness, or safe use.Sensitive applications warrant evaluation for bias, distribution shift, and subgroup performance, alongside appropriate human oversight.Source: §5.7 · p. 24
  • MHABR suits settings where a high-quality tree at a prescribed depth justifies additional offline training time, especially when CART is inadequate and global optimization is infeasible.The recommended workflow is to benchmark and warm-start with depth-prescribed CART, then try light MHABR if CART validation performance is unsatisfactory; intensify only when light MHABR yields meaningful improvement, as in Avila. When gains are marginal or absent, as in Htru, CART or DPDT offers a better accuracy-runtime tradeoff.Source: §5.7 · p. 24

6 Conclusion and Discussion

MHABR combines root-level branch-and-reduce search, approximate CART subtree solving, and moving-horizon refinement to train deep classification trees. It is exact for depth-2 trees and performs well empirically while remaining feasible on larger datasets than the exact global methods studied.

6 Conclusion and Discussion

  • MHABR combines root-level branch-and-reduce search, CART-based approximate subtree solving, and moving-horizon refinement within a hierarchical root-subtree framework.The paper describes the resulting method as approximate for deep trees.Source: §6 · p. 24
  • MHABR is exact for depth-2 trees and performs well empirically on the benchmark datasets considered.Source: §6 · p. 24
  • MHABR achieves strong test accuracy relative to the compared baselines while remaining computationally feasible on larger datasets than the exact global methods studied.The authors characterize this as an empirical trade-off among optimization quality, runtime, and scalability.Source: §6 · p. 24

7 Summary of Notation

The paper's notation is collected in Table 7, including terms for subtree problems and parameters used in complexity and experimental settings.

7 Summary of Notation

  • Table 7 collects the paper's notation, including subtree quantities and complexity and experimental parameters.Source: Table 7 · p. 27, §7 · p. 27
  • The listed parameters include the maximum number of feature-threshold pairs evaluated, mini-batch sampling ratio, threshold-search tolerance, and tree-complexity regularization coefficient.Source: §7 · p. 28

8 Supplementary Experiments: Comparison with TAO

The supplementary comparison uses TAO's published results on five datasets with the same data split. In the reported matched dataset-depth combinations, MHABR has higher average training and testing accuracy, but the comparison was not controlled across implementations and settings.

8 Supplementary Experiments: Comparison with TAO

  • MHABR averages 86.3% testing accuracy versus TAO's 85.3% across matched dataset-depth combinations reported by TAO.Results for deeper trees are absent because TAO did not report them.Source: §8 · p. 28, Table 8 · p. 28
  • MHABR averages 88.5% training accuracy versus TAO's 87.8% across the matched dataset-depth combinations.Performance varies across individual datasets and tree depths.Source: §8 · p. 28, Table 8 · p. 28
  • The comparison uses TAO results from its publication rather than a controlled reimplementation, and preprocessing, splits, stopping criteria, implementation, and hardware could not be standardized.The authors present it only as supplementary evidence and do not rely on it for primary empirical claims.Source: §8 · pp. 28–29

9 Additional Theoretical Results and Analysis

The additional analysis reviews CART properties, introduces a reduced CART implementation, and uses an XOR example to analyze greedy failure and lookahead. It also records dataset and implementation details for supplementary experiments.

9.1 Recall the basics of CART

  • CART's depth-1 split selection is optimal, and its misclassification loss is nonincreasing as tree depth increases.Source: §9.1 · p. 29

9.2 A reduced CART method

  • Reduced CART skips thresholds certified not to improve the incumbent and returns the same tree as standard CART under matching candidate sets, stopping conditions, and tie-breaking.This reduction applies to the local depth-1 split objective and may evaluate fewer candidates.Source: §9.2 · p. 30

9.3 An Illustrative XOR Case for Greedy Failure

  • In the XOR illustration, a single greedy split on either informative feature yields no immediate loss reduction, while depth-2 lookahead can recover the interaction.Source: §9.3 · p. 31, Figure 9 · p. 32
  • When true-feature child nodes remain balanced but a noise-feature child is unbalanced, greedy immediate-loss reduction selects a noise feature over either true feature.Source: §9.3 · p. 31
  • For XOR-distributed data, MHABR returns a global-optimal tree with zero training loss at depth 2 or greater, and strictly beats CART when CART has positive loss.Source: §9.3 · p. 32

10.1 Information of small-scale datasets

10.2 Configuration of additional techniques for large-scale datasets

  • For the five medium datasets, MHABR completes training without the specified ε and θ parameters; the three large datasets use dataset-specific ε and θ settings to meet time limits.Source: §10.2 · p. 33

10.3 Implementation details

  • The default MHABR implementation uses reduction parameters ε = 0 and θ = 1; STreeD results are omitted because hardware changes prevented a fair comparison.Source: §10.3 · p. 34
Loading 2609.38194v1…