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

# A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees
Source: [https://arxiv.org/html/2609.38194](https://arxiv.org/html/2609.38194)
Chenxuanyin Zouzcxy@student\.ubc\.caAffiliation:Department of Chemical and Biological EngineeringAffiliation:University of British ColumbiaJiayang Renrjy12307@student\.ubc\.caAffiliation:Department of Chemical and Biological EngineeringAffiliation:University of British ColumbiaQiangqiang Maomaoq@student\.ubc\.caAffiliation:Department of Chemical and Biological EngineeringAffiliation:University of British ColumbiaJing Liujingliu@ece\.ubc\.caAffiliation:Department of Electrical and Computer EngineeringAffiliation:University of British ColumbiaMarcus Laimarclai@student\.ubc\.caYankai Caoyankai\.cao@ubc\.ca††thanks:Corresponding author\.Affiliation:Department of Chemical and Biological EngineeringAffiliation: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\.

## 1Introduction

The decision tree \(DT\) model is a cornerstone of machine learning, lauded for its interpretable, flowchart\-like structure that makes it particularly suitable for classification and regression tasks requiring transparency and comprehensibility\([Freitas, 2014](https://arxiv.org/html/2609.38194#bib.bib22);[Krzywinski and Altman, 2017](https://arxiv.org/html/2609.38194#bib.bib27)\)\. Unlike many black\-box models, DTs offer a higher degree of trustworthiness, which is critical in advancing AI for scientific research and high\-stakes decision\-making\([Rudin, 2019](https://arxiv.org/html/2609.38194#bib.bib34);[Rudin, 2022](https://arxiv.org/html/2609.38194#bib.bib35)\)\. However, learning an optimal decision tree \(ODT\) has been classified to be𝒩​𝒫\\mathcal\{NP\}\-hard\([Laurent and Rivest, 1976](https://arxiv.org/html/2609.38194#bib.bib28)\)\. Traditional algorithms such asCART\([Breiman et al\., 1984](https://arxiv.org/html/2609.38194#bib.bib19)\),ID3\([Quinlan, 1986](https://arxiv.org/html/2609.38194#bib.bib32)\), andC4\.5\([Quinlan, 1993](https://arxiv.org/html/2609.38194#bib.bib33)\)have been widely used due to their simplicity and efficiency, employing greedy heuristics to recursively partition data from the root to the leaves\. Although these approaches generate trees efficiently, they fall significantly short of achieving optimality, especially for deeper trees\.

Recent advancements in deterministic optimization techniques for learning ODTs have focused on approaches leveraging mixed\-integer programming \(MIP\), satisfiability \(SAT\) solvers\([Hu et al\., 2020](https://arxiv.org/html/2609.38194#bib.bib24);[Alòs et al\., 2023](https://arxiv.org/html/2609.38194#bib.bib14)\), and dynamic programming \(DP\) approaches\([Nijssen and Fromont, 2007](https://arxiv.org/html/2609.38194#bib.bib31);[Van der Linden et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib36);[van der Linden et al\., 2023](https://arxiv.org/html/2609.38194#bib.bib5)\)\. Among these, MIP\-based methods\([Günlük et al\., 2021](https://arxiv.org/html/2609.38194#bib.bib23);[Zhu et al\., 2020](https://arxiv.org/html/2609.38194#bib.bib38);[Aghaei et al\., 2024](https://arxiv.org/html/2609.38194#bib.bib15)\)formulate the training process as a mixed\-integer optimization problem\([Bertsimas and Dunn, 2017](https://arxiv.org/html/2609.38194#bib.bib18)\)and have achieved notable success by providing global optimization guarantees \(optimality gap\)\. However, efficiency remains a major limitation of these methods\. For example,Quant\-BnB\([Mazumder et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib30)\)andRS\-OCT\([Hua et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib25)\)have demonstrated the ability to generate optimal trees up to depth 3; however, extending these approaches to deeper trees remains computationally hard\. In contrast, some other scalable DP methods, such asDL8\.5\([Aglin et al\., 2020](https://arxiv.org/html/2609.38194#bib.bib16)\)andMurTree\([Demirović et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib20)\), leverage advanced caching strategies to enable the learning of relatively deeper trees\. Despite these advances, most DP\- and SAT\-based approaches\([Huisman et al\., 2024](https://arxiv.org/html/2609.38194#bib.bib26);[Lin et al\., 2020](https://arxiv.org/html/2609.38194#bib.bib29);[Avellaneda, 2020](https://arxiv.org/html/2609.38194#bib.bib17)\)face inherent drawbacks\. They often require binarizing continuous features, which increases the number of features and necessitates approximation techniques fromBinOCT\([Verwer and Zhang, 2019](https://arxiv.org/html/2609.38194#bib.bib37)\)\(some methods directly consider encoding DTs\([Shati et al\., 2023](https://arxiv.org/html/2609.38194#bib.bib1)\)\)\. As a result, these methods solve a feature\-binarized approximation of the original problem, which causes information loss, and they still struggle to build trees deeper than 5 on large datasets\.

Beyond deterministic approaches, several heuristic methods warrant consideration\. One notable example isTAO\([Carreira\-Perpinán and Tavallali, 2018](https://arxiv.org/html/2609.38194#bib.bib4);[Carreira\-Perpiñán and Zharmagambetov, 2020](https://arxiv.org/html/2609.38194#bib.bib10);[Zharmagambetov et al\., 2021](https://arxiv.org/html/2609.38194#bib.bib11)\), which has been reported to yield only modest improvements overCART\([Zhu and Shoaran, 2021](https://arxiv.org/html/2609.38194#bib.bib12);[Mazumder et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib30)\)\. More recently,DPDT\([Kohler et al\., 2025](https://arxiv.org/html/2609.38194#bib.bib13)\)has been proposed, which frames tree induction as a Markov Decision Process in conjunction withCART\. AlthoughDPDThas been shown to outperformCART, its further accuracy gains come at a substantial computational cost, which significantly limits its optimality\. Within practical time budgets, the trees it produces remain far less accurate than global optimal ones\. This gap highlights the urgent need for an advanced method that can deliver both high accuracy and scalability for deep decision trees on large\-scale datasets\.

This paper introduces the Moving\-Horizon Approximate Branch\-and\-Reduce \(MHABR\) algorithm for training deep classification trees on large\-scale datasets with continuous features\. This method is designed to achieve better optimization quality than heuristic methods \(e\.g\.,CART\) while remaining substantially more scalable than global optimal solvers\. Extensive numerical experiments show thatMHABRcan successfully train trees of depth 8 on datasets with up to 60 million samples, achieving stronger optimization quality than the heuristic baselines we evaluate, while scaling to deeper trees and larger datasets than the global methods considered in our experiments\. Additionally, we provide anα\\alpha\-tuning option to mitigate overfitting, along with an extended variant that further improves solution quality and brings the result closer to the global optimum\.

Contributions:\(1\)We propose a hierarchical root\-subtree optimization framework for learning DTs, where the splitting parameters at the root node are optimized according to the values of the two induced child\-subtree optimization problems\.\(2\)Within this framework, we introduce a branch\-and\-reduce \(BR\) method for the root\-search problem\. When the child\-subtree problems are solved recursively and exactly, the framework guarantees convergence to global optimality\.\(3\)To improve efficiency for deep trees, we approximate the child\-subtree problems usingCART\. Under this approximate framework, exactness is retained for depth\-2 trees because the depth\-1 child\-subtree problems are solved exactly\.\(4\)We introduce a moving\-horizon \(MH\) technique to iteratively refine branch parameters at low cost, enabling the training of deep trees on large\-scale datasets\.

Performance:We evaluate the proposed method on 59 UCI datasets\([Dua and Graff, 2017](https://arxiv.org/html/2609.38194#bib.bib21)\), with sample sizes ranging from 47 to 60,807,600 and tree depths from22to88, and compare it against six baselines\.

- •Testing accuracy:On 51 small datasets \(fewer than 10K samples\),MHABRachieves the highest average testing accuracy among the compared methods at depths 2 and 3, excluding datasets for whichQuant\-BnBdoes not converge, and exceedsDL8\.5by 0\.99% on average across the reported depths\. On the 8 medium\- and large\-scale datasets,MHABRimproves average testing accuracy overDPDTby 3\.01% at depth 8\.
- •Scalability:On 5 medium datasets \(10K–1M samples\) and 3 large datasets \(1M–60M samples\),MHABRremains computationally feasible at depth 8, whereas the compared global optimal methods do not complete within the specified time budget\. Across these datasets,MHABRimproves average test accuracy overCARTby 3\.66%\.
- •Optimality:MHABRguarantees global optimality for depth\-2 trees\. On the 42 small datasets completed byQuant\-BnBat depth 3, its average training\-accuracy gap to the global optimum is 0\.58%\.

## 2Preliminary

This paper focuses on training a DT model for a classification task\. The notation primarily follows[Mazumder et al\. \(2022\)](https://arxiv.org/html/2609.38194#bib.bib30)\. We address a supervised learning problem involving a given dataset\{\(xi,yi\)\}i=1n\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{n\}, wherexi∈ℝpx\_\{i\}\\in\\mathbb\{R\}^\{p\}is the feature vector of sampleiiandyi∈𝒴y\_\{i\}\\in\\mathcal\{Y\}is its corresponding class label\. Here,\[n\]:=\{1,⋯,n\}\[n\]:=\\\{1,\\cdots,n\\\},nndenotes the number of samples,ppdenotes the number of features, and𝒴:=\[nc\]=\{1,…,nc\}\\mathcal\{Y\}:=\[n\_\{c\}\]=\\\{1,\\ldots,n\_\{c\}\\\},ncn\_\{c\}denotes the number of classes\. The features may be numerical, categorical, or binary\. Initially, we scale each feature value of the dataset to the range\[0,1\]\[0,\\ 1\]\.

### 2\.1Notations for Decision Trees

The induction of a decision treeT:\[0,1\]p→𝒴T:\[0,1\]^\{p\}\\rightarrow\\mathcal\{Y\}for a group of samples indexed by the setℐ\\mathcal\{I\}can be formulated as an optimization problem expressed as

T∗​\(ℐ\)=arg⁡minT∈𝒯d⁡L⁡\(ℐ,T\),andVd​\(ℐ\):=minT∈𝒯d⁡L​\(ℐ,T\),\\displaystyle T^\{\*\}\(\\mathcal\{I\}\)=\\arg\\min\_\{T\\in\\mathcal\{T\}\_\{d\}\}L\(\\mathcal\{I\},T\),\\quad\\text\{and\}\\quad\\textit\{V\}\_\{d\}\(\\mathcal\{I\}\):=\\min\_\{T\\in\\mathcal\{T\}\_\{d\}\}\\textit\{L\}\(\\mathcal\{I\},T\),\\quad\(1\)where𝒯d\\mathcal\{T\}\_\{d\}represents the family of DT of depthdd,L​\(ℐ,T\):=∑i∈ℐℓ⁡\(yi,T⁡\(xi\)\)\\textit\{L\}\(\\mathcal\{I\},T\):=\\sum\\limits\_\{i\\in\\mathcal\{I\}\}\\ell\(y\_\{i\},T\(x\_\{i\}\)\)denotes the number of misclassified instances associated with treeTTover the samplesℐ\\mathcal\{I\}, andℓ:=𝒴×𝒴→ℝ\\ell:=\\mathcal\{Y\}\\times\\mathcal\{Y\}\\rightarrow\\mathbb\{R\}denotes the loss function\. For classification tasks in this paper, the loss function is defined asℓ\(yi,y^i\)=𝟙\{yi≠y^i\}\\ell\(y\_\{i\},\\hat\{y\}\_\{i\}\)=\\mathbbm\{1\}\\\{y\_\{i\}\\neq\\hat\{y\}\_\{i\}\\\}\. In this formulation, a penalty termα⋅𝒞\\alpha\\cdot\\mathcal\{C\}can be introduced to balance the trade\-off between training accuracy and model generalization, where𝒞\\mathcal\{C\}denotes the complexity of the decision tree model andα\\alphaserves as the regularization coefficient\. However, this paper focuses on optimizing the training process; thus, the penalty term is omitted in this formulation\. The term will later be incorporated into numerical experiments to assess its impact on model performance\.

For a sample index setℐ⊆\[n\]\\mathcal\{I\}\\subseteq\[n\]and featureaa, letℐa\\mathcal\{I\}^\{a\}denote the indices inℐ\\mathcal\{I\}ordered nondecreasingly byxiax\_\{i\}^\{a\}, and letu1a<⋯<unaau\_\{1\}^\{a\}<\\cdots<u\_\{n\_\{a\}\}^\{a\}be thenan\_\{a\}distinct values of featureaaamong these samples\. Defineu0a=u1a−1u\_\{0\}^\{a\}=u\_\{1\}^\{a\}\-1anduna\+1a=unaa\+1u\_\{n\_\{a\}\+1\}^\{a\}=u\_\{n\_\{a\}\}^\{a\}\+1, and let𝒦a:=\{0,…,na\}\\mathcal\{K\}^\{a\}:=\\\{0,\\ldots,n\_\{a\}\\\}index thena\+1n\_\{a\}\+1candidate partitions induced by featureaa\. For eachk∈𝒦ak\\in\\mathcal\{K\}^\{a\}, defineβka:=\(uka\+uk\+1a\)/2\\beta\_\{k\}^\{a\}:=\(u\_\{k\}^\{a\}\+u\_\{k\+1\}^\{a\}\)/2\. Since all thresholds in\(uka,uk\+1a\)\(u\_\{k\}^\{a\},u\_\{k\+1\}^\{a\}\)induce the same partition, it suffices to considerℬa:=\{βka∣k∈𝒦a\}\\mathcal\{B\}^\{a\}:=\\\{\\beta\_\{k\}^\{a\}\\mid k\\in\\mathcal\{K\}^\{a\}\\\}andℬ:=⋃a∈\[p\]ℬa\\mathcal\{B\}:=\\bigcup\_\{a\\in\[p\]\}\\mathcal\{B\}^\{a\}\. For each fixed featureaa, defineζ⁡\(k\):=\|\{i∈ℐ∣xia≤βka\}\|\\zeta\(k\):=\|\\\{i\\in\\mathcal\{I\}\\mid x\_\{i\}^\{a\}\\leq\\beta\_\{k\}^\{a\}\\\}\|, where the dependence onaais suppressed for notational simplicity\. For0≤k1≤k2≤na0\\leq k\_\{1\}\\leq k\_\{2\}\\leq n\_\{a\}, we define

ℐ\[k1,k2\]a:=\{i∈ℐ∣βk1a≤xia≤βk2a\}\.\\displaystyle\\mathcal\{I\}\_\{\[k\_\{1\},k\_\{2\}\]\}^\{a\}:=\\\{i\\in\\mathcal\{I\}\\mid\\beta\_\{k\_\{1\}\}^\{a\}\\leq x\_\{i\}^\{a\}\\leq\\beta\_\{k\_\{2\}\}^\{a\}\\\}\.\(2\)In particular,ℐ\[0,k\]a\\mathcal\{I\}\_\{\[0,k\]\}^\{a\}andℐ\[k,na\]a\\mathcal\{I\}\_\{\[k,n\_\{a\}\]\}^\{a\}are the disjoint sample sets assigned to the left and right children, respectively, by the splitβka\\beta\_\{k\}^\{a\}\.

### 2\.2A Hierarchical Root–Subtree Framework for Decision Tree Training

We propose a hierarchical root\-subtree framework for training decision trees based on the above notation\. We denoteT:=\[a,k,TL,TR\]T:=\[a,k,T\_\{L\},T\_\{R\}\], whereaais the feature selected at the root node,kkdenotes the index of the root split among the candidate thresholds for featureaa\(that is, the threshold isβka\\beta^\{a\}\_\{k\}\), andTLT\_\{L\}andTRT\_\{R\}are the left and right subtrees, respectively\. The root node typically exerts the most significant influence on the overall loss in a decision tree\([Dwyer and Holte, 2007](https://arxiv.org/html/2609.38194#bib.bib3);[Shannon and Banks, 1999](https://arxiv.org/html/2609.38194#bib.bib2)\), as it processes the entire dataset due to its position at the top of the data flow\. Consequently, we isolate the parameters of the root node from the remainder of the tree for optimization through a root\-level problem \(RLP\)\. The optimal loss is subsequently defined as the sum of the losses from the two subtrees:TLT\_\{L\}andTRT\_\{R\}, optimized in the child\-subtree problem \(CSP\)\. Then, the optimization problem for training a depth\-ddtreeTTcan be denoted as:

Vd​\(ℐ\):=mina∈\[p\],k∈𝒦aTL,TR∈𝒯d−1L⁡\(ℐ,\[a,k,TL,TR\]\)=mina∈\[p\],k∈𝒦a⁡\{Vd−1​\(ℐ\[0,k\]a\)\+Vd−1​\(ℐ\[k,na\]a\)\},\\displaystyle\\textit\{V\}\_\{d\}\(\\mathcal\{I\}\):=\\mathop\{\\min\}\_\{a\\in\[p\],\\ k\\in\\mathcal\{K\}^\{a\}\\atop T\_\{L\},T\_\{R\}\\in\\mathcal\{T\}\_\{d\-1\}\}L\(\\mathcal\{I\},\[a,k,T\_\{L\},T\_\{R\}\]\)=\\min\_\{a\\in\[p\],\\ k\\in\\mathcal\{K\}^\{a\}\}\\left\\\{V\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}\)\+V\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\)\\right\\\},\(3\)
as well as a hierarchical root\-subtree form:

mina∈\[p\],k∈𝒦a\{minTL∈𝒯d−1⁡L⁡\(ℐ\[0,k\]a,TL\)\+minTR∈𝒯d−1⁡L⁡\(ℐ\[k,na\]a,TR\)\},\\displaystyle\\mathop\{\\min\}\_\{a\\in\[p\],\\ k\\in\\mathcal\{K\}^\{a\}\}\\\!\\\!\\left\\\{\\min\_\{T\_\{L\}\\in\\mathcal\{T\}\_\{d\-1\}\}\\\!\\\!L\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\},T\_\{L\}\)\\\!\+\\\!\\min\_\{T\_\{R\}\\in\\mathcal\{T\}\_\{d\-1\}\}\\\!\\\!L\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\},T\_\{R\}\)\\right\\\},\(4\)where the samples split to the left and right subtrees are denoted byℐ\[0,k\]a\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}andℐ\[k,na\]a\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\. In addition, we use a similar notation to define the optimal value whenaais fixed, or whenaaandkkare both fixed\.

Vd​\(ℐ,a\)=mink∈𝒦a⁡Vd​\(ℐ,a,k\)=\\displaystyle\\textit\{V\}\_\{d\}\(\\mathcal\{I\},a\)=\\min\_\{k\\in\\mathcal\{K\}^\{a\}\}\\textit\{V\}\_\{d\}\(\\mathcal\{I\},a,k\)=mink∈𝒦a⁡\{Vd−1​\(ℐ\[0,k\]a\)\+Vd−1​\(ℐ\[k,na\]a\)\}\.\\displaystyle\\min\_\{k\\in\\mathcal\{K\}^\{a\}\}\\left\\\{V\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}\)\+V\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\)\\right\\\}\.\(5\)

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

The hierarchical framework, which is explored inBRmethod \(detailed in[Section3\.2](https://arxiv.org/html/2609.38194#S3.SS2)\), forms the basis of the approach discussed in this section\. Here, we present this approach for solvingRLP, under the key assumption thatCSPscan be solved exactly and efficiently\.

Within theRLP, the decision variables areaaandkk\. The variablea∈\[p\]a\\in\[p\]can be readily enumerated given the typically limited number of features\. However, the selection ofk∈𝒦ak\\in\\mathcal\{K\}^\{a\}is more complex, contingent upon the number of unique feature valuesnan\_\{a\}\. For continuous features,nan\_\{a\}can be as large asnn, rendering the search space prohibitively extensive for exhaustive enumeration\. To mitigate this challenge, we propose theBRmethod to determine the optimalkkin this section\.

### 3\.1Upper Bound, Lower Bound, Reduction, and Branching Strategy

TheBRmethod involves four primary steps: Upper Bound, Lower Bound, Reduction Strategy, and Branching Strategy\. We now present their details in a general form\. Consider a node within theBRprocess, represented by the set of potential split indices𝒦i=\{k∈𝒦a∣l≤k≤m\}\\mathcal\{K\}\_\{i\}=\\\{k\\in\\mathcal\{K\}^\{a\}\\mid l\\leq k\\leq m\\\}, where0≤l≤m≤na0\\leq l\\leq m\\leq n\_\{a\}\. In the following description, we specifically select the midpointk¯=⌈l\+m2⌉\\bar\{k\}=\\lceil\\frac\{l\+m\}\{2\}\\rceil\(the midpoint of𝒦i\\mathcal\{K\}\_\{i\}\) for branching\.

##### Upper Bound

The upper boundUUdenotes the best loss among previously evaluated splits, serving as a historical record throughout the iterative search within the feasible set\. It is updated iteratively after evaluating a selected indexk¯\\bar\{k\}by:

U←min⁡\{U,Vd​\(ℐ,a,k¯\)\},where​Vd​\(ℐ,a,k¯\)=Vd−1​\(ℐ\[0,k¯\]a\)\+Vd−1​\(ℐ\[k¯,na\]a\)\.\\displaystyle U\\leftarrow\\min\\\{U,\\ V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\\\},\\quad\\text\{where\}\\ V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)=\\textit\{V\}\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\}\)\+\\textit\{V\}\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\}\)\.\(6\)

##### Boundary Analysis

DefineL⁡\(ℐ\)L\(\\mathcal\{I\}\)as the optimal loss of the dataset indexed byℐ\\mathcal\{I\}when training a DT of a fixed depth:

L⁡\(ℐ\)=minT∈𝒯⁡L⁡\(ℐ,T\)\.\\displaystyle L\(\\mathcal\{I\}\)=\\min\_\{T\\in\\mathcal\{T\}\}L\(\\mathcal\{I\},T\)\.\(7\)The following lemma bounds the loss functionLLin[Equation1](https://arxiv.org/html/2609.38194#S2.E1)\.

###### Lemma 3\.1\.

For two sample index setsℐ1\\mathcal\{I\}\_\{1\}andℐ2\\mathcal\{I\}\_\{2\}withℐ1⊆ℐ2\\mathcal\{I\}\_\{1\}\\subseteq\\mathcal\{I\}\_\{2\}, letn1n\_\{1\}andn2n\_\{2\}be the element numbers ofℐ1\\mathcal\{I\}\_\{1\}andℐ2\\mathcal\{I\}\_\{2\}, wheren2≥n1n\_\{2\}\\geq n\_\{1\}\. Then

0≤L⁡\(ℐ2\)−L⁡\(ℐ1\)≤n2−n1\.0\\leq L\(\\mathcal\{I\}\_\{2\}\)\-L\(\\mathcal\{I\}\_\{1\}\)\\leq n\_\{2\}\-n\_\{1\}\.

###### Proof\.

From the formulation of[Equation1](https://arxiv.org/html/2609.38194#S2.E1), we have:

L⁡\(ℐ1\)=min⁡∑i∈ℐ1T∈𝒯⁡ℓ⁡\(yi,T⁡\(xi\)\)\\displaystyle L\(\\mathcal\{I\}\_\{1\}\)=\\min\_\{T\\in\\mathcal\{T\}\}\\sum\_\{i\\in\\mathcal\{I\}\_\{1\}\}\\ell\(y\_\{i\},T\(x\_\{i\}\)\)≤min⁡∑i∈ℐ1∪\{ℐ2\\ℐ1\}T∈𝒯⁡ℓ⁡\(yi,T⁡\(xi\)\)\\displaystyle\\leq\\min\_\{T\\in\\mathcal\{T\}\}\\sum\_\{i\\in\\mathcal\{I\}\_\{1\}\\cup\\\{\\mathcal\{I\}\_\{2\}\\backslash\\mathcal\{I\}\_\{1\}\\\}\}\\ell\(y\_\{i\},T\(x\_\{i\}\)\)=min⁡∑i∈ℐ2T∈𝒯⁡ℓ⁡\(yi,T⁡\(xi\)\)=L⁡\(ℐ2\)\.\\displaystyle=\\min\_\{T\\in\\mathcal\{T\}\}\\sum\_\{i\\in\\mathcal\{I\}\_\{2\}\}\\ell\(y\_\{i\},T\(x\_\{i\}\)\)=L\(\\mathcal\{I\}\_\{2\}\)\.\(8\)So, we haveL⁡\(ℐ1\)≤L⁡\(ℐ2\)L\(\\mathcal\{I\}\_\{1\}\)\\leq L\(\\mathcal\{I\}\_\{2\}\), which implies that prediction errors monotonically increase with sample numbers\. Suppose the optimal tree forℐ1\\mathcal\{I\}\_\{1\}isT1∗T^\{\*\}\_\{1\}, and forℐ2\\mathcal\{I\}\_\{2\}we have

L⁡\(ℐ2\)\\displaystyle L\(\\mathcal\{I\}\_\{2\}\)≤L⁡\(ℐ2,T1∗\)=∑i∈ℐ2ℓ⁡\(yi,T1∗​\(xi\)\)\\displaystyle\\leq L\(\\mathcal\{I\}\_\{2\},T^\{\*\}\_\{1\}\)=\\sum\_\{i\\in\\mathcal\{I\}\_\{2\}\}\\ell\(y\_\{i\},T^\{\*\}\_\{1\}\(x\_\{i\}\)\)=∑i∈ℐ1ℓ⁡\(yi,T1∗​\(xi\)\)\+∑i∈ℐ2\\ℐ1ℓ⁡\(yi,T1∗​\(xi\)\)\\displaystyle=\\sum\_\{i\\in\\mathcal\{I\}\_\{1\}\}\\ell\(y\_\{i\},T^\{\*\}\_\{1\}\(x\_\{i\}\)\)\+\\sum\_\{i\\in\\mathcal\{I\}\_\{2\}\\backslash\\mathcal\{I\}\_\{1\}\}\\ell\(y\_\{i\},T^\{\*\}\_\{1\}\(x\_\{i\}\)\)=L⁡\(ℐ1\)\+∑i∈ℐ2\\ℐ1ℓ⁡\(yi,T1∗​\(xi\)\),\\displaystyle=L\(\\mathcal\{I\}\_\{1\}\)\+\\sum\_\{i\\in\\mathcal\{I\}\_\{2\}\\backslash\\mathcal\{I\}\_\{1\}\}\\ell\(y\_\{i\},T^\{\*\}\_\{1\}\(x\_\{i\}\)\),\(9\)where the first inequality is becauseL⁡\(ℐ2\)L\(\\mathcal\{I\}\_\{2\}\)is the optimal value\. Then we get:

L⁡\(ℐ2\)−L⁡\(ℐ1\)\\displaystyle L\(\\mathcal\{I\}\_\{2\}\)\-L\(\\mathcal\{I\}\_\{1\}\)≤∑i∈ℐ2\\ℐ1ℓ⁡\(yi,T1∗​\(xi\)\)≤∑i∈ℐ2\\ℐ11=n2−n1\.\\displaystyle\\leq\\sum\_\{i\\in\\mathcal\{I\}\_\{2\}\\backslash\\mathcal\{I\}\_\{1\}\}\\ell\(y\_\{i\},T^\{\*\}\_\{1\}\(x\_\{i\}\)\)\\leq\\sum\_\{i\\in\\mathcal\{I\}\_\{2\}\\backslash\\mathcal\{I\}\_\{1\}\}\\textbf\{1\}=n\_\{2\}\-n\_\{1\}\.\(10\)Now we have0≤L⁡\(ℐ2\)−L⁡\(ℐ1\)≤n2−n10\\leq L\(\\mathcal\{I\}\_\{2\}\)\-L\(\\mathcal\{I\}\_\{1\}\)\\leq n\_\{2\}\-n\_\{1\}, which bounds the loss functionLL\. ∎

##### Lower Bound

The lower bound is based on a Lipschitz\-type condition, which is illustrated by:

###### Lemma 3\.2\.

For anyℐ⊆\[n\]\\mathcal\{I\}\\subseteq\[n\]andd≥1d\\geq 1, letk1k\_\{1\}andk2k\_\{2\}be two split indices corresponding to featureaa\. Then we have\|Vd​\(ℐ,a,k1\)−Vd​\(ℐ,a,k2\)\|≤\|ζ⁡\(k1\)−ζ⁡\(k2\)\|\.\\lvert V\_\{d\}\(\\mathcal\{I\},a,k\_\{1\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k\_\{2\}\)\\rvert\\leq\\lvert\\zeta\(k\_\{1\}\)\-\\zeta\(k\_\{2\}\)\\rvert\.

###### Proof\.

Without loss of generality, suppose0≤k1≤k2≤na0\\leq k\_\{1\}\\leq k\_\{2\}\\leq n\_\{a\}, and letL⁡\(ℐ\)L\(\\mathcal\{I\}\)be defined as in[Equation7](https://arxiv.org/html/2609.38194#S3.E7)\. From[Equation3](https://arxiv.org/html/2609.38194#S2.E3), we have

Vd​\(ℐ,a,k1\)\\displaystyle V\_\{d\}\(\\mathcal\{I\},a,k\_\{1\}\)=L⁡\(ℐ\[0,k1\]a\)\+L⁡\(ℐ\[k1,na\]a\),\\displaystyle=L\(\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{1\}\]\}\)\+L\(\\mathcal\{I\}^\{a\}\_\{\[k\_\{1\},n\_\{a\}\]\}\),\(11\)Vd​\(ℐ,a,k2\)\\displaystyle V\_\{d\}\(\\mathcal\{I\},a,k\_\{2\}\)=L⁡\(ℐ\[0,k2\]a\)\+L⁡\(ℐ\[k2,na\]a\)\.\\displaystyle=L\(\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{2\}\]\}\)\+L\(\\mathcal\{I\}^\{a\}\_\{\[k\_\{2\},n\_\{a\}\]\}\)\.\(12\)Subtracting the two expressions gives

Vd​\(ℐ,a,k2\)−Vd​\(ℐ,a,k1\)\\displaystyle V\_\{d\}\(\\mathcal\{I\},a,k\_\{2\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k\_\{1\}\)=\{L⁡\(ℐ\[0,k2\]a\)−L⁡\(ℐ\[0,k1\]a\)\}−\{L⁡\(ℐ\[k1,na\]a\)−L⁡\(ℐ\[k2,na\]a\)\}\.\\displaystyle=\\left\\\{L\(\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{2\}\]\}\)\-L\(\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{1\}\]\}\)\\right\\\}\-\\left\\\{L\(\\mathcal\{I\}^\{a\}\_\{\[k\_\{1\},n\_\{a\}\]\}\)\-L\(\\mathcal\{I\}^\{a\}\_\{\[k\_\{2\},n\_\{a\}\]\}\)\\right\\\}\.\(13\)
Sinceℐ\[0,k1\]a⊆ℐ\[0,k2\]a\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{1\}\]\}\\subseteq\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{2\}\]\}andℐ\[k2,na\]a⊆ℐ\[k1,na\]a\\mathcal\{I\}^\{a\}\_\{\[k\_\{2\},n\_\{a\}\]\}\\subseteq\\mathcal\{I\}^\{a\}\_\{\[k\_\{1\},n\_\{a\}\]\}, Lemma[3\.1](https://arxiv.org/html/2609.38194#S3.Thmtheorem1)gives

0\\displaystyle 0≤L⁡\(ℐ\[0,k2\]a\)−L⁡\(ℐ\[0,k1\]a\)≤ζ⁡\(k2\)−ζ⁡\(k1\),\\displaystyle\\leq L\(\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{2\}\]\}\)\-L\(\\mathcal\{I\}^\{a\}\_\{\[0,k\_\{1\}\]\}\)\\leq\\zeta\(k\_\{2\}\)\-\\zeta\(k\_\{1\}\),0\\displaystyle 0≤L⁡\(ℐ\[k1,na\]a\)−L⁡\(ℐ\[k2,na\]a\)≤ζ⁡\(k2\)−ζ⁡\(k1\)\.\\displaystyle\\leq L\(\\mathcal\{I\}^\{a\}\_\{\[k\_\{1\},n\_\{a\}\]\}\)\-L\(\\mathcal\{I\}^\{a\}\_\{\[k\_\{2\},n\_\{a\}\]\}\)\\leq\\zeta\(k\_\{2\}\)\-\\zeta\(k\_\{1\}\)\.Using the nonnegativity of the second difference in[Equation13](https://arxiv.org/html/2609.38194#S3.E13), we obtain

Vd​\(ℐ,a,k2\)−Vd​\(ℐ,a,k1\)≤ζ⁡\(k2\)−ζ⁡\(k1\)\.\\displaystyle V\_\{d\}\(\\mathcal\{I\},a,k\_\{2\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k\_\{1\}\)\\leq\\zeta\(k\_\{2\}\)\-\\zeta\(k\_\{1\}\)\.Similarly, using the nonnegativity of the first difference,

Vd​\(ℐ,a,k2\)−Vd​\(ℐ,a,k1\)≥−\(ζ⁡\(k2\)−ζ⁡\(k1\)\)\.\\displaystyle V\_\{d\}\(\\mathcal\{I\},a,k\_\{2\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k\_\{1\}\)\\geq\-\\bigl\(\\zeta\(k\_\{2\}\)\-\\zeta\(k\_\{1\}\)\\bigr\)\.Combining these inequalities yields

\|Vd​\(ℐ,a,k2\)−Vd​\(ℐ,a,k1\)\|≤ζ⁡\(k2\)−ζ⁡\(k1\)=\|ζ⁡\(k2\)−ζ⁡\(k1\)\|\.\\displaystyle\\left\|V\_\{d\}\(\\mathcal\{I\},a,k\_\{2\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k\_\{1\}\)\\right\|\\leq\\zeta\(k\_\{2\}\)\-\\zeta\(k\_\{1\}\)=\\left\|\\zeta\(k\_\{2\}\)\-\\zeta\(k\_\{1\}\)\\right\|\.\(14\)The result follows by symmetry\. ∎

From Lemma[3\.2](https://arxiv.org/html/2609.38194#S3.Thmtheorem2), for a given loss ofk¯\\bar\{k\}, the lower bound of𝒦i\\mathcal\{K\}\_\{i\}is

L​B:=min⁡\{Vd​\(ℐ,a,k¯\)−\|ζ⁡\(k¯\)−ζ⁡\(l\)\|,Vd​\(ℐ,a,k¯\)−\|ζ⁡\(k¯\)−ζ⁡\(m\)\|\}\\displaystyle LB:=\\min\\\{V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-\\lvert\\zeta\(\\bar\{k\}\)\-\\zeta\(l\)\\rvert,V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-\\lvert\\zeta\(\\bar\{k\}\)\-\\zeta\(m\)\\rvert\\\}\(15\)

##### Reduction Strategy

GivenVd​\(ℐ,a,k¯\)V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)and an upper boundU≤Vd​\(ℐ,a,k¯\)U\\leq V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\), defineδ⁡\(k¯\):=Vd​\(ℐ,a,k¯\)−U\\delta\(\\bar\{k\}\):=V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-UandΔi:=\{k∈𝒦i∣\|ζ⁡\(k\)−ζ⁡\(k¯\)\|≤δ⁡\(k¯\)\}\\Delta\_\{i\}:=\\left\\\{k\\in\\mathcal\{K\}\_\{i\}\\mid\|\\zeta\(k\)\-\\zeta\(\\bar\{k\}\)\|\\leq\\delta\(\\bar\{k\}\)\\right\\\}\. The following lemma shows that no candidate inΔi\\Delta\_\{i\}can strictly improveUU; hence, we update𝒦i←𝒦i∖Δi\\mathcal\{K\}\_\{i\}\\leftarrow\\mathcal\{K\}\_\{i\}\\setminus\\Delta\_\{i\}\.

###### Lemma 3\.3\.

Under the above definitions, for anyℐ⊆\[n\]\\mathcal\{I\}\\subseteq\[n\]andd≥1d\\geq 1, everyk∈Δik\\in\\Delta\_\{i\}satisfiesVd​\(ℐ,a,k\)≥UV\_\{d\}\(\\mathcal\{I\},a,k\)\\geq U\. Therefore, removingΔi\\Delta\_\{i\}while retaining the incumbent solution preserves the global optimum\.

###### Proof\.

Suppose there is a splitk′∈Δik^\{\\prime\}\\in\\Delta\_\{i\}such thatVd​\(ℐ,a,k′\)<UV\_\{d\}\(\\mathcal\{I\},a,k^\{\\prime\}\)<U\. By Lemma[3\.2](https://arxiv.org/html/2609.38194#S3.Thmtheorem2), we have

\|Vd​\(ℐ,a,k¯\)−Vd​\(ℐ,a,k′\)\|≤\|ζ⁡\(k¯\)−ζ⁡\(k′\)\|≤δ⁡\(k¯\)=Vd​\(ℐ,a,k¯\)−U\.\\displaystyle\\lvert V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k^\{\\prime\}\)\\rvert\\leq\\lvert\\zeta\(\\bar\{k\}\)\-\\zeta\(k^\{\\prime\}\)\\rvert\\leq\\delta\(\\bar\{k\}\)=V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-U\.\(16\)However, sinceVd​\(ℐ,a,k′\)<U≤Vd​\(ℐ,a,k¯\)V\_\{d\}\(\\mathcal\{I\},a,k^\{\\prime\}\)<U\\leq V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\), we have

\|Vd​\(ℐ,a,k¯\)−Vd​\(ℐ,a,k′\)\|=Vd​\(ℐ,a,k¯\)−Vd​\(ℐ,a,k′\)\>Vd​\(ℐ,a,k¯\)−U,\\displaystyle\\lvert V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k^\{\\prime\}\)\\rvert=V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-V\_\{d\}\(\\mathcal\{I\},a,k^\{\\prime\}\)\>V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-U,\(17\)which is a contradiction of[Equation16](https://arxiv.org/html/2609.38194#S3.E16)\. Therefore,Vd​\(ℐ,a,k\)≥UV\_\{d\}\(\\mathcal\{I\},a,k\)\\geq Ufor everyk∈Δik\\in\\Delta\_\{i\}\. Since the incumbent solution with valueUUis retained, removingΔi\\Delta\_\{i\}preserves the global optimum\. ∎

##### Branching Strategy

To facilitate reduction, the branching strategy bisects the candidate split set at itsmidpointk¯\\bar\{k\}, ensuring a balanced and effective reduction\([Ryoo and Sahinidis, 1996](https://arxiv.org/html/2609.38194#bib.bib39);[Tawarmalani and Sahinidis, 2004](https://arxiv.org/html/2609.38194#bib.bib40)\)\. We can divide𝒦i\\mathcal\{K\}\_\{i\}by the midpointk¯\\bar\{k\}into two subsets:𝒦L\\mathcal\{K\}\_\{L\}and𝒦R\\mathcal\{K\}\_\{R\}after reduction\.

### 3\.2The Procedure of Branch\-and\-Reduce Method

Now, we are ready to introduce the procedure of ourBRmethod\. This method is designed to learn global optimal depth\-dddecision trees\. The process begins with an initial estimate \(e\.g\., usingCART\) of the upper boundUUand the datasetℐ\\mathcal\{I\}\. Fora∈\[p\]a\\in\[p\], the algorithm sorts the samples by their feature values to obtainℐa\\mathcal\{I\}^\{a\}and constructs the candidate split setℬa\\mathcal\{B\}^\{a\}\. The corresponding index set𝒦a\\mathcal\{K\}^\{a\}contains all split candidatesβka\\beta^\{a\}\_\{k\}fork∈𝒦ak\\in\\mathcal\{K\}^\{a\}, which is then passed to the main loop to obtain the optimalkk\.

1:functionExactTreeSearch\(

ℐ,d\\mathcal\{I\},d\):

2:Initialize

UUand

TTbyCART;

3:for

a∈\[p\]a\\in\[p\]do

4:Sort

ℐ\\mathcal\{I\}to obtain

ℐa\\mathcal\{I\}^\{a\},

𝒦a\\mathcal\{K\}^\{a\}, and set

𝕂←\{𝒦a\}\\mathbb\{K\}\\leftarrow\\\{\\mathcal\{K\}^\{a\}\\\};

5:

U,T←ExactSplitSearch​\(U,T,ℐa,a,d,𝕂\)U,T\\leftarrow\\texttt\{ExactSplitSearch\}\(U,T,\\mathcal\{I\}^\{a\},a,d,\\mathbb\{K\}\);\#102\.34375ptsolve for optimal trees

6:return:Optimal loss

UUand decision tree

TT\.

7:functionExactSplitSearch\(

U,T,ℐa,a,d,𝕂U,T,\\mathcal\{I\}^\{a\},a,d,\\mathbb\{K\}\):

8:Initialize the iteration index

i=0i=0,

L​B=0LB=0;

9:while

𝕂≠∅\\mathbb\{K\}\\neq\\emptysetdo

10:node selection

11:Select

𝒦i\\mathcal\{K\}\_\{i\}from

𝕂\\mathbb\{K\}, set

𝕂←𝕂\\\{𝒦i\}\\mathbb\{K\}\\leftarrow\\mathbb\{K\}\\backslash\\\{\\mathcal\{K\}\_\{i\}\\\}, and update

i←i\+1i\\leftarrow i\+1;

12:upper bound

13:Select the midpoint

k¯∈𝒦i\\bar\{k\}\\in\\mathcal\{K\}\_\{i\}, obtain

ℐ\[0,k¯\]a\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\},

ℐ\[k¯,na\]a\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\};

14:

\(Vd−1\(ℐ\[0,k¯\]a\),TL\)←ExactTreeSearch\(ℐ\[0,k¯\]a,d−1\)\(\\textit\{V\}\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\}\),\\ \\ T\_\{L\}\)\\leftarrow\\texttt\{ExactTreeSearch\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\},d\-1\),

15:

\(Vd−1​\(ℐ\[k¯,na\]a\),TR\)←ExactTreeSearch​\(ℐ\[k¯,na\]a,d−1\)\(\\textit\{V\}\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\}\),T\_\{R\}\)\\leftarrow\\texttt\{ExactTreeSearch\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\},d\-1\);

16:Evaluate loss

Vd​\(ℐ,a,k¯\)=Vd−1​\(ℐ\[0,k¯\]a\)\+Vd−1​\(ℐ\[k¯,na\]a\)\\textit\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\\\!=\\\!\\textit\{V\}\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\}\)\\\!\+\\\!\\textit\{V\}\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\}\);

17:if

Vd​\(ℐ,a,k¯\)<U\\textit\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)<Uthen

18:

U←Vd​\(ℐ,a,k¯\)U\\leftarrow\\textit\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\), update

T←\[a,k¯,TL,TR\]T\\leftarrow\[a,\\bar\{k\},T\_\{L\},T\_\{R\}\];

19:lower bound

20:Calculate

L​BLBby[Equation15](https://arxiv.org/html/2609.38194#S3.E15), and obtain the optimality gap

U−L​BU\-LB;

21:if

U−L​B≤0U\-LB\\leq 0then

22:continue\#112\.3103ptprune the current region

23:reduction

24:

δ⁡\(k¯\)←Vd​\(ℐ,a,k¯\)−U\\delta\(\\bar\{k\}\)\\leftarrow V\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-U, and get

Δi=\{k∈𝒦i:\|ζ⁡\(k\)−ζ⁡\(k¯\)\|≤δ⁡\(k¯\)\}\\Delta\_\{i\}=\\\{k\\in\\mathcal\{K\}\_\{i\}:\|\\zeta\(k\)\-\\zeta\(\\bar\{k\}\)\|\\leq\\delta\(\\bar\{k\}\)\\\},

25:branching

26:Divide the

𝒦i\\mathcal\{K\}\_\{i\}into

𝒦L=\{k∈𝒦i∖Δi:k<k¯\}\\mathcal\{K\}\_\{L\}=\\\{k\\in\\mathcal\{K\}\_\{i\}\\setminus\\Delta\_\{i\}:k<\\bar\{k\}\\\}, and

𝒦R=\{k∈𝒦i∖Δi:k\>k¯\}\\mathcal\{K\}\_\{R\}=\\\{k\\in\\mathcal\{K\}\_\{i\}\\setminus\\Delta\_\{i\}:k\>\\bar\{k\}\\\};

27:Update

𝕂←𝕂∪\{𝒦L\}\\mathbb\{K\}\\leftarrow\\mathbb\{K\}\\cup\\\{\\mathcal\{K\}\_\{L\}\\\}, if

𝒦L≠∅\\mathcal\{K\}\_\{L\}\\neq\\emptyset,

𝕂←𝕂∪\{𝒦R\}\\mathbb\{K\}\\leftarrow\\mathbb\{K\}\\cup\\\{\\mathcal\{K\}\_\{R\}\\\}, if

𝒦R≠∅\\mathcal\{K\}\_\{R\}\\neq\\emptyset;

28:return:Optimal loss

UUand decision tree

TT\.

Algorithm 1Branch\-and\-reduce method \(BR\)The main loop of theBRmethod solves for

Vd​\(ℐ,a\)\\textit\{V\}\_\{d\}\(\\mathcal\{I\},a\)with fixed

aa\. At each iteration, the steps of this loop are as follows:\(i\)ABRnode containing the set

𝒦i\\mathcal\{K\}\_\{i\}is selected from the entire feasible region of

kk, a step referred to asBRnode selection\.\(ii\)The midpoint candidate split

k¯\\bar\{k\}is then chosen from

𝒦i\\mathcal\{K\}\_\{i\}\. The algorithm evaluates

Vd​\(ℐ,a,k¯\)\\textit\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\), and updates the upper bound if the new solution improves upon the current best result\.\(iii\)Computing

δ⁡\(k¯\)\\delta\(\\bar\{k\}\)by the updated upper bound

UU, the reduction strategy narrows down the set

𝒦i\\mathcal\{K\}\_\{i\}\.\(iv\)Once the reduced set is determined, branching occurs on the remaining region\. While the lower bound from[Equation15](https://arxiv.org/html/2609.38194#S3.E15)enables the calculation of the optimality gap and termination based on a specified tolerance, to ensure a fair comparison with state\-of\-the\-art methods, the subsequent method employs a complete search strategy with a tolerance of

00\. Therefore, we consider terminating the main loop when

𝕂=∅\\mathbb\{K\}=\\emptyset\. We can easily prove that[Algorithm1](https://arxiv.org/html/2609.38194#alg1)converges to theglobal optimumof[Equation3](https://arxiv.org/html/2609.38194#S2.E3)based on Lemmas[3\.2](https://arxiv.org/html/2609.38194#S3.Thmtheorem2)and[3\.3](https://arxiv.org/html/2609.38194#S3.Thmtheorem3)\.

###### Theorem 3\.4\.

[Algorithm1](https://arxiv.org/html/2609.38194#alg1)converges to the global optimum of[Equation3](https://arxiv.org/html/2609.38194#S2.E3)\.

###### Proof\.

Since[Equation3](https://arxiv.org/html/2609.38194#S2.E3)has a hierarchical structure, we prove the result by induction on the tree depth\. We begin with the case of a depth\-1 tree \(includingR\-CART\), where theCSPcorresponds to optimizing a constant fit\. To establish the optimality of[Algorithm1](https://arxiv.org/html/2609.38194#alg1)for a depth\-1 tree, it suffices to show that the reduction strategy does not exclude any optimal solution, as the algorithm without reduction effectively performs an exhaustive enumeration\. Lemma[3\.3](https://arxiv.org/html/2609.38194#S3.Thmtheorem3)demonstrates that no candidate that can strictly improve the incumbent is removed from the reduced setΔ\\Delta; therefore, pruning preserves the global optimal objective value\.

Next, we assume that[Algorithm1](https://arxiv.org/html/2609.38194#alg1)converges to the global optimal solution for a depth\-\(d−1\)\(d\-1\)tree\. For a depth\-ddtree, eachCSPsubproblem corresponds to optimizing a depth\-\(d−1\)\(d\-1\)tree, which, by assumption, is solved to global optimality\. TheRLPfollows the same proof structure as the depth\-1 case\. Consequently, by induction,[Algorithm1](https://arxiv.org/html/2609.38194#alg1)converges to the global optimum of[Equation3](https://arxiv.org/html/2609.38194#S2.E3)\. ∎

## 4A Moving\-Horizon Approximate Method for Deep Trees

In the above hierarchical optimization framework, we assume that each valueVd−1V\_\{d\-1\}in aCSPis computed exactly\. Under this assumption, global convergence can be guaranteed for trees of any depth\. This condition can be satisfied by recursively callingBRforCSPs, but it results in an exponential increase in computational time\. To address this limitation, this section introduces an approximate method that significantly improves computational efficiency while maintaining high accuracy\. Despite the approximation, we show that the global optimality for depth\-2 trees is still guaranteed\.

### 4\.1Child\-Subtree Approximation

In tree structures, the influence of individual nodes on classification loss generally decreases with depth, as deeper nodes tend to affect fewer data points\. This implies thatCSPshave less impact on overall accuracy compared toRLP\. Consequently, we employ theCARTalgorithm to obtain approximate solutions forCSPs\. This method offers computational efficiency in addressing theCSPs, with limited impact on the optimality, but substantially reducing the overall computational demand\. LetWd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)denote the loss of a depth\-ddCARTtreeT^\\hat\{T\}on datasetℐ\\mathcal\{I\}\. TheCARTsplitting rule for each branch node typically involves minimizing the combined loss of the potential children \(detailed in[Section9\.1](https://arxiv.org/html/2609.38194#S9.SS1)\)\. In our implementation, we use the result of this approximate method to update the upper bound, where the approximate problem is denoted as

V^d​\(ℐ\):=mina∈\[p\],k∈𝒦a⁡V^d​\(ℐ,a,k\)=mina∈\[p\],k∈𝒦a⁡\{Wd−1​\(ℐ\[0,k\]a\)\+Wd−1​\(ℐ\[k,na\]a\)\}\.\\displaystyle\\hat\{V\}\_\{d\}\(\\mathcal\{I\}\):=\\min\_\{a\\in\[p\],k\\in\\mathcal\{K\}^\{a\}\}\\hat\{V\}\_\{d\}\(\\mathcal\{I\},a,k\)=\\min\_\{a\\in\[p\],k\\in\\mathcal\{K\}^\{a\}\}\\\{W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}\)\+W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\)\\\}\.\(18\)Compared toCART, this formulation performs a broader root\-level search under approximate subtree evaluation, leading to improved accuracy, which is essential for the effectiveness of the following MH procedure\. Drawing upon the procedural steps ofBR, we can obtain anapproximate branch\-and\-reduce \(ABR\)method to solveV^d​\(ℐ\)\\hat\{V\}\_\{d\}\(\\mathcal\{I\}\), detailed in[Algorithm2](https://arxiv.org/html/2609.38194#alg2)\. Then, we have the following lemma, stating thatABRis no worse thanCARTin this case\.

###### Lemma 4\.1\.

LetUABR​\(ℐ,d\)U\_\{\\texttt\{ABR\}\}\(\\mathcal\{I\},d\)denote the loss returned by[Algorithm2](https://arxiv.org/html/2609.38194#alg2)for a depth\-ddtree, and letWd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)denote the loss of the depth\-ddCARTtree \(detailed in[Section9\.1](https://arxiv.org/html/2609.38194#S9.SS1)\) used to initialize the algorithm\. Then the following statements hold\.

1. 1\.With or without the reduction strategy,V^d​\(ℐ\)≤UABR​\(ℐ,d\)≤Wd​\(ℐ\)\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)\\leq U\_\{\\texttt\{ABR\}\}\(\\mathcal\{I\},d\)\\leq W\_\{d\}\(\\mathcal\{I\}\)\.
2. 2\.If the reduction is disabled, thenUABR​\(ℐ,d\)=V^d​\(ℐ\)U\_\{\\texttt\{ABR\}\}\(\\mathcal\{I\},d\)=\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)\.
3. 3\.Ford=2d=2,[Algorithm2](https://arxiv.org/html/2609.38194#alg2)converges to theglobal optimal tree, even when the reduction strategy is applied\.

###### Proof\.

We first establish the relationship betweenV^d​\(ℐ\)\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)andWd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)\. If the depth\-ddCARTtree is nonterminal, let\(a′,k′\)\(a^\{\\prime\},k^\{\\prime\}\)denote the root split selected byCART\. By the recursive definition ofCART,

Wd​\(ℐ\)\\displaystyle W\_\{d\}\(\\mathcal\{I\}\)=Wd−1​\(ℐ\[0,k′\]a′\)\+Wd−1​\(ℐ\[k′,na′\]a′\)\\displaystyle=W\_\{d\-1\}\(\\mathcal\{I\}^\{a^\{\\prime\}\}\_\{\[0,k^\{\\prime\}\]\}\)\+W\_\{d\-1\}\(\\mathcal\{I\}^\{a^\{\\prime\}\}\_\{\[k^\{\\prime\},n\_\{a^\{\\prime\}\}\]\}\)=V^d​\(ℐ,a′,k′\)\.\\displaystyle=\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a^\{\\prime\},k^\{\\prime\}\)\.\(19\)Since\(a′,k′\)\(a^\{\\prime\},k^\{\\prime\}\)is a feasible candidate in the minimization definingV^d​\(ℐ\)\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\),

V^d​\(ℐ\)=mina∈\[p\],k∈𝒦a⁡V^d​\(ℐ,a,k\)≤V^d​\(ℐ,a′,k′\)=Wd​\(ℐ\)\.\\displaystyle\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)=\\min\_\{a\\in\[p\],\\,k\\in\\mathcal\{K\}^\{a\}\}\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,k\)\\leq\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a^\{\\prime\},k^\{\\prime\}\)=W\_\{d\}\(\\mathcal\{I\}\)\.\(20\)IfCARTterminates at the root \(\|ℐ\|≤1\|\\mathcal\{I\}\|\\leq 1orV0​\(ℐ\)=0V\_\{0\}\(\\mathcal\{I\}\)=0\), thenWd​\(ℐ\)=V^d​\(ℐ\)=0W\_\{d\}\(\\mathcal\{I\}\)=\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)=0, so the same inequality holds\.

Each candidate root split\(a,k\)\(a,k\)evaluated by[Algorithm2](https://arxiv.org/html/2609.38194#alg2)has lossV^d​\(ℐ,a,k\)≥V^d​\(ℐ\)\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,k\)\\geq\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)\. Moreover, by equation[20](https://arxiv.org/html/2609.38194#S4.E20), the initialCARTincumbent also satisfiesWd​\(ℐ\)≥V^d​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)\\geq\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)\. Since the final incumbent is the minimum of the initialCARTloss and the losses of the evaluated candidates, while the incumbent is updated only when a strictly smaller loss is found, we obtain

V^d​\(ℐ\)≤UABR​\(ℐ,d\)≤Wd​\(ℐ\),\\displaystyle\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)\\leq U\_\{\\texttt\{ABR\}\}\(\\mathcal\{I\},d\)\\leq W\_\{d\}\(\\mathcal\{I\}\),\(21\)regardless of whether reduction is enabled\. This proves the first statement\.

When the reduction strategy is disabled,[Algorithm2](https://arxiv.org/html/2609.38194#alg2)evaluates every candidate root split\(a,k\)\(a,k\), wherea∈\[p\]a\\in\[p\]andk∈𝒦ak\\in\\mathcal\{K\}^\{a\}\. Therefore,

UABR​\(ℐ,d\)\\displaystyle U\_\{\\texttt\{ABR\}\}\(\\mathcal\{I\},d\)=mina∈\[p\],k∈𝒦a⁡V^d​\(ℐ,a,k\)=V^d​\(ℐ\)\.\\displaystyle=\\min\_\{a\\in\[p\],\\,k\\in\\mathcal\{K\}^\{a\}\}\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,k\)=\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)\.\(22\)Combining this equality with the first statement givesUABR​\(ℐ,d\)=V^d​\(ℐ\)≤Wd​\(ℐ\)U\_\{\\texttt\{ABR\}\}\(\\mathcal\{I\},d\)=\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)\\leq W\_\{d\}\(\\mathcal\{I\}\), which proves the second statement\.

Ford=2d=2, each child\-subtree problem has depth11\. A depth\-11tree contains only one branch node, andCARTevaluates the candidate splits at that node exactly\. Therefore,

W1​\(ℐ\[0,k\]a\)=V1​\(ℐ\[0,k\]a\)​and​W1​\(ℐ\[k,na\]a\)=V1​\(ℐ\[k,na\]a\)\.\\displaystyle W\_\{1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}\)=V\_\{1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}\)\\ \\text\{and\}\\ W\_\{1\}\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\)=V\_\{1\}\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\)\.\(23\)It follows thatV^2​\(ℐ,a,k\)=V2​\(ℐ,a,k\)\\widehat\{V\}\_\{2\}\(\\mathcal\{I\},a,k\)=V\_\{2\}\(\\mathcal\{I\},a,k\)for every candidate root split\(a,k\)\(a,k\)\. Taking the minimum over all candidate root splits givesV^2​\(ℐ\)=V2​\(ℐ\)\\widehat\{V\}\_\{2\}\(\\mathcal\{I\}\)=V\_\{2\}\(\\mathcal\{I\}\)\. Consequently, the Lipschitz\-type condition in Lemma[3\.2](https://arxiv.org/html/2609.38194#S3.Thmtheorem2)and the safe reduction result in Lemma[3\.3](https://arxiv.org/html/2609.38194#S3.Thmtheorem3)apply directly to[Algorithm2](https://arxiv.org/html/2609.38194#alg2)whend=2d=2\. Thus, the reduction strategy preserves the global optimal objective value, and

UABR​\(ℐ,2\)=V^2​\(ℐ\)=V2​\(ℐ\)\.\\displaystyle U\_\{\\texttt\{ABR\}\}\(\\mathcal\{I\},2\)=\\widehat\{V\}\_\{2\}\(\\mathcal\{I\}\)=V\_\{2\}\(\\mathcal\{I\}\)\.\(24\)Therefore,[Algorithm2](https://arxiv.org/html/2609.38194#alg2)returns aglobal optimal depth\-22tree, even when reduction is enabled\. ∎

1:functionApproxTreeSearch\(

ℐ,d\\mathcal\{I\},d\):

2:Initialize

UUand

TTby

CART​\(ℐ,d\)\\texttt\{CART\}\(\\mathcal\{I\},d\);

3:for

a∈\[p\]a\\in\[p\]do

4:Sort

ℐ\\mathcal\{I\}by feature

aato obtain

ℐa\\mathcal\{I\}^\{a\}and

𝒦a\\mathcal\{K\}^\{a\}, and set

𝕂←\{𝒦a\}\\mathbb\{K\}\\leftarrow\\\{\\mathcal\{K\}^\{a\}\\\};

5:

U,T←ApproxSplitSearch​\(U,T,ℐa,a,d,𝕂\)U,T\\leftarrow\\texttt\{ApproxSplitSearch\}\(U,T,\\mathcal\{I\}^\{a\},a,d,\\mathbb\{K\}\);\#123\.81023ptsolve the root\-level problem

6:return:Approximate loss

UUand decision tree

TT\.

7:functionApproxSplitSearch\(

U,T,ℐa,a,d,𝕂U,T,\\mathcal\{I\}^\{a\},a,d,\\mathbb\{K\}\):

8:Initialize the iteration index

i=0i=0;

9:while

𝕂≠∅\\mathbb\{K\}\\neq\\emptysetdo

10:node selection

11:Select

𝒦i\\mathcal\{K\}\_\{i\}from

𝕂\\mathbb\{K\}, set

𝕂←𝕂\\\{𝒦i\}\\mathbb\{K\}\\leftarrow\\mathbb\{K\}\\backslash\\\{\\mathcal\{K\}\_\{i\}\\\}, and update

i←i\+1i\\leftarrow i\+1;

12:upper bound

13:Select the midpoint

k¯∈𝒦i\\bar\{k\}\\in\\mathcal\{K\}\_\{i\}, and obtain

ℐ\[0,k¯\]a\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\}and

ℐ\[k¯,na\]a\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\};

14:

\(Wd−1​\(ℐ\[0,k¯\]a\),T^L\)←CART​\(ℐ\[0,k¯\]a,d−1\)\\big\(W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\}\),\\widehat\{T\}\_\{L\}\\big\)\\leftarrow\\texttt\{CART\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\},d\-1\);

\(Wd−1​\(ℐ\[k¯,na\]a\),T^R\)←CART​\(ℐ\[k¯,na\]a,d−1\)\\big\(W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\}\),\\widehat\{T\}\_\{R\}\\big\)\\leftarrow\\texttt\{CART\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\},d\-1\);

15:Evaluate loss

V^d​\(ℐ,a,k¯\)=Wd−1​\(ℐ\[0,k¯\]a\)\+Wd−1​\(ℐ\[k¯,na\]a\)\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)=W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\}\)\+W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\}\);

16:if

V^d​\(ℐ,a,k¯\)<U\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)<Uthen

17:

U←V^d​\(ℐ,a,k¯\)U\\leftarrow\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\), and update

T←\[a,k¯,T^L,T^R\]T\\leftarrow\[a,\\bar\{k\},\\widehat\{T\}\_\{L\},\\widehat\{T\}\_\{R\}\];

18:reduction

19:

δ⁡\(k¯\)←V^d​\(ℐ,a,k¯\)−U\\delta\(\\bar\{k\}\)\\leftarrow\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-U, and obtain

Δi=\{k∈𝒦i:\|ζ⁡\(k\)−ζ⁡\(k¯\)\|≤δ⁡\(k¯\)\}\\Delta\_\{i\}=\\left\\\{k\\in\\mathcal\{K\}\_\{i\}:\|\\zeta\(k\)\-\\zeta\(\\bar\{k\}\)\|\\leq\\delta\(\\bar\{k\}\)\\right\\\};

20:branching

21:Divide the remaining candidates into

𝒦L=\{k∈𝒦i∖Δi:k<k¯\}\\mathcal\{K\}\_\{L\}=\\left\\\{k\\in\\mathcal\{K\}\_\{i\}\\setminus\\Delta\_\{i\}:k<\\bar\{k\}\\right\\\}and

𝒦R=\{k∈𝒦i∖Δi:k\>k¯\}\\mathcal\{K\}\_\{R\}=\\left\\\{k\\in\\mathcal\{K\}\_\{i\}\\setminus\\Delta\_\{i\}:k\>\\bar\{k\}\\right\\\};

22:Update

𝕂←𝕂∪\{𝒦L\}\\mathbb\{K\}\\leftarrow\\mathbb\{K\}\\cup\\\{\\mathcal\{K\}\_\{L\}\\\}if

𝒦L≠∅\\mathcal\{K\}\_\{L\}\\neq\\emptyset, and

𝕂←𝕂∪\{𝒦R\}\\mathbb\{K\}\\leftarrow\\mathbb\{K\}\\cup\\\{\\mathcal\{K\}\_\{R\}\\\}if

𝒦R≠∅\\mathcal\{K\}\_\{R\}\\neq\\emptyset;

23:return:Approximate loss

UUand decision tree

TT\.

Algorithm 2Approximate branch\-and\-reduce method \(ABR\)
### 4\.2A Reinforcement Learning Perspective

ABRcan be regarded as an approximate DP method\([Bertsekas, 2024](https://arxiv.org/html/2609.38194#bib.bib8)\), and can be explained by Reinforcement Learning \(RL\) theories\. FollowingDPDT\([Kohler et al\., 2025](https://arxiv.org/html/2609.38194#bib.bib13)\), we model the DT problem as a Markov Decision Process\. At each layer, the state is defined by theset of samplespresent at the nodes of that layer\. The action at a given layer corresponds to theset of splitting rulesapplied to all nodes in that layer\. The reward measures theloss descentachieved by the splits, calculated as the difference between the total loss at the previous layer and that at the current layer\.

Figure 1:Illustration of the Child\-Subtree Approximation via RL \(xxdenotes the state\)\.For a depth\-ddtree, the overall objective is to select splitting rules at all layers to minimize the cumulative loss from the root to the leaves\. This can be interpreted as a “cost\-to\-go” problem:

1st stage cost \+ optimal tail problem cost\.\\textit\{1st stage cost \+ optimal tail problem cost\}\.[Figure1](https://arxiv.org/html/2609.38194#S4.F1)is an illustration of Child\-Subtree approximation\. Computing the global optimum requires DP that explores all feasible splits, whose number grows exponentially with tree depth\. To make this tractable, theCSPis approximated in thevalue space\(see Section 1\.2\.3 of[Bertsekas \(2024\)](https://arxiv.org/html/2609.38194#bib.bib8)\) by constructing a suboptimal policy from two child subtrees using heuristics such asCART, replacing theoptimal tail problem cost\. This approximation can be further enhanced by starting the heuristic from stage 2, a 2\-step lookahead method, which improves performance at the cost of additional computation\.

### 4\.3A Moving\-Horizon Approach

The proposed approximation method usesCARTto generate suboptimal solutions for the left and right subtrees whend\>2d\>2\. To improve solution quality, we introduce the MH approach that iteratively refines branch parameters\. At each node, the subsequent nodes form a subtree that is re\-optimized with its corresponding samplesℐs​u​b\\mathcal\{I\}\_\{sub\}, creating a new optimization subproblem\. As tree depth increases, this iterative refinement helps close the gap betweenABRand the global optimum\. As illustrated in[Figure2](https://arxiv.org/html/2609.38194#S4.F2), the MH process begins at node 1, whereABRupdates all branch nodes in the depth\-4 tree \(Td=4T\_\{d=4\}, nodes1,2,…,15\{1,2,\\ldots,15\}\)\. Next, with node 2 as the root,ABRrefines the branch nodes of the depth\-3 subtree \(Td=3T\_\{d=3\}, nodes2,4,5,8,9,10,11\{2,4,5,8,9,10,11\}\)\. This iterative procedure continues in each step, with the subtree depth decreasing until the subtree depthds​u​b=2d\_\{sub\}=2\. Here, nodes such as4,8,9\{4,8,9\}inTd=2T\_\{d=2\}are updated three times throughout this process\.

Figure 2:An example of MH whend=4d=4\.After applying the MH refinement at nodet∈𝒩Bt\\in\\mathcal\{N\}\_\{B\}, we update the corresponding subtree parameters ofTTusingTs​u​bT\_\{sub\}as follows

T\[t⋅2j:\(t\+1\)⋅2j−1\]⇐Ts​u​b\[2j:2j\+1−1\],j∈\{0,…,d−ds​u​b\}\.\\displaystyle T\[t\\cdot 2^\{j\}:\(t\+1\)\\cdot 2^\{j\}\-1\]\\Leftarrow T\_\{sub\}\[2^\{j\}:2^\{j\+1\}\-1\],\\quad j\\in\\\{0,\\ldots,d\-d\_\{sub\}\\\}\.\(25\)This iterative refinement can substantially improve the accuracy of deep decision trees, requiring at most2d−1−12^\{d\-1\}\-1iterations at relatively low cost, and terminates when a subtree reaches an optimal loss, i\.e\.,ds​u​b=1d\_\{sub\}=1orL⁡\(ℐs​u​b,Ts​u​b\)=0L\(\\mathcal\{I\}\_\{sub\},T\_\{sub\}\)=0\.

### 4\.4WhyABRand MH Can Improve OverCART

We now give intuition for why the proposed approximation can outperform greedyCART\. The key difference is thatCARTselects each split using a purely local criterion, whereasABRevaluates a candidate root split by combining it with approximate subtree costs\. As a result,ABRcan prefer a split that appears suboptimal under a one\-step greedy criterion but yields a better tree once the downstream subtree structure is considered\.

##### XOR as an Illustration of Lookahead Benefits

Consider the canonical noiseless XOR dataset \(a special case\) consisting of the four input patterns\(x1,x2\)∈\{0,1\}2\(x^\{1\},x^\{2\}\)\\in\\\{0,1\\\}^\{2\}, each appearing once, with class labely=x1⊕x2y=x^\{1\}\\oplus x^\{2\}\. A root split on eitherx1x^\{1\}orx2x^\{2\}produces two child nodes that each contain one observation from each class and therefore yields no immediate reduction in classification loss; consequently, a one\-step greedy method may fail to identify either feature as informative\. In contrast, a depth\-2 lookahead recognizes that splitting first on one feature and then on the other perfectly classifies all four observations\. This example illustrates howABRcan select a root split with little immediate benefit but strong downstream value; the complete loss calculations and resulting tree are provided in[Section9\.3](https://arxiv.org/html/2609.38194#S9.SS3)\.

AlthoughABRuses a stronger root\-level objective thanCART, it still relies on approximate subtree values\. The purpose of the MH refinement is to reduce the resulting approximation error by re\-optimizing selected subtrees after the higher\-level structure has been fixed\. In this sense, MH can be viewed as a local repair mechanism: it revisits subproblems that were previously solved only approximately and may further reduce the training loss\. ForCART, the depth\-ddobjective is

Wd​\(ℐ\)=Wd−1​\(ℐ\[0,k′\]a′\)\+Wd−1​\(ℐ\[k′,na′\]a′\),\\displaystyle W\_\{d\}\(\\mathcal\{I\}\)=W\_\{d\-1\}\(\\mathcal\{I\}^\{a^\{\\prime\}\}\_\{\[0,k^\{\\prime\}\]\}\)\+W\_\{d\-1\}\(\\mathcal\{I\}^\{a^\{\\prime\}\}\_\{\[k^\{\\prime\},n\_\{a^\{\\prime\}\}\]\}\),\(26\)where\(a′,k′\)\(a^\{\\prime\},k^\{\\prime\}\)is the greedy root split\. In contrast,ABRselects the root split according to

V^d​\(ℐ\)=Wd−1​\(ℐ\[0,k∗\]a∗\)\+Wd−1​\(ℐ\[k∗,na∗\]a∗\),\\displaystyle\\hat\{V\}\_\{d\}\(\\mathcal\{I\}\)=W\_\{d\-1\}\(\\mathcal\{I\}^\{a^\{\*\}\}\_\{\[0,k^\{\*\}\]\}\)\+W\_\{d\-1\}\(\\mathcal\{I\}^\{a^\{\*\}\}\_\{\[k^\{\*\},n\_\{a^\{\*\}\}\]\}\),\(27\)where\(a∗,k∗\)\(a^\{\*\},k^\{\*\}\)minimizes the approximate lookahead objective\. Thus,ABRmay select a different root split fromCART, and the subsequent MH refinements can further improve the resulting tree by re\-optimizing selected subtrees\. We evaluate this effect empirically in the ablation study of[Section5\.6](https://arxiv.org/html/2609.38194#S5.SS6)\.

### 4\.5A Moving\-Horizon Approximate Branch\-and\-Reduce Method

By leveraging the child\-subtree approximation and the MH technique, we present theMHABRalgorithm for a depth\-ddtree, as described in[Algorithm3](https://arxiv.org/html/2609.38194#alg3)\. Designed specifically for trees withd≥2d\\geq 2, the algorithm applies the MH refinement for at most2d−1−12^\{d\-1\}\-1iterations\. At each iteration, it refines the current model by optimizing a selected subtree, usingABR\([Algorithm2](https://arxiv.org/html/2609.38194#alg2)\) to yield a subtree solutionTs​u​bT\_\{sub\}with depthds​u​bd\_\{sub\}and objective valueUs​u​bU\_\{sub\}\. BecauseABRmaintains and updates an incumbent solution over candidate thresholds within thebranchsubroutine, it naturally admits a warm\-start strategy\. In practice, warm\-starting improves efficiency and ensures that the returned subtree solution is no worse than theCARTinitialization\. We now analyze monotonicity of the MH refinement and the computational complexity of[Algorithm3](https://arxiv.org/html/2609.38194#alg3)\.

Algorithm 3Moving\-horizon approximate branch\-and\-reduce method \(MHABR\)1:functionMHABR\(

ℐ,d\\mathcal\{I\},d\):

2:Initialize

UUand

TTusing

CART​\(ℐ,d\)\\texttt\{CART\}\(\\mathcal\{I\},d\);

3:for

t∈\{1,⋯,2d−1−1\}t\\in\\\{1,\\cdots,2^\{d\-1\}\-1\\\}do

4:Set the remaining subtree depth as

dsub←d−⌊log2⁡t⌋d\_\{\\mathrm\{sub\}\}\\leftarrow d\-\\lfloor\\log\_\{2\}t\\rfloor;

5:Obtain the sample set

ℐt\\mathcal\{I\}\_\{t\}reaching node

ttunder the current tree

TT;

6:if

ℐt≠∅\\mathcal\{I\}\_\{t\}\\neq\\emptysetthen

7:Let

TtT\_\{t\}denote the current subtree rooted at node

tt, and calculate its loss

Ut←L⁡\(ℐt,Tt\)U\_\{t\}\\leftarrow L\(\\mathcal\{I\}\_\{t\},T\_\{t\}\);

8:Calculate

Usub,Tsub←ApproxTreeSearch​\(ℐt,dsub\)U\_\{\\mathrm\{sub\}\},T\_\{\\mathrm\{sub\}\}\\leftarrow\\texttt\{ApproxTreeSearch\}\(\\mathcal\{I\}\_\{t\},d\_\{\\mathrm\{sub\}\}\);

9:if

Usub<UtU\_\{\\mathrm\{sub\}\}<U\_\{t\}then

10:Update

TTby replacing

TtT\_\{t\}with

TsubT\_\{\\mathrm\{sub\}\}according to[Equation25](https://arxiv.org/html/2609.38194#S4.E25);

11:Update the total loss as

U←U−Ut\+UsubU\\leftarrow U\-U\_\{t\}\+U\_\{\\mathrm\{sub\}\};

12:return:Loss

UUand decision tree

TT\.

###### Corollary 4\.3\.

LetU\(r\)U^\{\(r\)\}denote the total training loss after therrth accepted moving\-horizon update, withU\(0\)=Wd​\(ℐ\)U^\{\(0\)\}=W\_\{d\}\(\\mathcal\{I\}\)\. ThenU\(r\+1\)≤U\(r\)U^\{\(r\+1\)\}\\leq U^\{\(r\)\}for every accepted update\. Consequently, the finalMHABRsolution satisfiesUMHABR​\(ℐ,d\)≤Wd​\(ℐ\)U\_\{\\texttt\{MHABR\}\}\(\\mathcal\{I\},d\)\\leq W\_\{d\}\(\\mathcal\{I\}\), regardless of whether reduction is enabled in the approximate subtree searches\.

###### Proof\.

At an iteration associated with nodett,[Algorithm2](https://arxiv.org/html/2609.38194#alg2)replaces the current subtree only if its new lossUsubU\_\{\\mathrm\{sub\}\}is strictly smaller than the current subtree lossUtU\_\{t\}\. The total loss is then updated asU\(r\+1\)=U\(r\)−Ut\+Us​u​b<U\(r\)U^\{\(r\+1\)\}=U^\{\(r\)\}\-U\_\{t\}\+U\_\{sub\}<U^\{\(r\)\}\. If the candidate subtree is not better, no replacement is performed and the total loss remains unchanged\. Since the initial tree is obtained byCART,U\(0\)=Wd​\(ℐ\)U^\{\(0\)\}=W\_\{d\}\(\\mathcal\{I\}\), and hence the final loss cannot exceedWd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)\. ∎

###### Theorem 4\.4\.

Letn\>1n\>1andppdenote the number of samples and features, respectively, and letn~≥1\\tilde\{n\}\\geq 1be the maximum actual number of candidate feature\-threshold pairs evaluated in anyBRorABRroot\-level search\. Suppose that, whenever a tree or subtree problem containingnt≥2n\_\{t\}\\geq 2samples is processed, its samples are independently sorted with respect to allppfeatures, requiring𝒪⁡\(p​nt​log⁡nt\)\\mathcal\{O\}\(pn\_\{t\}\\log n\_\{t\}\)time\. Problems containing at most one sample are treated as terminal and are not sorted\. We ignore implementation\-dependent speedups such as warm\-starting, reduction effectiveness, and early termination\. Then, for a tree of depthdd,

1. 1\.The cost ofCARTis bounded by𝒪⁡\(p​n​d​log⁡n\)\\mathcal\{O\}\(pnd\\log n\);
2. 2\.The cost ofBRis bounded by𝒪⁡\(p​n​log⁡n​n~d−1\)\\mathcal\{O\}\\left\(pn\\log n\\,\\tilde\{n\}^\{\\,d\-1\}\\right\);
3. 3\.The cost ofMHABRis bounded by𝒪⁡\(n~​p​n​log⁡n​d⁡\(d−1\)2\),d≥2\\mathcal\{O\}\\left\(\\tilde\{n\}\\,pn\\log n\\,\\frac\{d\(d\-1\)\}\{2\}\\right\),\\ d\\geq 2\.

Since each feature admits at mostn\+1n\+1candidate thresholds, the total number of candidate feature\-threshold pairs satisfiesn~≤p⁡\(n\+1\)=𝒪⁡\(p​n\)\\tilde\{n\}\\leq p\(n\+1\)=\\mathcal\{O\}\(pn\)\. Consequently, substitutingn~=𝒪⁡\(p​n\)\\tilde\{n\}=\\mathcal\{O\}\(pn\)gives the following coarse worst\-case bounds:

1. 1\.The cost ofBRis bounded by𝒪⁡\(\(p​n\)d​log⁡n\)\\mathcal\{O\}\\left\(\(pn\)^\{d\}\\log n\\right\);
2. 2\.The cost ofMHABRis bounded by𝒪⁡\(p2​n2​log⁡n​d⁡\(d−1\)2\)\\mathcal\{O\}\\left\(p^\{2\}n^\{2\}\\log n\\,\\frac\{d\(d\-1\)\}\{2\}\\right\)\.

###### Proof\.

We first establish an inequality that will be used throughout the proof\. Consider a collection of mutually disjoint tree nodes with sample sizesn1,…,nrn\_\{1\},\\ldots,n\_\{r\}satisfying∑j=1rnj≤n\\sum\_\{j=1\}^\{r\}n\_\{j\}\\leq n\. For everynj\>0n\_\{j\}\>0, we havenj≤nn\_\{j\}\\leq n, and hencelog⁡nj≤log⁡n\\log n\_\{j\}\\leq\\log n\. Therefore,

∑j=1rnj​log⁡nj≤∑j=1rnj​log⁡n≤n​log⁡n\.\\displaystyle\\sum\_\{j=1\}^\{r\}n\_\{j\}\\log n\_\{j\}\\leq\\sum\_\{j=1\}^\{r\}n\_\{j\}\\log n\\leq n\\log n\.\(28\)

##### CART

We consider theCARTroutine used in our implementation, which is based on theDecisionTree\.jlpackage, and analyze its complexity under the repeated\-sorting assumption of the theorem\. LetCCART​\(n,d\)C\_\{\\texttt\{CART\}\}\(n,d\)denote the cost of constructing a depth\-ddCARTtree fromnnsamples\. At a nodettcontainingntn\_\{t\}samples, sorting the samples with respect to allppfeatures costs𝒪⁡\(p​nt​log⁡nt\)\\mathcal\{O\}\(pn\_\{t\}\\log n\_\{t\}\)\. After sorting,CARTscores all candidate thresholds by a linear sweep using cumulative class counts\. Since there are at mostp⁡\(nt\+1\)=𝒪⁡\(p​nt\)p\(n\_\{t\}\+1\)=\\mathcal\{O\}\(pn\_\{t\}\)feature\-threshold pairs, this sweep requires𝒪⁡\(p​nt\)\\mathcal\{O\}\(pn\_\{t\}\)time and is dominated by the sorting cost\.

We prove by induction onddthatCCART​\(n,d\)=𝒪⁡\(p​n​d​log⁡n\)C\_\{\\texttt\{CART\}\}\(n,d\)=\\mathcal\{O\}\(pnd\\log n\)\. Ford=1d=1,CARTprocesses only the root node\. Therefore,CCART​\(n,1\)=𝒪⁡\(p​n​log⁡n\)C\_\{\\texttt\{CART\}\}\(n,1\)=\\mathcal\{O\}\(pn\\log n\)\. Now suppose that the result holds for trees of depthd−1d\-1\. LetnLn\_\{L\}andnRn\_\{R\}denote the numbers of samples assigned to the left and right children of the root, respectively\. Since the two child nodes partition the samples,nL\+nR=nn\_\{L\}\+n\_\{R\}=n\. The cost of constructing a depth\-ddtree satisfies

CCART​\(n,d\)\\displaystyle C\_\{\\texttt\{CART\}\}\(n,d\)≤𝒪⁡\(p​n​log⁡n\)\+CCART​\(nL,d−1\)\+CCART​\(nR,d−1\)\\displaystyle\\leq\\mathcal\{O\}\(pn\\log n\)\+C\_\{\\texttt\{CART\}\}\(n\_\{L\},d\-1\)\+C\_\{\\texttt\{CART\}\}\(n\_\{R\},d\-1\)≤𝒪⁡\(p​n​log⁡n\)\+𝒪⁡\(p⁡\(d−1\)​\(nL​log​nL\+nR​log​nR\)\),\\displaystyle\\leq\\mathcal\{O\}\(pn\\log n\)\+\\mathcal\{O\}\(p\(d\-1\)\\left\(n\_\{L\}\\log n\_\{L\}\+n\_\{R\}\\log n\_\{R\}\\right\)\),
where the second inequality follows from the induction hypothesis\. By[Equation28](https://arxiv.org/html/2609.38194#S4.E28), we havenL​log⁡nL\+nR​log⁡nR≤n​log⁡nn\_\{L\}\\log n\_\{L\}\+n\_\{R\}\\log n\_\{R\}\\leq n\\log n\. Hence,

CCART​\(n,d\)\\displaystyle C\_\{\\texttt\{CART\}\}\(n,d\)≤𝒪⁡\(p​n​log⁡n\)\+𝒪⁡\(p​n​\(d−1\)​log​n\)=𝒪⁡\(p​n​d​log​n\)\.\\displaystyle\\leq\\mathcal\{O\}\(pn\\log n\)\+\\mathcal\{O\}\(pn\(d\-1\)\\log n\)=\\mathcal\{O\}\(pnd\\log n\)\.\(29\)
Thus, the claimed bound holds forCART\.

##### BR

LetCBR​\(n,d\)C\_\{\\texttt\{BR\}\}\(n,d\)denote the cost of solving a depth\-ddtree exactly using BR\. We prove by induction onddthatCBR​\(n,d\)=𝒪⁡\(p​n​log⁡n​n~d−1\)C\_\{\\texttt\{BR\}\}\(n,d\)=\\mathcal\{O\}\\left\(pn\\log n\\,\\tilde\{n\}^\{\\,d\-1\}\\right\)\. Ford=1d=1,BRsorts the samples with respect to allppfeatures and scans the candidate root splits\. Therefore,CBR​\(n,1\)=𝒪⁡\(p​n​log⁡n\)C\_\{\\texttt\{BR\}\}\(n,1\)=\\mathcal\{O\}\(pn\\log n\)\. This agrees with the claimed bound becausen~d−1=n~0=1\\tilde\{n\}^\{\\,d\-1\}=\\tilde\{n\}^\{\\,0\}=1\.

Now suppose that the result holds for depthd−1d\-1\. At the root of a depth\-ddBRproblem, at mostn~\\tilde\{n\}candidate splits are evaluated\. For candidate splitjj, letnj,Ln\_\{j,L\}andnj,Rn\_\{j,R\}denote the sample sizes of the corresponding left and right subproblems\. The two child sample sets partition the parent sample set, sonj,L\+nj,R=nn\_\{j,L\}\+n\_\{j,R\}=n\. The depth\-ddBRcost therefore satisfies

CBR​\(n,d\)\\displaystyle C\_\{\\texttt\{BR\}\}\(n,d\)≤𝒪⁡\(p​n​log⁡n\)\+∑j=1n~\[CBR​\(nj,L,d−1\)\+CBR​\(nj,R,d−1\)\]\.\\displaystyle\\leq\\mathcal\{O\}\(pn\\log n\)\+\\sum\_\{j=1\}^\{\\tilde\{n\}\}\\left\[C\_\{\\texttt\{BR\}\}\(n\_\{j,L\},d\-1\)\+C\_\{\\texttt\{BR\}\}\(n\_\{j,R\},d\-1\)\\right\]\.
Applying the induction hypothesis gives

CBR​\(n,d\)≤𝒪⁡\(p​n​log​n\)\+𝒪⁡\(p​n~d−2​∑j=1n~\[nj,L​log​nj,L\+nj,R​log​nj,R\]\)\.\\displaystyle C\_\{\\texttt\{BR\}\}\(n,d\)\\leq\\mathcal\{O\}\(pn\\log n\)\+\\mathcal\{O\}\\left\(p\\tilde\{n\}^\{\\,d\-2\}\\sum\_\{j=1\}^\{\\tilde\{n\}\}\\left\[n\_\{j,L\}\\log n\_\{j,L\}\+n\_\{j,R\}\\log n\_\{j,R\}\\right\]\\right\)\.
For each candidatejj,[Equation28](https://arxiv.org/html/2609.38194#S4.E28)givesnj,L​log⁡nj,L\+nj,R​log⁡nj,R≤n​log⁡nn\_\{j,L\}\\log n\_\{j,L\}\+n\_\{j,R\}\\log n\_\{j,R\}\\leq n\\log n\. Since at mostn~\\tilde\{n\}candidates are evaluated,

CBR​\(n,d\)\\displaystyle C\_\{\\texttt\{BR\}\}\(n,d\)≤𝒪⁡\(p​n​log⁡n\)\+𝒪⁡\(p​n~d−2⋅n~​n​log⁡n\)\\displaystyle\\leq\\mathcal\{O\}\(pn\\log n\)\+\\mathcal\{O\}\(p\\tilde\{n\}^\{\\,d\-2\}\\cdot\\tilde\{n\}n\\log n\)=𝒪⁡\(p​n​log⁡n\)\+𝒪⁡\(p​n​log⁡n​n~d−1\)\\displaystyle=\\mathcal\{O\}\(pn\\log n\)\+\\mathcal\{O\}\(pn\\log n\\,\\tilde\{n\}^\{\\,d\-1\}\)=𝒪⁡\(p​n​log⁡n​n~d−1\)\.\\displaystyle=\\mathcal\{O\}\\left\(pn\\log n\\,\\tilde\{n\}^\{\\,d\-1\}\\right\)\.\(30\)Thus, the exactBRcomplexity grows multiplicatively with the number of candidate splits at each recursive depth\. Sincen~=𝒪⁡\(p​n\)\\tilde\{n\}=\\mathcal\{O\}\(pn\),

CBR​\(n,d\)=𝒪⁡\(\(p​n\)d​log⁡n\)\.\\displaystyle C\_\{\\texttt\{BR\}\}\(n,d\)=\\mathcal\{O\}\\left\(\(pn\)^\{d\}\\log n\\right\)\.\(31\)Thus, for fixedppandnn, theBRbound is exponential in the tree depthdd; for fixeddd, it is polynomial innnandpp, with a degree that increases withdd\.

##### OneABRcall

Before introducingMHABR, we consider anABRcall on a subtree containingnnsamples and having remaining depthds​u​b≥2d\_\{sub\}\\geq 2\. After initialization, at mostn~\\tilde\{n\}root candidates are evaluated\. For candidatejj, letnj,Ln\_\{j,L\}andnj,Rn\_\{j,R\}be the sample sizes of the corresponding left and right child subproblems\. The two child\-subtree problems induced by each candidate split are approximated using depth\-\(ds​u​b−1\)\(d\_\{sub\}\-1\)CARTtrees\. Using theCARTbound,

CCART​\(nj,L,ds​u​b−1\)\+CCART​\(nj,R,ds​u​b−1\)≤𝒪⁡\(p⁡\(ds​u​b−1\)​\[nj,L​log⁡nj,L\+nj,R​log⁡nj,R\]\)\.\\displaystyle C\_\{\\texttt\{CART\}\}\(n\_\{j,L\},d\_\{sub\}\-1\)\+C\_\{\\texttt\{CART\}\}\(n\_\{j,R\},d\_\{sub\}\-1\)\\leq\\mathcal\{O\}\(p\(d\_\{sub\}\-1\)\\left\[n\_\{j,L\}\\log n\_\{j,L\}\+n\_\{j,R\}\\log n\_\{j,R\}\\right\]\)\.\(32\)
Becausenj,L\+nj,R=nn\_\{j,L\}\+n\_\{j,R\}=n, by[Equation28](https://arxiv.org/html/2609.38194#S4.E28),nj,L​log⁡nj,L\+nj,R​log⁡nj,R≤n​log⁡nn\_\{j,L\}\\log n\_\{j,L\}\+n\_\{j,R\}\\log n\_\{j,R\}\\leq n\\log n\. Hence, the cost of evaluating one candidate root split is bounded by𝒪⁡\(p​n​\(ds​u​b−1\)​log⁡n\)\\mathcal\{O\}\\left\(pn\(d\_\{sub\}\-1\)\\log n\\right\)\. Evaluating at mostn~\\tilde\{n\}root candidates gives

CABR​\(n,ds​u​b\)\\displaystyle C\_\{\\texttt\{ABR\}\}\(n,d\_\{sub\}\)≤𝒪⁡\(p​n​log⁡n\)\+∑j=1n~𝒪⁡\(p​n​\(ds​u​b−1\)​log⁡n\)\\displaystyle\\leq\\mathcal\{O\}\(pn\\log n\)\+\\sum\_\{j=1\}^\{\\tilde\{n\}\}\\mathcal\{O\}\(pn\(d\_\{sub\}\-1\)\\log n\)=𝒪⁡\(n~​p​n​\(ds​u​b−1\)​log⁡n\)\.\\displaystyle=\\mathcal\{O\}\\left\(\\tilde\{n\}\\,pn\(d\_\{sub\}\-1\)\\log n\\right\)\.\(33\)The first term accounts for sorting and constructing the candidate root splits\. It is dominated by the candidate\-evaluation term whenn~≥1\\tilde\{n\}\\geq 1andds​u​b≥2d\_\{sub\}\\geq 2\.

##### MHABR

The moving\-horizon procedure appliesABRto subtrees with remaining depths\{d,d−1,…,2\}\\\{d,d\-1,\\ldots,2\\\}\. Consider one moving\-horizon level at which every processed subtree has remaining depthds​u​bd\_\{sub\}\. Let these subtrees containn1,…,nrn\_\{1\},\\ldots,n\_\{r\}samples\. The subtrees processed at a fixed remaining depthds​u​bd\_\{sub\}are rooted at distinct nodes of the same tree level\. Their sample sets are therefore mutually disjoint, and∑t=1rnt≤n\\sum\_\{t=1\}^\{r\}n\_\{t\}\\leq n\. By the definition ofn~\\tilde\{n\}, eachABRcall evaluates at mostn~\\tilde\{n\}root candidates\. Applying[33](https://arxiv.org/html/2609.38194#S4.Ex18)to each subtree gives

∑t=1rCABR​\(nt,ds​u​b\)\\displaystyle\\sum\_\{t=1\}^\{r\}C\_\{\\texttt\{ABR\}\}\(n\_\{t\},d\_\{sub\}\)=𝒪⁡\(n~​p​\(ds​u​b−1\)​∑t=1rnt​log⁡nt\)\\displaystyle=\\mathcal\{O\}\\left\(\\tilde\{n\}\\,p\(d\_\{sub\}\-1\)\\sum\_\{t=1\}^\{r\}n\_\{t\}\\log n\_\{t\}\\right\)=𝒪⁡\(n~​p​n​\(ds​u​b−1\)​log⁡n\),\\displaystyle=\\mathcal\{O\}\\left\(\\tilde\{n\}\\,pn\(d\_\{sub\}\-1\)\\log n\\right\),\(34\)where the final inequality follows from[Equation28](https://arxiv.org/html/2609.38194#S4.E28)\. Summing over all remaining subtree depthsds​u​b=d,d−1,…,2d\_\{sub\}=d,d\-1,\\ldots,2gives

CMHABR​\(n,d\)\\displaystyle C\_\{\\texttt\{MHABR\}\}\(n,d\)=𝒪⁡\(n~​p​n​log⁡n​∑ds​u​b=2d\(ds​u​b−1\)\)=𝒪⁡\(n~​p​n​log⁡n​d⁡\(d−1\)2\)\.\\displaystyle=\\mathcal\{O\}\\left\(\\tilde\{n\}\\,pn\\log n\\sum\_\{d\_\{sub\}=2\}^\{d\}\(d\_\{sub\}\-1\)\\right\)=\\mathcal\{O\}\\left\(\\tilde\{n\}\\,pn\\log n\\frac\{d\(d\-1\)\}\{2\}\\right\)\.\(35\)Finally, sincen~=𝒪⁡\(p​n\)\\tilde\{n\}=\\mathcal\{O\}\(pn\),

CMHABR​\(n,d\)=𝒪⁡\(p2​n2​log⁡n​d⁡\(d−1\)2\)\.\\displaystyle C\_\{\\texttt\{MHABR\}\}\(n,d\)=\\mathcal\{O\}\\left\(p^\{2\}n^\{2\}\\log n\\frac\{d\(d\-1\)\}\{2\}\\right\)\.\(36\)This completes the proof\. ∎

These bounds are intended only as coarse worst\-case estimates; in practice, the observed runtime is substantially reduced by warm\-starting, reduction, and early stopping\.

## 5Numerical Experiments

This section presents a comprehensive empirical evaluation of our proposed algorithm across various benchmark datasets \(detailed in[Section10](https://arxiv.org/html/2609.38194#S10)\)\. We assess key performance metrics, specifically predictive accuracy and computational efficiency, against five primary baseline methods\. These baselines encompass widely used heuristics, includingCART\([Sadeghi et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib7)\),LS\-OCT\([Dunn, 2018](https://arxiv.org/html/2609.38194#bib.bib9)\), andDPDT\([Kohler et al\., 2025](https://arxiv.org/html/2609.38194#bib.bib13)\), as well as state\-of\-the\-art global optimization solvers such asDL8\.5\([Aglin et al\., 2020](https://arxiv.org/html/2609.38194#bib.bib16)\)andQuant\-BnB\([Mazumder et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib30)\)\. Furthermore, due to the lack of an open\-source implementation for direct reproducibility, we provide a supplementary comparison against the self\-reported results ofTAO\([Carreira\-Perpinán and Tavallali, 2018](https://arxiv.org/html/2609.38194#bib.bib4)\)in[Section8](https://arxiv.org/html/2609.38194#S8)\. A central focus of this evaluation is demonstrating three key advantages of our method: \(i\) it consistently recovers the global optimum at depthd=2d=2; \(ii\) it achieves vast computational efficiency gains over exact global solvers at depthsd\>2d\>2with only a marginal trade\-off in optimality; and \(iii\) it can well scale to deep trees while delivering superior accuracy compared to heuristic baselines\.

Datasets and computing environment:We collected 59 classification datasets from the UCI Machine Learning Repository\([Dua and Graff, 2017](https://arxiv.org/html/2609.38194#bib.bib21)\), spanning both binary and multi\-class tasks, with sample sizes ranging from 47 to 60,807,600\. The datasets were categorized into 3 groups: 51 small\-scale datasets \(n<10​Kn<10K\) and 5 medium\-scale \(10​K≤n≤1​M10K\\leq n\\leq 1M\), and 3 large\-scale datasets \(n≥1​Mn\\geq 1M\)\. Before the experiments, each dataset was randomly split, with 75% for training and 25% for testing, respectively\. The results reflect the average of 10 runs for each dataset\. All experiments are conducted on a 40\-coreIntel Xeon Gold 5115 CPU\(2\.40GHz\) with 93\.9GB RAM\.

Implementation:Our algorithm is implemented inJulia, with the source code publicly available on GitHub111[https://github\.com/YankaiGroup/MHABR\.jl](https://github.com/YankaiGroup/MHABR.jl)\. We also provide an enhanced version ofCART\([Section9\.2](https://arxiv.org/html/2609.38194#S9.SS2)\), which is based onDecisionTree\.jlpackage and is integrated intoMHABR\. All the baselines are obtained from their official repositories, exceptLS\-OCT, which we reproduced inJulia\. Time limits are set to 4 hours for small\-scale datasets and 24 hours for larger datasets\. More details are given in[Section10\.3](https://arxiv.org/html/2609.38194#S10.SS3)\.

### 5\.1Performance on Small Datasets

We evaluate our algorithm on 51 small datasets, encompassing both an aggregate analysis to illustrate the relative performance of the methods and detailed individual comparisons\. Since global methods often suffer from limited scalability while heuristic approaches frequently compromise on optimality, we defer a granular analysis of these trade\-offs to the scenario\-specific discussions\.

[Table1](https://arxiv.org/html/2609.38194#S5.T1)provides overall results of these methods\. To rigorously assess optimality, we also utilize binarized datasets to benchmark the optimality gap againstDL8\.5\. Among the competing methods,DPDTemerges as the strongest baseline; like our approach, it is non\-greedy, yet it offers superior efficiency and scalability compared to other baselines\. Furthermore,DPDTcan be configured to mimic our root\-node search strategy by adjusting the\(N,p\)parameters\. Consequently, to ensure a comprehensive comparison, we explicitly evaluate this variant, denoted asDPDT\(Np\)\.

Table 1:Average training and testing accuracy on 51 small datasetsDepthBinarized DatasetsOriginal Datasets \(ODs\)DL8\.5MHABRb​i​n\\texttt\{MHABR\}\_\{bin\}Quant\-BnBLS\-OCTCARTDPDTDPDT\(Np\)MHABRTrainingaccuracy\(%\)283\.18∗83\.18^\{\*\}83\.1883\.1884\.31∗\\mathbf\{84\.31\}^\{\*\}83\.9083\.9081\.8481\.8483\.5483\.5483\.7883\.7884\.31∗\\mathbf\{84\.31\}^\{\*\}387\.71∗87\.71^\{\*\}86\.9786\.9789\.44¯∗\\underline\{\\mathbf\{89\.44\}\}^\{\*\}87\.5987\.5985\.9685\.9688\.1988\.1988\.0288\.0288\.9388\.93490\.79∗90\.79^\{\*\}89\.8989\.89/90\.1490\.1489\.0289\.0290\.9590\.9591\.0091\.0092\.26\\mathbf\{92\.26\}895\.89∗95\.89^\{\*\}94\.7994\.79/96\.9496\.9496\.7096\.7097\.7297\.7298\.0198\.0198\.55\\mathbf\{98\.55\}Testingaccuracy\(%\)279\.1879\.1875\.1475\.1479\.8979\.8979\.6779\.6778\.6378\.6379\.5279\.5279\.6479\.6479\.91\\mathbf\{79\.91\}381\.5681\.5679\.8279\.8282\.56¯\\underline\{82\.56\}82\.1882\.1881\.1381\.1381\.9681\.9682\.0882\.0882\.42\\mathbf\{82\.42\}482\.4282\.4281\.5281\.52/83\.53\\mathbf\{83\.53\}82\.6782\.6783\.3083\.3083\.1683\.1683\.3083\.30882\.6282\.6283\.5883\.58/85\.2085\.2085\.2085\.2085\.35\\mathbf\{85\.35\}84\.9584\.9584\.1084\.10

- 1“\*” denotes global optimal solutions\.
- 2Boldnumbers indicate the best result in each row\.
- 3b​i​n\.\{bin\.\}denotes binarized datasets\.
- 4Underlinednumbers indicate the average over 42 datasets thatQuant\-BnBcompletes\.
- 5Quant\-BnBfails to complete at depths 4 and 8\.

Accuracy:As shown in[Table1](https://arxiv.org/html/2609.38194#S5.T1),MHABRachieves the strongest average*testing*accuracy among the compared methods at depthsd=2d=2andd=3d=3\(excludingQuant\-BnBon datasets for which it does not converge\)\. Atd=8d=8, the gap between training and testing accuracy indicates some overfitting on the small datasets, so these results should be interpreted together with validation\-based tuning results reported later\. Even in this regime, however,MHABRmaintains an average0\.99%advantage overDL8\.5\. A broader comparison with non\-global baselines on medium\- and large\-scale datasets, where overfitting is less pronounced, is provided in the following subsection\.

In terms of training accuracy,MHABRconsistently achieves the highest values among the heuristic baselines, outperformingCARTby an average of2\.63%\. Since training accuracy more directly reflects the quality of the optimized tree on the training objective, we use it here as an indicator of optimization quality rather than generalization performance\. Under this metric,Quant\-BnBis competitive only atd=3d=3, where it completes 42 datasets and yields an average gap of 0\.51% relative toMHABR,but it fails to converge for deeper trees\. On binarized datasets,MHABRbin\.\\texttt\{MHABR\}\_\{\\text\{bin\.\}\}performs slightly belowDL8\.5, with an average gap of 0\.69%, whereas standardMHABRon the original continuous datasets exceedsDL8\.5by an average of 1\.62%\. Notably,MHABRattains theglobal optimumatd=2d=2on both dataset types\. AlthoughDPDT\(Np\)slightly improves upon standardDPDTin training accuracy, it remains on average 0\.81% belowMHABR, suggesting that the MH refinements improve optimization quality beyond the one\-shot approximate search\.

Scalability and efficiency:A key property ofMHABRis its scalability, demonstrated by a slower increase in computational cost with tree depth compared to global optimal methods, while maintaining higher accuracy than heuristic baselines\. As shown in[Figure3](https://arxiv.org/html/2609.38194#S5.F3), across the 51 small\-scale datasets,Quant\-BnBbecomes prohibitively expensive ford≥3d\\geq 3, andDL8\.5exhibits a sharp rise in computational cost with increasing depth, particularly between depths 4 and 8, eventually exceeding the runtime ofMHABR\. In contrast,MHABRexhibits nearly linear growth in computational cost, similar to other heuristic methods, which highlights its superior scalability for deeper trees\.

Figure 3:Average training time across 51 small datasets on a logarithmic scale\.CARTandDPDTremain the fastest methods, whereasQuant\-BnBandDL8\.5exhibit sharp runtime growth with depth\.MHABRis slower than the heuristic baselines but scales more moderately than the global optimization baselines, requiring26\.99​s26\.99~\\mathrm\{s\}at depth 8, compared with167\.2​s167\.2~\\mathrm\{s\}forDL8\.5and236\.7​s236\.7~\\mathrm\{s\}forLS\-OCT\.
### 5\.2Medium\-scale and Large\-scale Datasets

This section evaluates the proposed method on the challenge of learning deep trees \(ford=4,8d=4,8\) for large\-scale datasets, whereQuant\-BnBfails for all cases andDL8\.5only succeeds on several datasets at depth 4 and fails at depth 8\.[2](https://arxiv.org/html/2609.38194#S5.T2)compares the results on five medium and three large datasets against 3 baselines\. For large\-scale applications of our algorithm, we incorporate additional techniques \(detailed in[Section10\.2](https://arxiv.org/html/2609.38194#S10.SS2)\) to improve the efficiency of our algorithm, as detailed in the following, which is further analyzed in[Section5\.6](https://arxiv.org/html/2609.38194#S5.SS6)\.

Datasetnnppncn\_\{c\}Methodd=4d=4d=8d=8Train \(%\)Test \(%\)Time \(s\)Train \(%\)Test \(%\)Time \(s\)Avila10,4301012CART57\.2456\.580\.0376\.7774\.870\.05DPDT58\.7158\.850\.9079\.7177\.002\.96LS\-OCT60\.3359\.87183\.6179\.8477\.001585\.04MHABR61\.5960\.758\.4293\.1991\.5314\.21Eeg14,980142CART70\.1269\.300\.0379\.3176\.300\.06DPDT72\.8671\.921\.2083\.7279\.484\.24LS\-OCT71\.9471\.16326\.6881\.9378\.432498\.00MHABR74\.5072\.8423\.9888\.9382\.51102\.00Htru17,89882CART97\.9497\.830\.0598\.6697\.750\.08DPDT98\.1497\.921\.6398\.8797\.684\.82LS\-OCT98\.1197\.92230\.0598\.7497\.661897\.76MHABR98\.2397\.81521\.2599\.2697\.423363\.61Shuttle43,50097CART99\.8399\.800\.03100\.0099\.950\.04DPDT99\.9099\.880\.93100\.0099\.961\.64LS\-OCT99\.9299\.89665\.52100\.0099\.965655\.26MHABR99\.9799\.9528\.53100\.0099\.9530\.09Skin\-seg\.245,05732CART97\.4297\.370\.0899\.5099\.490\.10DPDT98\.2298\.205\.4899\.7699\.7410\.58LS\-OCT98\.4198\.391471\.5799\.7599\.7315259\.16MHABR98\.7298\.7246\.6299\.9599\.91164\.83SUSY5,000,000182CART76\.6076\.6129\.3278\.3878\.3475\.79DPDT76\.8676\.871197\.4478\.7278\.682951\.08MHABR77\.8477\.8617632\.2678\.9478\.8981290\.06HIGGS11,000,000282CART65\.5865\.5581\.9869\.4769\.40216\.10DPDT66\.2066\.183223\.5069\.6769\.577158\.52MHABR66\.8866\.8511826\.9470\.1770\.0578370\.11WESAD60,807,60088CART57\.4657\.46123\.2380\.2780\.26293\.24DPDT61\.2161\.205225\.4779\.4579\.4514623\.90MHABR61\.3361\.331464\.8285\.3785\.387977\.35

- 1Boldnumbers indicate the best result among all the methods\.
- 2LS\-OCTfails to converge on large datasets\.
- 3MHABRis a light version ofMHABRincorporating additional techniques\.

Table 2:Performance comparison on 5 medium\-scale \(top\) and 3 large\-scale datasets \(bottom\)\.Techniques for large\-scale datasets: mini\-batch and tolerance terminationTo enhance efficiency for large\-scale datasets, mini\-batch sampling and a tolerance termination criterion are employed\. Mini\-batch sampling uses a subset of the dataset, defined by a sampling ratioθ∈\(0,1\]\\theta\\in\(0,1\], as input toABR, while the tolerance criterion determines termination\. Although this approach may slightly reduce accuracy, it significantly decreases computational time, as demonstrated later\. The primary factor affecting computational time is the number of splits in the initial branch, influenced by dataset characteristics, with continuous features often contributing more distinct values, many of which minimally impact the loss function\.

For the mini\-batch strategy, a proportionθ\\thetaof the original data is sampled for each subtree\. On large\-scale datasets, continuous features often require fewer samples, as their splits generally result in only small fluctuations in the overall loss\. To further enhance the efficiency of this algorithm for extremely large\-scale datasets, we consider a tolerance parameterε\\varepsilonas a termination criterion\. Letlength​\(𝕂\)\\texttt\{length\}\(\\mathbb\{K\}\)denote the size of the split index set\. The termination criterion can be formally defined as:

length​\(𝕂\)/n≤ε\.\\displaystyle\{\\texttt\{length\}\(\\mathbb\{K\}\)\}/\{n\}\\leq\\varepsilon\.\(37\)
For a fixed feature indexaa, the candidate set𝒦a\\mathcal\{K\}^\{a\}ofBRcontainsna\+1n\_\{a\}\+1threshold indices\. Afterjjsuccessive bisections, any descendant candidate region𝕂\\mathbb\{K\}contains at most⌈\(na\+1\)/2j⌉\\left\\lceil\(n\_\{a\}\+1\)/2^\{j\}\\right\\rceilindices\. By[Equation37](https://arxiv.org/html/2609.38194#S5.E37), the search of this region terminates oncelength​\(𝕂\)≤n⋅ε\\texttt\{length\}\(\\mathbb\{K\}\)\\leq n\\cdot\\varepsilon\. Consequently, this condition is reached after at mostmax⁡\{0,⌈log2⁡\(\(na\+1\)/\(n​ε\)\)⌉\}\\max\\left\\\{0,\\left\\lceil\\log\_\{2\}\\left\(\(n\_\{a\}\+1\)/\(n\\varepsilon\)\\right\)\\right\\rceil\\right\\\}successive bisections, up to integer rounding\.

Performance on medium and large datasets:Across the evaluated datasets and baselines,MHABRachieves the highest average test accuracy among the compared methods on these datasets, while remaining computationally feasible for deeper trees\. On average, it outperformsCARTby3\.66%andDPDTby3\.01%in testing accuracy atd=8d=8\. On medium datasets, although solvers likeDPDToften require less runtime,MHABRuses additional computation to achieve higher test accuracy on these datasets\. Specifically, across the five medium\-scale datasets,MHABRsignificantly improves testing accuracy, outperformingCARTby an average of 1\.84% at depth 4 and 4\.59% at depth 8, while exceedingDPDTby 0\.66% at depth 4 and 3\.49% at depth 8\. The largest improvement is observed on theAviladataset atd=8d=8, whereMHABRsurpasses all other methods by at least 13\.35% in training accuracy and 14\.53% in testing accuracy\. Furthermore, on large\-scale datasets where exact methods likeLS\-OCTfail entirely,MHABRachieves the highest test accuracy among the compared methods on these datasets\. It consistently converges alongsideCARTandDPDT, outperformingCARTby an average of 1\.14% at depth 4 and 4\.13% at depth 8, while exceedingDPDTby 0\.63% at depth 4 and 3\.89% at depth 8\.

##### Runtime Determinants

The training time ofMHABRis not necessarily monotone in the sample sizenn, because its dominant computational burden is determined more directly by the number of unique split candidates, characterized bynan\_\{a\}and\|𝒦a\|\|\\mathcal\{K\}^\{a\}\|\. As shown in[2](https://arxiv.org/html/2609.38194#S5.T2),Shuttlecontains substantially more observations thanHtru, yet requires considerably less training time\. A similar non\-monotone relationship is also observed forQuant\-BnB; for example,Skinis larger thanAvilabut is solved in less time\([Mazumder et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib30)\)\. These observations indicate that sample size alone is an incomplete predictor of computational cost\. Repeated feature values do not create additional candidate thresholds, while dataset\-dependent reduction and early termination can further contract the effective search space\.

### 5\.3Compared toDPDT

DPDTis one of the strongest heuristic baselines in our experiments\. We therefore provide a more detailed comparison in this subsection\. We evaluateDPDTunder different parameter configurations and withα\\alpha\-tuning to show thatMHABRachieves better optimization quality while remaining computationally efficient under a comparable search space\.

Recall the training results ofd=8d=8across 51 datasets in[Table1](https://arxiv.org/html/2609.38194#S5.T1); more specifically,MHABRstrictly outperformsDPDTon 23 datasets with an overall improvement of 46\.29%, while being only 3\.93% worse on 7 datasets\. These results demonstrate thatMHABRachieves better optimization quality compared to defaultDPDT\.

Figure 4:Training/testing accuracy vs\. tree depth/running time onAvilaFigure 5:Training/testing accuracy vs\. tree depth/running time onEegFor a detailed comparison withDPDTunder comparable settings, we also compare toDPDT\(NP\),cart\_nodes\_list=\(Np, \), which enables it to achieve the same theoretical accuracy asABR\. To illustrate the performance gains brought by the reduction and MH techniques, we use the datasetsAvilaandEegto plot the corresponding Pareto fronts forCART,DPDT,DPDT\(NP\), andMHABR\. We evaluate tree depths from22to2020\. ForMHABR, we report results only up tod=15d=15, since it already reaches almost100%100\\%training accuracy at depth1010and begins to show signs of overfitting thereafter\.

The Pareto fronts shown in[Figures4](https://arxiv.org/html/2609.38194#S5.F4)and[5](https://arxiv.org/html/2609.38194#S5.F5)illustrate the trade\-offs between training/testing accuracy and tree depth, as well as between training/testing accuracy and training time\. To clearly show the relationship between tree depth and running time, we also connect the points of each same depth in the figures of training/testing accuracy vs\. time\. In[Figure4](https://arxiv.org/html/2609.38194#S5.F4), among all methods,MHABRachieves the highest training accuracy and the highest peak test accuracy among the compared methods in this experiment\. It achieves almost perfect training accuracy 99\.66% at depthd=10d=10, while its testing accuracy also achieves the highest peak performance98\.68%98\.68\\%\. Beyond this regime, its testing accuracy declines, reflecting its tendency to overfit at larger depths\. In contrast,DPDTandDPDT\(Np\)approach this level only at depthsd≥14d\\geq 14, whereasCARTapproaches it only at depthsd≥17d\\geq 17\. In[Figure5](https://arxiv.org/html/2609.38194#S5.F5),MHABRshows weaker testing accuracy whend≥10d\\geq 10, which is expected due to overfitting, as its training accuracy is nearly 100%\. This leads to a drop in testing accuracy while running time increases\. Nonetheless, excluding overfitting,MHABRstill outperforms the other methods\.

In terms of running time,CARTis the fastest method, but it requires substantially deeper trees \(i\.e\., much larger models\) to achieve competitive accuracy\.DPDTimproves accuracy relative toCARTwith only a modest increase in computation, but its strength is mainly evident in its default configuration\. For achieving higher accuracy,MHABRperforms better and requires less time thanDPDT\(Np\)\. Since model size is crucial for the interpretability of decision trees, obtaining high accuracy with a smaller model is particularly desirable, which is an advantage offered byMHABR\.

MHABRachieves higher accuracy thanDPDT\(Np\)at the same depth \(before overfitting\), demonstrating the substantial performance gains contributed by the MH component\. Moreover,MHABRrequires less training time thanDPDT\(Np\)before overfitting occurs, highlighting its superior efficiency enabled by the Reduction technique\. Although the slope of the running\-time increase forMHABRbecomes steeper than that ofDPDT\(Np\)once the depth exceeds 13, an effect attributable to the MH procedure, consistent with our complexity analysis, the training accuracy has already reached 100% at this point and cannot improve further\. Thus, MH iterations can be relaxed or omitted beyond this depth\.

Table 3:α\\alpha\-tuning results of 25 datasets withn≥500n\\geq 500\.DepthTraining AccuracyTesting AccuracyCARTDPDTDPDT\(Np\)MHABRCARTDPDTDPDT\(Np\)MHABR281\.29 \(1\.19\)82\.54 \(1\.13\)82\.57 \(1\.06\)82\.89\(1\.03\)80\.07 \(1\.94\)81\.05 \(1\.87\)81\.09 \(1\.93\)81\.34\(3\.16\)384\.29 \(1\.49\)85\.69 \(1\.33\)85\.78 \(1\.19\)86\.54\(1\.12\)82\.57 \(1\.85\)83\.47 \(1\.61\)83\.54 \(1\.71\)83\.92\(1\.77\)486\.66 \(1\.44\)87\.93 \(1\.56\)88\.23 \(1\.23\)89\.20\(1\.53\)84\.43 \(1\.79\)84\.87 \(1\.69\)84\.77 \(1\.76\)85\.40\(1\.90\)588\.35 \(1\.91\)90\.27 \(2\.12\)90\.47 \(1\.90\)91\.76\(1\.77\)85\.42 \(2\.02\)86\.11 \(2\.05\)86\.26 \(2\.12\)86\.31\(1\.95\)

##### α\\alpha\-tuning

To evaluate the methods under a realistic model\-selection setting, we split the data into 50% for training, 25% for validation, and 25% for testing subsets\. For every method,α\\alphais selected fromα∈\{0\.0,0\.001,0\.005,0\.01,0\.05,0\.1,0\.2\}\\alpha\\in\\\{0\.0,0\.001,0\.005,0\.01,0\.05,0\.1,0\.2\\\}, using the same validation\-based tuning procedure\. We consider 25 datasets with more than 500 samples and evaluate tree depths from 2 to 5, thereby reducing the instability associated with validation\-based selection on very small datasets\. As shown in[Table3](https://arxiv.org/html/2609.38194#S5.T3),MHABRachieves the highest average training and testing accuracy at every evaluated depth under this common tuning protocol\. In particular, its consistent advantage in testing accuracy indicates thatMHABRprovides the strongest overall predictive performance among the compared methods afterα\\alpha\-tuning\. Becauseα\\alphais selected by validation,[Table3](https://arxiv.org/html/2609.38194#S5.T3)evaluates model\-selection and predictive performance, not the ability of each method to minimize a common unpenalized training objective\.

### 5\.4Discussion about comparison with global optimal methods

In this subsection, we provide a comparative analysis ofMHABRand global optimal methods:DL8\.5andQuant\-BnB, focusing on small datasets for which all evaluated methods successfully identified feasible solutions\. The results show that our method achieves higher training accuracy thanDL8\.5in this setting and offers a favorable empirical trade\-off between optimization quality and runtime relative toQuant\-BnB\.

Figure 6:Training and testing accuracy of 51 small datasets acrossd=2,3,4,8d=2,3,4,8\.We use box plots, as shown in[Figure6](https://arxiv.org/html/2609.38194#S5.F6), to illustrate the results across all datasets\. AlthoughDL8\.5is a global optimal method, it relies on the binarization of continuous datasets\. This preprocessing step introduces approximation errors, leading to worse training accuracy compared to the other two methods\. This negative impact is particularly evident in the training results at depth 8\. In contrast,MHABRachieves higher training accuracy thanDL8\.5on these datasets, especially at depth 8\. Meanwhile,Quant\-BnBcan handle the original continuous datasets natively but is limited to a maximum depth of 3 \(successfully completing only 42 datasets\)\.[Table4](https://arxiv.org/html/2609.38194#S5.T4)presents the results for these 42 datasets at depths 2 and 3\.MHABRachieves training accuracy equivalent to that ofQuant\-BnBatd=2d=2\. Atd=3d=3, it demonstrates only a minor disparity, performing marginally lower thanQuant\-BnB\. This outcome suggests that the solutions generated byMHABRclosely approximate the global optimal solutions for shallow trees\. Furthermore, it indicates that the potential loss of optimality resulting from theCSPapproximation is effectively compensated for by the MH procedure\.

Table 4:Comparison on 42 small datasets \(excluding 9 datasets on whichQuant\-BnBfails to complete\)\.DepthCARTDL8\.5Quant\-BnBMHABRTrain \(%\)d=2d=284\.10±14\.1184\.10\\pm 14\.1183\.93±15\.04∗83\.93\\pm 15\.04^\{\*\}84\.70±14\.76∗\\mathbf\{84\.70\\pm 14\.76^\{\*\}\}84\.70±14\.76∗\\mathbf\{84\.70\\pm 14\.76^\{\*\}\}d=3d=387\.99±12\.4187\.99\\pm 12\.4188\.08±13\.18∗88\.08\\pm 13\.18^\{\*\}89\.44±12\.36∗\\mathbf\{89\.44\\pm 12\.36^\{\*\}\}88\.86±12\.6288\.86\\pm 12\.62Test \(%\)d=2d=278\.98±16\.3778\.98\\pm 16\.3779\.89±16\.4079\.89\\pm 16\.4080\.53±15\.71\\mathbf\{80\.53\\pm 15\.71\}80\.47±15\.9180\.47\\pm 15\.91d=3d=381\.41±14\.9781\.41\\pm 14\.9781\.71±15\.7981\.71\\pm 15\.7982\.56±15\.22\\mathbf\{82\.56\\pm 15\.22\}82\.30±15\.1482\.30\\pm 15\.14

- 1Boldnumbers indicate the best solutions\.
- 2“∗\*” signifies the global optimum in the corresponding formulation\.
- 3Even thoughQuant\-BnBandMHABRcan obtain the optimal loss whend=2d=2, the optimal trees might differ\.

### 5\.5Optimality Gap Evaluation and An Extension

To assess the optimality of our algorithm, we evaluate 10 datasets \(from the 51 small datasets\) and compute the optimality gap as the relative difference between the solution produced byMHABRand the global optimum obtained byBR\. We further introduce an extended variant,MHABR2\\texttt\{MHABR\}^\{2\}\(2\-step lookahead method\), which reduces the optimality gap by extending theRLPfrom the root node to the top two layers \(nodes\{1,2,3\}\\\{1,2,3\\\}\) ford≥3d\\geq 3\. Importantly,MHABR2\\texttt\{MHABR\}^\{2\}attains exact optimal solutions for depth\-3 trees and further reduces the optimality gap for deeper trees\.

MHABR𝟐\\mathbf\{\\texttt\{MHABR\}^\{2\}\}: Our algorithm is implemented inJulia\. For the default version, we adopt the reduction strategy with parametersε=0\\varepsilon=0andθ=1\\theta=1\. To constructMHABR2\\texttt\{MHABR\}^\{2\}, which enlarges theRLPto include the top two layers of nodes, we modify the evaluation function inABRrecursion as follows:

MHABR:\{BR,d−ds​u​b≤1CART,otherwise⇒MHABR2:\{BR,d−ds​u​b≤2CART,otherwise\.\\texttt\{MHABR\}:\\;\\begin\{cases\}\\texttt\{BR\},&d\-d\_\{sub\}\\leq 1\\\\ \\texttt\{CART\},&\\text\{otherwise\}\\end\{cases\}\\quad\\Rightarrow\\quad\\texttt\{MHABR\}^\{2\}:\\;\\begin\{cases\}\\texttt\{BR\},&d\-d\_\{sub\}\\leq 2\\\\ \\texttt\{CART\},&\\text\{otherwise\.\}\\end\{cases\}
Figure 7:Theoretical relationships in terms of optimality between our algorithms and other global optimal methodsFirst, we illustrate the scope of our method in[Figure7](https://arxiv.org/html/2609.38194#S5.F7), which summarizes the theoretical relationships among the proposed approaches\. As noted in Lemma[4\.1](https://arxiv.org/html/2609.38194#S4.Thmtheorem1), our algorithm guarantees solutions no worse thanCARTwhen no reductions are applied, with the MH procedure further refining results toward better optimality\. Expanding theRLPscope improves the approximation, makingABR2\\texttt\{ABR\}^\{2\}superior toABR, and further enlargement brings methods closer to global optimal approaches such as the unapproximatedBRandQuant\-BnB\. For binarized datasets, the binarization process introduces errors that reduce optimality, soMHABRbin\.\\texttt\{MHABR\}\_\{\\text\{bin\.\}\}performs worse than the original dataset version and is clearly inferior to global optimal methods such asDL8\.5andMurTree\.

We evaluate the optimality gap using 10 small datasets solvable byBR, with results reported in[Tables5](https://arxiv.org/html/2609.38194#S5.T5)and[6](https://arxiv.org/html/2609.38194#S5.T6)\. As shown,CARTexhibits a relatively large gap, typically exceeding 3% on average at both depths 3 and 4\. In contrast,MHABRmaintains a gap within 1% on average, while the extended variant,MHABR2\\texttt\{MHABR\}^\{2\}, further improves optimality, consistently reducing the gap below 1%\. Correspondingly, the computational cost increases fromCARTtoBRas optimality improves\. Therefore, we generally recommendMHABR, which offers strong optimality while keeping the computational cost reasonable\.

Table 5:Comparison ofCART,MHABR,MHABR2\\texttt\{MHABR\}^\{2\}, andBRagainst the global optimum across 10 datasets \(d=3d=3\)Datasetnnppncn\_\{c\}CART\(greedy\)MHABRMHABR2\\texttt\{MHABR\}^\{2\}\(optimal\)BR\(optimal\)Gap \(%\)Time \(ss\)Gap \(%\)Time \(ss\)Gap \(%\)Time \(ss\)Gap \(%\)Time \(ss\)Iris150432\.680\.00040\.180\.020\.000\.090\.000\.09Haberman\-survival306323\.970\.00020\.690\.010\.000\.120\.000\.12Monks\-problems\-3554622\.410\.00022\.460\.010\.000\.020\.000\.02Monks\-problems\-15566212\.150\.00051\.020\.010\.000\.020\.000\.02Monks\-problems\-2600622\.700\.00190\.450\.010\.000\.020\.000\.02Balance\-scale625433\.450\.00011\.090\.010\.000\.020\.000\.02Blood\-transfusion748422\.360\.00011\.030\.020\.000\.450\.000\.45Mammographic\-mass830521\.160\.00040\.220\.020\.000\.310\.000\.31Contraceptive\-method\-choice1,473939\.950\.00101\.000\.030\.000\.510\.000\.51Car\-evaluation1,728643\.720\.00010\.600\.010\.000\.070\.000\.07

Table 6:Comparison ofCART,MHABR,MHABR2\\texttt\{MHABR\}^\{2\}, andBRagainst the global optimum across 10 datasets \(d=4d=4\)Datasetnnppncn\_\{c\}CART\(greedy\)MHABRMHABR2\\texttt\{MHABR\}^\{2\}BR\(optimal\)Gap \(%\)Time \(ss\)Gap \(%\)Time \(ss\)Gap \(%\)Time \(ss\)Gap \(%\)Time \(ss\)Iris150430\.540\.00050\.000\.020\.000\.300\.008\.36Haberman\-survival306326\.940\.00021\.710\.030\.200\.240\.005\.05Monks\-problems\-3554620\.000\.00020\.000\.020\.000\.040\.000\.24Monks\-problems\-15566216\.260\.00062\.480\.020\.070\.040\.000\.25Monks\-problems\-2600624\.460\.00211\.130\.030\.640\.050\.000\.27Balance\-scale625435\.660\.00010\.780\.030\.400\.060\.000\.39Blood\-transfusion748424\.000\.00011\.230\.080\.491\.080\.0034\.71Mammographic\-mass830522\.360\.00050\.620\.070\.220\.730\.0015\.38Contraceptive\-method\-choice1,473935\.760\.00111\.190\.110\.271\.400\.0028\.79Car\-evaluation1,728643\.820\.00010\.110\.050\.000\.150\.001\.24

### 5\.6Ablation Studies

We now study how the reduction strategy, the MH method, and tunable parametersε\\varepsilonandθ\\thetaaffect the computational efficiency and accuracy ofMHABR, by systematically evaluating MH procedure performance per layer using anAvilacase study on a depth\-8 decision tree\.

\(a\) Impact of MH on training accuracy

\(b\) Reduction strategy

\(c\) Termination tolerance

\(d\) Mini\-batch

Figure 8:Ablation study ofMHABRonAvilausing 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\.To evaluate the contribution of the MH refinement, we show the results of a depth\-8 tree on the Avila dataset, without any other techniques except the approximation\. The result is shown in[Figure8](https://arxiv.org/html/2609.38194#S5.F8)\(a\)\. We observe that the most significant improvement occurs within the first five layers\. This suggests that the MH refinements have a greater impact on earlier branch nodes, where the corresponding subtrees are relatively larger and contain more samples\.

[Figure8](https://arxiv.org/html/2609.38194#S5.F8)\(b\) demonstrates that the reduction strategy significantly accelerates the computation of subtrees at various depths within the MH procedure\. It is evident that the reduction strategy yields a decrease in runtime of nearly two orders of magnitude for the depth\-8 subtree\. While this reduction in computational time becomes less pronounced as the subtree depth decreases, it still contributes to a considerable overall cost reduction\.

[Figure8](https://arxiv.org/html/2609.38194#S5.F8)\(c\) illustrates the convergence of results obtained through iterative refinement using MH under varying termination conditions\. The final accuracies achieved withε=\{10−2,10−3,10−4\}\\varepsilon=\\\{10^\{\-2\},10^\{\-3\},10^\{\-4\}\\\}are notably similar, butε=10−2\\varepsilon=10^\{\-2\}results in a 60% reduction in running time\. The scenario withε=10−1\\varepsilon=10^\{\-1\}exhibits a discernible decrease in accuracy\. Overall, larger values ofε\\varepsilonlead to lower accuracy forMHABR, but with the benefit of decreased training time\. This suggests the possibility of identifying a suitableε\\varepsilonthat incurs a minor reduction in accuracy while yielding significant savings in computational time, as exemplified byε=10−2\\varepsilon=10^\{\-2\}in this case\.

The influence of batch sizes is explored in[Figure8](https://arxiv.org/html/2609.38194#S5.F8)\(d\)\. Utilizing mini\-batches involves training a model on a subset of the data, which invariably reduces computational time\. Interestingly, this approach can sometimes yield superior performance\. As depicted in the figure, the accuracies achieved with batch size ratios \(θ\\theta\) of 0\.8 and 0\.9 surpass those obtained when using the complete dataset\. Conversely, a batch size ratio ofθ=0\.3\\theta=0\.3results in a relatively discernible reduction in accuracy \(but less than 5%\)\.

### 5\.7Practical Considerations and Limitations

##### Class imbalance and multiclass settings\.

MHABRapplies directly to both binary and multiclass classification because the feature\-threshold search is independent of the number of classes, while each leaf predicts the class that minimizes its misclassification loss\. Our experiments include multiclass datasets such asAvila,Shuttle, andWESAD, which demonstrate the applicability of the method beyond binary classification\. Nevertheless, the unweighted 0\-1 objective used in this study may favor majority classes on highly imbalanced datasets, and overall accuracy may not fully reflect minority\-class performance\. This limitation can be addressed by replacing the loss with a class\-weighted objective,Lw\(ℐ,T\)=∑i∈ℐwyi𝟏\{yi≠T\(xi\)\}L\_\{w\}\(\\mathcal\{I\},T\)=\\sum\_\{i\\in\\mathcal\{I\}\}w\_\{y\_\{i\}\}\\mathbf\{1\}\\\{y\_\{i\}\\neq T\(x\_\{i\}\)\\\}, while retaining the sameMHABRframework\. For problems with many classes, the feature\-threshold search space does not directly increase with the number of classes, although deeper trees may be required because a depth\-ddbinary tree has at most2d2^\{d\}leaves and can therefore predict at most2d2^\{d\}distinct class labels\.

##### Broader Impact

MHABRretains the explicit rule\-based structure of decision trees, which can improve transparency and facilitate model auditing\. However, interpretability alone does not guarantee fairness, robustness, or safe use\. In sensitive applications, the model should be carefully evaluated for bias, distribution shift, and subgroup performance, and should be used with appropriate human oversight\.

##### Practical Guidance

MHABRis intended for applications in which obtaining a high\-quality tree at a prescribed, interpretable depth is important and additional offline training time is acceptable\. It is particularly useful when greedy methods such asCARTprovide insufficient validation accuracy, while global optimization methods are computationally infeasible at the required dataset size or tree depth\. We recommend a staged workflow\. First, trainCARTat the prescribed depth to obtain a low\-cost accuracy benchmark and a feasible warm start forMHABR\. IfCARTalready achieves satisfactory validation performance, further optimization may be unnecessary\. Otherwise, apply a light version ofMHABR, and compare its validation gain against the additional training time\. A more intensiveMHABRconfiguration should be used only when the light version provides a meaningful improvement, as inAvila; when the gain is marginal or absent, as inHtru,CARTorDPDToffers a better accuracy\-runtime tradeoff\.

## 6Conclusion and Discussion

We introducedMHABR, an approximate method for training deep classification trees within a hierarchical root\-subtree framework\. The method combines a root\-level branch\-and\-reduce search, an approximate subtree solver based on CART, and a moving\-horizon refinement procedure\. The resulting algorithm is exact for depth\-2 trees and performs well empirically on the benchmark datasets considered in this paper\. In particular, it achieves strong test accuracy relative to the compared baselines while remaining computationally feasible on larger datasets than the exact global methods included in our study\. These results suggest thatMHABRoffers a favorable empirical trade\-off between optimization quality, runtime, and scalability\.

#### Acknowledgments and Disclosure of Funding

Yankai Cao acknowledges funding from the Discovery Grants program of the Natural Sciences and Engineering Research Council of Canada under Grant RGPIN\-2026\-07255, and from the New Frontiers in Research Fund under Grant NFRFE2022\-00663\. The authors also gratefully acknowledge the computing resources and services provided by the Digital Research Alliance of Canada and Advanced Research Computing at the University of British Columbia\.

## References

- Aghaeiet al\.\(2024\)S\. Aghaei, A\. Gómez, and P\. VayanosStrong optimal classification trees\.Operations Research\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Aglinet al\.\(2020\)G\. Aglin, S\. Nijssen, and P\. SchausLearning optimal decision trees using caching branch\-and\-bound search\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 3146–3153\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1),[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p6.1),[§5](https://arxiv.org/html/2609.38194#S5.p1.1)\.
- Alòset al\.\(2023\)J\. Alòs, C\. Ansótegui, and E\. TorresInterpretable decision trees through maxsat\.Artificial Intelligence Review56\(8\),pp\. 8303–8323\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Avellaneda \(2020\)F\. AvellanedaEfficient inference of optimal decision trees\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 3195–3202\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Bertsekas \(2024\)D\. BertsekasA course in reinforcement learning\.Athena Scientific\.Cited by:[§4\.2](https://arxiv.org/html/2609.38194#S4.SS2.p1.1),[§4\.2](https://arxiv.org/html/2609.38194#S4.SS2.p2.2)\.
- Bertsimas and Dunn \(2017\)D\. Bertsimas and J\. DunnOptimal classification trees\.Machine Learning106,pp\. 1039–1082\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Breimanet al\.\(1984\)L\. Breiman, J\. Friedman, R\. Olshen, and C\. StoneCart\.Classification and Regression Trees\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Carreira\-Perpinán and Tavallali \(2018\)M\. A\. Carreira\-Perpinán and P\. TavallaliAlternating optimization of decision trees, with application to learning sparse oblique trees\.Advances in neural information processing systems31\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p3.1),[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p8.1),[§5](https://arxiv.org/html/2609.38194#S5.p1.1),[§8](https://arxiv.org/html/2609.38194#S8.p1.1)\.
- Carreira\-Perpiñán and Zharmagambetov \(2020\)M\. Á\. Carreira\-Perpiñán and A\. ZharmagambetovEnsembles of bagged tao trees consistently improve over random forests, adaboost and gradient boosting\.InProceedings of the 2020 ACM\-IMS on foundations of data science conference,pp\. 35–46\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p3.1)\.
- Demirovićet al\.\(2022\)E\. Demirović, A\. Lukina, E\. Hebrard, J\. Chan, J\. Bailey, C\. Leckie, K\. Ramamohanarao, and P\. J\. StuckeyMurtree: optimal decision trees via dynamic programming and search\.Journal of Machine Learning Research23\(26\),pp\. 1–47\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1),[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p6.1)\.
- Dua and Graff \(2017\)D\. Dua and C\. GraffUCI machine learning repository\.University of California, Irvine, School of Information and Computer Sciences\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p6.1),[§5](https://arxiv.org/html/2609.38194#S5.p2.1)\.
- Dunn \(2018\)J\. DunnOptimal trees for prediction and prescription\.Ph\.D\. thesis,Massachusetts Institute of Technology\.Cited by:[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p5.1),[§5](https://arxiv.org/html/2609.38194#S5.p1.1)\.
- Dwyer and Holte \(2007\)K\. Dwyer and R\. HolteDecision tree instability and active learning\.InEuropean conference on machine learning,pp\. 128–139\.Cited by:[§2\.2](https://arxiv.org/html/2609.38194#S2.SS2.p1.1)\.
- Freitas \(2014\)A\. A\. FreitasComprehensible classification models: a position paper\.ACM SIGKDD Explorations Newsletter15\(1\),pp\. 1–10\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Günlüket al\.\(2021\)O\. Günlük, J\. Kalagnanam, M\. Li, M\. Menickelly, and K\. ScheinbergOptimal decision trees for categorical data via integer programming\.Journal of Global Optimization81,pp\. 233–260\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Huet al\.\(2020\)H\. Hu, M\. Siala, E\. Hebrard, and M\. HuguetLearning optimal decision trees with maxsat and its integration in adaboost\.InIJCAI\-PRICAI 2020, 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence,Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Huaet al\.\(2022\)K\. Hua, J\. Ren, and Y\. CaoA scalable deterministic global optimization algorithm for training optimal decision tree\.Advances in Neural Information Processing Systems35,pp\. 8347–8359\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1),[Remark 3\.5](https://arxiv.org/html/2609.38194#S3.Thmtheorem5.p1.1)\.
- Huismanet al\.\(2024\)T\. Huisman, J\. G\. van der Linden, and E\. DemirovićOptimal survival trees: a dynamic programming approach\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 12680–12688\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Kohleret al\.\(2025\)H\. Kohler, R\. Akrour, and P\. PreuxBreiman meets bellman: non\-greedy decision trees with mdps\.InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\. 2,pp\. 1207–1218\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p3.1),[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p4.1),[§4\.2](https://arxiv.org/html/2609.38194#S4.SS2.p1.1),[§5](https://arxiv.org/html/2609.38194#S5.p1.1)\.
- Krzywinski and Altman \(2017\)M\. Krzywinski and N\. AltmanClassification and regression trees\.Nature Methods14\(8\),pp\. 757–758\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Laurent and Rivest \(1976\)H\. Laurent and R\. L\. RivestConstructing optimal binary decision trees is np\-complete\.Information Processing Letters5\(1\),pp\. 15–17\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Linet al\.\(2020\)J\. Lin, C\. Zhong, D\. Hu, C\. Rudin, and M\. SeltzerGeneralized and scalable optimal sparse decision trees\.InInternational Conference on Machine Learning,pp\. 6150–6160\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Mazumderet al\.\(2022\)R\. Mazumder, X\. Meng, and H\. WangQuant\-bnb: a scalable branch\-and\-bound method for optimal decision trees with continuous features\.InInternational Conference on Machine Learning,pp\. 15255–15277\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1),[§1](https://arxiv.org/html/2609.38194#S1.p3.1),[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p7.1),[§2](https://arxiv.org/html/2609.38194#S2.p1.1),[Remark 3\.5](https://arxiv.org/html/2609.38194#S3.Thmtheorem5.p1.1),[§5\.2](https://arxiv.org/html/2609.38194#S5.SS2.SSS0.Px1.p1.1),[§5](https://arxiv.org/html/2609.38194#S5.p1.1)\.
- McTavishet al\.\(2022\)H\. McTavish, C\. Zhong, R\. Achermann, I\. Karimalis, J\. Chen, C\. Rudin, and M\. SeltzerFast sparse decision tree optimization via reference ensembles\.InProceedings of the AAAI conference on artificial intelligence,Vol\.36,pp\. 9604–9613\.Cited by:[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p6.1)\.
- Nijssen and Fromont \(2007\)S\. Nijssen and E\. FromontMining optimal decision trees from itemset lattices\.InProceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 530–539\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Quinlan \(1986\)J\. R\. QuinlanInduction of decision trees\.Machine Learning1,pp\. 81–106\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Quinlan \(1993\)J\. R\. QuinlanC4\. 5: programs for machine learning\.The Morgan Kaufmann Series in Machine Learning\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Rudin \(2019\)C\. RudinStop explaining black box machine learning models for high stakes decisions and use interpretable models instead\.Nature Machine Intelligence1\(5\),pp\. 206–215\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Rudin \(2022\)C\. RudinWhy black box machine learning should be avoided for high\-stakes decisions, in brief\.Nature Reviews Methods Primers2\(1\),pp\. 81\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p1.1)\.
- Ryoo and Sahinidis \(1996\)H\. S\. Ryoo and N\. V\. SahinidisA branch\-and\-reduce approach to global optimization\.Journal of Global Optimization8,pp\. 107–138\.Cited by:[§3\.1](https://arxiv.org/html/2609.38194#S3.SS1.SSS0.Px5.p1.1)\.
- Sadeghiet al\.\(2022\)DecisionTree\.jl \- A Julia implementation of the CART Decision Tree and Random Forest algorithmsExternal Links:[Document](https://dx.doi.org/10.5281/zenodo.7359268),[Link](https://doi.org/10.5281/zenodo.7359268)Cited by:[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p3.1),[§5](https://arxiv.org/html/2609.38194#S5.p1.1)\.
- Shannon and Banks \(1999\)W\. D\. Shannon and D\. BanksCombining classification trees using mle\.Statistics in medicine18\(6\),pp\. 727–740\.Cited by:[§2\.2](https://arxiv.org/html/2609.38194#S2.SS2.p1.1)\.
- Shatiet al\.\(2023\)P\. Shati, E\. Cohen, and S\. A\. McIlraithSAT\-based optimal classification trees for non\-binary data\.Constraints28\(2\),pp\. 166–202\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Tawarmalani and Sahinidis \(2004\)M\. Tawarmalani and N\. V\. SahinidisGlobal optimization of mixed\-integer nonlinear programs: a theoretical and computational study\.Mathematical Programming99\(3\),pp\. 563–591\.Cited by:[§3\.1](https://arxiv.org/html/2609.38194#S3.SS1.SSS0.Px5.p1.1)\.
- van der Lindenet al\.\(2023\)J\. van der Linden, M\. de Weerdt, and E\. DemirovićNecessary and sufficient conditions for optimal decision trees using dynamic programming\.Advances in Neural Information Processing Systems36,pp\. 9173–9212\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1),[§10\.3](https://arxiv.org/html/2609.38194#S10.SS3.p9.1)\.
- Van der Lindenet al\.\(2022\)J\. G\. M\. Van der Linden, M\. De Weerdt, and E\. DemirovićFair and optimal decision trees: a dynamic programming approach\.Advances in Neural Information Processing Systems35,pp\. 38899–38911\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Verwer and Zhang \(2019\)S\. Verwer and Y\. ZhangLearning optimal classification trees using a binary linear program formulation\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 1625–1632\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.
- Zharmagambetovet al\.\(2021\)A\. Zharmagambetov, M\. Gabidolla, and M\. Ê\. Carreira\-PerpiñánImproved boosted regression forests through non\-greedy tree optimization\.In2021 International Joint Conference on Neural Networks \(IJCNN\),pp\. 1–8\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p3.1)\.
- Zhu and Shoaran \(2021\)B\. Zhu and M\. ShoaranTree in tree: from decision trees to decision graphs\.Advances in Neural Information Processing Systems34,pp\. 13707–13718\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p3.1)\.
- Zhuet al\.\(2020\)H\. Zhu, P\. Murali, D\. Phan, L\. Nguyen, and J\. KalagnanamA scalable mip\-based method for learning optimal multivariate decision trees\.Advances in Neural Information Processing Systems33,pp\. 1771–1781\.Cited by:[§1](https://arxiv.org/html/2609.38194#S1.p2.1)\.

## Appendix

## 7Summary of Notation

Table[7](https://arxiv.org/html/2609.38194#S7.T7)summarizes the notation used throughout the paper\.

Table 7:Summary of notation used in this paper\.SymbolDescriptionData and decision\-tree notation\{\(xi,yi\)\}i=1n\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{n\}Dataset ofnnfeature–label pairs\.𝒴\\mathcal\{Y\}Set of class labels\.nn,pp,ncn\_\{c\}Numbers of samples, features, and classes, respectively\.\[n\]\[n\]Index set\{1,…,n\}\\\{1,\\ldots,n\\\}\.ℐ⊆\[n\]\\mathcal\{I\}\\subseteq\[n\]Index set of samples in a tree or subtree\.ddPrespecified depth of a decision tree\.𝒯d\\mathcal\{T\}\_\{d\}Set of feasible decision trees of depthdd\.𝒩B\\mathcal\{N\}\_\{B\},𝒩L\\mathcal\{N\}\_\{L\}Sets of branch nodes and leaf nodes, respectively\.T=\[a,k,TL,TR\]T=\[a,k,T\_\{L\},T\_\{R\}\]DT with root featureaa, threshold indexkk, left and right subtreesTLT\_\{L\}andTRT\_\{R\}\.𝐚\\mathbf\{a\},𝐛\\mathbf\{b\},𝐜\\mathbf\{c\}Vectors of split features, split thresholds, and leaf predictions\.L⁡\(ℐ,T\)L\(\\mathcal\{I\},T\)Misclassification loss of treeTTon the samples indexed byℐ\\mathcal\{I\}\.Vd​\(ℐ\)V\_\{d\}\(\\mathcal\{I\}\)Minimum loss achievable by a depth\-ddtree onℐ\\mathcal\{I\}\.Vd​\(ℐ,a,k\)V\_\{d\}\(\\mathcal\{I\},a,k\)Minimum loss when the root feature and threshold index are fixed toaaandkk\.V0​\(ℐ\)V\_\{0\}\(\\mathcal\{I\}\)Minimum loss of a constant\-label prediction onℐ\\mathcal\{I\}\.Candidate splits and sample partitionsℐa\\mathcal\{I\}^\{a\}Sample indices sorted according to featureaa\.nan\_\{a\}Number of unique values of featureaa\.ukau\_\{k\}^\{a\}Thekkth unique value of featureaa\.βka\\beta\_\{k\}^\{a\}Candidate split threshold associated with indexkkfor featureaa\.𝒦a\\mathcal\{K\}^\{a\}Set of candidate threshold indices for featureaa\.ℬa\\mathcal\{B\}^\{a\}Set of candidate thresholds\{βka:k∈𝒦a\}\\\{\\beta\_\{k\}^\{a\}:k\\in\\mathcal\{K\}^\{a\}\\\}\.ζ⁡\(k\)\\zeta\(k\)The number of samples assigned to the left child byβka\\beta\_\{k\}^\{a\}\.ℐ\[k1,k2\]a\\mathcal\{I\}^\{a\}\_\{\[k\_\{1\},k\_\{2\}\]\}Samples whose values of featureaalie between the thresholds indexed byk1k\_\{1\}andk2k\_\{2\}\.Branch\-and\-reduce notation𝒦i=\{l,…,m\}\\mathcal\{K\}\_\{i\}=\\\{l,\\ldots,m\\\}Candidate threshold\-index region represented by a search node\.k¯\\bar\{k\}Midpoint threshold index selected from𝒦i\\mathcal\{K\}\_\{i\}\.𝕂\\mathbb\{K\}Collection of active candidate regions in the branch\-and\-reduce search\.UUIncumbent upper bound, i\.e\., the best feasible loss found so far\.L​BLBLower bound associated with a candidate region\.δ⁡\(k¯\)\\delta\(\\bar\{k\}\)Reduction radius calculated from the evaluated loss and incumbent upper bound\.Δi\\Delta\_\{i\}Set of candidate threshold indices removed from𝒦i\\mathcal\{K\}\_\{i\}by the reduction rule\.𝒦L\\mathcal\{K\}\_\{L\},𝒦R\\mathcal\{K\}\_\{R\}Left and right candidate regions generated after reduction and branching\.Approximation and moving\-horizon notationWd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)Objective value attained by the depth\-ddCARTtree on the sample setℐ\\mathcal\{I\}\.V^d​\(ℐ\)\\widehat\{V\}\_\{d\}\(\\mathcal\{I\}\)Optimal value of theCART\-based approximate child\-subtree problem\.V^d​\(ℐ,a,k\)\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,k\)Approximate objective value for the fixed root split\(a,k\)\(a,k\)\.ttIndex of the node used as the root of the current moving\-horizon subproblem\.ℐt\\mathcal\{I\}\_\{t\}Samples reaching nodett\.SymbolDescriptionℐsub\\mathcal\{I\}\_\{\\mathrm\{sub\}\}Sample set associated with the current subtree optimization problem\.TsubT\_\{\\mathrm\{sub\}\}Tree returned for the current subtree optimization problem\.dsubd\_\{\\mathrm\{sub\}\}Depth of the current subtree\.UsubU\_\{\\mathrm\{sub\}\}Objective value of the current subtree solution\.Complexity and experimental parametersn~\\widetilde\{n\}Maximum feature–threshold pairs evaluated in aBR/ABRroot search\.θ∈\(0,1\]\\theta\\in\(0,1\]Mini\-batch sampling ratio used in the light version ofMHABR\.ε\\varepsilonThreshold\-search termination tolerance used for large\-scale datasets\.α\\alphaTree\-complexity regularization coefficient\.
## 8Supplementary Experiments: Comparison with TAO

We also provide an informal comparison with the well\-known heuristic methodTAO\([Carreira\-Perpinán and Tavallali, 2018](https://arxiv.org/html/2609.38194#bib.bib4)\)\. Because the authors do not provide publicly available code for reproducibility, we evaluated our method on the same five datasets reported in Appendix 2\.1 of their paper, using the identical data split \(50%50\\%training,25%25\\%validation, and25%25\\%testing\)\. The corresponding results are presented below:

Table 8:Performance comparison betweenTAOandMHABR\. Results are reported as mean accuracy with standard deviation in parentheses\. Best results for each dataset, depth, and split are highlighted in bold\.DatasetDepthTrainTestTAOMHABRTAOMHABRBalance\-scaled=2d=272\.5 \(1\.6\)72\.7\(0\.7\)69\.5\(2\.9\)68\.5 \(2\.0\)d=3d=376\.9\(1\.1\)76\.8 \(1\.4\)71\.6 \(1\.9\)74\.8\(2\.2\)d=4d=484\.0 \(1\.5\)84\.1\(1\.1\)79\.8\(3\.1\)78\.9 \(2\.7\)Banknote\-auth\.d=2d=291\.9 \(0\.4\)92\.8\(0\.4\)90\.6 \(0\.9\)91\.3\(1\.1\)d=3d=396\.0 \(0\.5\)98\.3\(0\.4\)95\.7 \(1\.2\)97\.2\(0\.6\)d=4d=498\.9 \(0\.7\)99\.5\(0\.3\)97\.2 \(0\.7\)98\.7\(0\.5\)Blood\-transfusiond=2d=278\.0\(0\.8\)77\.9 \(1\.4\)75\.8 \(2\.0\)77\.1\(3\.7\)d=3d=379\.5 \(1\.0\)80\.3\(1\.4\)77\.0 \(2\.0\)77\.8\(2\.9\)d=4d=481\.6\(1\.3\)80\.7 \(2\.3\)77\.2 \(1\.3\)77\.6\(3\.5\)Breast\-cancerd=2d=295\.0 \(0\.5\)96\.4\(0\.4\)92\.7 \(2\.2\)93\.9\(1\.7\)d=3d=397\.0 \(0\.6\)98\.5\(0\.5\)93\.1 \(1\.4\)95\.0\(1\.7\)d=4d=498\.0 \(0\.5\)99\.6\(0\.3\)93\.2 \(0\.5\)95\.1\(1\.8\)Spambased=2d=286\.5 \(0\.7\)87\.3\(0\.5\)86\.1 \(1\.0\)86\.9\(0\.6\)d=3d=390\.0 \(0\.4\)90\.8\(0\.3\)89\.1 \(1\.0\)90\.3\(0\.8\)d=4d=491\.8 \(0\.3\)92\.3\(0\.6\)90\.3 \(0\.8\)91\.3\(0\.8\)Across the matched dataset\-depth combinations reported byTAO,MHABRachieves an average training accuracy of 88\.5%, compared with 87\.8% forTAO, and an average testing accuracy of 86\.3%, compared with 85\.3%\. These differences correspond to average improvements of 0\.7 and 1\.0 percentage points in training and testing accuracy, respectively\. Although performance varies across individual datasets and tree depths, the aggregate results favorMHABR\. Results for deeper trees are not included because they were not reported forTAO\.

##### Limitations of theTAOcomparison

TheTAOresults are taken directly from its original publication rather than obtained through a controlled reimplementation\. Because a public implementation is unavailable, we could not standardize data preprocessing, train–test splits, stopping criteria, implementation details, or computational hardware across the two methods\. We therefore present this comparison only as supplementary evidence and do not rely on it to support the primary empirical claims of this paper\.

## 9Additional Theoretical Results and Analysis

In this section, we recall theCARTvariant used in our theoretical analysis, define its misclassification loss, introduce the reducedCARTalgorithm, and discuss conditions under whichMHABRimproves upon this greedy procedure\.

### 9\.1Recall the basics ofCART

Letℐt\\mathcal\{I\}\_\{t\}denote the sample index set at nodet∈𝒩B∪𝒩Lt\\in\\mathcal\{N\}\_\{B\}\\cup\\mathcal\{N\}\_\{L\}\. The optimal loss of assigning a constant class prediction to this node is

V0\(ℐt\):=minc∈𝒴L\(ℐt,c\)=minc∈𝒴∑i∈ℐt𝟏\{yi≠c\}\.V\_\{0\}\(\\mathcal\{I\}\_\{t\}\):=\\min\_\{c\\in\\mathcal\{Y\}\}L\(\\mathcal\{I\}\_\{t\},c\)=\\min\_\{c\\in\\mathcal\{Y\}\}\\sum\_\{i\\in\\mathcal\{I\}\_\{t\}\}\\mathbf\{1\}\\\{y\_\{i\}\\neq c\\\}\.\(38\)
The misclassification\-basedCARTrule selects the feature and threshold pair that minimizes the combined potential loss of its two children:

\(at′,kt′\)∈arg⁡mina∈\[p\],k∈𝒦a​\{V0​\(ℐt,\[0,k\]a\)\+V0​\(ℐt,\[k,na\]a\)\},\(a^\{\\prime\}\_\{t\},k^\{\\prime\}\_\{t\}\)\\in\\arg\\min\_\{a\\in\[p\],\\ k\\in\\mathcal\{K\}^\{a\}\}\\left\\\{V\_\{0\}\\\!\\left\(\\mathcal\{I\}^\{a\}\_\{t,\[0,k\]\}\\right\)\+V\_\{0\}\\\!\\left\(\\mathcal\{I\}^\{a\}\_\{t,\[k,n\_\{a\}\]\}\\right\)\\right\\\},\(39\)whereℐt,\[0,k\]a\\mathcal\{I\}^\{a\}\_\{t,\[0,k\]\}andℐt,\[k,na\]a\\mathcal\{I\}^\{a\}\_\{t,\[k,n\_\{a\}\]\}are the sample sets assigned to the left and right children, respectively\.

For a sample index setℐ\\mathcal\{I\}, letT^d​\(ℐ\)\\hat\{T\}\_\{d\}\(\\mathcal\{I\}\)denote the depth\-ddtree returned by this recursiveCARTprocedure\. Its loss is defined as the resulting misclassification count:

Wd\(ℐ\):=L\(ℐ,T^d\(ℐ\)\)=∑i∈ℐ𝟏\{yi≠T^d\(xi\)\}\.W\_\{d\}\(\\mathcal\{I\}\):=L\\\!\\left\(\\mathcal\{I\},\\hat\{T\}\_\{d\}\(\\mathcal\{I\}\)\\right\)=\\sum\_\{i\\in\\mathcal\{I\}\}\\mathbf\{1\}\\left\\\{y\_\{i\}\\neq\\hat\{T\}\_\{d\}\(x\_\{i\}\)\\right\\\}\.\(40\)Ford=0d=0, the tree consists of a majority\-class leaf, and therefore

W0​\(ℐ\)=V0​\(ℐ\)\.W\_\{0\}\(\\mathcal\{I\}\)=V\_\{0\}\(\\mathcal\{I\}\)\.\(41\)If\(a′,k′\)\(a^\{\\prime\},k^\{\\prime\}\)denotes the root split selected byCART, then the additivity of the misclassification loss gives

Wd​\(ℐ\)=Wd−1​\(ℐ\[0,k′\]a′\)\+Wd−1​\(ℐ\[k′,na′\]a′\)\.W\_\{d\}\(\\mathcal\{I\}\)=W\_\{d\-1\}\\\!\\left\(\\mathcal\{I\}^\{a^\{\\prime\}\}\_\{\[0,k^\{\\prime\}\]\}\\right\)\+W\_\{d\-1\}\\\!\\left\(\\mathcal\{I\}^\{a^\{\\prime\}\}\_\{\[k^\{\\prime\},n\_\{a^\{\\prime\}\}\]\}\\right\)\.\(42\)
The quantityWd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)always denotes the final misclassification loss of the resulting tree\. In the numerical comparison, the standardCARTbaseline may use a different impurity criterion, such as entropy, to select its splits; this does not change the definition of its reported misclassification loss\.

##### Depth\-1 optimality

For a sample subsetℐ⊆\[n\]\\mathcal\{I\}\\subseteq\[n\], a depth\-1 DT comprises two optimal constant fits, i\.e\., two optimal depth\-0 subtrees, expressed byV0​\(ℐ\)=minc∈𝒴⁡L⁡\(ℐ,c\)V\_\{0\}\(\\mathcal\{I\}\)=\\min\_\{c\\in\\mathcal\{Y\}\}L\(\\mathcal\{I\},c\), which denotes the loss of the best constant approximation to𝒴\\mathcal\{Y\}, in the same manner asCART\. Ford=1d=1,CARTsolves a one\-stage decision problem, which, according to the greedy nature, is optimal\.

##### Monotonicity

The loss function ofCARTexhibits monotonicity with respect to tree depth, such thatWd​\(ℐ\)≤Wd−1​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)\\leq W\_\{d\-1\}\(\\mathcal\{I\}\)\. This is attributed to the monotonic nature of the branching operation concerning the count of correctly classified samples \(accuracy\)\. Branching will either increase this count \(thereby decreasing the loss\) or, in the worst\-case scenario where the newly formed leaves offer no improvement over their parent node, the count will remain unchanged\.

For example, we consider a nodettwith dataℐt\\mathcal\{I\}\_\{t\}, the potential loss isV0​\(ℐt\)V\_\{0\}\(\\mathcal\{I\}\_\{t\}\)as defined by[Equation38](https://arxiv.org/html/2609.38194#S9.E38), with predictionc1c\_\{1\}\. Then, we branch the node to obtain two branch nodesℐ2​t,ℐ2​t\+1\\mathcal\{I\}\_\{2t\},\\mathcal\{I\}\_\{2t\+1\}, whereℐ2​t∪ℐ2​t\+1=ℐt\\mathcal\{I\}\_\{2t\}\\cup\\mathcal\{I\}\_\{2t\+1\}=\\mathcal\{I\}\_\{t\}\. The losses of these new nodes areV0​\(ℐ2​t\)V\_\{0\}\(\\mathcal\{I\}\_\{2t\}\)andV0​\(ℐ2​t\+1\)V\_\{0\}\(\\mathcal\{I\}\_\{2t\+1\}\)with predictionsc2c\_\{2\}andc3c\_\{3\}, respectively\. Then we have:

V0\(ℐt\)=∑i∈ℐ𝟙\{yi≠c1\}\\displaystyle V\_\{0\}\(\\mathcal\{I\}\_\{t\}\)=\\sum\_\{i\\in\\mathcal\{I\}\}\\mathbbm\{1\}\\\{y\_\{i\}\\neq c\_\{1\}\\\}=∑i∈ℐ2​t𝟙\{yi≠c1\}\+∑i∈ℐ2​t\+1𝟙\{yi≠c1\}\\displaystyle=\\sum\_\{i\\in\\mathcal\{I\}\_\{2t\}\}\\mathbbm\{1\}\\\{y\_\{i\}\\neq c\_\{1\}\\\}\+\\sum\_\{i\\in\\mathcal\{I\}\_\{2t\+1\}\}\\mathbbm\{1\}\\\{y\_\{i\}\\neq c\_\{1\}\\\}≥∑i∈ℐ2​t𝟙\{yi≠c2\}\+∑i∈ℐ2​t\+1𝟙\{yi≠c3\}\\displaystyle\\geq\\sum\_\{i\\in\\mathcal\{I\}\_\{2t\}\}\\mathbbm\{1\}\\\{y\_\{i\}\\neq c\_\{2\}\\\}\+\\sum\_\{i\\in\\mathcal\{I\}\_\{2t\+1\}\}\\mathbbm\{1\}\\\{y\_\{i\}\\neq c\_\{3\}\\\}=V0​\(ℐ2​t\)\+V0​\(ℐ2​t\+1\),\\displaystyle=V\_\{0\}\(\\mathcal\{I\}\_\{2t\}\)\+V\_\{0\}\(\\mathcal\{I\}\_\{2t\+1\}\),\(43\)The inequality holds becausec2c\_\{2\}andc3c\_\{3\}are chosen as the predictions that minimize the misclassifications within their respective nodes2​t2tand2​t\+12t\+1\(defined as the most frequent class in[Equation38](https://arxiv.org/html/2609.38194#S9.E38)\)\. By definition, the optimal predictionc2c\_\{2\}for nodeℐ2​t\\mathcal\{I\}\_\{2t\}must classify at least as many samples correctly withinℐ2​t\\mathcal\{I\}\_\{2t\}as any other prediction, includingc1c\_\{1\}\. Thus,∑i∈ℐ2​t𝟙\{yi≠c2\}≤∑i∈ℐ2​t𝟙\{yi≠c1\}\\sum\_\{i\\in\\mathcal\{I\}\_\{2t\}\}\\mathbbm\{1\}\\\{y\_\{i\}\\neq c\_\{2\}\\\}\\leq\\sum\_\{i\\in\\mathcal\{I\}\_\{2t\}\}\\mathbbm\{1\}\\\{y\_\{i\}\\neq c\_\{1\}\\\}, and similarly forc3c\_\{3\}overℐ2​t\+1\\mathcal\{I\}\_\{2t\+1\}\. Therefore, the loss after branching is less than or equal to the value before branching\.

### 9\.2A reducedCARTmethod

Algorithm 4ReducedCARTfor a depth\-ddtree1:functionR\-CART\(ℐ,d\)\(\\mathcal\{I\},d\)

2:Compute

V0​\(ℐ\)←minc∈𝒴⁡L⁡\(ℐ,c\)V\_\{0\}\(\\mathcal\{I\}\)\\leftarrow\\min\_\{c\\in\\mathcal\{Y\}\}L\(\\mathcal\{I\},c\)and

c′←arg⁡minc∈𝒴⁡L⁡\(ℐ,c\)c^\{\\prime\}\\leftarrow\\arg\\min\_\{c\\in\\mathcal\{Y\}\}L\(\\mathcal\{I\},c\)
3:if

d=0d=0or\|ℐ\|≤1\|\\mathcal\{I\}\|\\leq 1orV0​\(ℐ\)=0V\_\{0\}\(\\mathcal\{I\}\)=0then

4:return:

V0​\(ℐ\)V\_\{0\}\(\\mathcal\{I\}\)and leaf

c′c^\{\\prime\}
5:Initialize

U←\+∞U\\leftarrow\+\\inftyand

\(a′,k′\)←∅\(a^\{\\prime\},k^\{\\prime\}\)\\leftarrow\\emptyset
6:for

a∈\[p\]a\\in\[p\]do

7:Sort

ℐ\\mathcal\{I\}by feature

aato obtain

ℐa\\mathcal\{I\}^\{a\}and

𝒦a\\mathcal\{K\}^\{a\}, set

𝒦←𝒦a\\mathcal\{K\}\\leftarrow\\mathcal\{K\}^\{a\}
8:while

𝒦≠∅\\mathcal\{K\}\\neq\\emptysetdo

9:Select

k¯←𝒦⁡\[1\]\\bar\{k\}\\leftarrow\\mathcal\{K\}\[1\]and compute

V1​\(ℐ,a,k¯\)←V0​\(ℐ\[0,k¯\]a\)\+V0​\(ℐ\[k¯,na\]a\)V\_\{1\}\(\\mathcal\{I\},a,\\bar\{k\}\)\\leftarrow V\_\{0\}\(\\mathcal\{I\}^\{a\}\_\{\[0,\\bar\{k\}\]\}\)\+V\_\{0\}\(\\mathcal\{I\}^\{a\}\_\{\[\\bar\{k\},n\_\{a\}\]\}\)
10:if

V1​\(ℐ,a,k¯\)<UV\_\{1\}\(\\mathcal\{I\},a,\\bar\{k\}\)<Uthen

11:Update

U←V1​\(ℐ,a,k¯\)U\\leftarrow V\_\{1\}\(\\mathcal\{I\},a,\\bar\{k\}\)and

\(a′,k′\)←\(a,k¯\)\(a^\{\\prime\},k^\{\\prime\}\)\\leftarrow\(a,\\bar\{k\}\)
12:Compute

δ⁡\(k¯\)←V1​\(ℐ,a,k¯\)−U\\delta\(\\bar\{k\}\)\\leftarrow V\_\{1\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-Uand get

𝒦←\{k∈𝒦∣ζ⁡\(k\)−ζ⁡\(k¯\)\>δ⁡\(k¯\)\}\\mathcal\{K\}\\leftarrow\\\{k\\in\\mathcal\{K\}\\mid\\zeta\(k\)\-\\zeta\(\\bar\{k\}\)\>\\delta\(\\bar\{k\}\)\\\}
13:Get the data

ℐL←ℐ\[0,k′\]a′\\mathcal\{\\mathcal\{I\}\}\_\{L\}\\leftarrow\\mathcal\{I\}^\{a^\{\\prime\}\}\_\{\[0,k^\{\\prime\}\]\}and

ℐR←I\[k′,na′\]a′\\mathcal\{\\mathcal\{I\}\}\_\{R\}\\leftarrow I^\{a^\{\\prime\}\}\_\{\[k^\{\\prime\},n\_\{a^\{\\prime\}\}\]\}
14:Compute

\(Wd−1​\(ℐL\),TL\)←R\-CART​\(ℐL,d−1\)\(W\_\{d\-1\}\(\\mathcal\{I\}\_\{L\}\),T\_\{L\}\)\\leftarrow\\texttt\{R\-CART\}\(\\mathcal\{I\}\_\{L\},d\-1\)and

\(Wd−1​\(ℐR\),TR\)←R\-CART​\(ℐR,d−1\)\(W\_\{d\-1\}\(\\mathcal\{I\}\_\{R\}\),T\_\{R\}\)\\leftarrow\\texttt\{R\-CART\}\(\\mathcal\{I\}\_\{R\},d\-1\)
15:Calculate

Wd​\(ℐ\)←Wd−1​\(ℐL\)\+Wd−1​\(ℐR\)W\_\{d\}\(\\mathcal\{I\}\)\\leftarrow W\_\{d\-1\}\(\\mathcal\{I\}\_\{L\}\)\+W\_\{d\-1\}\(\\mathcal\{I\}\_\{R\}\)and update

T←\[a′,k′,TL,TR\]T\\leftarrow\[a^\{\\prime\},k^\{\\prime\},T\_\{L\},T\_\{R\}\]
16:return:Loss

Wd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)and decision tree

TT

At each nonterminal node while usingBRmethod,CARTsolves a depth\-11split\-selection problem by evaluatingV1​\(ℐ,a,k\)V\_\{1\}\(\\mathcal\{I\},a,k\)over the candidate feature\-threshold pairs\. Whend=1d=1, the child\-subtree problems reduce to optimal constant predictions, and henceApproxTreeSearch\(ℐ,1\)\(\\mathcal\{I\},1\)is exact\. In this setting, the reduction strategy of[Algorithm2](https://arxiv.org/html/2609.38194#alg2)can be applied directly to the localCARTsplit search\. We refer to this reduced implementation asR\-CART, whose procedure is given in[Algorithm4](https://arxiv.org/html/2609.38194#alg4)\.

Unlike the midpoint\-based branching strategy used inBR,R\-CARTscans the candidate thresholds in ascending order and skips candidates that are certified not to improve the current incumbent\. The reduction is applied only to the local depth\-11split objective\. After a split is selected,R\-CARTis recursively applied to the two child datasets to construct a tree of depthdd\. Under the same candidate sets, stopping conditions, and tie\-breaking rule,R\-CARTreturns the same tree as standardCART, while potentially evaluating fewer split candidates\.

BecauseMHABRrepeatedly callsCARTwhen approximating child\-subtree problems, the computational savings provided byR\-CARTcan accumulate over the entire algorithm\. Without reduction, the root\-level search evaluates at most∑a=1p\|𝒦a\|\\sum\_\{a=1\}^\{p\}\|\\mathcal\{K\}^\{a\}\|candidate splits\. The reduction strategy decreases this number by skipping candidate thresholds that cannot strictly improve the incumbent solution\.

### 9\.3An Illustrative XOR Case for Greedy Failure

In this section, we use XOR\-style datasets as an illustrative example to explain why a lookahead\-based method can outperform greedyCART\. The XOR problem is a canonical topological trap for greedy splitting: a depth\-1 criterion may fail to identify informative features, whereas a shallow lookahead can recover the correct interaction\. Our goal here is to build intuition for the behavior ofMHABR\.

More broadly,ABRcan improve uponCARTin settings where a split that appears suboptimal under a purely greedy criterion leads to a better downstream subtree configuration under lookahead\. The following XOR example provides a simple instance of this phenomenon\.

##### XOR\-Distractor Dataset\.

We consider the following stylized data distribution\.

###### Definition 9\.1\.

Let the dataset be given by\{\(xi,yi\)\}i=1n\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{n\}wherexi∈\{0,1\}px\_\{i\}\\in\\\{0,1\\\}^\{p\}andyi∈𝒴=\{0,1\}y\_\{i\}\\in\\mathcal\{Y\}=\\\{0,1\\\}\. The targetyiy\_\{i\}is determined exclusively by the first two features via the XOR function:yi=xi1⊕xi2y\_\{i\}=x\_\{i\}^\{1\}\\oplus x\_\{i\}^\{2\}, wherexi1x\_\{i\}^\{1\}andxi2x\_\{i\}^\{2\}are drawn from independent uniform Bernoulli distributions \(P=0\.5P=0\.5\)\. The remaining featuresxi3,…,xipx\_\{i\}^\{3\},\\dots,x\_\{i\}^\{p\}are pure noise, drawn independently fromP⁡\(xih=1\)=0\.5P\(x\_\{i\}^\{h\}=1\)=0\.5forh≥3h\\geq 3\.

In this setting, a single greedy split on either informative feature does not reduce the immediate misclassification loss, because each informative feature alone leaves the label distribution balanced within the resulting child nodes\. In contrast, a depth\-2 lookahead can recover the XOR interaction by selecting splits that jointly isolate the homogeneous quadrants\.

###### Theorem 9\.2\(Failure of Greedy Splits\)\.

Given an XOR\-Distractor dataset defined in Definition[9\.1](https://arxiv.org/html/2609.38194#S9.Thmtheorem1), letV0​\(ℐ\)V\_\{0\}\(\\mathcal\{I\}\)denote the misclassification loss \(obtained using a constant prediction\) of a root node containingℐ\\mathcal\{I\}withnnsamples\. Suppose that, in the realized finite sample, the classes are balanced at the root and remain balanced in both child nodes after splitting on either true featurea=1a=1ora=2a=2\. Suppose further that there exists a noise featureh≥3h\\geq 3for which the class distribution is not balanced in at least one of the resulting child nodes\. Then, a greedy top\-down decision tree algorithm that selects a root split by maximizing the immediate misclassification\-loss reduction will select a noise feature rather than either true featurea=1a=1ora=2a=2\.

###### Proof\.

Let\|ℐ\|=n\|\\mathcal\{I\}\|=n\. Since the classes are balanced at the root,V0​\(ℐ\)=0\.5​nV\_\{0\}\(\\mathcal\{I\}\)=0\.5n\. For an informative featurea∈\{1,2\}a\\in\\\{1,2\\\}, letℐLa\\mathcal\{I\}\_\{L\}^\{a\}andℐRa\\mathcal\{I\}\_\{R\}^\{a\}denote the two child\-node sample sets\. By assumption, both child nodes remain class\-balanced\. Hence,V0​\(ℐLa\)=0\.5​\|ℐLa\|V\_\{0\}\(\\mathcal\{I\}\_\{L\}^\{a\}\)=0\.5\|\\mathcal\{I\}\_\{L\}^\{a\}\|andV0​\(ℐRa\)=0\.5​\|ℐRa\|V\_\{0\}\(\\mathcal\{I\}\_\{R\}^\{a\}\)=0\.5\|\\mathcal\{I\}\_\{R\}^\{a\}\|\. Therefore,

Δ​V0​\(a=1\)\\displaystyle\\Delta V\_\{0\}\(a=1\)=V0​\(ℐ\)−\(V0​\(ℐL1\)\+V0​\(ℐR1\)\)\\displaystyle=V\_\{0\}\(\\mathcal\{I\}\)\-\\left\(V\_\{0\}\(\\mathcal\{I\}\_\{L\}^\{1\}\)\+V\_\{0\}\(\\mathcal\{I\}\_\{R\}^\{1\}\)\\right\)=0\.5​n−\(0\.5​\|ℐL1\|\+0\.5​\|ℐR1\|\)\\displaystyle=0\.5n\-\\left\(0\.5\|\\mathcal\{I\}\_\{L\}^\{1\}\|\+0\.5\|\\mathcal\{I\}\_\{R\}^\{1\}\|\\right\)=0\.5​n−0\.5​n=0\\displaystyle=0\.5n\-0\.5n=0Now consider the noise featureh≥3h\\geq 3\. Fors∈\{L,R\}s\\in\\\{L,R\\\}andc∈\{0,1\}c\\in\\\{0,1\\\}, definens,ch:=\|\{i∈ℐsh:yi=c\}\|n\_\{s,c\}^\{h\}:=\|\\\{i\\in\\mathcal\{I\}\_\{s\}^\{h\}:y\_\{i\}=c\\\}\|\. The minimum constant\-prediction loss in child nodeℐsh\\mathcal\{I\}\_\{s\}^\{h\}isV0​\(ℐsh\)=min⁡\{ns,0h,ns,1h\}=\(\|ℐsh\|−\|ns,1h−ns,0h\|\)/2V\_\{0\}\(\\mathcal\{I\}\_\{s\}^\{h\}\)=\\min\\\{n\_\{s,0\}^\{h\},n\_\{s,1\}^\{h\}\\\}=\(\|\\mathcal\{I\}\_\{s\}^\{h\}\|\-\|n\_\{s,1\}^\{h\}\-n\_\{s,0\}^\{h\}\|\)/2\. Thus,

Δ​V0​\(a=h\)=\(\|nL,1h−nL,0h\|\+\|nR,1h−nR,0h\|\)/2\\displaystyle\\Delta V\_\{0\}\(a=h\)=\(\|n\_\{L,1\}^\{h\}\-n\_\{L,0\}^\{h\}\|\+\|n\_\{R,1\}^\{h\}\-n\_\{R,0\}^\{h\}\|\)/2
By assumption, at least one child node is class\-unbalanced, soΔ​V0​\(h\)\>0\\Delta V\_\{0\}\(h\)\>0\. Therefore,

Δ​V0​\(a=h\)\>Δ​V0​\(a=1\)=Δ​V0​\(a=2\)=0,\\displaystyle\\Delta V\_\{0\}\(a=h\)\>\\Delta V\_\{0\}\(a=1\)=\\Delta V\_\{0\}\(a=2\)=0,and a greedy algorithm maximizing immediate loss reduction selects a noise feature rather than either informative feature\. ∎

##### Illustrative role of lookahead

For XOR\-style data, a depth\-2 tree can represent the target rule exactly, whereas a purely greedy depth\-1 criterion may not discover the required structure\. This makes XOR an example for visualizing the difference between greedy splitting and lookahead\. Figure[9](https://arxiv.org/html/2609.38194#S9.F9)illustrates this contrast\.

x1x\_\{1\}x2x\_\{2\}CART: Greedy Depth\-1Impurity Reduction = 0\(Fails to separate classes\)x1x\_\{1\}x2x\_\{2\}ABR: Global Depth\-2Misclassification Loss = 0\(Perfectly isolates quadrants\)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\.This example highlights a basic limitation of greedy splitting: the usefulness of a feature may only become apparent after subsequent splits are taken into account\. A lookahead\-based method such asABRis designed to evaluate such downstream effects more explicitly\.

###### Theorem 9\.3\.

Let𝒟\\mathcal\{D\}be the XOR\-distributed dataset described above, where the two informative features are binary\. Ford≥2d\\geq 2,MHABRreturns a global optimal tree with zero training loss, even when the reduction strategy is enabled\. Moreover, ifCARTreturns a tree with positive loss, as established in[Theorem9\.2](https://arxiv.org/html/2609.38194#S9.Thmtheorem2), thenMHABRstrictly outperformsCART\.

###### Proof\.

LetWd​\(ℐ\)W\_\{d\}\(\\mathcal\{I\}\)denote the misclassification loss of the initial tree generated byCART, establishing the initial upper boundU=Wd​\(ℐ\)U=W\_\{d\}\(\\mathcal\{I\}\)forMHABR\. Leta∈\{1,2\}a\\in\\\{1,2\\\}be an informative feature and letk∗k^\{\*\}denote its nontrivial split index\. We aim to prove thatk∗k^\{\*\}is never removed by the reduction strategy defined in Lemma[3\.3](https://arxiv.org/html/2609.38194#S3.Thmtheorem3)before a globally optimal solution is found\.

By the definition of XOR, splitting on featureaaatk∗k^\{\*\}and then on the other informative feature partitions the sample space into four class\-pure quadrants\. Therefore, the corresponding depth\-22tree has zero misclassification loss:V2​\(ℐ,a,k∗\)=0V\_\{2\}\(\\mathcal\{I\},a,k^\{\*\}\)=0\. For everyd≥2d\\geq 2, the training loss ofCARTis nonincreasing with the available depth, and a depth\-11tree is solved exactly\. Hence, for every candidate split\(a,k\)\(a,k\),

V^d​\(ℐ,a,k\)\\displaystyle\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,k\)=Wd−1​\(ℐ\[0,k\]a\)\+Wd−1​\(ℐ\[k,na\]a\)\\displaystyle=W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}\)\+W\_\{d\-1\}\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\)≤W1​\(ℐ\[0,k\]a\)\+W1​\(ℐ\[k,na\]a\)\\displaystyle\\leq W\_\{1\}\(\\mathcal\{I\}^\{a\}\_\{\[0,k\]\}\)\+W\_\{1\}\(\\mathcal\{I\}^\{a\}\_\{\[k,n\_\{a\}\]\}\)=V2​\(ℐ,a,k\)\.\\displaystyle=V\_\{2\}\(\\mathcal\{I\},a,k\)\.Since the loss is nonnegative andV2​\(ℐ,a,k∗\)=0V\_\{2\}\(\\mathcal\{I\},a,k^\{\*\}\)=0, it follows thatV^d​\(ℐ,a,k∗\)=0\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,k^\{\*\}\)=0\. During the search, suppose that the algorithm evaluates a midpointk¯\\bar\{k\}before evaluatingk∗k^\{\*\}\. Applying Lemma[3\.2](https://arxiv.org/html/2609.38194#S3.Thmtheorem2)to the exact depth\-22objective givesV2​\(ℐ,a,k¯\)=\|V2​\(ℐ,a,k¯\)−V2​\(ℐ,a,k∗\)\|≤\|ζ⁡\(k¯\)−ζ⁡\(k∗\)\|V\_\{2\}\(\\mathcal\{I\},a,\\bar\{k\}\)=\\left\|V\_\{2\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-V\_\{2\}\(\\mathcal\{I\},a,k^\{\*\}\)\\right\|\\leq\|\\zeta\(\\bar\{k\}\)\-\\zeta\(k^\{\*\}\)\|\. Consequently,

V^d​\(ℐ,a,k¯\)≤V2​\(ℐ,a,k¯\)≤\|ζ⁡\(k¯\)−ζ⁡\(k∗\)\|\.\\displaystyle\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\\leq V\_\{2\}\(\\mathcal\{I\},a,\\bar\{k\}\)\\leq\|\\zeta\(\\bar\{k\}\)\-\\zeta\(k^\{\*\}\)\|\.\(44\)
Before a zero\-loss solution is found, the incumbent satisfiesU\>0U\>0\. According to the reduction strategy, the reduction margin isδ⁡\(k¯\):=V^d​\(ℐ,a,k¯\)−U\\delta\(\\bar\{k\}\):=\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-U\. Therefore,

δ⁡\(k¯\)=V^d​\(ℐ,a,k¯\)−U<V^d​\(ℐ,a,k¯\)\.\\displaystyle\\delta\(\\bar\{k\}\)=\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\-U<\\widehat\{V\}\_\{d\}\(\\mathcal\{I\},a,\\bar\{k\}\)\.Combining this inequality with[Equation44](https://arxiv.org/html/2609.38194#S9.E44)yields

δ⁡\(k¯\)<\|ζ⁡\(k¯\)−ζ⁡\(k∗\)\|\.\\displaystyle\\delta\(\\bar\{k\}\)<\|\\zeta\(\\bar\{k\}\)\-\\zeta\(k^\{\*\}\)\|\.
Hence, the condition required to removek∗k^\{\*\},\|ζ⁡\(k¯\)−ζ⁡\(k∗\)\|≤δ⁡\(k¯\)\|\\zeta\(\\bar\{k\}\)\-\\zeta\(k^\{\*\}\)\|\\leq\\delta\(\\bar\{k\}\)cannot hold\. Thus,k∗k^\{\*\}is not removed by the reduction strategy\. IfU=0U=0at an earlier iteration, a global optimal solution has already been found\. Since the candidate set is finite andk∗k^\{\*\}remains active, it is eventually evaluated, after which the incumbent is updated toUMHABR​\(ℐ,d\)=Vd​\(ℐ\)=0U\_\{\\texttt\{MHABR\}\}\(\\mathcal\{I\},d\)=V\_\{d\}\(\\mathcal\{I\}\)=0\. Because misclassification loss is nonnegative, this solution is global optimal\. Finally, if the initialCARTtree satisfiesWd​\(ℐ\)\>0W\_\{d\}\(\\mathcal\{I\}\)\>0, thenUMHABR​\(ℐ,d\)=0<Wd​\(ℐ\)U\_\{\\texttt\{MHABR\}\}\(\\mathcal\{I\},d\)=0<W\_\{d\}\(\\mathcal\{I\}\), soMHABRstrictly outperformsCART\. ∎

## 10Details of Numerical Experiments

### 10\.1Information of small\-scale datasets

The details of the 51 small datasets are presented in[Table9](https://arxiv.org/html/2609.38194#S10.T9)\.

Table 9:The information of 51 small\-scale datasets\.Dataset NamennppClassDataset NamennppClassSoybean\-small47354Body50752Echocardiogram61112Climate\-model\-crashes540202Hepatitis80192Monks\-problems\-355462Fertility10092Monks\-problems\-155662Acute\-inflammations\-112062Breast\-cancer\-diagnosti569302Acute\-inflammations\-212062Monks\-problems\-260062Hayes–roth13253Balance\-scale62543Iris15043Credit\-approval653152Teaching\-assistant\-evaluation15153Breast\-cancer68392Wine178133Blood\-transfusion74842Breast\-cancer\-prognostic194312Mammographic\-mass83052Parkinsons195232Tic\-tac\-toe\-endgame95892Connectionist\-bench\-sonar208602Connectionist\-bench9901311Image\-segmentation210197Statlog\-project\-German\-credit1,000202Seeds21073Concrete1,03083Glass21496Banknote\-authentication1,37242Thyroid\-disease\-new\-thyroid21553Contraceptive\-method\-choice1,47393Congressional\-voting\-records232162Car\-evaluation1,72864Spect\-heart267222Ozone\-level\-detection\-eight1,847722Spectf\-heart267442Ozone\-level\-detection\-one1,848722Cylinder\-bands277392Seismic\-bumps2,584182Heart\-disease\-Cleveland282135Chess\-king\-rook\-versus\-king\-pawn3,196362Haberman\-survival30632Thyroidann3,772213Ionosphere351342Wall\-following\-robot\-25,45624Dermatology358346Thyroid\-disease\-ann\-thyroid7,200213Thoracic\-surgery470162

### 10\.2Configuration of additional techniques for large\-scale datasets

The configurations for datasets containing more than10,00010,000are described below\. For the 5 medium\-scale datasets, we do not introduce the parametersε\\varepsilonandθ\\theta;MHABRsuccessfully completes all the training tasks\. For the three large\-scale datasets, we configure the algorithms to terminate within the time limit\. The configurations are SUSY:ε=0\.01,θ=0\.25\\varepsilon=0\.01,\\theta=0\.25, HIGGS:ε=0\.01,θ=0\.5\\varepsilon=0\.01,\\theta=0\.5, WESAD:ε=0\.00025,θ=0\.25\\varepsilon=0\.00025,\\theta=0\.25\.

### 10\.3Implementation details

Details and experimental settings of all comparison algorithms are stated below\. Unless otherwise specified, the implementations used in our experiments are obtained from their original authors\.

MHABR: Our algorithm is implemented inJulia\. For the default version, we adopt the reduction strategy with parametersε=0\\varepsilon=0andθ=1\\theta=1\.

CART\([Sadeghi et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib7)\): We use the implementation from theJuliapackageDecisionTree, selecting entropy loss as it provides the best results among the three options; its performance may occasionally surpassMHABRandDPDTon several datasets\.

DPDT\([Kohler et al\., 2025](https://arxiv.org/html/2609.38194#bib.bib13)\): This algorithm is written inPythonand callsCARTthrough thePythonpackagescikit\-learn, using theGini loss\(default\)\. Therefore, in our results, it may be surpassed byCART\.

LS\-OCT\([Dunn, 2018](https://arxiv.org/html/2609.38194#bib.bib9)\): Since the original code is not available, we implement both methods inJuliaand callGurobito solve MIP models\.

DL8\.5\([Aglin et al\., 2020](https://arxiv.org/html/2609.38194#bib.bib16)\): This algorithm is written inC\+\+and is run as an extension ofPython\. The current version also integrates the methods ofMurTree\([Demirović et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib20)\)\. Besides, we useGUESS\([McTavish et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib6)\)for binarization because it provided the best performance among the evaluated options\.

Quant\-BnB\([Mazumder et al\., 2022](https://arxiv.org/html/2609.38194#bib.bib30)\): The authors provide an open\-source implementation of this algorithm, which is written inJulia\.

TAO\([Carreira\-Perpinán and Tavallali, 2018](https://arxiv.org/html/2609.38194#bib.bib4)\): Because the source code for this method is not publicly available, we directly compare our approach with the results reported in the original paper under the same experimental configuration\.

Additionally, we experimented withSTreeD\([van der Linden et al\., 2023](https://arxiv.org/html/2609.38194#bib.bib5)\), implemented inC\+\+with aPythoninterface\. However, due to changes in computational hardware, a fair comparison could not be ensured; therefore, we omit its results\.