aiqbench analysis
This large-scale study resolves conflicting literature by demonstrating that optimal decision trees directly optimizing accuracy yield smaller models and better out-of-sample performance than traditional greedy methods. The research refutes the hypothesis that these advantages diminish with increased data volume, while emphasizing that rigorous hyperparameter tuning is essential for realizing their benefits. Practitioners should adopt global optimization strategies over local impurity metrics when model size and direct objective alignment are priorities.
Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance
arXiv:2409.12788v3 Announce Type: replace 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 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.
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 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.
Machine Learning (cs.LG)
arXiv:2409.12788 [cs.LG]
(or arXiv:2409.12788v3 [cs.LG] for this version)
From: Jacobus G. M. Van Der Linden [view email] [v1] Thu, 19 Sep 2024 13:55:29 UTC (2,848 KB) [v2] Tue, 1 Apr 2025 15:35:39 UTC (4,404 KB) [v3] Thu, 6 Aug 2026 11:43:28 UTC (3,337 KB)
Full text under the publisher's open licence · 264 words
Related coverage
Notes on Algorithms
LessWrong · Jun 10, 2026
[AINews] Meta Muse Wonder & Wonder Full: MSL’s Claude 5.5-tier Frontier Model
Latent Space · Oct 13, 2026
Frontier AI Risk Report (February–March 2026)
METR · May 19, 2026
Informe de riesgos de la IA de frontera (febrero–marzo de 2026)
METR · May 19, 2026