acceptodds
Under review as a conference paper at ICLR 2027

Optimal hypersurface decision trees

Abstract

Optimal decision trees have attracted increasing attention in recent years, yet existing algorithms face two closely related challenges. First, the trees they construct have limited expressivity because their splitting rules are typically restricted to axis-parallel splits or binary features. Second, these algorithms generally scale poorly to large datasets. These challenges compound one another: more expressive splitting rules increase the combinatorial complexity of the search space, making the resulting optimal decision tree (ODT) problem even more difficult to solve. Building on the proper decision tree framework of he2025odt, we propose, to the best of our knowledge, the first algorithm for constructing optimal decision trees with hypersurface splits. The algorithm has worst-case work complexity when and fixed-dimensional feasibility tests are treated as constant-cost operations, where depends on the hypersurface polynomial degree and the data dimension . Its structure is naturally amenable to vectorization and parallelization, enabling efficient execution on GPUs, and the generic algorithm design can be used to accelerate other ODT variants, such as axis-parallel decision (ADT) trees. We further develop a safe pruning strategy that substantially reduces the number of candidate configurations and an incremental generation procedure that reduces the associated feasibility-checking cost from to . Experiments show that, for small trees, our efficient vectorized solver can explore over one million candidate trees in a matter of seconds. On both synthetic and real-world datasets, more expressive tree models consistently achieve higher predictive accuracy than approximate and optimal axis-parallel decision-tree models, often with substantially smaller tree sizes. In the most pronounced case, our model improves test accuracy by nearly 30% points relative to the optimal ADT algorithm.

Primary area:
learning theory
Keywords:
Decision trees, interpretable machine learning, optimal algorithm, empirical risk minimization

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_6y2BOpenReview ↗
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
  1. 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.

  2. 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
  1. 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 D\mathcal D, R\mathcal R, [R][\mathcal R], and DL(xs)DL(xs) 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 min⁡E\min_E 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.

  2. 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.

  3. 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.

  4. 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
  1. Does K include both the root and leaf nodes of the decision tree?

  2. It is unclear whether the branching rules are applied in the original feature space (x) or the lifted feature space (\phi_M(x)).

  3. The paper lacks sufficient details about the experimental setup, making it difficult to assess the results and their reproducibility.

  4. 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”

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

This paper studies size-constrained decision trees with hyperplane and polynomial hypersurface splits. Building on the proper decision tree framework, it proposes vectorized tree enumeration and geometric fatal-pair pruning with incremental checks. Experiments report faster evaluation of candidate configurations and improved predictive accuracy over axis-parallel trees, primarily using heuristically selected hyperplane rules.

Critical strengths
  1. The vectorized tree construction addresses a practical computational bottleneck and enables efficient batched execution. The comparisons with the recursive solver demonstrate useful speedups for processing candidate configurations.
  2. The fatal-pair criterion strengthens mutual straddling with convex-hull intersection. Under the defining-point containment condition in Eq. (5), its proof provides a sound geometric pruning certificate.
Critical weaknesses
  1. The global-optimality guarantee is not fully justified by the stated rule generation and boundary convention. Consider a one-node tree on the six points in XiX_i and XjX_j of Fig. 7, assigning a different class to each set. These points are in general position, and x=5x=5 separates them perfectly. However, every plane through three data points makes at least one error under Lemma 2's fixed boundary assignment. Thus, the stated enumeration misses the optimum for K=1K=1 unless additional boundary handling is employed. The paper should clarify this mechanism and its compatibility with Eq. (5)-based pruning.
  2. The experiments do not sufficiently distinguish the benefits of the proposed solver from those of more expressive splitting rules. Comparisons with CART and ConTree, both axis-parallel methods, cannot establish the solver's relative advantages over existing oblique-tree methods. Furthermore, systematic predictive evaluations are limited to M=1M=1, leaving the practical effectiveness and computational feasibility of higher-degree hypersurface trees insufficiently validated.
Questions for authors
  1. What precise boundary-handling procedure resolves the counterexample above, and how does it preserve exhaustive search and the validity of Eq. (5)-based pruning?
  2. Can you compare against an existing oblique-tree method under comparable tree-size and computational budgets, and provide systematic results on tractable M>1M> 1 instances to assess their predictive benefit and computational cost?
Reviewer_p9ofOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies size-constrained optimal decision trees whose splits are hyperplanes (yielding problem HDT) or degree-M polynomial hypersurfaces (yielding problem HSDT). This is different from most works on optimal decision trees, which focus on axis-parallel cuts (yielding problem ADT). The paper is based on the proper decision tree (PDT) framework by He & Little. The idea of using degree-M polynomial hypersurfaces is based on monomial lifting into a higher dimensional space such that these objects become hyperplanes. The main contributions of the paper are (1) a non-recursive parallel-executable algorithm enumerating all proper decision trees for a fixed set of K rules, (2) a so-called fatal-pair pruning rule, and (3) an efficient test reducing the number of pairwise rule tests from O(K^2) to O(K), resulting in a worst-case running time of O(K! K N^{KG+1}) for the algorithm. The developed algorithm (in fact only some heuristic versions) is then tested experimentally on both synthetic and real-world data. The algorithm is tested against variants of CART and an optimal axis-parallel DT solver, and it is shown that the new approach is superior.

JUDGMENT:

Optimal hypersurface decision trees are an interesting and very hard problem with potential for the ML community. From the technical side I liked the fatal-pair observation. My main concerns are as follows:

  1. The claim that this is the first algorithm for this problem is not justified due to the work of He & Little (2025b).
  2. The presentation of the paper should be substantially improved. The main part should be understandable without the appendix. For example, many notations and algorithmic parts are not defined in the main part.
  3. The experiments also need an improvement: the accuracy of the exact algorithm is never tested, but only a heuristic version which is sometimes worse than CART. Hence, I think in the current version, this paper is clearly below the bar for ICLR.
Critical strengths
  • The idea of using more expressive splits is interesting and could be important in practice, since it can yield much smaller trees than axis-parallel splits. Also, the parallel execution is a nice addition which is not straightforward for depth-first DP/BnB solvers

  • The modular description has the nice effect of separating the rule generation from the tree construction and another advantage is that axis-parallel DTs are a special case

  • I also found the illustrations in Figures 7 and 8 helpful to understand the ancestry relation

  • The fatal-pair pruning is a nice idea to reduce the search space

  • The synthetic study varies several parameters (tree size, N, D, label and feature noise)

Critical weaknesses
  • The presentation is hard to follow: the ODT problem is only defined by a program without specifying the objective E. I think a simple description could be: Compute a decision tree with K inner nodes, minimizing the error such that each inner node is a hyperplane cut. Moreover, 1) many notations and acronyms are undefined (or are only defined somewhere in the appendix without a reference), 2) central parts (decision regions, Algorithms 3 and 4, the heuristics) are only in the poorly organized appendix (for example appendix D is not referenced in the main part), and 3) most experimental figures are too small (Figures 4, 5, 9, 10, 11, 12).

  • If I understand the paper correctly then the developed algorithm is not evaluated itself, but rather only some heuristics. This also has the result that the trees developed by the new method sometimes perform worse than CART which itself is a heuristic and is only allowed to use axis-parallel cuts. For an example see UKM with K=2 in Table 8

  • The main technical novelty is the new pruning test, but its effect is only evaluated on sub-datasets of 8 to 10 points (lines 1548-1551)

  • I can't find a proof for Lemma 2

  • It seems a bit unfair to compare CART on the same tree size with the new approach since the new approach allows much more freedom in any cut than CART. So for an optimal version of the proposed algorithm, the performance cannot be worse for the same K; in fact, the heuristic version is sometimes even worse (see above)

  • line 174: optimal solvers for axis-parallel decision trees with a size constraint exist, for example MurTree and Witty; they would be more suitable baselines than ConTree

Questions for authors

Q1) In the introduction it is stated that big axis-parallel decision trees are hardly interpretable. Now I wonder whether even a small hypersurface decision tree is interpretable at all. Can you comment on the interpretability of such trees?

Q2) How big can the size difference between an optimal hypersurface decision tree and an optimal axis-parallel decision tree be (assuming they make the same number of errors)?

Q3) The experiments only use heuristic versions of your algorithm, so they do not show how much better optimal hypersurface trees are than optimal axis-parallel trees with the same bound on K. Can you also report results of the exact algorithm, at least on smaller datasets? Related to this: How do the authors justify the word 'optimal' in the title given that only heuristics are evaluated (this only concerns the experimental part)?

Q4) Which instances can the exact algorithm solve within a reasonable time limit of, say, one hour, that is, how many samples N and dimensions D, and which polynomial degrees M and tree sizes K do such instances have?

Q5) I am a bit confused about the following: The abstract, the conclusion and Figure 2 claim that this is the first algorithm for optimal hypersurface decision trees. But if I understand the paper correctly, then He & Little (2025b) already claim to have provided optimal algorithms for hyperplane and hypersurface splits. Could you clarify what is new compared to their work?

Q6) I am a bit worried about the fact that the heuristic version of the hyperplane algorithm is sometimes worse than CART which is only allowed to do axis-parallel cuts (see UKM in Table 8), despite the fact that the new approach has way more combinatorial options. How can such cases be explained?

COMMENTS ABOUT NOTATION (mainly that the main part is not self-contained):

  • abstract: say that N is the number of samples

  • line 74: the ODT-BF problem is only named, not defined

  • undefined acronyms: OHSDT (line 120), HDT and HSDT (line 127) are only introduced in Figure 2

  • line 145: the dataset is called xs here but \mathcal{D} in footnote 2 (line 107)

  • line 159: "spatial partitions" and "transitive ancestry relations" are unclear at this point

  • line 165: t^* should be T^*

  • line 167: sodt(xs) is not defined

  • line 253: please give a reference to the appendix where "proper" is defined

  • line 259: the sentence is broken, and the lifted dataset \phi_M(xs) is not defined in the main text

  • line 277: the definition of genDTs_vec is not self-contained: for example DL(xs) is not defined

  • line 330: decision regions are only defined in the appendix

  • line 377: the functions filter_{p_safe} and map calARM are not explained

  • line 962: rs denotes a subset of K rules here, while previously it denoted the entire set of rules

  • Table 1: D_max, D_avg and D_exp are not defined

  • Table 2: is C the number of classes? Please clarify

FURTHER COMMENTS:

  • line 69: More studies directly address the problem of computing (optimal) axis-parallel decision trees than the works by Bertsimas & Dunn, Mazumder et al. and Brita et al. cited here . Examples are: (1) MurTree (Demirović et al., 2022), which computes optimal depth- (or additionally also size)-constrained trees and handles numerical features via binarization, which yields exactly axis-parallel splits. The authors of Witty argue that thus MurTree can also be used to compute optimal size-constrained axis parallel decision trees. (2) Witty (Staus et al.), which computes minimum-size trees on non-binary data. But there optimal means 0 errors. (3) The SAT-based local improvement of Schidler & Szeider, which improves the trees computed by heuristics (this one would also fit the discussion of heuristics for large instances in line 112). They also support a size-constraint. But this is not globally optimal, but only locally optimal. Of course it can also be globally optimal if the search radius is large enough. Hence, in line 174: also these 3 solvers could be named

  • line 184: the claim that depth-first search typically exhibits poor cache locality is not substantiated and does not seem to hold for all depth-constrained solvers. For example, the specialized depth-two routine of Demirović et al. (MurTree) computes all depth-two trees from frequency counts collected in a single pass over the data

  • lines 225 and 238: please give concrete references to the theorems of He & Little

  • line 255: 'exactly D data points' only holds under the general-position assumption. I think this cannot be assumed when features are categorical.

  • line 380: Algorithms 3 and 4 are not described in the main text, only referenced

  • line 391: the sentence 'under the assumptions stated in Theorem 13, as proved in Theorem 13' is weird

  • line 825: this part is hard to follow, since many functions are introduced without intuition

  • line 1651: I think ConTree solves a different problem: it minimizes the number of errors subject to a maximum depth, but supports no size constraint. So I think MurTree with a limit on the number of nodes, which solves the same problem as the paper, would be a more appropriate baseline. Witty is also a candidate if the focus is on decision trees with 0 errors.

  • line 423 / Figure 5: for consistency with the rest of the paper, please write O(N^{KG}) instead of O(N^{DK})

  • typos: line 817 "exhuastively", line 1090 "cab"

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.