Abstract
Greedy decision tree induction heuristics, such as ID3, C4.5, and CART, are foundational to machine learning practice. However, their theoretical performance, particularly in noisy or "agnostic" settings, has remained poorly understood. This paper establishes the first provable guarantees for these heuristics when learning monotone Boolean functions. We demonstrate that for any monotone target, top-down induction can compete with the optimal decision tree, albeit with a quasi-polynomial increase in size. We also provide a near-matching lower bound, showing that this complexity is inherent to the agnostic setting and that previous guarantees for juntas do not extend to the agnostic or smoothed settings for general decision trees.
Introduction
Top-down decision tree learning is a cornerstone of data science. By greedily splitting data based on impurity measures like Information Gain or the Gini Index, algorithms like CART and ID3 produce interpretable and effective models. Despite their ubiquity, these heuristics are known to be "brittle." Simple functions like Parity pose a significant challenge because no single feature provides a purity gain until the entire structure is revealed.
To bridge the gap between theory and practice, researchers often focus on restricted function classes or alternative analysis models. Monotonicity—where the output is non-decreasing with respect to the inputs—is a natural constraint found in many real-world domains. While previous work provided guarantees for monotone functions in the "realizable" setting (where a perfect tree exists), this work addresses the more challenging agnostic setting, where the goal is to perform nearly as well as the best possible tree of a given size, even in the presence of noise.
Methodology
The analysis centers on the behavior of impurity-based splitting criteria. The authors' approach relies on three primary pillars:
1. Robust OSSS Inequality
The authors utilize a robust version of the O'Donnell–Saks–Schramm–Servedio (OSSS) inequality from Boolean Fourier analysis. This tool allows them to relate the "influence" of individual variables to the distance between the target function and the best small decision tree. It essentially proves that if a function is far from being well-approximated by a small tree, there must be a variable with significant influence.
2. Potential Function Analysis
To track the progress of the greedy heuristic, the authors define a potential function based on the total impurity across the leaves of the evolving tree. They prove that as long as the current tree's error is significantly higher than the optimal error (opt_s), a split exists that guarantees a substantial reduction in the potential function.
3. Extension to Real-Valued Features
While the core theory is developed for Boolean inputs, the results are extended to real-valued features and arbitrary product distributions. This is achieved by "rounding" real-valued thresholds into a high-dimensional Boolean space, demonstrating that the algorithmic guarantees are preserved under this transformation.
Key Results
The paper presents findings that characterize both the power and the fundamental limits of greedy induction:
- Algorithmic Guarantees for Monotone Targets: For any monotone function, standard top-down heuristics will construct a tree of size $s^{\tilde{O}((\log s)/\epsilon^2)}$ that achieves an error of at most $\text{opt}_s + \epsilon$. This confirms that greedy induction is a "proper" learner—it outputs an actual decision tree rather than a complex mathematical surrogate.
- The Agnostic "Tax": The authors prove that the quasi-polynomial size is not an artifact of the analysis. Any top-down heuristic must build a tree of size $s^{\Omega(\log s)}$ to achieve high accuracy in the agnostic setting, even if a much smaller tree exists.
- Failure in the Smoothed Setting: Contrary to previous conjectures, the authors show that even in the smoothed setting, greedy heuristics can fail. They construct depth-$k$ decision trees that require hypotheses of depth $2^{\Omega(k)}$ before achieving high accuracy, demonstrating that the success of these heuristics on juntas does not generalize to all decision trees.
Discussion and Limitations
This work provides a theoretical foundation for the empirical success of decision tree heuristics while identifying clear boundaries. The reliance on monotonicity is a significant constraint; while common in fields like credit scoring, it does not cover all practical use cases. Furthermore, the assumption of product distributions (independent features) is often violated in practice. Extending these guarantees to distributions with correlations remains a major open challenge in the field.
Summary updated