acceptodds
Under review as a conference paper at ICLR 2027

Loss-Guided Stochastic Exploration for Learning a Single Decision Tree

Abstract

Decision trees provide predictions through compact decision paths, but greedy construction often commits to locally optimal splits, creating a performance gap between single trees and ensembles. We introduce a loss-guided stochastic node exploration method for learning stronger single-tree structures. The method augments original features with data-derived directions, generates randomized and criterion-guided split candidates, and evaluates their downstream utility through staged search. This allows later splits to inform earlier decisions while using only one tree at inference time. Across diverse tabular classification datasets, the resulting trees outperform conventional and recent single-tree baselines, achieving state-of-the-art performance among the evaluated methods. Their mean Macro-F1 was approximately 1–2 percentage points lower than that of the tuned tree ensembles. These results suggest that improving feature representation and tree-construction search can narrow the performance gap between single trees and ensembles while retaining an explicit decision structure.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Decision Trees, Stochastic Split Search, Loss-Guided Optimization, Tabular Classification

Reviews

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

The paper grows a single classification tree by stochastic search instead of greedy induction. The search has 3 parts:

  1. Sample many complete trees, with each node using either a random split or a greedy split under a randomly chosen criterion, and score each root by the mean loss of its best sampled continuations.
  2. Fix a prefix in stages and resample the subtrees below it.
  3. Refine with a beam, where each split replacement regrows subtrees under four criteria.

The loss combines prediction performance with a leaf penalty on a held-out split, and the input is augmented with PCA and ridge directions, so splits can be oblique. The authors find that on 22 small UCI datasets the tree mostly beats single-tree baselines.

Critical strengths
  • The method is intuitive and understandable, although the authors could do a better job to make it clear by describing it at a high level before diving into a technical explanation
  • The problem of improving the performance of a decision tree with a reasonable search time is well-motivated
  • The evaluation is well-done overall
Critical weaknesses
  1. Oblique trees are compared with axis-aligned ones. Every single-tree baseline uses axis-aligned splits, while the proposed tree splits on PCA/ridge projections. The paper needs its own method without learned directions, plus oblique baselines (e.g. HHCART, TAO, DTSemNet, or ReLU+Argmin). Without that it's unclear where the gains come from.
  2. The paper makes some overclaims. Stage 3 is chosen because it has the best mean test Macro-F1 in Table 1, even though Sec. 4.2 says the stage should be picked on validation. Against single trees, only ExtraTree is beaten significantly.
  3. Interpretability is the reason to want a single tree, and it isn't measured. It would be nice to have some measurement of the number of tree nodes and some visualizations of whether the oblique trees can me interpreted at all.

Smaller note: random restarts + lookahead + refinement over complete trees is close to older stochastic tree search that isn't discussed: Bayesian CART (Chipman et al. 1998), evtree (Grubinger et al. 2014), lookahead induction (Murthy & Salzberg 1995), and MCTS for decision trees (Nunes et al. 2018). Born-again tree ensembles (Vidal & Schiffer 2020) target the same "close the gap with one tree" goal.

Questions for authors
  1. Can you report results for the method with learned directions disabled, against the same axis-aligned baselines, with the stage selected on validation?
  2. Can you show Macro-F1 vs number of leaves for all single-tree methods, and the fraction of oblique splits in the final trees?
  3. What is the wall-clock training time per dataset vs baselines?]
Reviewer_xQHwOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes to learn a single decision tree through a loss-guided stochastic search procedure. It considers both axis-aligned and hyperplane partitions at decision nodes. It first finds best bb complete trees through candidate generation, root and stage search and structural updates. These candidate splits are refined through splits. Then the best tree is selected within the beam of bb trees. Experiments are performed on 22 datasets with baselines including CART, dynamic programming decision trees and tree ensembles.

Critical strengths

None

Critical weaknesses
  • The problem being solved is not well-defined. There is no objective function stated that involve loss + regularization or constraints.
  • The proposed tree-learning algorithm is very ad-hoc. Figure 1 outlines the overview of the method. It is not clear why bb candidates are generated, how optimal they are, what is their size, etc. Then in the beam refinement step, it is not clear why the four purity criteria are used. The paper mixes balanced and imbalanced classification problems in the same domain.
  • The paper learns oblique decision trees. But it only considers PCA, ridge regression directions and other "additional directions". The search space of oblique splits is much more diverse.
  • The comparison with single trees is not apples-to-apples. None of the baselines use oblique splits.
  • The datasets used seem to be small scale datasets from UCI repository. I could not references to the dataset sources and their statistics.
  • Important baselines such as C5.0 by R. Quinlan and "Alternating optimization of decision trees, with application to learning sparse oblique trees" by M. Carreira-Perpinan and P. Tavallali are missing.
Questions for authors

No questions.

Reviewer_WJpdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a stochastic search method for learning a single decision tree. Instead of selecting splits based only on local impurity, the method evaluates complete candidate trees using a loss combining Macro-F1, Brier score, and tree complexity. It also uses learned feature directions and several stages of tree refinement. Experiments on 22 tabular datasets show improvements over existing single-tree baselines and competitive Macro-F1 compared with ensembles.

Critical strengths
  1. The idea of evaluating early splits through complete downstream trees is interesting. The method explores more possibilities than greedy construction while still producing a single tree for prediction.
  2. The evaluation covers 22 datasets overall, with comparisons against several ensemble and single-tree baselines.
Critical weaknesses
  1. It is difficult to tell how much of the improvement comes from the proposed search strategy. The method also introduces PCA, ridge-based, and other learned feature directions. Table 6 shows that feature augmentation can improve ensemble performance, but no matched comparison using the same augmented features is reported for the single-tree baselines. There is also no clear ablation separating the contributions of root assessment, staged search, and final refinement.
  2. The practical benefit is not fully convincing. The comparison with ensembles is strongly affected by Hill Valley. Without this dataset, Stage 5 achieves 78.04 Macro-F1 compared with 79.51 for the ensemble mean. The method also evaluates many candidate trees during training, but actual training and inference times are not reported. This makes the performance and computation trade-off difficult to assess.
Questions for authors
  1. How much improvement remains when the single-tree baselines use the same augmented features? It would also be helpful to isolate the gains from staged search and refinement under comparable search budgets.
  2. What are the actual training and inference times compared with the single-tree baselines? This seems important given the large number of candidate trees evaluated during training.
  3. I noticed a discrepancy in Section 4.7. Table 6 reports ensemble mean improvements of +2.07 Macro-F1 and +1.20 accuracy, while the text reports +2.47 and +1.75. The values after excluding Hill Valley also differ. Can the authors clarify these differences?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.