CLARITree uses lookahead strategies and rank-one Cholesky updates to build near-optimal sparse piecewise linear regression trees with better scalability than prior optimal methods.
Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
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.
fields
cs.LG 2years
2026 2representative citing papers
Combinatorial optimization provides global guarantees, certificates, and explicit trade-offs for trustworthy ML tasks spanning training, explanation, fairness, robustness, compression, and privacy.
citing papers explorer
-
CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees
CLARITree uses lookahead strategies and rank-one Cholesky updates to build near-optimal sparse piecewise linear regression trees with better scalability than prior optimal methods.
-
Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives
Combinatorial optimization provides global guarantees, certificates, and explicit trade-offs for trustworthy ML tasks spanning training, explanation, fairness, robustness, compression, and privacy.