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

Problem Statement

Decision trees (DTs) are widely used for their interpretability and ability to model non-linear relationships. However, a fundamental tension exists between greedy top-down induction (e.g., CART, C4.5) and optimal decision tree (ODT) learning. Greedy methods are computationally efficient but optimize local impurity metrics (like Gini or entropy) rather than the global target objective, potentially leading to suboptimal structures. Conversely, ODTs globally optimize an objective (typically accuracy) under size constraints but have historically been limited by NP-hard complexity, restricting their application to small datasets and shallow trees.

Previous literature presents conflicting evidence regarding the value of ODTs. Some studies claim ODTs offer 1-2% accuracy improvements over greedy methods, while others suggest greedy methods perform better or that ODTs are prone to overfitting. These contradictions often stem from inconsistent experimental setups, such as varying depth limits, lack of hyperparameter tuning, and comparisons on small-scale synthetic data. This paper addresses five open questions to resolve these conflicts using a scalable, large-scale empirical study.

Methodology

The authors conducted the largest evaluation to date, utilizing 109 real-world binary classification datasets from OpenML and various synthetic datasets (including ground-truth trees and linear separators). The study focuses on binary, axis-aligned decision trees.

Experimental Setup

• Algorithms:
  • ODT: The study employs STreeD, a dynamic programming-based algorithm capable of handling datasets with up to hundreds of thousands of instances.
  • Greedy: Standard CART implementation (scikit-learn), with custom implementations for specific objective comparisons.
• Data Preprocessing: Numeric and categorical features were binarized (using quantile thresholds and one-hot encoding) to ensure fair comparison and scalability, though experiments confirmed results hold on original numeric data.
• Evaluation Metrics:
  • Rank-based Analysis: Average test accuracy ranks across datasets, analyzed using Nemenyi critical distance tests for statistical significance.
  • New Metric: Size-Error Area Under the Curve (SE-AUC), which measures the trade-off between tree size (interpretability) and error across a range of size limits, rather than a single point estimate.
  • Structure Metrics: True Discovery Rate (TDR) and False Discovery Rate (FDR) for synthetic ground-truth comparisons.
• Hyperparameter Tuning: The study rigorously tuned both ODT and greedy methods, testing various strategies (depth, node count, complexity cost, minimum support, smoothing) to ensure fair comparisons.

Key Contributions

1. Resolution of Conflicting Literature: The paper systematically identifies that previous conflicting results were largely due to experimental design flaws, specifically the failure to tune hyperparameters and the inconsistent application of depth limits between greedy and optimal methods.
2. Scalability Demonstration: By leveraging modern dynamic programming techniques, the study demonstrates that ODTs can be trained on datasets with up to 100,000+ instances and 250 binary features, moving beyond the "toy dataset" limitations of previous ODT research.
3. Five Open Questions Addressed: The paper provides definitive answers to five specific questions regarding objectives, tuning, accuracy, data efficiency, and overfitting.

Key Results

1. Impact of Objectives (Open Question 1)

• Finding: For ODTs, directly optimizing the target objective (e.g., Accuracy) yields significantly better out-of-sample performance than optimizing traditional concave proxies like Gini impurity or Entropy.
• Contrast: For greedy methods, strictly concave objectives (Gini, Entropy) remain superior because the top-down induction heuristic requires them to function correctly.
• Implication: ODTs offer a unique advantage: the flexibility to optimize the true target metric directly without needing a proxy splitting criterion.

2. Impact of Hyperparameter Tuning (Open Question 2)

• Finding: Hyperparameter tuning is essential for ODTs to achieve high accuracy and prevent overfitting.
• Tuning Methods: While tuning the depth is the fastest approach, tuning the number of nodes, complexity cost, or smoothing parameters yields similar accuracy results. The choice of tuning method primarily affects tree size and runtime, not final accuracy.
• Implication: Un-tuned ODTs often underperform or overfit; proper tuning is a prerequisite for their success.

3. Accuracy vs. Greedy Methods (Open Question 3)

• Finding: When compared under the same depth limit, ODTs significantly outperform greedy CART (average improvement of 1.3%–1.7% for depths 3–5).
• Trade-off: If no depth limit is applied, unconstrained greedy CART can match or slightly exceed ODT accuracy but at the cost of generating trees that are orders of magnitude larger (e.g., 100+ nodes vs. 8 nodes).
• Conclusion: The primary value of ODTs is not raw accuracy in an unconstrained setting, but a superior accuracy-interpretability trade-off. They achieve high accuracy with compact, interpretable structures.

4. Data Efficiency (Open Question 4)

• Finding: The hypothesis that the gap between greedy and optimal methods diminishes with more data is refuted.
• Observation: As data increases, the differences between the two approaches actually increase rather than decrease. Unconstrained greedy trees grow significantly larger to maintain or slightly exceed accuracy, while ODTs maintain compactness. Depth-constrained greedy trees often fail to recover the optimal structure even with massive datasets, whereas ODTs succeed in finding the optimal tree within the size constraint.
• Implication: ODTs do not "catch up" to greedy methods in efficiency; rather, they maintain a distinct advantage in structural compactness and the ability to recover the true tree structure under size constraints as data scales, whereas greedy methods either fail to find the optimal structure or require exponentially larger trees to match performance.

5. Overfitting (Open Question 5)

• Finding: The claim that ODTs are more prone to overfitting is refuted, provided they are properly tuned.
• Observation: Without tuning, ODTs can overfit on small datasets. However, with proper hyperparameter tuning, ODTs are less sensitive to noise (both feature and class noise) than greedy counterparts.
• Implication: The perceived overfitting risk is a result of improper training practices, not an inherent flaw of the optimal approach.

Significance and Claims

The paper argues that the "value" of Optimal Decision Trees has been obscured by scalability limitations and inconsistent experimental practices. The authors claim that:

• ODTs are viable for practical use on large, real-world datasets when using modern dynamic programming solvers like STreeD.
• Direct optimization of the target objective is a critical advantage of ODTs over greedy methods, which are constrained by the need for concave proxy metrics.
• Proper tuning is non-negotiable; when tuned correctly, ODTs are less prone to overfitting and more robust to noise than greedy trees.
• Interpretability is the key differentiator: ODTs provide the best balance of high accuracy and small model size, making them ideal for high-stakes domains requiring human comprehensibility.

The authors conclude that for applications requiring compact, interpretable, and accurate models, particularly with noisy data or when direct optimization of non-standard objectives is required, ODTs are superior to greedy approaches. They provide a set of best practices for training and comparing these methods to guide future research and application.