Research map / Learning theory and algorithms / Prediction and decision losses
Near-Optimal Decision Trees in a SPLIT Second
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SPLIT, a family of optimal-then-greedy decision tree algorithms that run branch-and-bound (GOSDT-style) only up to a lookahead depth and split greedily below it, plus LicketySPLIT (polynomial-time) and RESPLIT for approximate Rashomon sets.
Problem
Globally optimal decision tree methods (branch and bound with dynamic programming) yield sparse accurate trees but scale poorly with features and depth, while greedy methods are fast but suboptimal.
Approach
Run dynamic-programming branch and bound only up to a shallow lookahead depth, fixing the bounds at that depth to the loss of a greedy subtree, then optionally post-process with optimal or recursive subtrees; greediness near the leaves costs little because optimality gaps shrink there.
Key results
- On the Bike dataset SPLIT trains in roughly 10 seconds while GOSDT runs for roughly 10^3 seconds; the paper reports over 100x speedups with negligible loss.
- RESPLIT computes bootstrapped Rashomon sets 10-20x faster than full TreeFARMS-based computation, with variable-importance correlation of 0.93-1.0 across datasets.
- Most RESPLIT trees lie in the true Rashomon set (precision 0.974 on Bike, 1.000 on COMPAS), and LicketySPLIT lies within epsilon of the Rashomon set down to about 1e-3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RESPLIT instead of computing full Rashomon sets | RID variable-importance computation · COMPAS, Spambase, Netherlands, HELOC, HIV, Bike | computation time: 152 -> 18; 2659 -> 154; 4255 -> 216; 5564 -> 337; 9273 -> 388; 14330 -> 194 | Helped |
| Use RESPLIT to approximate the full Rashomon set | RID variable-importance computation · COMPAS, Spambase, Netherlands, HELOC, HIV, Bike | Pearson correlation of variable importances: 1.0; 0.930; 0.932; 0.979; 0.959; 0.999 | No clear effect |
| Approximate the Rashomon set with RESPLIT | Rashomon-set tree generation · Bike, COMPAS, HELOC, HIV, Netherlands, Spambase | precision within Slack .01: 1.000; 1.000; 1.000; 0.984; 1.000; 0.933 | Helped |
| Increase lookahead depth (ablation) | SPLIT · Aggressively binarized datasets | regularized training loss | Mixed |
| Choose the runtime-minimizing lookahead depth (ablation) | SPLIT · Aggressively binarized datasets | regularized test loss | Helped |
| Use threshold guessing instead of full binarization (ablation) | SPLIT and LicketySPLIT · Netherlands, Covertype, HELOC, Bike | regularized training loss | No clear effect |
| Use threshold guessing instead of full binarization (ablation) | SPLIT and LicketySPLIT · Netherlands, Covertype, HELOC, Bike | runtime | Helped |
| Replace the greedy subtrees after the lookahead prefix with optimal GOSDT subtrees (ablation) | SPLIT · Training data | regularized objective | Helped |
| Replace greedy post-processing with recursive LicketySPLIT subtrees (ablation) | LicketySPLIT · Training data | regularized objective | Helped |
Surprising findings
- Test loss can be lower at the runtime-minimizing lookahead depth.
- Fully binarized features give almost no loss advantage over threshold guessing while being orders of magnitude slower.
Limitations
- Speedups are reported relative to a 1200-second GOSDT timeout, and overhead makes the method slower in the super-sparse regime.
- Optimality is relative to a binarized (threshold-guessed) dataset rather than the real-valued data.
- Rashomon set precision is low on some datasets (HIV 0.528, Spambase 0.597) without slack.
Experimental setup
Datasets: HELOC COMPAS Netherlands Covertype Adult Bike Hypothyroid Spambase Bank HIV
Benchmarks: HELOC COMPAS Netherlands Covertype Adult Bike Hypothyroid Spambase Bank HIV
Metrics: regularized test loss training time (seconds) number of leaves Pearson correlation of variable importance Rashomon set precision
Baselines: GOSDT Murtree MAPTree Top-k (DL8.5) Thompson Sampled Decision Trees (TSDT) Greedy CART TreeFARMS
Builds on: GOSDT TreeFARMS CART Threshold guessing
Closest papers by meaning
- Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.92)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.90)
- SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration (NeurIPS 2025 · similarity 0.90)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.89)
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.89)
- Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.