Popular decision tree algorithms are provably noise tolerant

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

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.

Introduction

Decision trees are the "workhorses" of interpretable machine learning. Despite the dominance of deep learning in specific domains, algorithms like CART and C4.5 remain staples in industry because they are computationally efficient, easy to interpret, and empirically successful across a wide range of tabular data. However, a significant gap has long existed between their practical utility and our theoretical understanding of their robustness.

While existing theoretical guarantees for decision trees often assume "noiseless" settings or "agnostic noise" (where only labels are corrupted), real-world data is frequently messy, with corruptions affecting both features and labels. This paper addresses this gap by providing the first formal proof that classic, greedy decision tree algorithms are inherently robust against "nasty noise"—an adversarial model where a fraction of the data is strategically corrupted to mislead the learner.

The Nasty Noise Model

In the nasty noise model, an adversary is permitted to inspect the entire dataset and then corrupt an $\eta$-fraction of the samples. This corruption can involve changing both the feature values and the labels. This is significantly more challenging than random noise or label-only noise, as the adversary can specifically target the most informative features to create spurious correlations. Until now, it was unclear if the simple greedy splitting heuristics used by ID3 or CART could survive such targeted interference.

Methodology: The Boosting Connection

The authors bridge the gap between practice and theory by viewing decision tree induction through the lens of boosting. Building on the framework established by Kearns and Mansour (1996), the paper treats the greedy splitting of nodes as a process of combining "weak" hypotheses into a "strong" learner.

Generalizing Impurity

The analysis covers a broad class of "impurity-based" algorithms. Whether an algorithm utilizes Information Gain (as in ID3 and C4.5) or the Gini Index (as in CART), the paper demonstrates that these impurity functions behave similarly under noise. By maximizing "purity gain" at each split, these algorithms effectively filter out adversarial noise without requiring specialized robust loss functions or complex regularization.

Mathematical Foundations

To establish these bounds, the authors employ tools from discrete Fourier analysis, specifically:

  • The KKL (Kahn-Kalai-Linial) Inequality: Used to bound the influence of specific features.
  • The OSSS Inequality: Helps relate the complexity of the decision tree to its error rate.

Key Results and Insights

1. Noise Tolerance Thresholds

The research identifies a specific noise tolerance threshold: $\eta \leq O(\epsilon\gamma)$. This implies that as long as the noise rate $\eta$ is proportional to the desired error $\epsilon$ and the "weak learning advantage" $\gamma$ (the ability of a single feature to perform slightly better than random guessing), the algorithm will converge to an accurate solution.

2. Tree Complexity

To achieve an error rate of $\epsilon$, the resulting tree grows to a size of $\exp(O(1/\gamma^2 \epsilon^2))$. While this exponential dependence is standard in boosting theory, it provides a concrete upper bound on the complexity required to overcome adversarial corruption.

3. The Power of Monotonicity

For monotone functions—where increasing a feature value only ever increases the probability of a positive label—the results are even stronger. The authors show that these algorithms can learn monotone trees in quasi-polynomial time ($\text{poly}(d) \cdot s^{O(\log s)}$) even in the presence of nasty noise. This represents the first practical time guarantee for this class of problems under such severe noise conditions.

4. Near-Optimality

The paper provides a lower bound confirming that these limits are nearly tight. If the noise rate $\eta$ exceeds $\Omega(\tilde{\epsilon}\gamma)$, the tree size must explode to $2^{\Omega(d)}$ to maintain accuracy. This suggests that classic greedy algorithms are performing near the theoretical limit of what is possible for any decision tree learner.

Limitations and Future Directions

While this work places individual decision trees on firm theoretical ground, several avenues for future research remain:

  • Ensemble Methods: The current proof does not formally extend to ensembles like Random Forests or Gradient Boosted Trees (e.g., XGBoost). Extending these robustness guarantees to forest-based methods is a natural next step.
  • The Weak Learning Assumption: The results rely on the existence of a $\gamma$-advantage at every node. In extremely high-dimensional or sparse data, finding such an advantage may be computationally difficult.
  • Algorithmic Refinement: Future work may investigate whether minor modifications to classic splitting criteria could further improve noise resilience, potentially pushing past the current lower bounds.

Conclusion

By proving that greedy, impurity-based splitting is a robust boosting process, this paper reconciles decades of empirical success with formal theory. It demonstrates that the simple algorithms used in everyday data science are not just heuristics, but are provably optimal learners capable of resisting sophisticated adversarial noise.

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