Certified Sparse Trees at Greedy Speed: Depth-Aware Bound Escalation

Sparse decision trees are among the few models a person can read in full and check line by line. Finding the best small tree is a hard search problem, and the solvers that guarantee optimality all run the same bounding routine at every node they visit. A bounding routine is a cheap estimate of the best score any completion of a partial tree could reach; if that estimate is already worse than a tree we hold, the branch is discarded. These solvers either finish slowly or time out. A recent heuristic avoids the problem. It searches exhaustively near the root, finishes the deeper parts of the tree greedily, and runs hundreds of times faster, but it gives up any proof that the result is optimal. This proposal joins the two. It treats the speed of the heuristic as a statement about where bounds pay off. Deep in the tree, the cheap greedy answer is usually already optimal, so a cheap lower bound plus a greedy upper bound should close the gap without expansion. Expensive, tight bounds should be saved for the shallow, large subproblems where greedy choices go wrong.

In two sentences: build an exact sparse-tree solver whose per-node bounding effort scales with how likely the cheap greedy completion is to be wrong, which depends on depth and subproblem size. The aim is optimality certificates, or explicit certified optimality gaps, at close to heuristic speed.

Core Claim

Wall-clock time in branch-and-bound search follows $T = N \cdot C_{\text{bound}} + M \cdot C_{\text{exact}}$. Here $N$ is the number of subproblems bounded, $C_{\text{bound}}$ is the cost of one bound evaluation, $M$ is the number of subproblems that survive and must be expanded, and $C_{\text{exact}}$ is the cost of expanding one. Tight bounds shrink $M$ but raise $C_{\text{bound}}$.

Near Optimal Decision Trees in a SPLIT Second documents a "greedy-at-the-leaves" effect: greedy splits are suboptimal near the root but match optimal splits deep in the tree. SPLIT exploits this by not searching deep subtrees at all. We claim the same effect can be used to cut $C_{\text{bound}}$ and $M$ without losing exactness, by attaching a certificate to every greedy completion.

For a subproblem $s$, let $\text{LB}(s)$ be an admissible lower bound on the regularized objective $\text{Loss} + \lambda \cdot \text{leaves}$ of its best subtree. Admissible means it never overestimates the best achievable score. Let $\text{UB}(s)$ be the objective of the greedy completion. If

$$\text{UB}(s) - \text{LB}(s) \le \epsilon,$$

the greedy subtree is within $\epsilon$ of optimal and $s$ never needs to be expanded. Setting $\epsilon = 0$ gives exact optimality. Setting $\epsilon > 0$ gives an anytime solver that reports a certified gap. The new part is a scheduler that decides, node by node, whether to stop at the cheapest certificate or escalate to a tighter bound. Its decisions come from online statistics on how often each bound tier closes the gap at a given depth and support size.

Relation to Prior Work

The exact solvers motivate the gap. Optimal Sparse Decision Trees (OSDT) runs depth-first branch-and-bound with analytical bounds, such as the rule that any internal node must capture at least $2\lambda$ of the data. It proves optimality on COMPAS and FICO within a 30-minute limit. Generalized and Scalable Optimal Sparse Decision Trees (GOSDT) identifies each subproblem by the exact set of training samples that reach it and propagates bounds asynchronously through dynamic programming. It maps exact accuracy-sparsity frontiers but struggles with many features and suffers memory blowup on continuous features. Branches uses best-first AND/OR search with a single "purification" bound and reaches the Mushroom optimum in 0.15 seconds where binary-encoded solvers time out, at the cost of storing the whole search graph in memory. All three apply one bounding policy uniformly across the tree. We keep their bounds and change where each one is spent.

The heuristic side supplies the observation we reuse. SPLIT reports 100x to 600x speedups over GOSDT with test loss within 1%. Its authors acknowledge that the greedy-at-the-leaves assumption can fail on some data distributions, and SPLIT offers no certificate when it does. CLARITree applies similar lookahead-plus-greedy reasoning to piecewise linear regression trees, also without bounds. Our solver should match SPLIT's behaviour where greedy is right and detect, with proof, where it is not.

The staging idea comes from outside trees. FAST filters 99.8% of time-series candidates with constant-time bounds before costlier checks. Li et al. (2025) run an expensive MaxSAT core-unlocking bound only when a fast bound fails to prune, which raised solved instances from 1,397 to 1,427 on unweighted MaxSAT Evaluation benchmarks. Several papers constrain the design by showing that tighter bounds can lose on wall-clock time: LP relaxations in Conitzer et al., Hsu et al. and Xiong and Xiao, and tighter parameterizations in Liu et al.. Those cascades are static: the same rule applies everywhere. Our escalation depends on position in the tree, which is the specific structure SPLIT exposed.

Research Program

The solver keeps GOSDT's representation, in which each subproblem is identified by the samples reaching it, and adds four bound tiers.

Tier 0 is free given the sample bit-vector. It combines OSDT's support bound with the equivalent-points bound, which charges the error that is unavoidable when identical inputs carry different labels.

Tier 1 runs a greedy completion of the subproblem to the depth limit, which yields an upper bound and a candidate subtree. The cost is roughly linear in samples times features per level.

Tier 2 is a one-split lookahead lower bound: the minimum, over all candidate splits, of the sum of the two children's Tier 0 bounds plus $\lambda$. This is tighter than Tier 0 and costs one pass over the features.

Tier 3 is full expansion, either GOSDT-style dynamic programming or Branches-style AND/OR expansion.

At each subproblem, the scheduler escalates one tier at a time and stops as soon as the gap condition holds or the node is pruned against the global incumbent. Before escalating, it compares two quantities. The first is the estimated benefit: the probability that the next tier closes the gap, times the expected cost of the expansions avoided. The second is the cost of the next tier. Probabilities are tracked as running frequencies in coarse cells indexed by depth and log support size, so the policy stays inspectable and adds negligible overhead.

We will also build the analysis tools needed to read the results. These include per-run logs of how much bound work and how many surviving subproblems each depth produced, which break $T$ down by depth. They also include a curve of certified gap against time, which makes the anytime claim measurable. A theoretical side-goal is to state the conditions under which certified greedy completions close at depth $d$, connecting SPLIT's Goldilocks lookahead depth to the point where Tier 1 alone suffices.

Baselines

The naive reference point is CART, a greedy tree learner with cost-complexity pruning, tuned over the pruning parameter to match each target leaf count. It shows how much accuracy at fixed sparsity the exact solvers buy. GOSDT and OSDT already show greedy trees lie off the optimal frontier on Monk-2, so any method that cannot beat CART on regularized objective at equal leaf count fails.

The strongest exact competitor is GOSDT, together with Branches on the categorical UCI sets where its multi-way splits apply. Both run with the same binarization, depth limit, $\lambda$ grid, single thread, memory cap and time limit as our solver. The comparison metric is time to proven optimality, and on timeout the best certified gap. Beating them means proving optimality on strictly more (dataset, $\lambda$) pairs within the limit, and being faster on the median pair both solve.

The strongest heuristic competitor is SPLIT and LicketySPLIT at the Goldilocks lookahead. SPLIT reports 100x to 600x speedups over GOSDT and test loss within 1% on its ten benchmarks, including COMPAS, HELOC and Covertype. No absolute runtimes or loss values are reported on Lacuna for GOSDT or SPLIT, so we will rerun both on identical hardware. We do not expect to beat SPLIT on raw speed. Success means landing within a small constant factor of SPLIT's runtime while certifying optimality, and finding strictly better trees on instances where SPLIT is suboptimal.

Three ablations isolate the key ingredient. A static cascade always runs Tiers 0→1→2→3 in order regardless of depth, which is the Li et al. 2025 style. A greedy-upper-bound-only variant adds the Tier 1 certificate to GOSDT with no Tier 2 and no scheduler. A depth-blind scheduler uses the same benefit rule but conditions only on support size. All ablations share the solver code, so differences reflect policy alone.

Why not just…?

Why not just run CART and post-prune? Greedy root splits cause errors that later splits cannot undo. GOSDT shows exact frontiers dominate greedy ones on Monk-2, and SPLIT shows the damage concentrates at the top of the tree. The CART baseline makes this explicit on our benchmarks. If CART matched the optimal objective at equal sparsity on most of them, the case for certification would weaken to auditing alone, and we would report that.

Why not just use LicketySPLIT and accept "near-optimal"? For many users this is the right answer, and we treat it as a real threat on speed. Its weakness is that nobody knows when it is near-optimal. Our gap-versus-time curves report SPLIT's true suboptimality on each instance. We will also add instances with parity or strongly correlated features, such as Monk-1, Monk-2 and Tic-tac-toe, where greedy-at-the-leaves should break. If SPLIT is provably optimal on essentially every instance, the contribution reduces to a cheap certificate for it, which is still useful for regulatory audits on COMPAS or FICO but is narrower.

Why not just give GOSDT a greedy upper bound at every node? This is the most dangerous alternative, because it may capture most of the gain. It is exactly our greedy-upper-bound-only ablation. If it matches the full scheduler within noise, we drop the scheduler and publish the simpler method. The scheduler earns its place only if skipping Tier 1 where it rarely closes the gap (near the root) and adding Tier 2 where it often does (mid-depth) yields a measurable reduction in $T$.

Why not just bucketize continuous features and run a discrete solver? GOSDT proves bucketization forfeits strict optimality. More to the point, bucketization changes which problem is solved, whereas our proposal changes how a fixed problem is solved. We hold binarization fixed across all methods so that this question does not confound the comparison.

Proposed Experiments

The benchmarks are COMPAS, FICO/HELOC, Covertype (about 580k rows), and the UCI categorical sets: Mushroom, Monk 1–3, Tic-tac-toe, Car-evaluation, Nursery, Balance-scale and Zoo. All are drawn from OSDT, GOSDT, Branches and SPLIT. Each runs over a $\lambda$ grid and depth limits from 3 to 6. Metrics are time to proven optimality, the fraction of runs solved within a 30-minute limit (matching OSDT's protocol), certified gap at fixed time budgets, peak memory, and regularized training objective. We also report test accuracy against leaf count to confirm all methods sit on the same frontier.

The decisive checks are three. First, the per-depth breakdown of $T$ should show the scheduler using Tier 1 certificates at depth and Tier 2 or 3 near the root. Second, the full scheduler must beat both the static cascade and the greedy-upper-bound-only GOSDT; otherwise the depth-aware idea is refuted. Third, on the adversarial parity datasets, the solver should degrade to roughly GOSDT's cost rather than below it, while exposing SPLIT's certified suboptimality. A secondary memory check compares peak memory against Branches on Covertype, because subproblems certified by greedy completion are never expanded and should never be stored.