acceptodds
Withdrawn from ICLR 2027

Beyond Impurity: Transport Margins for Geometry-Aware Decision Trees

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 : the coupled class-to-class mass that crosses a candidate threshold with both endpoints at distance at least . Its height at 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 equals the certified robust balanced-accuracy advantage of the split, and its moments integrate over thresholds to Wasserstein distances, with . We split on the radius-capped area , 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.

Primary area:
learning theory
Keywords:
Optimal Transport, Decision Trees, Robust Classification, Margin-Based Learning, Wasserstein Geometry

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_PHwtOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces the transport-margin profile, which couples the class-conditional feature distributions at a tree node using one-dimensional monotone optimal transport. The profile provides a unified view of several split notions: its value at zero recovers KS-style separation and is closely related to Gini gain, its survival radius recovers a hard-margin notion, and its values at positive radii correspond to robust balanced-accuracy advantages. The proposed transport-margin splitting (TMS) criterion integrates this profile up to a radius cap and can be evaluated for all thresholds in linear time after sorting. The paper further provides consistency/stability results and evaluates TMS through matched random-forest experiments, synthetic mechanism studies, fixed-budget robust baselines, and exact/certified worst-case robustness experiments.

Critical strengths
  1. A strong conceptual and theoretical unification. The transport-margin profile connects impurity/KS-style splitting, geometric margins, fixed-radius robustness, and Wasserstein geometry through a single object. The layer-cake and Wasserstein decomposition results make the proposed criterion more than a heuristic robustness objective.

  2. Careful validation of the proposed mechanism. The experiments largely isolate the effect of the split criterion through matched forests, include fixed-budget robust baselines and cheap alternatives, and complement average-case noise experiments with exact worst-case evaluation and certification. The paper also explicitly studies important failure regimes rather than hiding them.

Critical weaknesses
  1. The statistical treatment of the exact-robustness experiments appears inconsistent with the stated experimental unit. The appendix states that the dataset is the experimental unit, but several exact-robustness comparisons report Wilcoxon tests over individual train/test splits. Since splits from the same dataset are not independent experimental units, these p-values may be anti-conservative. The qualitative direction of the results appears strong, so this seems fixable rather than fatal.

  2. The demonstrated generality is narrower than the overall framing. Exact worst-case experiments are limited to relatively small depth-limited forests on six numeric binary datasets, and the method can degrade substantially in interaction-dominated/high-noise-feature regimes. The proposed signal-density fallback is sensible, but its empirical validation is still relatively limited. The method also currently excludes categorical features and missing values.

Questions for authors
  1. For the exact worst-case experiments, can the authors report statistical inference with the dataset, rather than individual data splits, as the experimental unit (or alternatively use an appropriate hierarchical procedure)? Does the main significance conclusion remain unchanged?

  2. How sensitive are the recommended defaults, particularly the signal-density cutoff and R=0.1R=0.1, to dataset selection? Clarifying whether these values were fixed before evaluating the corresponding held-out datasets, or providing a leave-one-dataset-out sensitivity check, would materially strengthen the claim that these are validation-free defaults.

1 comment

Thank you for the careful reading. Your summary is accurate, and both questions led to analyses that we report here.

Q1. Dataset-level inference for the exact worst-case experiments. You are right: Appendix G names the dataset as the experimental unit, and these comparisons should follow it. Recomputed with the dataset as the unit (five-split mean per dataset, six datasets):

comparisonper-dataset resultexact Wilcoxon phierarchical bootstrap 95% CI (points)
TMS − Gini, ε = 0.16 of 6 positive, mean +9.0, median +3.20.031[+1.7, +21.7]
TMS − Gini, ε = 0.056 of 6 positive, mean +2.70.031[+0.4, +6.1]
TMS − Gini, ε = 0.1, √d features6 of 6 positive, mean +12.00.031[+1.4, +31.5]
GROOT(0.1) − TMS, ε = 0.15 positive, 1 tie, mean +2.80.06[+0.6, +5.4]
augmentation − TMS, ε = 0.12 positive, 4 negative, mean 0.00.84[−1.4, +1.9]

With six datasets, 0.031 is the smallest p-value an exact test can reach. The bootstrap resamples datasets, then splits within each dataset. The main conclusion is unchanged: TMS beats the matched Gini forest on every dataset at ε = 0.05 and ε = 0.1, and the gain survives dataset-level inference. Without spambase, the mean gain at ε = 0.1 is still +3.2 points. The one change is that GROOT trained at the attack radius leads TMS at that radius with p = 0.06 instead of p < 0.001. The ties stay ties. The revised PDF reports the dataset-level tests in place of the split-level ones.

Q2. Sensitivity of the defaults to dataset selection.

Radius cap. R = 0.1 is one value used throughout, never tuned per dataset. A leave-one-dataset-out choice of R from {0.05, 0.1, 0.2} on the 19-dataset benchmark picks R = 0.2 in all 19 folds. Held-out robustness AUC rises by 0.4 points on average (the largest change on any dataset is 1.5), and the gain over Gini rises from +1.6 points (14 of 19 wins, p = 0.006) to +2.1 points (17 of 19, p = 0.0002). R = 0.05 gives +1.6 (p = 0.004). The default is conservative rather than selected, and the conclusion holds across the window. Dropping any one dataset leaves a mean gain of at least +0.95 points.

Density cutoff. The cutoff 0.1 was set on the 19 benchmark datasets and frozen before the out-of-sample checks were run: eight OpenML datasets outside the benchmark (Table 17) and six constructed interaction families. On the external datasets the rule flags the only one where TMS clearly trails (dexter, −3.4 AUC points), costs at most 1.3 points where falling back was unnecessary, and beats always using TMS by 0.5 clean and 0.4 AUC points. The decision is not knife-edge: every cutoff from 0.04 to 0.15 makes the same decision on all 19 benchmark datasets and all 24 external splits. The external check is small (three splits per dataset), so we read it as bounding the rule's cost rather than measuring its gain.

On generality. Exact verification of tree ensembles is NP-complete in general (Kantchelian et al., 2016; Chen et al., 2019b), and depth-6 forests of 20 trees are where the MILP stays exact at under a second per instance. The polynomial LP certificate is within 0.011 of the exact value at ε ≤ 0.05 for every forest tested and within 0.01 at every budget for TMS forests (Table 18), so it can carry the evaluation to larger forests. The average-case robustness study uses forests without a depth limit on all 19 datasets, and the multiclass study adds five datasets with up to ten classes. The interaction-dominated regime limits every per-feature criterion, Gini included. Proposition 5 shows that when each feature's class conditionals coincide, all such criteria sit at their uninformative value. We report this regime rather than hide it, as you note, and the density test identifies it before training. Categorical features and missing values are outside the scope we tested, as Section 4 states.

Reviewer_qDrBOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduces a new split criterion for decision trees, which combines classic accuracy-based splits with large-margin ideas. The split is derived from optimal transport. Choosing a threshold that sits in the gap between classes results in more robust trees. Additionally, the new criterion can be implemented efficiently.

Critical strengths

Decision trees are fundamental model in ML, and this paper suggest a meaningful split criterion. I think that the idea is interesting and has potential for making a good contribution.

Critical weaknesses

The most critical weakness is that it is almost impossible to understand the paper. There is not a proper introduction for the main concepts and ideas used. The paper assumes that the reader is an expert on the exact topic. Even the abstract is very technical and goes into many details. In general, there is a lot of terminology that is used without being defined properly, or if it is defined it is not in a linear order and not there is no logical structure. The experimental evaluation also is difficult to follow. I understand that a paper may have some technical ideas that require significant effort to understand, but I expect that the authors make an effort to make the paper self-contained, and that the main ideas and intuition are accessible to a wide ML/AI audience.

Additionally, there seem to be previous papers that have suggested margin-based splits and the authors do not explain convincingly the novelty of their idea. Actually, the related work section is in the Appendix, so comparison with related work and discussion is not part of the argument.

Questions for authors

I do not have concrete questions, as the convoluted and non-conventional writing does not allow understanding the paper.

1 comment

Thank you for saying that the idea is interesting and has potential. We take the readability concern seriously and answer it here with a short explanation of the idea and in the general response with a map of where each concept is defined.

The idea in plain terms. When a tree chooses a split, it counts how many samples of each class land on each side of a threshold. Two thresholds can have identical counts while one sits in a wide empty gap between the classes and the other in a crowded corridor (Figure 1). The first is robust to small input noise and the second is not, yet counting cannot tell them apart. Our criterion pairs the samples of the two classes in sorted order and measures, for each threshold, how much paired mass clears it at each distance. The area of that curve up to a cap R is the split score. It is computed exactly in one pass after sorting, so a tree built with it costs about as much as one built with Gini.

Novelty relative to margin-based splits. Margin-based splits do have a history, which Section 1 and Appendix A discuss. The difference is specific.

  • Point-margin trees (perceptron decision trees, Bennett et al., 2000; margin trees, Tibshirani & Hastie, 2007; margin optimal classification trees, D'Onofrio et al., 2024) maximize the distance to the closest sample, as an SVM does, so a single sample near the boundary decides the split.
  • Robust trees (Chen et al., 2019a; GROOT, Vos & Verwer, 2021; Vos & Verwer, 2022; Justin et al., 2023) and certified stumps (Andriushchenko & Hein, 2019) optimize robustness at one attack radius fixed before training.

Our curve contains both as special cases. Its value at a single radius is the certified balanced-accuracy advantage of the split at that radius, which is what a fixed-budget method evaluates (Theorem 2), and the radius at which it first drops is the hard margin (Theorem 5). What is new is scoring with the whole curve, which commits to no single radius. Table 1 shows why this matters. Every fixed budget fails on one of two synthetic families, because small budgets miss wide margins and large budgets refuse fine-scale structure, while the integrated criterion is in the top group on both (worst-case AUC 0.94 against 0.88 for the best fixed budget). On real data, budgets of 0.02 and 0.05 collapse to 0.23 to 0.36 exact robust accuracy on spambase at ε = 0.1, where TMS holds 0.82. The same curve also gives the KS and Gini criteria at radius zero (Theorem 1) and integrates to Wasserstein distances (Theorem 4). As Reviewer PHwt puts it, these results make the criterion "more than a heuristic robustness objective".

On related work in the appendix. The second paragraph of Section 1 makes the comparison the argument needs: each existing method sees one slice of the boundary geometry (the closest point, one radius, margins in the model's output space, or response distributions), and the profile holds all of them. The detailed survey, with 41 references, is in Appendix A because of the nine-page limit.

On the experiments. Section 3.1 checks the mechanism on synthetic data. Section 3.2 measures robustness: average-case noise on 19 datasets, fixed-budget baselines, and exact worst-case evaluation on six datasets. Section 3.3 measures clean accuracy, and Section 3.4 ablates the design. Every comparison holds everything fixed except the split criterion. The headline numbers are in the general response.

We agree that the abstract is technical, and the revised abstract keeps the same content without formulas. The revised main text also explains in words what Figure 1 shows, what the transport coupling adds and how the linear-time scan works. In one sentence: counting-based split criteria cannot see how far samples sit from a threshold, and a transport-based criterion that can see it makes forests more robust to input perturbations at almost no cost in accuracy.

Reviewer_wjUDOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper is broadly focused on connections between decision trees and margin classifiers, including optimal transport, KS split criterion and Gini gain. Beyond this, I could not determine what the paper claims to contribute.

Critical strengths

None

Critical weaknesses

The paper is not human readable in its current form:

  • Notation is not defined. There are no formal or informal definitions in the paper.
  • There is no background section. There is no stated motivation for the paper.
  • The writing places a significant and unnecessary decoding burden on the reader. Complex noun phrases are used that are not complete sentences (e.g. in the contributions section: "The transport-margin profile, with classical criteria and fixed-budget certificates as its functionals, and results that exist only for the whole curve: no orientation switching, the layer-cake identity, the hard-margin endpoint, and the capped family.")
  • There is no related work section. A large body of work has been done on theoretical connections between decision trees and margin classifiers. None of it is discussed, credited, reviewed or summarized in the main paper.
  • There does not seem to be a research question that is clearly stated.
  • Citations are placed next to textbook information.
  • The manuscript contains seven theorems, three corollaries and four propositions with no intuition, notation defined, proof sketches or proofs in the main paper.
  • There is no description of the experimental setup, datasets, how the experiments were performed, etc…
  • The goal of scientific writing is communication. The writing itself (in addition to the lack of definitions, background, related work) obscures information rather than communicating it.
Questions for authors

While there are no questions whose answers would materially affect my assessment (see weaknesses above), I do question what specific problem this paper addresses, what is the proposed solution, and what result shows that it works?

1 comment

Thank you for the review. It lists several elements it could not find in the manuscript. We first give the location of each, then answer your question and address the ethics flag. Every location can be checked in the PDF.

Where each element appears

  • "There are no formal or informal definitions in the paper." Section 2.2 opens with Definition 1 (eq. 2). Section 2.1 opens with a notation paragraph that defines the labels, the class prior, the normalized feature, the class conditionals with their CDFs and quantile functions, the Wasserstein distance and the routing map. The coupling, the crossing set, the transport margin and the capped score that TMS splits on (eq. 7) are each defined in the sentence that introduces them. The abstract defines the central object in words.
  • "There is no background section. There is no stated motivation." The first paragraph of Section 1 gives the motivation with a concrete case (Figure 1): two features with identical counts, KS statistic and Gini gain whose boundaries differ sharply in robustness. The question the paper answers follows from it: can a split criterion see this geometry at close to the cost of counting, with comparable statistical guarantees? Section 2.1 gives the background. It shows how CART and KS score a split and proves that no count-based criterion can see the difference (Proposition 1).
  • "There is no related work section ... None of it is discussed in the main paper." The second paragraph of Section 1 places the work against hard-margin and margin-tree methods, robust tree learning, certified stumps, the margin theory of boosting and transport-based forests (more than 20 works cited in Section 1). Appendix A is a dedicated related-work section with 41 references, placed there because of the nine-page limit.
  • "There is no description of the experimental setup, datasets ..." Section 3 opens with the protocol. Section 3.3 states how the 19 benchmark datasets were selected (a mechanical filter on OpenML-CC18). Appendix G gives the data-generating processes, OpenML IDs, hyperparameters, noise models, normalizations, statistical tests and the MILP setup.
  • "... no intuition ... or proofs in the main paper." Each result is followed by what it means, and Figure 2 marks four of them on one curve. Proofs are in Appendix B, as stated at the end of Section 2.1.
  • Citations next to textbook facts. We cite standard facts to their original sources so that readers can trace them.
  • The contribution list. The revision writes it in full sentences. In short: we define one curve that contains the classical split criteria and fixed-budget robustness certificates as special cases, and prove properties that only the whole curve has. We show that integrating it over thresholds decomposes Wasserstein distances. We give an exact linear-time algorithm with statistical guarantees and test it in forests that differ only in the split criterion.

Your question: problem, solution, evidence. Trees choose splits by counting samples on each side of a threshold, so a split that leaves a wide margin and one that leaves almost none can score the same. We score a split by how much paired opposite-class mass clears the threshold at every distance up to a cap, computed exactly in linear time after sorting. In forests matched in everything else, this costs 0.6 points of clean accuracy on 19 datasets, raises noise robustness on 14 of them (p = 0.006), and raises exact worst-case robust accuracy on all six datasets tested (+9.0 points on average, 0.44 to 0.82 on spambase). The general response gives more detail.

The ethics flag. The review notes that this concern cannot be verified, and the reasons it gives are the points answered above. Our use of generative AI is disclosed in the AI use statement and on the submission form, as ICLR 2027 policy requires. The policy permits this use when the authors review the work and take responsibility for it, and we have done both. Every formal result has a complete proof in Appendix B.

We accept that the paper is dense. It fits a theory and an experimental study into nine pages and assumes familiarity with tree induction and one-dimensional optimal transport. Reviewer PHwt summarized the contribution accurately and called it "a strong conceptual and theoretical unification". Density is a fair comment on style, and the revision addresses it in the abstract, with explanations added throughout the main text, and with a notation table. We hope the locations above also show that the manuscript was written and checked with care.

Comments on the paper

1 comment

Two reviews found the paper hard to follow, so we begin with a plain summary and a map of where each concept is defined. Reviewer PHwt's questions led to two new analyses, summarized with the revision at the end. Both confirm the main conclusions.

The problem. A decision tree chooses each split by counting how many samples of each class fall on each side of a threshold. Counting cannot see how far the samples sit from the threshold. Figure 1 shows two features with the same counts, the same Kolmogorov-Smirnov (KS) statistic and the same Gini gain. One separates the classes across a crowded corridor, the other across a wide empty gap, so small input noise flips many predictions on the first and none on the second. Proposition 1 proves that every criterion computed from the counts alone has this blind spot.

The idea. At a node, pair the samples of the two classes in sorted order (one-dimensional optimal transport) and ask, for each threshold t and each distance r, how much paired mass crosses t with both ends at least r away. This curve, the transport-margin profile (Definition 1), contains the familiar criteria as special readings. At r = 0 it is the KS criterion, and after squaring and balance normalization it is the Gini gain (Theorem 1). At a single r it equals the certified balanced-accuracy advantage of the split under perturbations of size r, which is what a fixed-budget method evaluates (Theorem 2). The radius at which the curve first drops is the hard margin (Theorem 5). Our criterion, TMS, scores a split by the area under the curve up to a cap R. It rewards wide gaps without committing to one attack budget, and one sort plus one linear pass scores every threshold exactly, at close to the cost of Gini (Proposition 2).

The evidence. All forests are matched in everything except the split criterion. On 19 OpenML datasets the swap costs 0.6 points of clean accuracy (95% CI [−1.4, 0.0], no significant difference) and raises the area under the accuracy-versus-noise curve on 14 of them (p = 0.006). Under exact worst-case evaluation by a mixed-integer program on six datasets, it raises robust accuracy on all six at ε = 0.1, by 9.0 points on average and from 0.44 to 0.82 on spambase. Against fixed-budget methods (the certified-stump objective and GROOT), every fixed budget fails on one of two synthetic families, while TMS is in the top group on both (Table 1).

Where things are. Notation: first paragraph of Section 2.1 and the table that opens the appendix. Central object: Definition 1. Meaning of each result: the sentences after it, and Figure 2, which marks four of them on one curve. Proofs: Appendix B. Related work: second paragraph of Section 1 and Appendix A. Protocols, datasets and hyperparameters: first paragraph of Section 3 and Appendix G.

Summary of the revision. We have uploaded a revised PDF with the following changes.

  • Dataset-level inference (PHwt, Q1). Section 3.2, Appendix F and Appendix G now test the six-dataset exact comparisons with the dataset as the unit. TMS beats the matched Gini forest on 6 of 6 datasets at ε = 0.05 and ε = 0.1 (exact Wilcoxon p = 0.031, hierarchical bootstrap 95% CI [+1.7, +21.7] points at ε = 0.1). The split-level tests are gone.
  • Sensitivity of the defaults (PHwt, Q2). Appendix F adds the leave-one-dataset-out choice of R, which picks R = 0.2 in all 19 folds and raises the gain over Gini from +1.6 to +2.1 AUC points. It also shows that every density cutoff from 0.04 to 0.15 makes the same decisions on all benchmark datasets and external splits, and states that the cutoff was frozen before the out-of-sample checks.
  • Scope of the exact evaluation (PHwt). Section 4 now says why the exact evaluation covers forests of 20 depth-6 trees and what certifies larger ones.
  • Readability (wjUD, qDrB). The abstract keeps its content without the formulas. Section 1 states the research question explicitly, lists the contributions as full sentences, and adds margin trees to the positioning paragraph. Where the text was terse, it now explains in words what Figure 1 shows, what the coupling adds beyond the CDF formula, how the linear-time scan works and what the guarantees mean, with a worked example for Theorem 2, and the conclusion answers the research question directly. A notation table, giving the place each symbol is defined, now opens the appendix.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.