Beyond Impurity: Transport Margins for Geometry-Aware Decision Trees

Decision trees score a split by how many samples of each class it routes to each side. Margin classifiers score a boundary by its distance to the closest point. We show both are functionals of one object. Coupling the class-conditional feature distributions at a node by one-dimensional monotone optimal transport, we define the transport-margin profile ${\Phi }_t(r)$: the coupled class-to-class mass that crosses a candidate threshold $t$ with both endpoints at distance at least $r$. Its height at $r=0$ is exactly the Kolmogorov–Smirnov (KS) split criterion and, after balance-normalized squaring, exactly the Gini gain. Its full-survival radius recovers the hard margin, its value at every $r$ equals the certified robust balanced-accuracy advantage of the split, and its moments ${\mathcal{M}}_p$ integrate over thresholds to Wasserstein distances, with $\int {\mathcal{M}}_1(t)dt=\frac{1}{4}{W}_2^2$. We split on the radius-capped area ${\mathcal{M}}_1^R$, which interpolates between KS and the full transport margin. Sparsity of monotone transport yields an exact linear-time scan of all thresholds after sorting, at near-CART cost, with uniform consistency and contamination-stability guarantees. In forests matched in everything but the criterion, the swap costs under one point of average clean tabular accuracy, significantly improves noise robustness, exact worst-case robustness, and partition stability on real tabular data, and, on geometry-driven families, turns collapses of worst-case and shift robustness into flat curves, with no attack budget committed in advance and a polynomial-time certificate that tracks exact worst-case evaluation.