- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper studies size-constrained decision trees with hyperplane (HDT) or degree-M polynomial hypersurface (HSDT) splits. Building on the proper decision tree (PDT) framework, it proposes batched tree construction, geometric pruning of incompatible rule pairs, and incremental configuration filtering. Validation includes CPU/GPU benchmarks, pruning experiments, 50 synthetic datasets per setting, and five-fold cross-validation on 30 UCI datasets. Systematic accuracy experiments use hyperplanes (M=1 for HDT) and restricted-search heuristics.
Critical strengths
-
The authors introduce a tree-search algorithm that supports an efficient GPU execution. The solver enumerates admissible proper trees for a supplied rule configuration, with acceleration over the recursive solver. This provides a useful computational component for exhaustive search with expressive splits. Exactness is conditional on the configuration and framework assumptions.
-
A sound geometric pruning certificate within the stated proper-tree model is given. Theorem 3 combines mutual straddling with intersection of the defining-point convex hulls to certify that two rules cannot coexist in a proper tree satisfying Eq. (5). The argument holds in any dimension and extends to polynomial rules when the convex-hull test is performed in the lifted space. This certificate could be reused by other exact solvers satisfying the same assumptions, giving it value beyond this implementation.
Critical weaknesses
-
The main algorithm is difficult to understand from the main text. Although Eq. (3) specifies the overall composition, Eq. (4) uses types and constructors such as , , , and without sufficiently explicit local explanations. Definitions of candidates, rule removal, and updates_A are largely deferred to Appendix C.1, while the formal PDT axioms appear in Appendix B.2. Although and concatMapL are explained near Eq. (2), the remaining definitions are scattered. A self-contained operational description connecting rule generation, tree assembly, and loss evaluation is missing from the main text, making the algorithmic contribution difficult to assess.
-
The GPU implementation and complete training-time advantage are insufficiently established. How vectorized construction can be built is not shown? Benchmarks compare the solver against recursive search on supplied configurations; complete training-time comparisons with other popular baseline such as ConTree or OCT-H are missing.
-
Missing oblique baselines and limited hypersurface evaluation weaken the empirical contribution. All baselines are axis-parallel; oblique methods such as OC1, HHCART, TAO, OCT-H, and Zhu et al. (2020) are absent. Gains may therefore reflect split expressiveness. Moreover, systematic accuracy experiments cover only M=1, leaving the title's higher-degree hypersurface model empirically under-supported.
-
The accuracy experiments do not establish the benefit of globally optimal training. Experiments use hodtCoreset and sodtWSH, explicitly described as “not necessarily globally optimal.” Exact search within restricted candidates does not certify full-model optimality.
Questions for authors
-
Does K include both the root and leaf nodes of the decision tree?
-
It is unclear whether the branching rules are applied in the original feature space (x) or the lifted feature space (\phi_M(x)).
-
The paper lacks sufficient details about the experimental setup, making it difficult to assess the results and their reproducibility.
-
Several terms and concepts require further clarification or definition, including: Line 257: “proper decision trees”, Line 293: “13-line Haskell implementation, Lines 402–409: “the number of nested combinations”