Popular decision tree algorithms are provably noise tolerant

Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan

Decision trees have been a staple of machine learning since the 1980s. Algorithms like ID3, C4.5, and CART are prized for being fast, interpretable, and empirically successful. However, there has long been a gap between their practical performance and our theoretical understanding of them. This paper bridges that gap, providing the first formal proof that classic decision tree algorithms are naturally robust to "nasty noise"—adversarial corruptions affecting both features and labels.

The Problem: Surviving "Nasty" Noise

Most existing theoretical guarantees for decision trees only work in a vacuum. They typically assume that the training data is perfectly clean or that noise only affects the labels (known as agnostic noise).

In the real world, data is often "nasty." An adversary, a faulty sensor, or a systemic error might corrupt both the features and the labels simultaneously. Until this research, there was no solid mathematical proof that the simple, greedy heuristics used to build trees—specifically, picking the split that maximizes node "purity"—could survive such a hostile environment.

Methodology: Decision Trees as Boosting

To prove the robustness of these algorithms, the researchers viewed decision tree induction through the lens of boosting. In boosting, many "weak" learners (models that perform only slightly better than random guessing) are combined to create one "strong" learner.

The authors analyzed a generic algorithm called TOPDOWNDT, which captures the core top-down, greedy logic of ID3, C4.5, and CART. Their theoretical framework relies on a few key pillars:

  • Impurity Functions as Covariance: They demonstrate that standard measures of progress, such as Information Gain (Entropy) or Gini Impurity, act as proxies for the covariance between a feature and the target label.
  • Weak Learning Assumption: The analysis assumes that for any relevant subset of data, there exists at least one feature that provides a slight predictive advantage (a $\gamma$-weak learner).
  • Mathematical Lower Bounds: To establish the limits of what is possible, the researchers utilized the KKL (Kahn-Kalai-Linial) inequality from discrete Fourier analysis, which relates the influence of individual variables to the overall variance of a function.

Because this is a theoretical foundation, the paper does not rely on empirical benchmarks or specific real-world datasets. Instead, the general proofs apply to arbitrary distributions of features and labels, with specific results for monotone decision trees analyzed over independent binary features.

Key Insights and Results

The paper reveals several critical insights about why our favorite tree algorithms are tougher than we thought:

  • Greedy is Good (Enough): The core revelation is that the greedy choice—picking the split that looks best at the current node—is mathematically sufficient to filter out adversarial noise. As long as the noise rate isn't high enough to completely drown out the weak learning advantage, the algorithm will eventually uncover the correct underlying structure.
  • Provable Noise Tolerance Bound: The authors prove that if the noise rate $\eta$ is less than $O(\epsilon \gamma)$ (where $\epsilon$ is the target error and $\gamma$ is the weak learning advantage), the algorithm will succeed.
  • Near-Optimality: This analysis is nearly tight. The authors provide a lower bound showing that if the noise exceeds $\Omega(\tilde{\epsilon} \gamma)$, any impurity-based algorithm can be tricked into building an exponentially large, useless tree.
  • Efficiency in Monotone Trees: For monotone decision trees (where increasing a feature value never decreases the predicted label), these algorithms run in $poly(d) \cdot s^{O(\log s)}$ time. This significantly outperforms previous theoretical algorithms, which were far more complex and less practical.

Limitations and Future Directions

While this work places decision trees on a much firmer theoretical footing, some practical and theoretical hurdles remain.

First, the theoretical guarantees sometimes require growing very large trees—exponential in $1/\gamma^2$—to achieve high accuracy. In practice, this could lead to overfitting if not carefully managed by pruning techniques. Second, this research focuses exclusively on single trees. A natural and highly anticipated next step is to extend these noise-tolerance proofs to popular ensemble methods like Random Forests and XGBoost, which dominate modern industry applications. Finally, the authors suggest that future work could explore modifications to classic algorithms that might allow them to evade the lower bounds discovered in this paper, paving the way for even more robust iterations of CART or ID3.

Summary updated

Abstract

Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4.5, and CART, are highly noise tolerant. Our guarantees hold under the strongest noise model of nasty noise, and we provide near-matching upper and lower bounds on the allowable noise rate. We further show that these algorithms, which are simple and have long been central to everyday machine learning, enjoy provable guarantees in the noisy setting that are unmatched by existing algorithms in the theoretical literature on decision tree learning. Taken together, our results add to an ongoing line of research that seeks to place the empirical success of these practical decision tree algorithms on firm theoretical footing.
BibTeX
@inproceedings{blanc2022popular,
  author = {Guy Blanc and Jane Lange and Ali Malik and Li-Yang Tan},
  title = {{Popular decision tree algorithms are provably noise tolerant}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=BTZZ2WXXEW},
}
Figure