Decision Tree Heuristics Can Fail, Even in the Smoothed Setting

Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang TanAPPROX-RANDOM 2020 · DOI · OpenReview

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

Abstract

Greedy decision tree learning heuristics are mainstays of machine learning practice, but theoretical justification for their empirical success remains elusive. In fact, it has long been known that there are simple target functions for which they fail badly (Kearns and Mansour, STOC 1996). Recent work of Brutzkus, Daniely, and Malach (COLT 2020) considered the smoothed analysis model as a possible avenue towards resolving this disconnect. Within the smoothed setting and for targets f that are k-juntas, they showed that these heuristics successfully learn f with depth-k decision tree hypotheses. They conjectured that the same guarantee holds more generally for targets that are depth-k decision trees. We provide a counterexample to this conjecture: we construct targets that are depth-k decision trees and show that even in the smoothed setting, these heuristics build trees of depth 2^{Ω(k)} before achieving high accuracy. We also show that the guarantees of Brutzkus et al. cannot extend to the agnostic setting: there are targets that are very close to k-juntas, for which these heuristics build trees of depth 2^{Ω(k)} before achieving high accuracy.
BibTeX
@inproceedings{blanc2020decision,
  author = {Guy Blanc and Jane Lange and Mingda Qiao and Li-Yang Tan},
  title = {{Decision Tree Heuristics Can Fail, Even in the Smoothed Setting}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  doi = {10.4230/lipics.approx/random.2021.45},
}
Figure