Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

# Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
Source: [https://arxiv.org/html/2609.05826](https://arxiv.org/html/2609.05826)
Jiancheng TuAffiliation:Department of Computing, The Hong Kong Polytechnic UniversityEmail:[jiancheng\.tu@connect\.polyu\.hk](mailto:)Wenqi FanAffiliation:Department of Computing, The Hong Kong Polytechnic UniversityAffiliation:Department of Management and Marketing, The Hong Kong Polytechnic UniversityEmail:[wenqi\.fan@polyu\.edu\.hk](mailto:)

###### Abstract

Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase\. We develop a joint feature\- and sample\-space reduction framework based onSTreeD\.Weighted STreeDmerges duplicate records created after projection onto a fixed candidate set into weighted representatives\. This reduces sample\-dependent computation without changing the fixed\-candidate optimization problem\.Adaptive STreeDrepeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems\. Each certifiedWeighted STreeDsolution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space\. Experiments on five data sets show thatWeighted STreeDachieves speedups of up to 121\.41 times over standardSTreeD\.Adaptive STreeDreduces runtime in matched comparisons at depths 2–4 and continues to return feasible trees at greater depths where full\-feature methods are limited by time or memory\. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons\. These results show how joint feature\- and sample\-space reduction can scale dynamic\-programming\-based optimal\-tree learning to more demanding instances\.

Keywords:Interpretable machine learning, optimal classification tree, dynamic programming

## 1Introduction

Classification trees are widely used when predictions must be explained through explicit decision rules\. This is particularly relevant in high\-stakes applications such as credit scoring, medical prediction, and criminal justice, where decision makers may need to inspect and justify individual predictions\([Rudin 2019](https://arxiv.org/html/2609.05826#bib.bib4)\)\. A shallow tree provides such transparency through a short sequence of rules from the root node to a leaf\.

Classical tree\-learning methods such as CART, ID3, and C4\.5 construct trees greedily\([Breiman et al\. 1984](https://arxiv.org/html/2609.05826#bib.bib1),[Quinlan 1986](https://arxiv.org/html/2609.05826#bib.bib2),[Quinlan 1993](https://arxiv.org/html/2609.05826#bib.bib3)\)\. They are computationally efficient, but local split decisions may not lead to the best final tree\. Optimal classification tree methods instead optimize the complete tree\. Existing approaches include mixed\-integer optimization\([Bertsimas and Dunn 2017](https://arxiv.org/html/2609.05826#bib.bib5),[Verwer and Zhang 2019](https://arxiv.org/html/2609.05826#bib.bib6),[Alston et al\. 2026](https://arxiv.org/html/2609.05826#bib.bib50),[Liu et al\. 2024](https://arxiv.org/html/2609.05826#bib.bib51),[Blanquero et al\. 2021](https://arxiv.org/html/2609.05826#bib.bib52),[Blanquero et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib53)\), dynamic programming\([Aglin et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib19),[Demirović et al\. 2022](https://arxiv.org/html/2609.05826#bib.bib20),[Lin et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib21),[van der Linden et al\. 2023](https://arxiv.org/html/2609.05826#bib.bib22)\), SAT, and constraint programming\([Verhaeghe et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib30),[Shati et al\. 2021](https://arxiv.org/html/2609.05826#bib.bib31)\)\. Among these approaches, dynamic programming exploits the recursive tree structure and has been effective for shallow optimal\-tree learning\.

We build onSTreeD, a general dynamic\-programming framework for optimal decision trees\([van der Linden et al\. 2023](https://arxiv.org/html/2609.05826#bib.bib22)\)\. Its computational cost depends strongly on the number of candidate features and training samples\. Large feature spaces increase the number of states and split evaluations, while many states repeatedly process training records\. These costs become more severe after preprocessing creates a high\-dimensional binary feature space\.

We exploit the interaction between feature and sample reduction\. Restricting the candidate set reduces split enumeration and can create additional duplicate projected records, which are merged into weighted representatives\. Based on this idea,Weighted STreeDprovides a lossless reformulation for fixed candidate sets, andAdaptive STreeDiteratively refines bounded candidate sets while rebuilding the weighted representation\.

The two methods have different guarantee scopes\. A certifiedWeighted STreeDsolution is optimal for its fixed candidate set\.Adaptive STreeD, however, remains heuristic over the full feature space\. It recovers a full\-feature optimum when a visited candidate set contains the split features of such an optimal tree and the corresponding reduced problem is solved to optimality\. We also derive complexity and conditional solution\-quality results that clarify these guarantees\.

Experiments on five binarized data sets show thatWeighted STreeDachieves speedups of up to121\.41×121\.41\\timesover standardSTreeD\.Adaptive STreeDreduces runtime in matched comparisons at depths 2–4 and continues to return feasible trees at greater depths where full\-feature methods are limited by time or memory\. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal\-tree baselines\.

The paper makes two methodological contributions\. First, we develop a joint feature\- and sample\-space reduction scheme in which candidate restriction can increase the amount of lossless weighted aggregation\. Second, we develop an adaptive candidate\-refinement method that updates the reduced feature space while preserving features used by the incumbent\. Theoretical analysis characterizes the computational reductions and guarantee scope, and computational experiments evaluate the two mechanisms separately and jointly\.

## 2Related Work

We organize the closest work by optimization, data and feature reduction, and near\-optimal search, emphasizing what each method reduces and the scope of its guarantees\.

### 2\.1Optimal Classification Trees

Optimal classification tree methods optimize the complete tree rather than selecting splits greedily\. Major exact approaches include mixed\-integer optimization, dynamic programming, SAT/MaxSAT, constraint programming, and branch\-and\-bound\.

Mixed\-integer optimization models jointly determine tree structure, split rules, and leaf predictions\. The OCT formulation established this approach for bounded\-depth trees\([Bertsimas and Dunn 2017](https://arxiv.org/html/2609.05826#bib.bib5)\), followed by stronger formulations and extensions to richer split rules, objectives, and constraints\([Verwer and Zhang 2019](https://arxiv.org/html/2609.05826#bib.bib6),[Aghaei et al\. 2025](https://arxiv.org/html/2609.05826#bib.bib7),[Günlük et al\. 2021](https://arxiv.org/html/2609.05826#bib.bib8),[Subramanian and Sun 2023](https://arxiv.org/html/2609.05826#bib.bib16),[Ales et al\. 2024](https://arxiv.org/html/2609.05826#bib.bib17),[D’Onofrio et al\. 2024](https://arxiv.org/html/2609.05826#bib.bib18)\)\. These models are flexible, but sample\-indexed routing variables and large split spaces can limit scalability\. SAT, MaxSAT, and constraint\-programming methods provide alternative exact formulations based on logical constraints and structured search\([Shati et al\. 2021](https://arxiv.org/html/2609.05826#bib.bib31),[Hu et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib32),[Verhaeghe et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib30)\)\. Column\-generation and path\-based approaches further reduce the initial model by generating rules or paths as needed\([Firat et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib14),[Patel et al\. 2024](https://arxiv.org/html/2609.05826#bib.bib15),[Subramanian and Sun 2023](https://arxiv.org/html/2609.05826#bib.bib16)\)\.

Dynamic\-programming methods exploit the recursive structure of a decision tree and reuse repeated subproblems through caching and bounds\. DL8\.5 combines caching with branch\-and\-bound search\([Aglin et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib19)\), while MurTree introduces specialized bounds, similarity\-based pruning, and efficient shallow\-tree routines\([Demirović et al\. 2022](https://arxiv.org/html/2609.05826#bib.bib20)\)\. OSDT and GOSDT use regularization and strong pruning rules to learn sparse optimal trees\([Hu et al\. 2019](https://arxiv.org/html/2609.05826#bib.bib23),[Lin et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib21)\)\.STreeDgeneralizes this line of work by identifying conditions under which objectives and constraints can be decomposed into independent subtree problems\([van der Linden et al\. 2023](https://arxiv.org/html/2609.05826#bib.bib22)\)\. Recent alternatives include AND/OR search in MAPTree and AO\* search in Branches\([Sullivan et al\. 2024](https://arxiv.org/html/2609.05826#bib.bib47),[Chaouki et al\. 2025](https://arxiv.org/html/2609.05826#bib.bib48)\)\. Quant\-BnB and ConTree instead specialize search for continuous features\([Mazumder et al\. 2022](https://arxiv.org/html/2609.05826#bib.bib11),[Briţa et al\. 2025](https://arxiv.org/html/2609.05826#bib.bib28)\)\.

### 2\.2Data and Feature Reduction

Data\-reduction methods use repeated or indistinguishable records to reduce computation\. CORELS and OSDT use equivalent\-point arguments to derive unavoidable prediction errors\([Angelino et al\. 2018](https://arxiv.org/html/2609.05826#bib.bib43),[Hu et al\. 2019](https://arxiv.org/html/2609.05826#bib.bib23)\)\. Similar ideas have been used to strengthen lower bounds or reduce redundant observations in optimal\-tree search\([Zhang et al\. 2023](https://arxiv.org/html/2609.05826#bib.bib44),[Keegan et al\. 2025](https://arxiv.org/html/2609.05826#bib.bib10),[Hua et al\. 2022](https://arxiv.org/html/2609.05826#bib.bib33)\)\.

GOSDT provides a related dynamic\-programming precedent\. It stores positive and negative empirical mass for each distinct row in a fixed binary feature matrix\([Lin et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib21)\)\. WFlowOCT aggregates duplicate feature–label records into weighted instances within a flow\-based mixed\-integer model\([Tu et al\. 2026](https://arxiv.org/html/2609.05826#bib.bib9)\)\.Weighted STreeDdiffers in that duplicate records are defined after projection onto the current candidate set\. Restricting the candidate set can therefore create additional duplicate records, which are merged into weighted representatives\. The weighted representation is rebuilt whenever the candidate set changes, coupling feature\-space reduction with sample\-space reduction\. Under the stated separability and information\-preservation conditions, the transformation leaves the fixed\-candidate optimization problem unchanged\.

Feature reduction can be applied before optimization or during the solution process\. BinOCT reduces binary variables associated with distinct feature values\([Verwer and Zhang 2019](https://arxiv.org/html/2609.05826#bib.bib6)\), while reference\-guided methods use black\-box models to select thresholds, estimate tree size, or guide lower bounds\([McTavish et al\. 2022](https://arxiv.org/html/2609.05826#bib.bib24)\)\. Other studies reduce the feature space more directly\.[Ruggieri \(2019\)](https://arxiv.org/html/2609.05826#bib.bib45)enumerates feature subsets for a fixed greedy learner, while[Ing et al\. \(2024\)](https://arxiv.org/html/2609.05826#bib.bib46)and[Eiben et al\. \(2023\)](https://arxiv.org/html/2609.05826#bib.bib12)study compact feature supports under different structural assumptions\. These methods reduce the search space, but they do not generally guarantee that the selected features contain those used by a full\-feature optimal tree\.Adaptive STreeDfollows a different strategy: it solves a sequence of bounded candidate\-set problems and rebuilds the weighted data representation after each candidate update\.

### 2\.3Near\-Optimal Classification Trees

When proving full optimality is too expensive, several methods seek high\-quality trees within a fixed computational budget\. Limited\-discrepancy search, Blossom, and anytime beam search retain the full search space but prioritize strong incumbents before completing the optimality proof\([Demirović et al\. 2023](https://arxiv.org/html/2609.05826#bib.bib25),[Kiossou and Schaus 2026](https://arxiv.org/html/2609.05826#bib.bib27)\)\. Memory\-constrained methods instead limit cache usage or modify state processing\([Aglin et al\. 2022](https://arxiv.org/html/2609.05826#bib.bib26)\)\. Other approaches reduce exact search by optimizing only part of the tree: SPLIT solves upper subproblems exactly and constructs lower levels greedily\([Babbar et al\. 2025](https://arxiv.org/html/2609.05826#bib.bib29)\), while SAT\-based local improvement reoptimizes selected subtrees of a heuristic solution\([Schidler and Szeider 2021](https://arxiv.org/html/2609.05826#bib.bib13)\)\.

Adaptive STreeDdiffers by restricting the candidate feature space rather than the tree structure or search order\. Each certified inner solve is optimal for its current candidate set, while the outer feature refinement remains heuristic over the full feature space\. A full\-feature optimum is recovered only when a visited candidate set contains the split features of such an optimal tree and the corresponding reduced problem is solved to optimality\.

## 3Weighted Unique\-Data Dynamic Programming

This section develops the fixed\-candidate weighted reformulation ofSTreeD\. We first establish fixed\-candidate equivalence between the original and weighted representations for separable tasks that satisfy the information\-preservation condition\. We then specialize to the training\-accuracy objective to present the explicit recursion and analyze its time and space complexity\. This specialization reflects the paper’s focus on scalability rather than a restriction of the weighted reformulation\. Proofs are given in Appendix[D](https://arxiv.org/html/2609.05826#A4)\.

### 3\.1Problem Setting

Letℐ=\{\(𝐱i,yi,ηi\)\}i=1n\\mathcal\{I\}=\\\{\(\\mathbf\{x\}\_\{i\},y\_\{i\},\\eta\_\{i\}\)\\\}\_\{i=1\}^\{n\}be a training set, where𝐱i∈\{0,1\}p\\mathbf\{x\}\_\{i\}\\in\\\{0,1\\\}^\{p\}is the post\-binarization feature vector,yi∈𝒦y\_\{i\}\\in\\mathcal\{K\}is the class label drawn from the finite class set𝒦\\mathcal\{K\}, andηi\\eta\_\{i\}collects any additional record\-level information required by the task, such as class\-specific costs, treatment and outcome information, or group membership\.

Letℱ=\{1,…,p\}\\mathcal\{F\}=\\\{1,\\ldots,p\\\}be the full post\-binarization feature set\. Fix a candidate setS⊆ℱS\\subseteq\\mathcal\{F\}and letq=\|S\|q=\|S\|\. A tree restricted toSSmay use only features inSSas split features;hT​\(𝐱i​S\)h\_\{T\}\(\\mathbf\{x\}\_\{iS\}\)denotes the prediction of treeTTafter projecting observationiiontoSS\.

For a treeTT, letLmis\(T\)=∑i=1n𝟏\{yi≠hT\(𝐱i​S\)\}L\_\{\\mathrm\{mis\}\}\(T\)=\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{y\_\{i\}\\neq h\_\{T\}\(\\mathbf\{x\}\_\{iS\}\)\\\}denote its training misclassification count\. The empirical misclassification error isLmis​\(T\)/nL\_\{\\mathrm\{mis\}\}\(T\)/n, and training accuracy is1−Lmis​\(T\)/n1\-L\_\{\\mathrm\{mis\}\}\(T\)/n\. Thus, maximizing training accuracy is equivalent to minimizingLmis​\(T\)L\_\{\\mathrm\{mis\}\}\(T\)\. The recursions below use this additive count\.

###### Definition 1\.

Following Definition 4\.2 of[van der Linden et al\. \(2023\)](https://arxiv.org/html/2609.05826#bib.bib22), an optimization task is*separable*if and only if the optimal solution to any subtree can be determined independently of decision variables outside that subtree and the branching decisions of its parent nodes\.

With appropriate task states,STreeDsupports ordinary and cost\-sensitive classification, prescriptive policy learning,F1F\_\{1\}\-score and Matthews correlation coefficient optimization, and gurop fairness objectives\. The aggregation argument below applies whenever the key or stored statistics retain all information used by the task’s dynamic program\.

For the fixed candidate setSS, define the aggregation key

gi​\(S\)=\(𝐱i​S,yi,ηi\)\.g\_\{i\}\(S\)=\(\\mathbf\{x\}\_\{iS\},y\_\{i\},\\eta\_\{i\}\)\.\(1\)Observations with the same key form one group in the fixed\-candidate problem\. The weighted unique data set𝒰⁡\(S\)\\mathcal\{U\}\(S\)contains one representative\(𝐳u,yu,ηu,wu\)\(\\mathbf\{z\}\_\{u\},y\_\{u\},\\eta\_\{u\},w\_\{u\}\)for each distinct key\. Here,𝐳u\\mathbf\{z\}\_\{u\}is the projected binary feature vector,yuy\_\{u\}andηu\\eta\_\{u\}retain the task\-relevant information, andwuw\_\{u\}is the number of original observations represented byuu\. Let

uS=\|𝒰⁡\(S\)\|u\_\{S\}=\|\\mathcal\{U\}\(S\)\|denote the number of weighted unique records\. Each representative must retain all task\-specific information and sufficient statistics required by the dynamic program\.

Let𝒯⁡\(S,D,M\)\\mathcal\{T\}\(S,D,M\)denote the class of classification trees with depth at mostDD, at mostMMinternal split nodes, and split features restricted toSS\. All results below use the same fixedSS, the same post\-binarized representation, and the same feasible tree class\. We useAAandBBfor states over original and weighted records, respectively, andddandmmfor the remaining depth and node budget\. Appendix[B\.1](https://arxiv.org/html/2609.05826#A2.SS1)collects the notation\.

### 3\.2STreeD Dynamic Programming Baseline

For the training\-accuracy objective,STreeDrecursively solves the two child subproblems created by a split\([van der Linden et al\. 2023](https://arxiv.org/html/2609.05826#bib.bib22)\)\. Its state\(A,d,m\)\(A,d,m\)records the observations reaching the node, the remaining depth, and the remaining node budget\.Leaf⁡\(A\)\\mathrm\{Leaf\}\(A\)is the smallest misclassification count attainable by a constant class prediction\. Forf∈Sf\\in S, let

Aj​\(f\)=\{i∈A:xi​f=j\},j∈\{0,1\}\.A\_\{j\}\(f\)=\\\{i\\in A:x\_\{if\}=j\\\},\\qquad j\\in\\\{0,1\\\}\.The cache avoids repeated solution of identical states\. The simplified recursion in Appendix[B\.2](https://arxiv.org/html/2609.05826#A2.SS2)omits implementation enhancements because it is used only to expose sample\-dependent work\.

Let𝒜D,M​\(S\)\\mathcal\{A\}\_\{D,M\}\(S\)be the set of distinct cached states visited by the baseline recursion\. For a state\(A,d,m\)\(A,d,m\), define

We use the conservative path\-state bound

HD​\(q\)=∑ℓ=0min⁡\{D,q\}\(qℓ\)​2ℓ\.H\_\{D\}\(q\)=\\sum\_\{\\ell=0\}^\{\\min\\\{D,q\\\}\}\\binom\{q\}\{\\ell\}2^\{\\ell\}\.\(2\)WhenD≤qD\\leq q, treatingDDas fixed andqqas the input variable,

HD​\(q\)=O⁡\(\(2​q\)D\)\.H\_\{D\}\(q\)=O\(\(2q\)^\{D\}\)\.
The following proposition records the baseline time and space terms\. The bounds are intended for complexity accounting rather than as tight models of a specific implementation\.

###### Proposition 1\.

Consider the accuracy\-based recursion above for labels in the finite class set𝒦\\mathcal\{K\}, and suppose that the baseline implementation scans the records in every visited state\. The asymptotic input quantities arenn,qq,DD,MM, and\|𝒦\|\|\\mathcal\{K\}\|;bbdenotes the machine\-word size\. Its running time is

TSTreeD=O⁡\(∑\(A,d,m\)∈𝒜D,M​\(S\)\[\(\|𝒦\|\+q\)​nA\+q​m\]\)\.T\_\{\\mathrm\{STreeD\}\}=O\\\!\\left\(\\sum\_\{\(A,d,m\)\\in\\mathcal\{A\}\_\{D,M\}\(S\)\}\\left\[\(\|\\mathcal\{K\}\|\+q\)n\_\{A\}\+qm\\right\]\\right\)\.\(3\)A conservative worst\-case bound is

TSTreeD=O⁡\(\(D\+1\)​\(M\+1\)​HD​\(q\)​\[\(\|𝒦\|\+q\)​n\+q​M\]\)\.T\_\{\\mathrm\{STreeD\}\}=O\\\!\\left\(\(D\+1\)\(M\+1\)H\_\{D\}\(q\)\\left\[\(\|\\mathcal\{K\}\|\+q\)n\+qM\\right\]\\right\)\.\(4\)
If each cached state is represented by a bitset over thennoriginal records and one machine word storesbbbits, then the sample\-dependent cache\-space requirement is

SpaceSTreeD=O⁡\(\|𝒜D,M​\(S\)\|​\(nb\+1\)\)\.\\mathrm\{Space\}\_\{\\mathrm\{STreeD\}\}=O\\\!\\left\(\|\\mathcal\{A\}\_\{D,M\}\(S\)\|\\left\(\\frac\{n\}\{b\}\+1\\right\)\\right\)\.\(5\)These expressions exclude storage for the input feature matrix, returned trees, and auxiliary solver statistics\.

The state\-sum expressions separate work performed on the records from split and budget enumeration\. The worst\-case form replaces the actual visited\-state collection by a conservative path bound, so it should be read as an accounting bound rather than a prediction of realized runtime\. Pruning and state reuse can reduce realized work below this bound\.

### 3\.3Weighted STreeD

Weighted STreeDapplies the same fixed\-candidate recursion to the weighted unique data set𝒰⁡\(S\)\\mathcal\{U\}\(S\)\. The multiplicity weights satisfy

∑u∈𝒰⁡\(S\)wu=n\.\\sum\_\{u\\in\\mathcal\{U\}\(S\)\}w\_\{u\}=n\.
Letℰ\\mathcal\{E\}denote the set of distinct task\-specific values ofηi\\eta\_\{i\}\. Because all projected features are binary,

uS=\|𝒰⁡\(S\)\|≤min⁡\{n,\|𝒦\|​\|ℰ\|​2q\}\.u\_\{S\}=\|\\mathcal\{U\}\(S\)\|\\leq\\min\\left\\\{n,\|\\mathcal\{K\}\|\\,\|\\mathcal\{E\}\|\\,2^\{q\}\\right\\\}\.\(6\)For the training\-accuracy objective,\|ℰ\|=1\|\\mathcal\{E\}\|=1\.

Equation \([6](https://arxiv.org/html/2609.05826#S3.E6)\) is only an upper bound\. The actual value ofuSu\_\{S\}depends on the patterns observed in the data\. When only a small fraction of the possible patterns occurs, projection onto a small candidate set can create many duplicate records\. In such cases,uSu\_\{S\}can be much smaller than both the original sample size and the combinatorial upper bound\. The main theoretical result is the equivalence between the original and weighted fixed\-candidate problems\.

###### Proposition 2\.

Fix a candidate setSS, a feasible tree class𝒯⁡\(S,D,M\)\\mathcal\{T\}\(S,D,M\), and a separable optimization task\. Suppose the aggregation key retains all record\-level information required by that task\. For each feasible treeTT, letϕi​\(T\)\\bm\{\\phi\}\_\{i\}\(T\)denote recordii’s contribution to the vector of sufficient statistics used by the dynamic program\. Assume that this contribution depends only onhT​\(𝐱i​S\)h\_\{T\}\(\\mathbf\{x\}\_\{iS\}\),yiy\_\{i\}, andηi\\eta\_\{i\}, and that the task value and feasibility ofTTare determined by the sum of these contributions together with any tree\-only terms\. Ifϕu​\(T\)\\bm\{\\phi\}\_\{u\}\(T\)denotes the corresponding contribution for weighted recorduu, then

∑i=1nϕi​\(T\)=∑u∈𝒰⁡\(S\)wu​ϕu​\(T\)\.\\sum\_\{i=1\}^\{n\}\\bm\{\\phi\}\_\{i\}\(T\)=\\sum\_\{u\\in\\mathcal\{U\}\(S\)\}w\_\{u\}\\bm\{\\phi\}\_\{u\}\(T\)\.\(7\)The original and weighted representations therefore give every feasible tree the same task statistics and the same value under the possibly nonlinear task objective computed from those statistics\. Because the feasible tree class and tree\-only terms are unchanged, the two fixed\-candidate problems also have the same optimal value and the same set of optimal trees\.

We now specialize the weighted recursion and its complexity analysis to the training\-accuracy objective\. For this weighted recursion, let

B⊆𝒰⁡\(S\)B\\subseteq\\mathcal\{U\}\(S\)be the weighted records reaching a node\. The best weighted leaf cost is

Leaf⁡\(B\)\\displaystyle\\mathrm\{Leaf\}\(B\)=mink∈𝒦∑u∈Bwu𝟏\{yu≠k\}\\displaystyle=\\min\_\{k\\in\\mathcal\{K\}\}\\sum\_\{u\\in B\}w\_\{u\}\\mathbf\{1\}\\\{y\_\{u\}\\neq k\\\}\(8\)=∑u∈Bwu−maxk∈𝒦∑u∈Bwu𝟏\{yu=k\}\.\\displaystyle=\\sum\_\{u\\in B\}w\_\{u\}\-\\max\_\{k\\in\\mathcal\{K\}\}\\sum\_\{u\\in B\}w\_\{u\}\\mathbf\{1\}\\\{y\_\{u\}=k\\\}\.
For a split featuref∈Sf\\in S, define

B0​\(f\)=\{u∈B:zu​f=0\},B1​\(f\)=\{u∈B:zu​f=1\}\.B\_\{0\}\(f\)=\\\{u\\in B:z\_\{uf\}=0\\\},\\qquad B\_\{1\}\(f\)=\\\{u\\in B:z\_\{uf\}=1\\\}\.
LetV⁡\(B,d,m\)V\(B,d,m\)be the minimum weighted misclassification count for state\(B,d,m\)\(B,d,m\)\. The recursion is

V⁡\(B,d,m\)=\{Leaf⁡\(B\),d=0​or​m=0,min⁡\{Leaf⁡\(B\),Φ⁡\(B,d,m\)\},otherwise,V\(B,d,m\)=\\begin\{cases\}\\mathrm\{Leaf\}\(B\),&d=0\\text\{ or \}m=0,\\\\\[3\.0pt\] \\min\\left\\\{\\mathrm\{Leaf\}\(B\),\\Phi\(B,d,m\)\\right\\\},&\\text\{otherwise\},\\end\{cases\}\(9\)where

Φ\(B,d,m\)=minf∈S:B0​\(f\)≠∅,B1​\(f\)≠∅minm0\+m1=m−1m0,m1≥0\[V\(B0\(f\),d−1,m0\)\+V\(B1\(f\),d−1,m1\)\]\.\\Phi\(B,d,m\)=\\min\_\{\\begin\{subarray\}\{c\}f\\in S:\\\\ B\_\{0\}\(f\)\\neq\\emptyset,\\;B\_\{1\}\(f\)\\neq\\emptyset\\end\{subarray\}\}\\;\\min\_\{\\begin\{subarray\}\{c\}m\_\{0\}\+m\_\{1\}=m\-1\\\\ m\_\{0\},m\_\{1\}\\geq 0\\end\{subarray\}\}\\left\[V\(B\_\{0\}\(f\),d\-1,m\_\{0\}\)\+V\(B\_\{1\}\(f\),d\-1,m\_\{1\}\)\\right\]\.\(10\)
The weighted and unweighted recursions have the same structure\. Their only difference is the representation of the records and the use of weights in the sufficient statistics\.

###### Corollary 1\.

For the training\-accuracy objective with labels in the finite class set𝒦\\mathcal\{K\}, suppose the weighted and unweighted recursions use the same fixed candidate setSS, depth limitDD, internal\-node budgetMM, and pruning rules\. If those rules are computed from aggregation\-preserving weighted class counts, then \([9](https://arxiv.org/html/2609.05826#S3.E9)\)–\([10](https://arxiv.org/html/2609.05826#S3.E10)\) returns the same optimal misclassification count as the corresponding recursion on the original data\.

LetℬD,M​\(S\)\\mathcal\{B\}\_\{D,M\}\(S\)be the set of distinct weighted states visited byWeighted STreeD\. For a weighted state\(B,d,m\)\(B,d,m\), defineuB=\|B\|u\_\{B\}=\|B\|\.

The following proposition gives the weighted time and space terms\.

###### Proposition 3\.

Consider the weighted misclassification\-count recursion above for labels in the finite class set𝒦\\mathcal\{K\}, and suppose thatWeighted STreeDuses the same direct state\-scanning implementation as the baseline\. The asymptotic input quantities areuSu\_\{S\},qq,DD,MM, and\|𝒦\|\|\\mathcal\{K\}\|;bbdenotes the machine\-word size\. Its running time is

TW​\-​STreeD=O⁡\(∑\(B,d,m\)∈ℬD,M​\(S\)\[\(\|𝒦\|\+q\)​uB\+q​m\]\)\.T\_\{\\mathrm\{W\\text\{\-\}STreeD\}\}=O\\\!\\left\(\\sum\_\{\(B,d,m\)\\in\\mathcal\{B\}\_\{D,M\}\(S\)\}\\left\[\(\|\\mathcal\{K\}\|\+q\)u\_\{B\}\+qm\\right\]\\right\)\.\(11\)Using the path\-state bound in \([2](https://arxiv.org/html/2609.05826#S3.E2)\), a conservative worst\-case bound is

TW​\-​STreeD=O⁡\(\(D\+1\)​\(M\+1\)​HD​\(q\)​\[\(\|𝒦\|\+q\)​uS\+q​M\]\)\.T\_\{\\mathrm\{W\\text\{\-\}STreeD\}\}=O\\\!\\left\(\(D\+1\)\(M\+1\)H\_\{D\}\(q\)\\left\[\(\|\\mathcal\{K\}\|\+q\)u\_\{S\}\+qM\\right\]\\right\)\.\(12\)
If each weighted state is represented by a bitset over theuSu\_\{S\}weighted unique records, then the sample\-dependent cache\-space requirement is

SpaceW​\-​STreeD=O⁡\(\|ℬD,M​\(S\)\|​\(uSb\+1\)\)\.\\mathrm\{Space\}\_\{\\mathrm\{W\\text\{\-\}STreeD\}\}=O\\\!\\left\(\|\\mathcal\{B\}\_\{D,M\}\(S\)\|\\left\(\\frac\{u\_\{S\}\}\{b\}\+1\\right\)\\right\)\.\(13\)These expressions exclude storage for the weighted input table, returned trees, and auxiliary solver statistics\.

Relative to the baseline bounds, the sample\-universe terms replacennand the state sizesnAn\_\{A\}byuSu\_\{S\}anduBu\_\{B\}\. Candidate\-set size, depth, and node\-budget factors remain\. The weighted representation can reduce record\-processing work and bitset length without eliminating the combinatorial search over feasible trees\. The exact reduction in sample\-scanning work depends on the compression achieved within all visited states, not only at the root state\.

###### Proposition 4\.

For the training\-accuracy objective with labels in the finite class set𝒦\\mathcal\{K\}, assume that the baseline and weighted recursions visit corresponding logical states under the same candidate set, depth limit, internal\-node budget, search order, and aggregation\-preserving pruning rules\. Then the reduction ratio in the sample\-scanning term is

RTscan=∑\(A,d,m\)∈𝒜D,M​\(S\)nA∑\(B,d,m\)∈ℬD,M​\(S\)uB\.R\_\{T\}^\{\\mathrm\{scan\}\}=\\frac\{\\displaystyle\\sum\_\{\(A,d,m\)\\in\\mathcal\{A\}\_\{D,M\}\(S\)\}n\_\{A\}\}\{\\displaystyle\\sum\_\{\(B,d,m\)\\in\\mathcal\{B\}\_\{D,M\}\(S\)\}u\_\{B\}\}\.\(14\)
If the state\-level compression ratios are close to the root\-level compression ratio, then

RTscan≈nuS\.R\_\{T\}^\{\\mathrm\{scan\}\}\\approx\\frac\{n\}\{u\_\{S\}\}\.\(15\)
For bitset\-based cache representations and corresponding logical states, the per\-state sample\-dependent storage ratio is

RSbitset=n/b\+1uS/b\+1\.R\_\{S\}^\{\\mathrm\{bitset\}\}=\\frac\{n/b\+1\}\{u\_\{S\}/b\+1\}\.\(16\)When bothn/bn/banduS/bu\_\{S\}/bare large,

RSbitset≈nuS\.R\_\{S\}^\{\\mathrm\{bitset\}\}\\approx\\frac\{n\}\{u\_\{S\}\}\.\(17\)

The ration/uSn/u\_\{S\}approximates sample\-scanning and bitset\-storage reductions only when similar compression persists across visited states\. It is not a wall\-clock speedup because feature enumeration, budget allocation, caching, pruning, and fixed solver overhead remain\. The fixed\-candidate ablation in Section[5\.3](https://arxiv.org/html/2609.05826#S5.SS3)evaluates the realized effect\. WhenSSchanges, projection and aggregation are repeated, so the equivalence and complexity results apply separately to each candidate set\.

## 4Adaptive STreeD

Section[3](https://arxiv.org/html/2609.05826#S3)gives a lossless weighted reformulation for a fixed candidate feature set\.Adaptive STreeDapplies this reformulation to a sequence of reduced problems with bounded candidate sets in large binarized feature spaces\. The initial candidate set consists of theKKmost important features selected by a random forest\. Later iterations retain the features used by the current incumbent and use repeated CART fits to propose new candidates\. After each update, the data are projected onto the active feature set, which can create additional duplicate records\. These records are merged into weighted representatives, and the resulting problem is solved byWeighted STreeD\. Random forests and CART are used only for feature proposal\. A certified inner solve is optimal for its current candidate set under the assumptions of Section[3](https://arxiv.org/html/2609.05826#S3), whereas the outer candidate refinement remains heuristic over the full feature space\.

### 4\.1Candidate\-Refinement Algorithm

Algorithm[1](https://arxiv.org/html/2609.05826#alg1)summarizes the completeAdaptive STreeDprocedure\. Letp=\|ℱ\|p=\|\\mathcal\{F\}\|, and let the target tree have maximum depthDDand node budgetMM\(M=2D−1M=2^\{D\}\-1when unrestricted\)\. The training score isQ⁡\(T,ℐ\)∈\[0,1\]Q\(T;\\mathcal\{I\}\)\\in\[0,1\]; the experiments use accuracy\. Each active setEtE\_\{t\}contains at mostKKfeatures\.

Algorithm 1Adaptive STreeD1:Data

ℐ\\mathcal\{I\}, features

ℱ\\mathcal\{F\}, depth

DD, node budget

MM, score

QQ, capacity

KK, time limits

\(Tmax,τ¯\)\(T\_\{\\max\},\\bar\{\\tau\}\), iteration limit

NmaxN\_\{\\max\}, patience

PmaxP\_\{\\max\}, switch threshold

PswitchP\_\{\\mathrm\{switch\}\}, tolerance

ϵ\\epsilon
2:Best feasible tree

TincT^\{\\mathrm\{inc\}\}
3:

E←E\\leftarrowtop\-

KKfeatures ranked by a random forest

4:

Tinc←T^\{\\mathrm\{inc\}\}\\leftarrowbest constant\-leaf tree;

Qinc←Q⁡\(Tinc,ℐ\)Q^\{\\mathrm\{inc\}\}\\leftarrow Q\(T^\{\\mathrm\{inc\}\};\\mathcal\{I\}\)
5:

C←∅C\\leftarrow\\emptyset,

R←∅R\\leftarrow\\emptyset,

P←EP\\leftarrow E,

r←0r\\leftarrow 0
6:for

t=1,…,Nmaxt=1,\\ldots,N\_\{\\max\}do

7:if

elapsed≥Tmax\\operatorname\{elapsed\}\\geq T\_\{\\max\}or

Qinc≥1−ϵQ^\{\\mathrm\{inc\}\}\\geq 1\-\\epsilonthen

8:break

9:endif

10:if

t\>1t\>1then

11:if

\|C\|≥K\|C\|\\geq Kthen

12:break

13:endif

14:

G←RG\\leftarrow Rif

r<Pswitchr<P\_\{\\mathrm\{switch\}\}; otherwise

G←R∪PG\\leftarrow R\\cup P
15:

N←N\\leftarrowat most

K−\|C\|K\-\|C\|top features from repeated CART fits on

ℱ∖G\\mathcal\{F\}\\setminus G
16:if

N=∅N=\\emptysetthen

17:break

18:endif

19:

E←C∪NE\\leftarrow C\\cup N;

P←P∪NP\\leftarrow P\\cup N
20:endif

21:

τ←min⁡\{τ¯,Tmax−elapsed\}\\tau\\leftarrow\\min\\\{\\bar\{\\tau\},\\,T\_\{\\max\}\-\\operatorname\{elapsed\}\\\}
22:

𝒰⁡\(E\)←\\mathcal\{U\}\(E\)\\leftarrowweighted unique data obtained from the projection of

ℐ\\mathcal\{I\}onto

EE
23:

T←WeightedSTreeD⁡\(𝒰⁡\(E\),E,D,M,τ\)T\\leftarrow\\mathrm\{WeightedSTreeD\}\(\\mathcal\{U\}\(E\),E,D,M,\\tau\)
24:if

TTis feasible and

Q⁡\(T,ℐ\)\>Qinc\+ϵQ\(T;\\mathcal\{I\}\)\>Q^\{\\mathrm\{inc\}\}\+\\epsilonthen

25:

Tinc←TT^\{\\mathrm\{inc\}\}\\leftarrow T;

Qinc←Q⁡\(T,ℐ\)Q^\{\\mathrm\{inc\}\}\\leftarrow Q\(T;\\mathcal\{I\}\)
26:

C←supp⁡\(T\)C\\leftarrow\\operatorname\{supp\}\(T\);

R←R∪CR\\leftarrow R\\cup C;

r←0r\\leftarrow 0
27:else

28:

r←r\+1r\\leftarrow r\+1
29:endif

30:if

r≥Pmaxr\\geq P\_\{\\max\}then

31:break

32:endif

33:endfor

34:return

TincT^\{\\mathrm\{inc\}\}

A depth\-DDbinary tree has at most2D−12^\{D\}\-1internal nodes and therefore cannot use more than2D−12^\{D\}\-1distinct split features\. The capacityKKexploits this structural sparsity\. A smaller value reduces split enumeration and usually increases compression after projection; a larger value supplies broader feature coverage but makes the exact reduced problem harder\. The sensitivity experiment in Section[5\.4](https://arxiv.org/html/2609.05826#S5.SS4)evaluates this tradeoff directly\.

The initial candidate set contains the top\-KKfeatures ranked by random forest, and the incumbent is initialized as the best constant leaf\. At later iterations, the incumbent supportCCis retained and at mostK−\|C\|K\-\|C\|additional features are proposed using repeated multi\-level CART fits, which can identify features that become useful after earlier splits\. The archivesRRandPPrecord features used by accepted incumbents and previously proposed features, respectively\. AfterPswitchP\_\{\\mathrm\{switch\}\}nonimproving iterations, the proposal step also excludesPP, encouraging exploration of new feature blocks\. CART is used only for feature proposal and provides no optimality guarantee\.

The incumbent support is never removed\. If\|C\|=K\|C\|=K, no new feature can be added while retaining the incumbent, and the procedure stops; otherwise, the proposal block is truncated so thatEt=Ct−1∪NtE\_\{t\}=C\_\{t\-1\}\\cup N\_\{t\}satisfies\|Et\|≤K\|E\_\{t\}\|\\leq K\. For each active candidate set, the data are projected, aggregated, and solved byWeighted STreeD\. LetTmaxT\_\{\\max\}be the total time limit andτ¯\\bar\{\\tau\}the maximum time for one inner solve\. Provided thatelapsed<Tmax\\operatorname\{elapsed\}<T\_\{\\max\}, the time assigned to iterationttis

τt=min⁡\{τ¯,Tmax−elapsed\}\.\\tau\_\{t\}=\\min\\left\\\{\\bar\{\\tau\},T\_\{\\max\}\-\\operatorname\{elapsed\}\\right\\\}\.\(18\)
Only an improvement greater thanϵ\\epsilonreplaces the incumbent; failed or nonimproving inner solves leave it unchanged\. Hence, the incumbent\-score sequence is nondecreasing, and an interrupted inner solve cannot discard the best feasible tree found previously\. A certified inner solution is optimal for the current candidate set, whereas an uncertified feasible solution is only an incumbent for that reduced problem\. Retaining the incumbent support keeps the current tree feasible in subsequent reduced problems as long as its support fits within the candidate capacity\.

### 4\.2Joint Feature\- and Sample\-Space Reduction

At iterationtt, letqt=\|Et\|≤Kq\_\{t\}=\|E\_\{t\}\|\\leq Kandut=\|𝒰⁡\(Et\)\|u\_\{t\}=\|\\mathcal\{U\}\(E\_\{t\}\)\|\. Feature restriction replaces the full dimensionppbyqtq\_\{t\}, while weighted aggregation replaces the originalnnrecords byutu\_\{t\}weighted records in the sample\-dependent terms of the inner dynamic program\. For binarized features and labels in𝒦\\mathcal\{K\},

ut≤min⁡\{n,\|𝒦\|​2qt\}\.u\_\{t\}\\leq\\min\\left\\\{n,\|\\mathcal\{K\}\|2^\{q\_\{t\}\}\\right\\\}\.\(19\)This is an upper bound\. The actual value ofutu\_\{t\}depends on the feature–label patterns observed after projection and may be much smaller\. The following proposition gives the per\-iteration complexity under the model developed in Section[3](https://arxiv.org/html/2609.05826#S3)\.

###### Proposition 5\.

Consider classification with labels in the finite class set𝒦\\mathcal\{K\}, binarized candidate features, and the training\-accuracy objective\. Suppose that iterationttuses candidate setEtE\_\{t\}, withqt=\|Et\|≤Kq\_\{t\}=\|E\_\{t\}\|\\leq K, and aggregation key\(𝐱i​Et,yi\)\(\\mathbf\{x\}\_\{iE\_\{t\}\},y\_\{i\}\)\. Under the direct state\-scanning model of Proposition[3](https://arxiv.org/html/2609.05826#Thmproposition3), the running time of the innerWeighted STreeDsolve is

O⁡\(\(D\+1\)​\(M\+1\)​HD​\(qt\)​\[\(\|𝒦\|\+qt\)​ut\+qt​M\]\),O\\\!\\left\(\(D\+1\)\(M\+1\)H\_\{D\}\(q\_\{t\}\)\\left\[\(\|\\mathcal\{K\}\|\+q\_\{t\}\)u\_\{t\}\+q\_\{t\}M\\right\]\\right\),\(20\)whereut≤min⁡\{n,\|𝒦\|​2qt\}u\_\{t\}\\leq\\min\\\{n,\|\\mathcal\{K\}\|2^\{q\_\{t\}\}\\\}\. The asymptotic input quantities arenn,qtq\_\{t\},DD,MM,KK, and\|𝒦\|\|\\mathcal\{K\}\|\. Sinceqt≤Kq\_\{t\}\\leq K, a uniform per\-iteration bound is

O⁡\(\(D\+1\)​\(M\+1\)​HD​\(K\)​\[\(\|𝒦\|\+K\)​min⁡\{n,\|𝒦\|​2K\}\+K​M\]\)\.O\\\!\\left\(\(D\+1\)\(M\+1\)H\_\{D\}\(K\)\\left\[\(\|\\mathcal\{K\}\|\+K\)\\min\\\{n,\|\\mathcal\{K\}\|2^\{K\}\\\}\+KM\\right\]\\right\)\.\(21\)

The capacityKKreduces two sources of computational cost\. First, each dynamic\-programming state considers at mostKKcandidate features instead of allppfeatures\. Second, projection onto a smaller feature set can create fewer distinct records\.Weighted STreeDtherefore processes fewer weighted records\. Once the active candidate set is constructed, the complexity of the inner dynamic program depends onKKrather than the full feature dimensionpp\. The completeAdaptive STreeDprocedure, however, still depends on the original data because feature proposal, projection, and aggregation operate on the full input\.

ForNNcompleted iterations, letCRF​\(n,p\)C\_\{\\mathrm\{RF\}\}\(n,p\)denote the cost of the initial random\-forest ranking andCCART,t​\(n,p\)C\_\{\\mathrm\{CART\},t\}\(n,p\)the cost of the CART proposal at iterationtt\. Assuming expected constant\-time hash\-table operations, projection and aggregation requireO⁡\(n​∑t=1Nqt\)O\(n\\sum\_\{t=1\}^\{N\}q\_\{t\}\)expected work\. The total computational cost is therefore

CRF​\(n,p\)\+∑t=2NCCART,t​\(n,p\)\+O⁡\(n​∑t=1Nqt\)\+∑t=1NTDP,t,C\_\{\\mathrm\{RF\}\}\(n,p\)\+\\sum\_\{t=2\}^\{N\}C\_\{\\mathrm\{CART\},t\}\(n,p\)\+O\\\!\\left\(n\\sum\_\{t=1\}^\{N\}q\_\{t\}\\right\)\+\\sum\_\{t=1\}^\{N\}T\_\{\\mathrm\{DP\},t\},\(22\)whereTDP,tT\_\{\\mathrm\{DP\},t\}is bounded by \([20](https://arxiv.org/html/2609.05826#S4.E20)\)\. HereNN,nn,pp, and the candidate sizesqtq\_\{t\}are input quantities\. Equation \([22](https://arxiv.org/html/2609.05826#S4.E22)\) accounts for the entire pipeline\. In contrast,TDP,tT\_\{\\mathrm\{DP\},t\}covers only the exact dynamic\-programming solve at iterationtt\.

Equation \([22](https://arxiv.org/html/2609.05826#S4.E22)\) shows that the complete procedure still depends on the original sample sizennand feature dimensionpp, even though each inner dynamic\-programming problem operates on a reduced representation\. Accordingly,n/utn/u\_\{t\}andHD​\(p\)/HD​\(qt\)H\_\{D\}\(p\)/H\_\{D\}\(q\_\{t\}\)quantify the reductions in the sample\- and feature\-dependent components of the dynamic program, respectively\. They should not be interpreted as guarantees on total wall\-clock speedup\. Figure[1](https://arxiv.org/html/2609.05826#S4.F1)summarizes one refinement cycle ofAdaptive STreeD\.

Original data nnobservations ppbinary features1\. Feature proposal p→q,q≤K≤pp\\rightarrow q,\\ q\\leq K\\leq p costCRF​\(n,p\)C\_\{\\mathrm\{RF\}\}\(n,p\)ift=1t=1; costCCART,t​\(n,p\)C\_\{\\mathrm\{CART\},t\}\(n,p\)ift≥2t\\geq 22\. Projection X→XSX\\rightarrow X\_\{S\} expected costO⁡\(n​q\)O\(nq\)3\. Aggregation n→uSn\\rightarrow u\_\{S\} expected costO⁡\(n​q\)O\(nq\) uS≤min⁡\{n,\|𝒦\|​2q\}u\_\{S\}\\leq\\min\\\{n,\|\\mathcal\{K\}\|2^\{q\}\\\}4\. Weighted STreeD solve inputuS×qu\_\{S\}\\times q O⁡\(\(D\+1\)​\(M\+1\)​HD​\(q\)CLOSE\\displaystyle O\\\!\\left\(\(D\+1\)\(M\+1\)H\_\{D\}\(q\)\\right\. ×\[\(\|𝒦\|\+q\)uS\+qM\]\)\\displaystyle\\left\.\{\}\\times\[\(\|\\mathcal\{K\}\|\+q\)u\_\{S\}\+qM\]\\right\)Feature\-space reductionHD​\(p\)→HD​\(q\)H\_\{D\}\(p\)\\rightarrow H\_\{D\}\(q\)HD​\(q\)=O⁡\(\(2​q\)D\)H\_\{D\}\(q\)=O\(\(2q\)^\{D\}\)Sample\-space reductionn→uSn\\rightarrow u\_\{S\}5\. Incumbent update retain useful split features; refine the next candidate set

Figure 1:One Adaptive STreeD refinement cycle\. Candidate restriction reducesppfeatures toqtq\_\{t\}, and aggregation mapsnnprojected records toutu\_\{t\}weighted unique records before the inner solve\.
### 4\.3Conditional Solution\-Quality Analysis

We examine how the main parameters ofAdaptive STreeDinfluence solution quality, with particular attention to training accuracy\. Recovering a full\-feature optimum requires that some visited candidate set contain the split features of an optimal tree and that the corresponding reduced problem be solved to certified optimality\. This section relates this event to candidate capacity, refinement opportunities, and the quality of the retained incumbent\.

Let

QD⋆=maxT∈𝒯⁡\(ℱ,D,M\)⁡Q⁡\(T,ℐ\)\>0\.Q\_\{D\}^\{\\star\}=\\max\_\{T\\in\\mathcal\{T\}\(\\mathcal\{F\},D,M\)\}Q\(T;\\mathcal\{I\}\)\>0\.\(23\)Choose a full\-feature optimal treeTD⋆T\_\{D\}^\{\\star\}, and define

SD⋆=supp⁡\(TD⋆\),K⋆=\|SD⋆\|\.S\_\{D\}^\{\\star\}=\\operatorname\{supp\}\(T\_\{D\}^\{\\star\}\),\\qquad K^\{\\star\}=\|S\_\{D\}^\{\\star\}\|\.Since a feasible tree has depth at mostDDand at mostMMinternal nodes,

K⋆≤min⁡\{M,2D−1\}\.K^\{\\star\}\\leq\\min\\\{M,2^\{D\}\-1\\\}\.We assumeK⋆≤KK^\{\\star\}\\leq K, so that an active candidate set can contain the selected optimal support\.

For iterationtt, define

𝒜t=\{SD⋆⊆Et\},\\mathcal\{A\}\_\{t\}=\\\{S\_\{D\}^\{\\star\}\\subseteq E\_\{t\}\\\},and

ℬt−1=⋂s=1t−1𝒜sc,\\mathcal\{B\}\_\{t\-1\}=\\bigcap\_\{s=1\}^\{t\-1\}\\mathcal\{A\}\_\{s\}^\{c\},withℬ0\\mathcal\{B\}\_\{0\}equal to the whole sample space\. Letℋt−1\\mathcal\{H\}\_\{t\-1\}denote the search history before iterationtt\. Suppose deterministic constantsρ¯t∈\[0,1\]\\underline\{\\rho\}\_\{t\}\\in\[0,1\]satisfy

Pr⁡\(𝒜t∣ℋt−1\)≥ρ¯talmost surely on​ℬt−1\.\\Pr\\\!\\left\(\\mathcal\{A\}\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\}\\right\)\\geq\\underline\{\\rho\}\_\{t\}\\qquad\\text\{almost surely on \}\\mathcal\{B\}\_\{t\-1\}\.\(24\)
###### Proposition 6\.

Assume that \([24](https://arxiv.org/html/2609.05826#S4.E24)\) holds fort=1,…,Nt=1,\\ldots,N, and that whenever𝒜t\\mathcal\{A\}\_\{t\}occurs, the corresponding reduced problem is solved to certified optimality\. Suppose further that the retained incumbent has approximation ratio at leastr0∈\[0,1\]r\_\{0\}\\in\[0,1\]\. IfQA,NQ\_\{A,N\}denotes the final incumbent score afterNNcompleted iterations, then

𝔼⁡\[QA,NQD⋆\]≥1−\(1−r0\)​∏t=1N\(1−ρ¯t\)\.\\mathbb\{E\}\\\!\\left\[\\frac\{Q\_\{A,N\}\}\{Q\_\{D\}^\{\\star\}\}\\right\]\\geq 1\-\(1\-r\_\{0\}\)\\prod\_\{t=1\}^\{N\}\(1\-\\underline\{\\rho\}\_\{t\}\)\.\(25\)

Proposition[6](https://arxiv.org/html/2609.05826#Thmproposition6)highlights three factors: the baseline ratior0r\_\{0\}, the number of completed iterationsNN, and the conditional support\-coverage boundsρ¯t\\underline\{\\rho\}\_\{t\}\. Larger values of any of these quantities improve the bound\. Theρ¯t\\underline\{\\rho\}\_\{t\}are theoretical lower bounds; random\-forest and CART importance scores are used only to rank candidate features and are not estimates of these probabilities\.

For training accuracy, let

πmax=maxk∈𝒦1n∑i=1n𝟏\{yi=k\}\\pi\_\{\\max\}=\\max\_\{k\\in\\mathcal\{K\}\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{y\_\{i\}=k\\\}denote the majority\-class proportion\. Since Algorithm[1](https://arxiv.org/html/2609.05826#alg1)initializes the incumbent with the majority\-class leaf andQD⋆≤1Q\_\{D\}^\{\\star\}\\leq 1, the initial approximation ratio is at leastπmax\\pi\_\{\\max\}\.

###### Corollary 2\.

For training accuracy, under the assumptions of Proposition[6](https://arxiv.org/html/2609.05826#Thmproposition6),

𝔼⁡\[QA,NQD⋆\]≥1−\(1−πmax\)​∏t=1N\(1−ρ¯t\)\.\\mathbb\{E\}\\\!\\left\[\\frac\{Q\_\{A,N\}\}\{Q\_\{D\}^\{\\star\}\}\\right\]\\geq 1\-\(1\-\\pi\_\{\\max\}\)\\prod\_\{t=1\}^\{N\}\(1\-\\underline\{\\rho\}\_\{t\}\)\.\(26\)

The candidate capacityKKaffects both feature coverage and the difficulty of the reduced problem\. The conditionK⋆≤KK^\{\\star\}\\leq Kis necessary for an active set to contain the selected optimal support\. IncreasingKKmay improve coverage, but it also enlarges the reduced problem and can make certification more difficult\. The random\-forest initialization and CART\-guided refinement determine which features enter the candidate sets and therefore influence the coverage probabilitiesρ¯t\\underline\{\\rho\}\_\{t\}\.

The remaining parameters mainly control how many reduced problems can be explored and certified\. The iteration and patience limits affect the number of completed iterationsNN\. A larger inner time limitτ¯\\bar\{\\tau\}gives each reduced problem more time to reach certified optimality, whereas the total budgetTmaxT\_\{\\max\}limits both the number and duration of inner solves\. Tree depthDDand node budgetMMaffect the possible support size throughK⋆≤min⁡\{M,2D−1\}K^\{\\star\}\\leq\\min\\\{M,2^\{D\}\-1\\\}and also determine the difficulty of the dynamic program\. Under a fixed computational budget, training accuracy therefore depends on the balance between feature coverage, refinement opportunities, and the ability to certify the resulting reduced problems\.

## 5Computational Experiments

The computational study addresses three questions:

1. Q1\.DoesAdaptive STreeDimprove the scalability of optimal classification tree learning while maintaining predictive performance as the maximum tree depth increases?
2. Q2\.When the candidate feature set is fixed, to what extent does weighted unique\-data aggregation reduce the computational cost ofSTreeD?
3. Q3\.How does the candidate\-set capacityKKaffect the tradeoff between computational efficiency and predictive performance?

We conduct three experiments\. The overall comparison evaluatesAdaptive STreeDagainst CART and two full\-feature optimal\-tree solvers across different tree depths\. The fixed\-candidate ablation isolates the computational effect ofWeighted STreeD\. The candidate\-capacity study examines the sensitivity ofAdaptive STreeDtoKK\. Appendix[A](https://arxiv.org/html/2609.05826#A1)separately examines the preprocessing resolution used to construct the binary candidate universe\.

### 5\.1Experimental Setup

Data and preprocessing\.We use five public tabular data sets: COMPAS\([Angwin et al\. 2016](https://arxiv.org/html/2609.05826#bib.bib34),[ProPublica 2016](https://arxiv.org/html/2609.05826#bib.bib35)\), Diabetes 130\-US Hospitals\([Strack et al\. 2014](https://arxiv.org/html/2609.05826#bib.bib36),[Clore et al\. 2014](https://arxiv.org/html/2609.05826#bib.bib37)\), Give Me Some Credit\([Kaggle 2011](https://arxiv.org/html/2609.05826#bib.bib38)\), FICO HELOC\([FICO 2018](https://arxiv.org/html/2609.05826#bib.bib39),[Arya et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib40)\), and Capital One Transactions\([Capital One Recruiting 2018](https://arxiv.org/html/2609.05826#bib.bib41),[Bhardwaj 2020](https://arxiv.org/html/2609.05826#bib.bib42)\)\. We use five independent 80/20 train–test splits\. Continuous features are quantile binned into at most 100 intervals and represented by cumulative binary indicators; categorical features are one\-hot encoded\. The 100\-bin cap is used as a conservative preprocessing choice to retain more threshold information before optimization, rather than to minimize runtime\. Appendix[A](https://arxiv.org/html/2609.05826#A1)examines the sensitivity to this choice, and Table[1](https://arxiv.org/html/2609.05826#S5.T1)reports the resulting Bin100 dimensions\.

Table 1:Data sets used in the computational experimentsMethod settings\.The overall comparison usesK=20K=20\. Unless otherwise stated,Adaptive STreeDuses a total time limit ofTmax=600T\_\{\\max\}=600seconds, a maximum inner\-solve time ofτ¯=100\\bar\{\\tau\}=100seconds,Nmax=300N\_\{\\max\}=300outer iterations,Pmax=3P\_\{\\max\}=3,Pswitch=2P\_\{\\mathrm\{switch\}\}=2, and an improvement tolerance ofϵ=10−9\\epsilon=10^\{\-9\}\. The CART proposal procedure uses depth 5 and 20 repeated fits per iteration\. The sensitivity experiment variesKKwhile holding the remaining parameters fixed\.STreeD,Weighted STreeD, and DL8\.5 optimize training accuracy with the full depth\-based node budgetM=2D−1M=2^\{D\}\-1\. Each configuration has a 600\-second time limit\. CART is included as a fast greedy baseline\.Adaptive STreeDuses a single total time budget covering feature proposal, projection, aggregation, and all innerWeighted STreeDsolves\. To focus the computational study on scalability, all optimization\-based methods use training accuracy as the common objective\. This experimental choice does not restrict the weighted reformulation to accuracy\. Our implementation also includes weighted variants forF1F\_\{1\}\-score optimization and cost\-sensitive classification\.

Computing environment and status\.The CART and Random Forest \(RF\) algorithms were implemented in Python 3\.12 using scikit\-learn\([Pedregosa et al\. 2011](https://arxiv.org/html/2609.05826#bib.bib49)\)\. All experiments were conducted on a 64\-bit Windows system with an Intel Core i9\-14900KF at 3\.20 GHz and 64 GB of memory\. The implementations ofAdaptive STreeDandWeighted STreeD, together with reproducible examples, are publicly available at[https://github\.com/Tommytutu/AdaptiveSTreeD](https://github.com/Tommytutu/AdaptiveSTreeD)\. For full\-feature STreeD and DL8\.5,*Optimal*denotes a certified optimum over the full candidate feature set\. For fixed\-candidate Weighted STreeD, it denotes a certified optimum for the specified candidate set\. Adaptive STreeD does not in general provide a full\-feature optimality certificate; for this method, we report whether a feasible incumbent is returned and whether the total time limit is reached\. A run with no feasible return before the time or memory limit is reported as*Infeasible*; this is an experimental status and does not imply mathematical infeasibility\.

### 5\.2Overall Computational Performance

This subsection addressesQ1by comparing computational scalability and predictive performance across CART,Adaptive STreeD, full\-featureSTreeD, and DL8\.5 at depths 2–7 under a common 600\-second time limit\. Full\-featureSTreeDserves as the direct reference becauseAdaptive STreeDis built on the same dynamic\-programming framework, while DL8\.5 provides an additional dynamic\-programming baseline for finite\-budget optimal\-tree search\([Aglin et al\. 2020](https://arxiv.org/html/2609.05826#bib.bib19)\)\.

Scalability\.Results are matched by data set, random split, and maximum depth\. CART andAdaptive STreeDare evaluated at all depths\. Full\-featureSTreeDreturns feasible trees only through depth 4, and its certification rate drops sharply at depth 4\. At depths 5–7, runs that reach the time or memory limit without a feasible tree are reported as*Infeasible*\. DL8\.5 returns only uncertified incumbents in all 75 runs at these depths\. Comparisons at larger depths are therefore interpreted under the common computational budget rather than against consistently certified full\-feature optima\.

Figure[2](https://arxiv.org/html/2609.05826#S5.F2)reports median runtimes and interquartile ranges\. At depths 2–4, median runtimes forAdaptive STreeDare 5\.38, 12\.70, and 17\.84 seconds, compared with 7\.19, 98\.48, and 607\.11 seconds for full\-featureSTreeD\. The corresponding runtime ratios are1\.34×1\.34\\times,7\.75×7\.75\\times, and34\.02×34\.02\\times\. The depth\-4 ratio is capped because many full\-feature runs reach the time or memory limit\. The widening gap with depth reflects the growing cost of full\-feature search, whereas at depth 2 the overhead of feature proposal and aggregation offsets much of the benefit\.

At depths 5–7,Adaptive STreeDreturns a feasible tree in all 25 runs at each depth, with median runtimes of 42\.08, 94\.91, and 223\.94 seconds\. Among these runs, 1, 6, and 9 reach the time limit, respectively\. Full\-featureSTreeD, in contrast, fails to return a feasible tree before the time or memory limit at these depths\. Candidate restriction therefore extends the range of depths for which a feasible tree can be obtained under the stated computational protocol, although the computational burden still grows with depth\.

DL8\.5 is faster thanAdaptive STreeDat depth 2, reflecting the overhead of the adaptive procedure on easier instances\. At depths 3 and 4, 11 of 25 and 23 of 25 DL8\.5 runs reach the time limit, and all 75 runs at depths 5–7 are time\-limited\. These solutions are therefore treated as uncertified incumbents\. Overall, the relative computational advantage ofAdaptive STreeDbecomes more pronounced as depth and problem difficulty increase\.

Figure 2:Runtime distributions by maximum tree depth\. Boxes show interquartile ranges and center lines show medians\. The dashed line marks the 600\-second time limit\.Predictive performance\.Figure[3](https://arxiv.org/html/2609.05826#S5.F3)reports five\-split means with sample\-standard\-deviation error bars\. At depths 2–4,Adaptive STreeDclosely matches the available full\-featureSTreeDresults\. Across the 75 matched data\-set–split–depth configurations, the training\-accuracy difference is at most 0\.1 percentage points in 60 cases and at most 0\.2 percentage points in 67 cases\. The average Adaptive\-minus\-STreeDdifference is−0\.0553\-0\.0553percentage points for training accuracy and0\.080\.08percentage points for test accuracy\. These differences are descriptive, and no statistical significance is claimed\.

For COMPAS, Diabetic, Give Me Some Credit, and FICO,Adaptive STreeDgenerally achieves predictive performance comparable to the other optimal\-tree methods over the depths for which matched results are available\. The small test\-accuracy differences indicate that the scalability improvement does not come with a systematic loss in predictive performance\.

A different pattern appears for Transactions, the largest data set with 786,363 observations\. At depth 4,Adaptive STreeDachieves better predictive performance than full\-featureSTreeDand DL8\.5\. The full\-feature search is particularly difficult on this large instance, and many competing runs are limited by the 600\-second budget\. Under the same budget,Adaptive STreeDsearches a reduced feature space and obtains a tree with higher predictive performance\. This is a finite\-budget advantage and does not imply that a certified full\-feature optimum would have lower predictive performance\.

At greater depths, the pooled mean training accuracy ofAdaptive STreeDincreases from80\.08%80\.08\\%at depth 4 to80\.54%80\.54\\%,80\.87%80\.87\\%, and81\.00%81\.00\\%at depths 5–7\. Full\-featureSTreeDprovides no comparable feasible solutions at these depths, while DL8\.5 returns time\-limited incumbents\. Test accuracy, however, is not monotone in depth: the best five\-split mean occurs at depth 3 for COMPAS and Give Me Some Credit, depth 4 for Diabetic and Transactions, and depth 5 for FICO\. This pattern is consistent with overfitting, as deeper trees can improve the training objective without necessarily improving out\-of\-sample performance\.

ForQ1, the matched results indicate thatAdaptive STreeDscales better as tree depth and problem difficulty increase\. Its predictive performance remains comparable to the evaluated optimal\-tree methods under the same computational budget\. On the largest data set, the reduced search also yields higher predictive performance within that budget\.

Figure 3:Training and test accuracy by data set and maximum tree depth\. Points show five\-split means and error bars show sample standard deviations\.
### 5\.3Fixed\-Candidate Weighted Aggregation

This subsection addressesQ2by isolating the computational effect of weighted unique\-data aggregation\. A 500\-tree random forest ranks the binary features, and matchedSTreeDandWeighted STreeDruns receive the same topK∈\{10,20,30,40,50\}K\\in\\\{10,20,30,40,50\\\}features, training split, depth, objective, and 600\-second time limit\. Thus, the two methods solve the same fixed\-candidate tree problem and differ only in the representation of the training records\. StandardSTreeDretains all training records, whereasWeighted STreeDmerges duplicate projected feature–label records into weighted representatives\.

For each matched pair, we report

Compression=nuS,Speedup=TSTreeDTW​\-​STreeD\.\\mathrm\{Compression\}=\\frac\{n\}\{u\_\{S\}\},\\qquad\\mathrm\{Speedup\}=\\frac\{T\_\{\\mathrm\{STreeD\}\}\}\{T\_\{\\mathrm\{W\\text\{\-\}STreeD\}\}\}\.\(27\)A speedup above one favorsWeighted STreeD\. Ratios involving time\-limited runs are interpreted as capped comparisons\.

Table 2:Weighted aggregation ablation on five binarized data sets- •Note\.“Mean comp\.” and “Mean sp\.” denote arithmetic\-mean compression and runtime speedup, respectively\. “Faster” denotes a recorded speedup greater than one\. “Same” indicates equal training misclassification, while “Better” indicates lower training misclassification forWeighted STreeD\.

Computational effect\.Table[2](https://arxiv.org/html/2609.05826#S5.T2)and Figure[4](https://arxiv.org/html/2609.05826#S5.F4)show thatWeighted STreeDhas lower recorded runtime in 100 of 150 matched cases\. All 50 cases in which it is not faster occur at depths 2 and 3, where the underlying optimization problems are relatively easy and aggregation overhead is more noticeable\. Across all cases, the arithmetic\-mean speedup is8\.20×8\.20\\times, with a maximum of121\.41×121\.41\\times\.

Compression and speedup vary across data sets\. Transactions has the largest mean compression ratio, 538\.46, and the largest mean speedup,23\.05×23\.05\\times, while Give Me Some Credit achieves a mean speedup of9\.53×9\.53\\times\. In contrast, COMPAS has a smaller mean compression ratio of 10\.19 and a more moderate mean speedup of2\.44×2\.44\\times\.

Depth and candidate\-set size further explain the runtime differences\. At depths 2 and 3, the additional cost of aggregation, initialization, and weight management can offset the savings from shorter record scans\. From depth 4 onward,Weighted STreeDis faster in all matched cases, as repeated record processing across more dynamic\-programming states becomes more important\. The largest gains also tend to occur for smallerKK, because projection onto fewer features creates more duplicate records\. AsKKincreases,uSu\_\{S\}generally approachesnn, reducing the benefit of aggregation\.

The compression ratio and runtime improvement are positively related, but not proportional\. Compression and log speedup have a Spearman correlation of 0\.342\. This is consistent with the complexity analysis:n/uSn/u\_\{S\}measures the reduction in sample\-dependent work, whereas total runtime also includes feature enumeration, caching, pruning, and solver overhead\. Therefore, a large compression ratio does not imply an equally large wall\-clock speedup\.

Solution quality\.The two methods solve the same fixed\-candidate optimization problem, so weighted aggregation does not change its optimum\. Training misclassification is identical in 138 of 150 matched cases\. All 12 differences occur in time\-limited runs, whereWeighted STreeDobtains a better incumbent before termination\. When both methods certify optimality, Proposition[2](https://arxiv.org/html/2609.05826#Thmproposition2)requires their optimal objective values to agree\.

![Refer to caption](https://arxiv.org/html/2609.05826v1/weighted_mean_speedup_heatmap.png)\(a\)Mean speedup byKKand depth\.
\(b\)Compression ratio and matched runtime speedup\.
Figure 4:Effect of weighted unique\-data aggregation under fixed candidate sets\. The dashed line in panel \(b\) indicates equal recorded runtime between standard STreeD and Weighted STreeD\.ForQ2, aggregation is most effective when projection creates many duplicate records and tree depth makes repeated scanning costly\.

### 5\.4Sensitivity to Candidate\-Set Capacity

This subsection addressesQ3by examining how the candidate\-set capacityKKaffects computational cost and predictive performance\. We evaluateK∈\{10,15,20,25,30,35,40\}K\\in\\\{10,15,20,25,30,35,40\\\}at depths 2–7 on five data sets and five train–test splits\. Runtime ratios and test\-accuracy differences are computed within matched blocks usingK=20K=20as the reference\. Of the 1,050 planned runs, 1,043 return results; missing runs are not imputed\. Complete numerical results are reported in Appendix[C\.1](https://arxiv.org/html/2609.05826#A3.SS1)\.

Seven configurations are unavailable\. These missing runs occur only at larger candidate capacities and greater depths and are therefore not treated as random\. Accuracy differences are computed only for matched blocks in which both the target capacity andK=20K=20return a feasible tree\.

Computational cost\.Figure[5](https://arxiv.org/html/2609.05826#S5.F5)\(a\) shows that runtime generally increases withKK, and the effect becomes stronger as tree depth increases\. AtK=20K=20, all 150 runs return results and the pooled median runtime is 10\.48 seconds\. AtK=40K=40, 144 runs return results, the pooled median runtime increases to 32\.03 seconds, and the median matched runtime ratio relative toK=20K=20is2\.433×2\.433\\times\.

Across the full capacity sequence, pooled median runtime increases from 7\.95 seconds atK=10K=10to 20\.89 seconds atK=30K=30and 32\.03 seconds atK=40K=40\. All 150 runs return results throughK=30K=30, compared with 149 atK=35K=35and 144 atK=40K=40\. The runtime increase is especially pronounced at greater depths\. For example, at depth 6, the median matched runtime ratio forK=40K=40relative toK=20K=20reaches7\.75×7\.75\\times\.

This behavior is consistent with the complexity analysis\. A larger candidate set increases the number of split features considered at each dynamic\-programming state\. It can also create more distinct projected records, reducing the amount of compression available toWeighted STreeD\. Both effects become more important as tree depth increases\.

Predictive performance\.Figure[5](https://arxiv.org/html/2609.05826#S5.F5)\(b\) shows that predictive performance changes much less than runtime\. Pooled mean training accuracy is 0\.7942, 0\.7965, and 0\.8029 forK=10K=10,2020, and4040, respectively, while pooled mean test accuracy is 0\.7892, 0\.7905, and 0\.7946\. Relative toK=20K=20, the mean matched test\-accuracy difference ranges from−0\.127\-0\.127percentage points atK=10K=10to\+0\.122\+0\.122percentage points atK=40K=40\.

IncreasingKKtherefore provides modest average improvements in predictive performance compared with its effect on runtime\. The depth\-specific differences are also not monotone\. A larger candidate set gives the algorithm access to more features, but the additional coverage does not necessarily improve test accuracy at every depth\.

\(a\)Runtime sensitivity\.\(b\)Matched test\-accuracy difference\.
Figure 5:Sensitivity to candidate\-set capacityKK\. Runtime curves show depth\-specific medians on a logarithmic scale, with shaded interquartile ranges\. Accuracy curves report mean matched test\-accuracy differences relative toK=20K=20in percentage points\.ForQ3, the results identify a tradeoff between feature coverage and computational cost\. IncreasingKKprovides more candidate features and modestly improves average predictive performance, but at a much larger computational cost\. The completion rate also decreases at the largest capacities, especially for deeper trees\. In these experiments,K=20K=20provides a computationally efficient operating point, whereasK=40K=40provides broader feature coverage and slightly higher solution quality at greater computational cost\.

## 6Conclusion

This paper develops two complementary mechanisms for improving the scalability of dynamic\-programming\-based optimal classification trees\.Weighted STreeDmerges duplicate projected records into weighted representatives while preserving the fixed\-candidate optimization problem under the stated assumptions\.Adaptive STreeDfurther combines bounded candidate sets, feature refinement, andWeighted STreeD\. Each certified inner solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space\.

Across five data sets,Adaptive STreeDrequires less runtime than full\-featureSTreeDin matched comparisons at depths 2–4 and continues to return feasible trees at greater depths\. Its predictive performance remains comparable to the evaluated optimal\-tree methods under the same computational budget\. On the largest data set, Transactions, it also achieves higher predictive performance in the finite\-budget comparison with the full\-feature methods\. The fixed\-candidate ablation shows thatWeighted STreeDachieves an average speedup of8\.20×8\.20\\timesand a maximum of121\.41×121\.41\\times, with larger gains for deeper trees and more compressible data\. The sensitivity analysis further identifies a tradeoff in the candidate capacityKK: increasingKKimproves feature coverage and slightly improves solution quality, but also increases runtime, especially for deeper trees\.

The main limitation is thatAdaptive STreeDdoes not guarantee full\-feature optimality because the feature\-proposal procedure may omit features used by an optimal tree\. Its performance also depends on the candidate capacity, time allocation, and stopping rules, and reducing the feature and sample spaces does not remove the combinatorial dependence on tree depth\. In addition, the current analysis gives explicit recursions and complexity bounds only for binarized candidate features under the training\-accuracy objective\. Proposition[2](https://arxiv.org/html/2609.05826#Thmproposition2)separately establishes fixed\-candidate equivalence for separable tasks that satisfy the information\-preservation condition\.

Future work will investigate safe feature\-screening rules, stronger full\-space bounds, adaptive candidate capacities, and more efficient memory and parallelization strategies\. Extensions to continuous features, task\-specific recursions and complexity bounds for objectives beyond training accuracy, robust formulations, and broader high\-stakes applications are also left for future work\.

## References

- S\. Aghaei, A\. Gómez, and P\. VayanosStrong optimal classification trees\.Operations Research73\(4\),pp\. 2223–2241\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Aglinet al\.\(2020\)G\. Aglin, S\. Nijssen, and P\. SchausLearning optimal decision trees using caching branch\-and\-bound search\.Proceedings of the AAAI Conference on Artificial Intelligence34\(4\),pp\. 3146–3153\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1),[§5\.2](https://arxiv.org/html/2609.05826#S5.SS2.p1.1)\.
- Aglinet al\.\(2022\)G\. Aglin, S\. Nijssen, and P\. SchausLearning optimal decision trees under memory constraints\.InMachine Learning and Knowledge Discovery in Databases\. Research Track,Lecture Notes in Artificial Intelligence, Vol\.13717,pp\. 393–409\.Cited by:[§2\.3](https://arxiv.org/html/2609.05826#S2.SS3.p1.1)\.
- Aleset al\.\(2024\)Z\. Ales, V\. Huré, and A\. LambertNew optimization models for optimal classification trees\.Computers & Operations Research164,pp\. 106515\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Alstonet al\.\(2026\)B\. C\. Alston, H\. Validi, and I\. V\. HicksMixed integer linear optimization formulations for learning optimal binary classification trees\.INFORMS Journal on Computing\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1)\.
- Angelinoet al\.\(2018\)E\. Angelino, N\. Larus\-Stone, D\. Alabi, M\. Seltzer, and C\. RudinLearning certifiably optimal rule lists for categorical data\.Journal of Machine Learning Research18\(234\),pp\. 1–78\.Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p1.1)\.
- Angwinet al\.\(2016\)J\. Angwin, J\. Larson, S\. Mattu, and L\. KirchnerMachine bias\.Note:ProPublica, May 23\. Available at[https://www\.propublica\.org/article/machine\-bias\-risk\-assessments\-in\-criminal\-sentencing](https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing)Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Aryaet al\.\(2020\)V\. Arya, R\. K\. E\. Bellamy, P\. Chen, A\. Dhurandhar, M\. Hind, S\. C\. Hoffman, S\. Houde, Q\. V\. Liao, R\. Luss, A\. Mojsilovic, S\. Mourad, P\. Pedemonte, R\. Raghavendra, J\. T\. Richards, P\. Sattigeri, K\. Shanmugam, M\. Singh, K\. R\. Varshney, D\. Wei, and Y\. ZhangAI Explainability 360: an extensible toolkit for understanding data and machine learning models\.Journal of Machine Learning Research21\(130\),pp\. 1–6\.Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Babbaret al\.\(2025\)V\. Babbar, H\. McTavish, C\. Rudin, and M\. SeltzerNear\-optimal decision trees in a SPLIT second\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 2114–2175\.Cited by:[§2\.3](https://arxiv.org/html/2609.05826#S2.SS3.p1.1)\.
- Bertsimas and Dunn \(2017\)D\. Bertsimas and J\. DunnOptimal classification trees\.Machine Learning106\(7\),pp\. 1039–1082\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Bhardwaj \(2020\)A\. BhardwajFraud detection\.Note:Kaggle data set\. Available at[https://www\.kaggle\.com/datasets/iabhishekbhardwaj/fraud\-detection](https://www.kaggle.com/datasets/iabhishekbhardwaj/fraud-detection)Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Blanqueroet al\.\(2020\)R\. Blanquero, E\. Carrizosa, C\. Molero\-Río, and D\. Romero MoralesSparsity in optimal randomized classification trees\.European Journal of Operational Research284\(1\),pp\. 255–272\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1)\.
- Blanqueroet al\.\(2021\)R\. Blanquero, E\. Carrizosa, C\. Molero\-Río, and D\. Romero MoralesOptimal randomized classification trees\.Computers & Operations Research132,pp\. 105281\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1)\.
- Breimanet al\.\(1984\)L\. Breiman, J\. H\. Friedman, R\. A\. Olshen, and C\. J\. StoneClassification and regression trees\.Wadsworth International Group,Belmont, CA\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1)\.
- Briţaet al\.\(2025\)C\. E\. Briţa, J\. G\. M\. van der Linden, and E\. DemirovićOptimal classification trees for continuous feature data using dynamic programming with branch\-and\-bound\.Proceedings of the AAAI Conference on Artificial Intelligence39\(11\),pp\. 11131–11139\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1)\.
- Capital One Recruiting \(2018\)Capital One RecruitingCapital one data science challenge\.Note:Synthetic card\-transaction data\. Available at[https://github\.com/CapitalOneRecruiting/DS](https://github.com/CapitalOneRecruiting/DS)Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Chaoukiet al\.\(2025\)A\. Chaouki, J\. Read, and A\. BifetBranches: efficiently seeking optimal sparse decision trees via AO\*\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 7430–7484\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1)\.
- Cloreet al\.\(2014\)J\. Clore, K\. J\. Cios, J\. P\. DeShazo, and B\. StrackDiabetes 130\-us hospitals for years 1999–2008\.Note:UCI Machine Learning Repository\. DOI: 10\.24432/C5230JCited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Demirovićet al\.\(2023\)E\. Demirović, E\. Hebrard, and L\. JeanBlossom: an anytime algorithm for computing optimal decision trees\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 7533–7562\.Cited by:[§2\.3](https://arxiv.org/html/2609.05826#S2.SS3.p1.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.05826#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1)\.
- D’Onofrioet al\.\(2024\)F\. D’Onofrio, G\. Grani, M\. Monaci, and L\. PalagiMargin optimal classification trees\.Computers & Operations Research161,pp\. 106441\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Eibenet al\.\(2023\)E\. Eiben, S\. Ordyniak, G\. Paesani, and S\. SzeiderLearning small decision trees with large domain\.InProceedings of the Thirty\-Second International Joint Conference on Artificial Intelligence,pp\. 3184–3192\.Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p3.1)\.
- FICO \(2018\)FICOExplainable machine learning challenge: HELOC data set\.Note:FICO Community\. Available at[https://community\.fico\.com/s/explainable\-machine\-learning\-challenge](https://community.fico.com/s/explainable-machine-learning-challenge)Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Firatet al\.\(2020\)M\. Firat, G\. Crognier, A\. F\. Gabor, C\. A\. J\. Hurkens, and Y\. ZhangColumn generation based heuristic for learning classification trees\.Computers & Operations Research116,pp\. 104866\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.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\(1\),pp\. 233–260\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Huet al\.\(2020\)H\. Hu, M\. Siala, E\. Hebrard, and M\. HuguetLearning optimal decision trees with MaxSAT and its integration in AdaBoost\.InProceedings of the Twenty\-Ninth International Joint Conference on Artificial Intelligence,pp\. 1170–1176\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Huet al\.\(2019\)X\. Hu, C\. Rudin, and M\. SeltzerOptimal sparse decision trees\.InAdvances in Neural Information Processing Systems,Vol\.32,pp\. 7265–7273\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1),[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p1.1)\.
- Huaet al\.\(2022\)K\. Hua, J\. Ren, and Y\. CaoA scalable deterministic global optimization algorithm for training optimal decision tree\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 8347–8359\.Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p1.1)\.
- Inget al\.\(2024\)D\. Ing, S\. Jabbour, L\. Sais, and F\. DelormeLAD\-based feature selection for optimal decision trees and other classifiers\.InProceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning,pp\. 867–877\.Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p3.1)\.
- Kaggle \(2011\)KaggleGive me some credit\.Note:Kaggle competition\. Available at[https://www\.kaggle\.com/c/GiveMeSomeCredit](https://www.kaggle.com/c/GiveMeSomeCredit)Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Keeganet al\.\(2025\)M\. Keegan, M\. Forbes, P\. Corry, and M\. AbolghasemiAcceleration techniques for learning optimal classification trees with integer programming\.External Links:2511\.18791,[Document](https://dx.doi.org/10.48550/arXiv.2511.18791),[Link](https://arxiv.org/abs/2511.18791)Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p1.1)\.
- Kiossou and Schaus \(2026\)H\. Kiossou and P\. SchausA generic complete anytime beam search for optimal decision tree\.InAdvances in Intelligent Data Analysis XXIV,Lecture Notes in Computer Science, Vol\.16513,pp\. 97–109\.Cited by:[§2\.3](https://arxiv.org/html/2609.05826#S2.SS3.p1.1)\.
- Linet al\.\(2020\)J\. Lin, C\. Zhong, D\. Hu, C\. Rudin, and M\. SeltzerGeneralized and scalable optimal sparse decision trees\.InProceedings of the 37th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.119,pp\. 6150–6160\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1),[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p2.1)\.
- Liuet al\.\(2024\)E\. Liu, T\. Hu, T\. T\. Allen, and C\. HermesOptimal classification trees with leaf\-branch and binary constraints\.Computers & Operations Research166,pp\. 106629\.Cited by:[§1](https://arxiv.org/html/2609.05826#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\.InProceedings of the 39th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.162,pp\. 15255–15277\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.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\.Proceedings of the AAAI Conference on Artificial Intelligence36\(9\),pp\. 9604–9613\.Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p3.1)\.
- Patelet al\.\(2024\)K\. K\. Patel, G\. Desaulniers, and A\. LodiAn improved column\-generation\-based matheuristic for learning classification trees\.Computers & Operations Research165,pp\. 106579\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Pedregosaet al\.\(2011\)F\. Pedregosa, G\. Varoquaux, A\. Gramfort, V\. Michel, B\. Thirion, O\. Grisel, M\. Blondel, P\. Prettenhofer, R\. Weiss, V\. Dubourg, J\. Vanderplas, A\. Passos, D\. Cournapeau, M\. Brucher, M\. Perrot, and É\. DuchesnayScikit\-learn: machine learning in python\.Journal of Machine Learning Research12,pp\. 2825–2830\.Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p3.1)\.
- ProPublica \(2016\)ProPublicaData and analysis for “Machine Bias”\.Note:GitHub repository\. Available at[https://github\.com/propublica/compas\-analysis](https://github.com/propublica/compas-analysis)Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Quinlan \(1986\)J\. R\. QuinlanInduction of decision trees\.Machine Learning1\(1\),pp\. 81–106\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1)\.
- Quinlan \(1993\)J\. R\. QuinlanC4\.5: programs for machine learning\.Morgan Kaufmann,San Mateo, CA\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.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.05826#S1.p1.1)\.
- Ruggieri \(2019\)S\. RuggieriComplete search for feature selection in decision trees\.Journal of Machine Learning Research20\(104\),pp\. 1–34\.Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p3.1)\.
- Schidler and Szeider \(2021\)A\. Schidler and S\. SzeiderSAT\-based decision tree learning for large data sets\.Proceedings of the AAAI Conference on Artificial Intelligence35\(5\),pp\. 3904–3912\.Cited by:[§2\.3](https://arxiv.org/html/2609.05826#S2.SS3.p1.1)\.
- Shatiet al\.\(2021\)P\. Shati, E\. Cohen, and S\. A\. McIlraithSAT\-based approach for learning optimal decision trees with non\-binary features\.In27th International Conference on Principles and Practice of Constraint Programming,Leibniz International Proceedings in Informatics, Vol\.210,pp\. 50:1–50:16\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Stracket al\.\(2014\)B\. Strack, J\. P\. DeShazo, C\. Gennings, J\. L\. Olmo, S\. Ventura, K\. J\. Cios, and J\. N\. CloreImpact of HbA1c measurement on hospital readmission rates: analysis of 70,000 clinical database patient records\.BioMed Research International2014,pp\. 781670\.Cited by:[§5\.1](https://arxiv.org/html/2609.05826#S5.SS1.p1.1)\.
- Subramanian and Sun \(2023\)S\. Subramanian and W\. SunScalable optimal multiway\-split decision trees with constraints\.Proceedings of the AAAI Conference on Artificial Intelligence37\(8\),pp\. 9891–9899\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Sullivanet al\.\(2024\)C\. Sullivan, M\. Tiwari, and S\. ThrunMAPTree: beating “optimal” decision trees with Bayesian decision trees\.Proceedings of the AAAI Conference on Artificial Intelligence38\(8\),pp\. 9019–9026\.Cited by:[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1)\.
- Tuet al\.\(2026\)J\. Tu, W\. Fan, and Z\. WuGeneralized optimal classification trees: a mixed\-integer programming approach\.External Links:2602\.02173,[Document](https://dx.doi.org/10.48550/arXiv.2602.02173),[Link](https://arxiv.org/abs/2602.02173)Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p2.1)\.
- van der Lindenet al\.\(2023\)J\. G\. M\. van der Linden, M\. M\. de Weerdt, and E\. DemirovićNecessary and sufficient conditions for optimal decision trees using dynamic programming\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 9173–9212\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1),[§1](https://arxiv.org/html/2609.05826#S1.p3.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p3.1),[§3\.2](https://arxiv.org/html/2609.05826#S3.SS2.p1.1),[Definition 1](https://arxiv.org/html/2609.05826#Thmdefinition1.p1.1)\.
- Verhaegheet al\.\(2020\)H\. Verhaeghe, S\. Nijssen, G\. Pesant, C\. Quimper, and P\. SchausLearning optimal decision trees using constraint programming\.Constraints25\(3–4\),pp\. 226–250\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1)\.
- Verwer and Zhang \(2019\)S\. Verwer and Y\. ZhangLearning optimal classification trees using a binary linear program formulation\.Proceedings of the AAAI Conference on Artificial Intelligence33\(1\),pp\. 1625–1632\.Cited by:[§1](https://arxiv.org/html/2609.05826#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05826#S2.SS1.p2.1),[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p3.1)\.
- Zhanget al\.\(2023\)R\. Zhang, R\. Xin, M\. Seltzer, and C\. RudinOptimal sparse regression trees\.Proceedings of the AAAI Conference on Artificial Intelligence37\(9\),pp\. 11270–11279\.Cited by:[§2\.2](https://arxiv.org/html/2609.05826#S2.SS2.p1.1)\.

## Appendix ABinning Sensitivity

The main experiments discretize each continuous feature using at most 100 quantile bins before cumulative binary encoding\. The value 100 is an upper bound rather than a requirement that every feature produce 100 distinct bins\. Tied values and repeated quantiles may produce fewer intervals and, consequently, fewer binary thresholds\. This resolution defines a common candidate threshold universe for all methods while limiting the threshold information removed before optimization\. The 100\-bin setting is not assumed to minimize runtime or maximize predictive accuracy\. It also serves a different purpose from the candidate capacityKK: the binning cap determines the feature universe during preprocessing, whereasKKlimits the active feature set during Adaptive STreeD\.

We examine the effect of preprocessing resolution by applying Weighted STreeD to representations constructed withB∈\{5,10,20,50,100\}B\\in\\\{5,10,20,50,100\\\}maximum quantile bins\. Adaptive candidate refinement is not used in this experiment, so the comparison isolates the effect ofBB\. We evaluate five data sets at depthsD∈\{2,3,4\}D\\in\\\{2,3,4\\\}, giving 15 configurations for each value ofBBand 75 configurations in total\. All runs use the same fixed 80/20 train–test split with random state 42\. Using a fixed split avoids variation from repeated data partitioning, but the resulting accuracy differences should be interpreted as descriptive rather than as estimates across random splits\.

Each configuration maximizes training accuracy, uses the complete depth\-based node budget, and has a nominal runtime limit of 600 seconds\. A time\-limited run contributes its best feasible incumbent when one is available\. Table[3](https://arxiv.org/html/2609.05826#A1.T3)reports the pooled results, while Figure[6](https://arxiv.org/html/2609.05826#A1.F6)separates the runtime effect by depth and the test\-accuracy effect by data set\.

Table 3:Sensitivity of Weighted STreeD to the maximum number of quantile bins- •Note\.Each row aggregates 15 successful runs \(five data sets and depthsD∈\{2,3,4\}D\\in\\\{2,3,4\\\}\) usingWeighted STreeD\. Binary\-feature counts and accuracies are means; runtimes and compression factors are medians\. “Limit share” is the fraction of runs with fit runtime at least 599 seconds\. TheD=4D=4column is the median over the five depth\-4 runs\. The bin count is a cap; repeated quantiles can yield fewer distinct thresholds\.

\(a\)Median recorded runtime by depth\.\(b\)Test\-accuracy difference relative toB=100B=100\.
Figure 6:Sensitivity to the maximum number of quantile bins\. Panel \(a\) reports the median recorded runtime over the five data sets at each depth; the dashed line marks the nominal 600\-second limit\. Panel \(b\) reports the mean test\-accuracy difference relative toB=100B=100for each data set, averaged over depths 2–4\. Positive values favor the indicated binning level\. Time\-limited runs contribute their best feasible incumbents\.Increasing the binning resolution substantially raises computational cost\. AsBBincreases from 5 to 100, the average number of binary features increases from 100\.8 to 512\.0, corresponding to a5\.1×5\.1\\timesincrease\. The pooled median recorded runtime rises from 1\.50 to 119\.71 seconds, while the depth\-4 median increases from 7\.74 to 609\.26 seconds\. The fraction of runs with a recorded runtime of at least 599 seconds increases from6\.7%6\.7\\%to33\.3%33\.3\\%\.

Recorded runtimes may slightly exceed the nominal 600\-second limit because termination checks and result collection introduce a small amount of additional time\. The largest depth\-4 observations should therefore be interpreted as censored by the computational budget rather than as uncensored runtime measurements\. Nevertheless, the measurements indicate that finer binning increases computational cost\.

Finer binning affects both sources of dynamic\-programming cost\. It creates more candidate split features and reduces the number of duplicate projected records\. The median compression ratio consequently decreases from 1\.28 atB=5B=5to 1\.01 atB=100B=100\. Increasing the preprocessing resolution therefore expands the feature search space and leaves fewer duplicate records for Weighted STreeD to aggregate\.

The predictive effect is much smaller and is not monotone\. Mean test accuracy increases by approximately 0\.50 percentage points fromB=5B=5toB=20B=20\. The pooled mean test accuracies atB=20B=20andB=100B=100are 0\.79275 and 0\.79256, respectively, corresponding to a difference of only 0\.02 percentage points in favor ofB=20B=20\. Hence, the sensitivity study does not identify 100 bins as a predictive optimum\.

Instead, the results support the intended role of Bin100 as a conservative preprocessing cap\. It preserves a relatively rich set of candidate thresholds and applies the same encoded representation to all methods\. Adaptive candidate refinement is then responsible for controlling the feature dimension considered during optimization\. A smaller cap, such asB=20B=20, provides a computationally attractive alternative and achieves similar predictive performance in this fixed\-split experiment, but it defines a coarser candidate universe and may discard thresholds before optimization\. Because the analysis uses only one train–test split, broader conclusions about the predictive effect ofBBwould require evaluation across repeated random splits\.

## Appendix BSupplementary Method Details

### B\.1Notation

Table 4:Notation used in the weighted unique\-data dynamic program\.- •Note\.The candidate set and post\-binarized feature representation remain fixed within each dynamic\-programming solve\.

### B\.2Baseline STreeD Recursion

Algorithm 2Simplified STreeD Recursion for Fixed Candidate Features1:Record set

AA, candidate features

SS, remaining depth

dd, remaining internal\-node budget

mm, cache

𝒞\\mathcal\{C\}
2:if

\(A,d,m\)∈𝒞\(A,d,m\)\\in\\mathcal\{C\}then

3:return

𝒞⁡\(A,d,m\)\\mathcal\{C\}\(A,d,m\)
4:endif

5:

C⋆←Leaf⁡\(A\)C^\{\\star\}\\leftarrow\\mathrm\{Leaf\}\(A\)
6:

T⋆←T^\{\\star\}\\leftarrowbest leaf for

AA
7:if

d=0d=0or

m=0m=0then

8:

𝒞⁡\(A,d,m\)←\(C⋆,T⋆\)\\mathcal\{C\}\(A,d,m\)\\leftarrow\(C^\{\\star\},T^\{\\star\}\)
9:return

\(C⋆,T⋆\)\(C^\{\\star\},T^\{\\star\}\)
10:endif

11:for

f∈Sf\\in Sdo

12:

A0​\(f\)←\{i∈A:xi​f=0\}A\_\{0\}\(f\)\\leftarrow\\\{i\\in A:x\_\{if\}=0\\\}
13:

A1​\(f\)←\{i∈A:xi​f=1\}A\_\{1\}\(f\)\\leftarrow\\\{i\\in A:x\_\{if\}=1\\\}
14:if

A0​\(f\)=∅A\_\{0\}\(f\)=\\emptysetor

A1​\(f\)=∅A\_\{1\}\(f\)=\\emptysetthen

15:continue

16:endif

17:for

m0=0,…,m−1m\_\{0\}=0,\\ldots,m\-1do

18:

m1←m−1−m0m\_\{1\}\\leftarrow m\-1\-m\_\{0\}
19:

\(C0,T0\)←STreeD⁡\(A0​\(f\),S,d−1,m0,𝒞\)\(C\_\{0\},T\_\{0\}\)\\leftarrow\\mathrm\{STreeD\}\(A\_\{0\}\(f\),S,d\-1,m\_\{0\},\\mathcal\{C\}\)
20:

\(C1,T1\)←STreeD⁡\(A1​\(f\),S,d−1,m1,𝒞\)\(C\_\{1\},T\_\{1\}\)\\leftarrow\\mathrm\{STreeD\}\(A\_\{1\}\(f\),S,d\-1,m\_\{1\},\\mathcal\{C\}\)
21:if

C0\+C1<C⋆C\_\{0\}\+C\_\{1\}<C^\{\\star\}then

22:

C⋆←C0\+C1C^\{\\star\}\\leftarrow C\_\{0\}\+C\_\{1\}
23:

T⋆←\(f,T0,T1\)T^\{\\star\}\\leftarrow\(f,T\_\{0\},T\_\{1\}\)
24:endif

25:endfor

26:endfor

27:

𝒞⁡\(A,d,m\)←\(C⋆,T⋆\)\\mathcal\{C\}\(A,d,m\)\\leftarrow\(C^\{\\star\},T^\{\\star\}\)
28:return

\(C⋆,T⋆\)\(C^\{\\star\},T^\{\\star\}\)

## Appendix CSupplementary Experimental Results

### C\.1Complete Candidate\-Capacity Results

Table 5:Sensitivity of Adaptive STreeD to candidate\-set capacity- •Note\.Runtime is the median \[interquartile range\] in seconds over available configurations\. Accuracies are mean±\\pmsample standard deviation\. Runtime ratios and test\-accuracy differences are computed within matched blocks relative toK=20K=20\. The reported runtime ratio is the median of within\-block ratios and is not the ratio of the pooled median runtimes\.

## Appendix DProofs

### D\.1Proof of Proposition[1](https://arxiv.org/html/2609.05826#Thmproposition1)

Consider a cached state\(A,d,m\)\(A,d,m\), wherenA=\|A\|n\_\{A\}=\|A\|\. Under the direct state\-scanning model, computing the class counts required by the best leaf costsO⁡\(\|𝒦\|​nA\)O\(\|\\mathcal\{K\}\|n\_\{A\}\)in the stated conservative accounting\. Evaluating theqqbinary candidate splits requiresO⁡\(q​nA\)O\(qn\_\{A\}\)additional work\. For each candidate split, the remaining internal\-node budget can be divided between the two child subtrees in at mostmmways, contributingO⁡\(q​m\)O\(qm\)work once the child values are available\. The total cost at the state is therefore

O⁡\(\(\|𝒦\|\+q\)​nA\+q​m\)\.O\\\!\\left\(\(\|\\mathcal\{K\}\|\+q\)n\_\{A\}\+qm\\right\)\.Summing this quantity over all states in𝒜D,M​\(S\)\\mathcal\{A\}\_\{D,M\}\(S\)gives \([3](https://arxiv.org/html/2609.05826#S3.E3)\)\.

To obtain the worst\-case bound, consider a nonredundant path of lengthℓ\\ell\. Such a path fixes at mostℓ\\elldistinct binary features and one outcome for each selected feature\. The number of possible path descriptions is therefore at most

\(qℓ\)​2ℓ\.\\binom\{q\}\{\\ell\}2^\{\\ell\}\.Summing overℓ=0,…,min⁡\{D,q\}\\ell=0,\\ldots,\\min\\\{D,q\\\}gives the path\-state boundHD​\(q\)H\_\{D\}\(q\)in \([2](https://arxiv.org/html/2609.05826#S3.E2)\)\. Including the possible remaining\-depth and remaining\-budget values gives at most

\(D\+1\)​\(M\+1\)​HD​\(q\)\(D\+1\)\(M\+1\)H\_\{D\}\(q\)cached states\. UsingnA≤nn\_\{A\}\\leq nandm≤Mm\\leq Min the per\-state cost then gives \([4](https://arxiv.org/html/2609.05826#S3.E4)\)\.

For the space bound, a bitset representing a subset of thennoriginal records requiresO⁡\(n/b\)O\(n/b\)machine words\. The remaining information stored with a state, includingdd,mm, and its dynamic\-programming value, requires constant space\. Summing over all cached states gives \([5](https://arxiv.org/html/2609.05826#S3.E5)\)\. The input feature matrix, returned trees, and auxiliary solver statistics are excluded, as stated in the proposition\.

### D\.2Proof of Proposition[2](https://arxiv.org/html/2609.05826#Thmproposition2)

For each weighted recordu∈𝒰⁡\(S\)u\\in\\mathcal\{U\}\(S\), let

𝒢u=\{i:gi​\(S\)=\(𝐳u,yu,ηu\)\}\\mathcal\{G\}\_\{u\}=\\\{i:g\_\{i\}\(S\)=\(\\mathbf\{z\}\_\{u\},y\_\{u\},\\eta\_\{u\}\)\\\}be the group of original observations represented byuu\. By construction,\|𝒢u\|=wu\|\\mathcal\{G\}\_\{u\}\|=w\_\{u\}\. Every observation in𝒢u\\mathcal\{G\}\_\{u\}has the same projected features, label, and record\-level task information\. Moreover, anyT∈𝒯⁡\(S,D,M\)T\\in\\mathcal\{T\}\(S,D,M\)uses only features inSS, so all observations in the group reach the same leaf and receive the same prediction\. Their sufficient\-statistic contributions are therefore identical; denote this common vector byϕu​\(T\)\\bm\{\\phi\}\_\{u\}\(T\)\. It follows that

∑i∈𝒢uϕi​\(T\)=wu​ϕu​\(T\)\.\\sum\_\{i\\in\\mathcal\{G\}\_\{u\}\}\\bm\{\\phi\}\_\{i\}\(T\)=w\_\{u\}\\bm\{\\phi\}\_\{u\}\(T\)\.Because the groups𝒢u\\mathcal\{G\}\_\{u\}partition the original data, summing overuugives

∑i=1nϕi​\(T\)=∑u∈𝒰⁡\(S\)wu​ϕu​\(T\)\.\\sum\_\{i=1\}^\{n\}\\bm\{\\phi\}\_\{i\}\(T\)=\\sum\_\{u\\in\\mathcal\{U\}\(S\)\}w\_\{u\}\\bm\{\\phi\}\_\{u\}\(T\)\.Thus, every feasible tree has the same task statistics under the original and weighted representations\. The feasible tree class and all tree\-only terms are also unchanged\. Applying the same, possibly nonlinear, task objective and constraints therefore gives each tree the same objective value and feasibility status in both representations\. The two fixed\-candidate problems consequently have the same optimal value and the same set of optimal trees\.

### D\.3Proof of Corollary[1](https://arxiv.org/html/2609.05826#Thmcorollary1)

For a weighted stateB⊆𝒰⁡\(S\)B\\subseteq\\mathcal\{U\}\(S\), let

A⁡\(B\)=⋃u∈B𝒢uA\(B\)=\\bigcup\_\{u\\in B\}\\mathcal\{G\}\_\{u\}be the corresponding set of original observations\. The weighted class counts inBBequal the unweighted class counts inA⁡\(B\)A\(B\)\. Therefore, the weighted leaf cost in \([8](https://arxiv.org/html/2609.05826#S3.E8)\) equals the unweighted leaf cost of the corresponding original state\.

For everyf∈Sf\\in S, the split ofBBintoB0​\(f\)B\_\{0\}\(f\)andB1​\(f\)B\_\{1\}\(f\)corresponds exactly to the split ofA⁡\(B\)A\(B\)into its original observation copies\. In particular,

A⁡\(Bj​\(f\)\)=\{i∈A⁡\(B\):xi​f=j\},j∈\{0,1\}\.A\(B\_\{j\}\(f\)\)=\\left\\\{i\\in A\(B\):x\_\{if\}=j\\right\\\},\\qquad j\\in\\\{0,1\\\}\.
The result now follows by induction on the remaining depth and node budget\. Whend=0d=0orm=0m=0, both recursions return the same leaf cost\. Ford\>0d\>0andm\>0m\>0, assume that corresponding child states have equal optimal values\. The two recursions examine the same split features and the same allocations satisfyingm0\+m1=m−1m\_\{0\}\+m\_\{1\}=m\-1\. Their child\-state values are equal by the induction hypothesis, and their leaf alternatives are also equal\. Taking the minimum over the same alternatives therefore gives the same value at the parent state\.

Aggregation\-preserving bounds and pruning rules do not change this correspondence because they are computed from the same weighted sufficient statistics\. Hence, the weighted and unweighted recursions return the same optimal misclassification count over𝒯⁡\(S,D,M\)\\mathcal\{T\}\(S,D,M\)\.

### D\.4Proof of Proposition[3](https://arxiv.org/html/2609.05826#Thmproposition3)

At a weighted state\(B,d,m\)\(B,d,m\),Weighted STreeDscansuB=\|B\|u\_\{B\}=\|B\|weighted records\. Computing weighted class counts and evaluating theqqcandidate splits require

O⁡\(\(\|𝒦\|\+q\)​uB\)O\\\!\\left\(\(\|\\mathcal\{K\}\|\+q\)u\_\{B\}\\right\)work\. Allocating the remaining internal\-node budget between the child subtrees contributesO⁡\(q​m\)O\(qm\)\. Summing the resulting per\-state cost overℬD,M​\(S\)\\mathcal\{B\}\_\{D,M\}\(S\)gives \([11](https://arxiv.org/html/2609.05826#S3.E11)\)\.

The logical path\-state bound remainsHD​\(q\)H\_\{D\}\(q\)because aggregation changes the record representation but not the candidate features or the possible feature–outcome paths\. There are therefore at most

\(D\+1\)​\(M\+1\)​HD​\(q\)\(D\+1\)\(M\+1\)H\_\{D\}\(q\)depth\- and budget\-indexed states under the conservative accounting\. UsinguB≤uSu\_\{B\}\\leq u\_\{S\}andm≤Mm\\leq Mgives \([12](https://arxiv.org/html/2609.05826#S3.E12)\)\.

For the space bound, a bitset over theuSu\_\{S\}weighted records requiresO⁡\(uS/b\)O\(u\_\{S\}/b\)machine words, and the remaining information stored with a state requires constant space\. Summing over the cached weighted states gives \([13](https://arxiv.org/html/2609.05826#S3.E13)\)\. Storage for the weighted input table, returned trees, and auxiliary solver statistics is excluded\.□\\square

### D\.5Proof of Proposition[4](https://arxiv.org/html/2609.05826#Thmproposition4)

Under the proposition’s correspondence assumption, each logical baseline state\(A,d,m\)\(A,d,m\)has a corresponding weighted state\(B,d,m\)\(B,d,m\)\. The sample\-scanning part of the baseline running time is proportional to

\(\|𝒦\|\+q\)​∑\(A,d,m\)∈𝒜D,M​\(S\)nA,\(\|\\mathcal\{K\}\|\+q\)\\sum\_\{\(A,d,m\)\\in\\mathcal\{A\}\_\{D,M\}\(S\)\}n\_\{A\},whereas the corresponding term forWeighted STreeDis proportional to

\(\|𝒦\|\+q\)​∑\(B,d,m\)∈ℬD,M​\(S\)uB\.\(\|\\mathcal\{K\}\|\+q\)\\sum\_\{\(B,d,m\)\\in\\mathcal\{B\}\_\{D,M\}\(S\)\}u\_\{B\}\.The common factor\|𝒦\|\+q\|\\mathcal\{K\}\|\+qcancels, giving exactly \([14](https://arxiv.org/html/2609.05826#S3.E14)\)\. Theq​mqmbudget\-allocation terms are not included because the proposition concerns only the sample\-scanning component\.

Suppose that the compression ratio in each pair of corresponding states is close to the root\-level ratio:

nAuB≈nuS\.\\frac\{n\_\{A\}\}\{u\_\{B\}\}\\approx\\frac\{n\}\{u\_\{S\}\}\.Equivalently,nA≈\(n/uS\)​uBn\_\{A\}\\approx\(n/u\_\{S\}\)u\_\{B\}\. Summing this relation over the corresponding states gives

∑nA≈nuS​∑uB\.\\sum n\_\{A\}\\approx\\frac\{n\}\{u\_\{S\}\}\\sum u\_\{B\}\.Substitution into \([14](https://arxiv.org/html/2609.05826#S3.E14)\) yields \([15](https://arxiv.org/html/2609.05826#S3.E15)\)\.

For bitset\-based representations, every baseline state uses a bitset over the universe ofnnoriginal records, whereas every weighted state uses a bitset over the universe ofuSu\_\{S\}weighted records\. Including constant state metadata gives the per\-state ratio

n/b\+1uS/b\+1,\\frac\{n/b\+1\}\{u\_\{S\}/b\+1\},which is \([16](https://arxiv.org/html/2609.05826#S3.E16)\)\. When bothn/bn/banduS/bu\_\{S\}/bare large, the additive constants are negligible and the ratio approachesn/uSn/u\_\{S\}\.

### D\.6Proof of Proposition[5](https://arxiv.org/html/2609.05826#Thmproposition5)

At iterationtt, apply \([12](https://arxiv.org/html/2609.05826#S3.E12)\) with candidate setEtE\_\{t\}, candidate\-set sizeqt=\|Et\|q\_\{t\}=\|E\_\{t\}\|, and weighted unique\-data sizeut=\|𝒰⁡\(Et\)\|u\_\{t\}=\|\\mathcal\{U\}\(E\_\{t\}\)\|\. This directly gives \([20](https://arxiv.org/html/2609.05826#S4.E20)\)\.

For ordinary classification with binarized candidate features, there are at most2qt2^\{q\_\{t\}\}projected feature vectors and\|𝒦\|\|\\mathcal\{K\}\|possible labels\. Hence,

ut≤min⁡\{n,\|𝒦\|​2qt\}\.u\_\{t\}\\leq\\min\\\{n,\|\\mathcal\{K\}\|2^\{q\_\{t\}\}\\\}\.Sinceqt≤Kq\_\{t\}\\leq K,

HD​\(qt\)≤HD​\(K\),ut≤min⁡\{n,\|𝒦\|​2K\}\.H\_\{D\}\(q\_\{t\}\)\\leq H\_\{D\}\(K\),\\qquad u\_\{t\}\\leq\\min\\\{n,\|\\mathcal\{K\}\|2^\{K\}\\\}\.Moreover,

\|𝒦\|\+qt≤\|𝒦\|\+K,qt​M≤K​M\.\|\\mathcal\{K\}\|\+q\_\{t\}\\leq\|\\mathcal\{K\}\|\+K,\\qquad q\_\{t\}M\\leq KM\.Substituting these inequalities into \([20](https://arxiv.org/html/2609.05826#S4.E20)\) gives the uniform bound \([21](https://arxiv.org/html/2609.05826#S4.E21)\)\.

This proposition begins afterEtE\_\{t\}and𝒰⁡\(Et\)\\mathcal\{U\}\(E\_\{t\}\)have been constructed\. It therefore does not include random\-forest or CART fitting, projection, or aggregation\. Those terms are accounted for separately in \([22](https://arxiv.org/html/2609.05826#S4.E22)\)\.

### D\.7Proof of Proposition[6](https://arxiv.org/html/2609.05826#Thmproposition6)

Let

ℬt=⋂s=1t𝒜sc\\mathcal\{B\}\_\{t\}=\\bigcap\_\{s=1\}^\{t\}\\mathcal\{A\}\_\{s\}^\{c\}be the event that the selected optimal support has not been covered during the firstttcompleted iterations\. Sinceℬt−1\\mathcal\{B\}\_\{t\-1\}isℋt−1\\mathcal\{H\}\_\{t\-1\}\-measurable,

Pr⁡\(ℬt\)\\displaystyle\\Pr\(\\mathcal\{B\}\_\{t\}\)=𝔼⁡\[𝟏ℬt−1​𝟏𝒜tc\]\\displaystyle=\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{B\}\_\{t\-1\}\}\\mathbf\{1\}\_\{\\mathcal\{A\}\_\{t\}^\{c\}\}\\right\]=𝔼⁡\[𝟏ℬt−1​Pr⁡\(𝒜tc∣ℋt−1\)\]\.\\displaystyle=\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{B\}\_\{t\-1\}\}\\Pr\\\!\\left\(\\mathcal\{A\}\_\{t\}^\{c\}\\mid\\mathcal\{H\}\_\{t\-1\}\\right\)\\right\]\.Onℬt−1\\mathcal\{B\}\_\{t\-1\}, condition \([24](https://arxiv.org/html/2609.05826#S4.E24)\) implies

Pr⁡\(𝒜tc∣ℋt−1\)≤1−ρ¯t\.\\Pr\\\!\\left\(\\mathcal\{A\}\_\{t\}^\{c\}\\mid\\mathcal\{H\}\_\{t\-1\}\\right\)\\leq 1\-\\underline\{\\rho\}\_\{t\}\.Therefore,

Pr⁡\(ℬt\)≤\(1−ρ¯t\)​Pr⁡\(ℬt−1\)\.\\Pr\(\\mathcal\{B\}\_\{t\}\)\\leq\(1\-\\underline\{\\rho\}\_\{t\}\)\\Pr\(\\mathcal\{B\}\_\{t\-1\}\)\.Iterating fromPr⁡\(ℬ0\)=1\\Pr\(\\mathcal\{B\}\_\{0\}\)=1gives

Pr⁡\(ℬN\)≤∏t=1N\(1−ρ¯t\)\.\\Pr\(\\mathcal\{B\}\_\{N\}\)\\leq\\prod\_\{t=1\}^\{N\}\(1\-\\underline\{\\rho\}\_\{t\}\)\.
OnℬNc\\mathcal\{B\}\_\{N\}^\{c\}, at least one active candidate set containsSD⋆S\_\{D\}^\{\\star\}\. The corresponding reduced tree class containsTD⋆T\_\{D\}^\{\\star\}and is a subset of the full\-feature tree class\. Its optimal score is therefore exactlyQD⋆Q\_\{D\}^\{\\star\}\. By assumption, that reduced problem is solved to certified optimality, and incumbent preservation retains the scoreQD⋆Q\_\{D\}^\{\\star\}through iterationNN\.

OnℬN\\mathcal\{B\}\_\{N\}, the baseline assumption gives

QA,NQD⋆≥r0\.\\frac\{Q\_\{A,N\}\}\{Q\_\{D\}^\{\\star\}\}\\geq r\_\{0\}\.Consequently,

𝔼⁡\[QA,NQD⋆\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\frac\{Q\_\{A,N\}\}\{Q\_\{D\}^\{\\star\}\}\\right\]≥Pr⁡\(ℬNc\)\+r0​Pr⁡\(ℬN\)\\displaystyle\\geq\\Pr\(\\mathcal\{B\}\_\{N\}^\{c\}\)\+r\_\{0\}\\Pr\(\\mathcal\{B\}\_\{N\}\)=1−\(1−r0\)​Pr⁡\(ℬN\)\\displaystyle=1\-\(1\-r\_\{0\}\)\\Pr\(\\mathcal\{B\}\_\{N\}\)≥1−\(1−r0\)​∏t=1N\(1−ρ¯t\),\\displaystyle\\geq 1\-\(1\-r\_\{0\}\)\\prod\_\{t=1\}^\{N\}\(1\-\\underline\{\\rho\}\_\{t\}\),which is \([25](https://arxiv.org/html/2609.05826#S4.E25)\)\.

### D\.8Proof of Corollary[2](https://arxiv.org/html/2609.05826#Thmcorollary2)

For training accuracy, the best constant\-leaf tree has scoreπmax\\pi\_\{\\max\}\. Algorithm[1](https://arxiv.org/html/2609.05826#alg1)initializes the incumbent with this tree and never replaces the incumbent with a worse solution\. Hence,

QA,N≥πmax\.Q\_\{A,N\}\\geq\\pi\_\{\\max\}\.SinceQD⋆≤1Q\_\{D\}^\{\\star\}\\leq 1,

QA,NQD⋆≥QA,N≥πmax\.\\frac\{Q\_\{A,N\}\}\{Q\_\{D\}^\{\\star\}\}\\geq Q\_\{A,N\}\\geq\\pi\_\{\\max\}\.Thus, the baseline condition in Proposition[6](https://arxiv.org/html/2609.05826#Thmproposition6)holds withr0=πmaxr\_\{0\}=\\pi\_\{\\max\}\. Substitution into \([25](https://arxiv.org/html/2609.05826#S4.E25)\) gives \([26](https://arxiv.org/html/2609.05826#S4.E26)\)\.

### D\.9Verification of the Algorithmic Properties

Algorithm[1](https://arxiv.org/html/2609.05826#alg1)executes at mostNmaxN\_\{\\max\}iterations because its outer loop is indexed byt=1,…,Nmaxt=1,\\ldots,N\_\{\\max\}\. Its remaining stopping conditions correspond to the explicit tests for the runtime limit, maximum score, full incumbent support, empty proposal block, and patience limit\.

The initial candidate set contains at mostKKrandom\-forest\-ranked features\. In every later iteration, CART proposes at mostK−\|C\|K\-\|C\|features, and the active set is updated asE=C∪NE=C\\cup N\. Therefore,

\|E\|≤\|C\|\+\|N\|≤K\.\|E\|\\leq\|C\|\+\|N\|\\leq K\.A feasible tree of depth at mostDDand with at mostMMinternal nodes uses no more than

min⁡\{M,2D−1\}\\min\\\{M,2^\{D\}\-1\\\}distinct split features\.

For a fixed active setEE, Proposition[2](https://arxiv.org/html/2609.05826#Thmproposition2)ensures equivalence between the weighted and expanded reduced problems whenever its preservation conditions hold\. A certifiedWeighted STreeDsolve therefore returns an optimum over𝒯⁡\(E,D,M\)\\mathcal\{T\}\(E,D,M\)\. The certificate is specific toEEand does not establish optimality over the full feature set\.

Finally, the algorithm replaces the incumbent only when

Q⁡\(T,ℐ\)\>Qinc\+ϵ\.Q\(T;\\mathcal\{I\}\)\>Q^\{\\mathrm\{inc\}\}\+\\epsilon\.Otherwise, it retains the existing incumbent\. The incumbent\-score sequence is therefore nondecreasing, and an unsuccessful inner solve does not remove the best feasible tree found previously\.