Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
cs.LG
Quick verdict
Adds lossless record dedup and heuristic feature refinement atop STreeD; guarantees are cleanly scoped and ablations solid, but baselines stay narrow.
Summary
The paper attacks the scaling limits of dynamic-programming methods for optimal classification trees, building on STreeD. Two mechanisms are contributed. Weighted STreeD merges training records that become duplicates after projection onto a fixed candidate feature set into weighted representatives; the authors prove (Proposition 2) this is a lossless reformulation — same optimal value and same optimal trees — for separable tasks whose aggregation key retains all task information, and analyze how sample-dependent cost terms shrink from n to the unique-record count u_S. Adaptive STreeD wraps this in an outer heuristic loop: start from the top-K random-forest features, retain features used by the incumbent tree, propose new candidates via repeated CART fits, and re-solve reduced problems; certified optimality holds only per fixed candidate set. On five binarized public datasets (COMPAS, Diabetic, Give Me Some Credit, FICO HELOC, and Transactions with 786,363 rows), the fixed-candidate ablation shows a mean speedup of 8.20x and a maximum of 121.41x over standard STreeD, faster in 100/150 matched pairs. Adaptive STreeD cuts matched median runtime at depths 2-4 (up to a capped 34.02x) and still returns feasible trees at depths 5-7 where full-feature STreeD hits the 600-second limit, with test accuracy within about 0.2 percentage points in 67/75 matched configurations. Limitations: narrow baselines (no GOSDT/OSDT/MurTree), small statistically untested accuracy margins, and an outer search that carries no full-feature optimality guarantee.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Weighted STreeD is a lossless reformulation: for a fixed candidate feature set, merging duplicate projected records leaves the optimal value and the set of optimal trees unchanged for separable tasks (Proposition 2).
- Weighted STreeD achieves a mean speedup of 8.20× and a maximum of 121.41× over standard STreeD across 150 matched fixed-candidate runs, being faster in 100/150 pairs (Table 2).
- Adaptive STreeD reduces matched median runtime versus full-feature STreeD at depths 2–4 (ratios 1.34×/7.75×/34.02×, the last capped) and returns feasible trees in all 25 runs at each of depths 5–7 where full-feature STreeD fails within 600 seconds (Sec. 5.2).
- Under the same budget, its predictive performance is comparable to the evaluated optimal-tree baselines — training-accuracy differences ≤0.2pp in 67/75 matched configurations — and higher on Transactions at depth 4 as a finite-budget effect.
Strengths
Exemplary guarantee scoping
Secs. 1, 4, 5.1 and the conclusion repeatedly separate certified fixed-candidate optimality (Prop. 2) from the heuristic outer search; 'Infeasible' is explicitly an experimental status, and the Transactions depth-4 win is framed as a finite-budget effect, not a quality claim against certified optima.
Clean ablation isolating the lossless mechanism
Sec. 5.3 runs 150 matched pairs with identical candidate sets, depths, objectives and time limits; training misclassification is identical in 138/150, and all 12 discrepancies occur in time-limited runs — exactly what Proposition 2 predicts.
Correct and fully proved core reformulation
Transparent, reproducible experimental reporting
Honest descriptive statistics stance
Weaknesses
Narrow empirical baselines
Benefit regime is bounded and skewed
Predictive-equivalence claim rests on untested small margins
Theory-practice gap in the outer loop
Incremental novelty relative to prior row-aggregation work
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets a concrete bottleneck: STreeD-style dynamic programming for optimal classification trees scales poorly in the number of post-binarization features (up to 758 here) and training records (up to 786,363). It contributes (1) Weighted STreeD, a fixed-candidate reformulation merging records made identical by projection onto a candidate set S into weighted representatives, and (2) Adaptive STreeD, an outer loop over bounded candidate sets (initial top-K random-forest features; later incumbent support plus CART-proposed features) that rebuilds the weighted table each step. Guarantee scoping is exemplary for this literature: Proposition 2 proves the reformulation leaves the fixed-candidate optimum and the set of optimal trees unchanged for separable tasks, while Adaptive STreeD is repeatedly and explicitly labeled heuristic over the full feature space — in the abstract, Sec. 5.1 ("Infeasible … does not imply mathematical infeasibility"), and the conclusion. The Transactions depth-4 accuracy win is framed as a finite-budget effect, not evidence the certified optimum is worse. This restraint is rare and credible.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Is Weighted STreeD still an exact/optimal method?
Yes, for any fixed candidate feature set: merging training records that become duplicates after projection provably leaves the optimal value and the set of optimal trees unchanged (Proposition 2 of the paper). Adaptive STreeD's outer feature search is heuristic, so its returned tree carries no full-feature optimality guarantee — only each inner solve on its candidate set is certified.
How much faster is it than standard STreeD?
In the fixed-candidate ablation (150 matched pairs across five datasets, identical candidate sets, depths and time limits), Weighted STreeD shows a mean speedup of 8.20× and a maximum of 121.41× (on the Transactions dataset). It was faster in 100 of 150 pairs; all 50 exceptions occurred at depths 2–3, where aggregation overhead outweighs savings.
What datasets and settings were used?
Five public datasets — COMPAS (12,381 rows), Diabetes 130-US hospitals (101,766), Give Me Some Credit (150,000), FICO HELOC (10,459) and Capital One Transactions (786,363) — quantile-binned into at most 100 binary indicators per continuous feature. Default settings: candidate capacity K=20, 600-second total limit, 100-second inner-solve cap, five 80/20 train-test splits, training-accuracy objective.
Is code available for this paper?
Yes. The authors state that implementations of Adaptive STreeD and Weighted STreeD with reproducible examples are publicly available at github.com/Tommytutu/AdaptiveSTreeD, and all five datasets are public.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figure interiors (box plots in Fig. 2, curves in Figs. 3–6) are images whose plotted values cannot be read from the extracted text; figure-level judgments rely on the body text, captions and axis tick labels. No truncation detected — text runs completely through Appendix D.9.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.