Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance

Jacobus G. M. van der Linden, Daniël Vos, Mathijs Michiel de Weerdt, Sicco Verwer, Emir Demirovic

Abstract: Recently there has been a surge of interest in optimal decision tree (ODT) methods that globally optimize accuracy directly, in contrast to traditional approaches that locally optimize an impurity or information metric. However, the value of optimal methods is not well understood yet, as the literature provides conflicting results, with some demonstrating superior out-of-sample performance of ODTs over greedy approaches, while others show the opposite. Through a novel extensive experimental study, we provide new insights into the design and behavior of learning decision trees. In particular, we identify and analyze two relatively unexplored aspects of ODTs: the objective function used in training trees, and tuning techniques. Thus, we address these three questions: what objective to optimize in ODTs; how to tune ODTs; and how do optimal and greedy methods compare? Our experimental evaluation examines 11 objective functions, six tuning methods, and six claims from the literature on optimal and greedy methods on 180 real and synthetic data sets. Through our analysis, both conceptually and experimentally, we show the effect of (non-)concave objectives in greedy and optimal approaches; we highlight the importance of proper tuning of ODTs; support and refute several claims from the literature; provide clear recommendations for researchers and practitioners on the usage of greedy and optimal methods; and code for future comparisons.

Introduction

Decision trees are widely regarded as the "gold standard" for interpretable machine learning. For decades, the dominant paradigm for building these models has been greedy induction—splitting nodes one by one based on local impurity metrics like Gini or Entropy. However, the recent rise of Optimal Decision Trees (ODTs), which use global optimization to find the best possible tree for a given size, has sparked a debate. Conflicting reports in the literature have left researchers unsure whether ODTs truly outperform greedy methods or if they are prone to overfitting. This paper presents a comprehensive study of 180 datasets to provide definitive answers.

The Role of Objective Functions

A fundamental insight of this study is the relationship between the optimization method and the objective function. Greedy algorithms rely on strictly concave functions because the direct accuracy metric is piecewise linear and "flat," offering no local signal for improvement unless a split immediately changes a classification label. ODTs, by contrast, optimize the tree globally and are not restricted by this "greedy necessity."

Figure 3: Comparison of splitting criteria (left) and the geometric interpretation of split value improvement (right). Concave functions like Entropy provide a clear improvement metric for greedy splits, whereas Accuracy is piecewise linear.

The authors demonstrate that using concave proxies like Gini impurity actually degrades the performance of ODTs. Instead, non-concave objectives such as direct Accuracy or Binomial Pessimistic Error are far more effective for global optimization.

Experimental Framework and Tuning

Using the STreeD dynamic programming framework, the authors evaluated 11 objective functions and six tuning methods. Proper tuning is identified as the key to debunking the "overfitting myth" surrounding ODTs. When tuned correctly using methods like Laplace smoothing or depth constraints, ODTs show no greater sensitivity to noise than their greedy counterparts.

Figure 6: Objective value behavior across different functions relative to misclassifications (left) and leaf node size (right). The study evaluates 11 such objectives to determine the best fit for ODTs.

Key Results and Insights

The experimental results support several major claims:

  1. Superior Accuracy: ODTs achieve 1.0% to 1.3% higher out-of-sample accuracy than greedy methods for trees of depth 3 and 4.
  2. Interpretability Gains: ODTs find much smaller trees for the same level of accuracy. In one instance, an ODT with 8 leaf nodes matched the accuracy of a greedy tree with over 100 nodes.
  3. Scalability: Modern dynamic programming methods allow ODTs to handle datasets with up to 1 million instances and 150 features within reasonable timeframes, refuting the idea that ODTs are only for tiny datasets.
  4. Persistence of the Gap: The accuracy gap between optimal and greedy methods does not diminish as more data is added; in many cases, it grows as the underlying concept complexity increases.

Conclusion

This study provides a definitive revisit of decision tree induction. By identifying that concavity is a "greedy necessity" but an "optimal liability," the authors pave the way for more effective use of ODTs. For practitioners, the message is clear: ODTs offer a superior accuracy-interpretability trade-off, provided they are paired with non-concave objectives and rigorous tuning.

Summary updated

Abstract

Recently there has been a surge of interest in optimal decision tree (ODT) methods that globally optimize accuracy directly, in contrast to traditional approaches that locally optimize an impurity or information metric. However, the value of optimal methods is not well understood yet, as the literature provides conflicting results, with some demonstrating superior out-of-sample performance of ODTs over greedy approaches, while others show the opposite. Through a novel extensive experimental study, we provide new insights into the design and behavior of learning decision trees. In particular, we identify and analyze two relatively unexplored aspects of ODTs: the objective function used in training trees, and tuning techniques. Thus, we address these three questions: what objective to optimize in ODTs; how to tune ODTs; and how do optimal and greedy methods compare? Our experimental evaluation examines 11 objective functions, six tuning methods, and six claims from the literature on optimal and greedy methods on 180 real and synthetic data sets. Through our analysis, both conceptually and experimentally, we show the effect of (non-)concave objectives in greedy and optimal approaches; we highlight the importance of proper tuning of ODTs; support and refute several claims from the literature; provide clear recommendations for researchers and practitioners on the usage of greedy and optimal methods; and code for future comparisons.
BibTeX
@misc{linden2024optimal,
  author = {Jacobus G. M. van der Linden and Daniël Vos and Mathijs Michiel de Weerdt and Sicco Verwer and Emir Demirovic},
  title = {{Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance}},
  year = {2024},
  eprint = {2409.12788},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.12788},
}
Figure