# Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance arXiv: https://arxiv.org/abs/2409.12788 ยท HTML: https://mlsanity.com/paper/2409.12788/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 28 of its 140 references that are in the map. - First posted on arXiv 19 Sep 2024. ## Builds on (most cited first, 28 of 28) - [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019) - [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014) - [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019) - [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020) - [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022) - [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019) - [OpenML-Python: an extensible Python API for OpenML](https://mlsanity.com/paper/1911.02490/) (2019) - [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020) - [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022) - [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023) - [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021) - [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020) - [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022) - [Efficient non-greedy optimization of decision trees](https://mlsanity.com/paper/1511.04056/) (2015) - [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (2021) - [Optimal Decision Trees for Nonlinear Metrics](https://mlsanity.com/paper/2009.06921/) (2020) - [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022) - [Robust Optimal Classification Trees Against Adversarial Examples](https://mlsanity.com/paper/2109.03857/) (2021) - [GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent](https://mlsanity.com/paper/2305.03515/) (2023) - [Learning Optimal Prescriptive Trees from Observational Data](https://mlsanity.com/paper/2108.13628/) (2021) - [Optimal Decision Tree Policies for Markov Decision Processes](https://mlsanity.com/paper/2301.13185/) (2023) - [Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches](https://mlsanity.com/paper/1907.02211/) (2019) - [MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees](https://mlsanity.com/paper/2309.15312/) (2023) - [Optimal Survival Trees: A Dynamic Programming Approach](https://mlsanity.com/paper/2401.04489/) (2024) - [Optimal Sparse Survival Trees](https://mlsanity.com/paper/2401.15330/) (2024) - [bsnsing: A decision tree induction method based on recursive optimal boolean rule composition](https://mlsanity.com/paper/2205.15263/) (2022) - [Interpretable Decision Trees Through MaxSAT](https://mlsanity.com/paper/2110.13854/) (2021) - [Harnessing the Power of Choices in Decision Tree Learning](https://mlsanity.com/paper/2310.01551/) (2023) ## Built on by (most cited first, 9 of 9) - [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025) - [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025) - [A Generic Complete Anytime Beam Search for Optimal Decision Tree](https://mlsanity.com/paper/2508.06064/) (2025) - [Anytime Optimal Decision Tree Learning with Continuous Features](https://mlsanity.com/paper/2601.14765/) (2026) - [Boosting Revisited: Benchmarking and Advancing LP-Based Ensemble Methods](https://mlsanity.com/paper/2507.18242/) (2025) - [An Empirical Comparison of Cost Functions in Inductive Logic Programming](https://mlsanity.com/paper/2503.07554/) (2025) - [CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees](https://mlsanity.com/paper/2606.12840/) (2026) - [Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives](https://mlsanity.com/paper/2607.07762/) (2026) - [Search Strategies for Optimal Classification and Regression Trees](https://mlsanity.com/paper/2607.28170/) (2026) ## Abstract (arXiv) 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 literature shows conflicting evidence on the value of ODTs, with some demonstrating superior out-of-sample performance of ODTs over greedy approaches, while others show the opposite. The value and performance of ODTs therefore remains one of several open question regarding ODTs, most of which could not be answered before due to lack of scalability. With our experimental study---the largest to this date---we examine five such open questions. Our results show (i) that a major advantage of ODTs over greedy approaches is that they can optimize the target objective directly (e.g., accuracy rather than a proxy such as Gini impurity); (ii) that hyperparameter tuning of ODTs is essential; and reaffirm (iii) that optimal methods, on average, obtain smaller and more accurate trees than greedy approaches. Our results also refute two previously posited hypotheses: (iv) that the difference between optimal and greedy approaches diminish with more data, and (v) that optimal methods are more sensitive to overfitting. Finally, our work provides insights on the value of ODTs, clear recommendations for researchers and practitioners on the usage of greedy and optimal methods, and code for future comparisons.