# Decision tree heuristics can fail, even in the smoothed setting

arXiv: https://arxiv.org/abs/2107.00819 · HTML: https://mlsanity.com/paper/2107.00819/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 2 Jul 2021.

## Builds on (most cited first, 7 of 7)

- [Hyperparameter Optimization: A Spectral Approach](https://mlsanity.com/paper/1706.00764/) (2017)
- [Top-down induction of decision trees: rigorous guarantees and inherent limitations](https://mlsanity.com/paper/1911.07375/) (2019)
- [Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications](https://mlsanity.com/paper/1803.06521/) (2018)
- [ID3 Learns Juntas for Smoothed Product Distributions](https://mlsanity.com/paper/1906.08654/) (2019)
- [Provable guarantees for decision tree induction: the agnostic setting](https://mlsanity.com/paper/2006.00743/) (2020)
- [Universal guarantees for decision tree induction via a higher-order splitting criterion](https://mlsanity.com/paper/2010.08633/) (2020)
- [On the Optimality of Trees Generated by ID3](https://mlsanity.com/paper/1907.05444/) (2019)

## Built on by (most cited first, 7 of 7)

- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Properly Learning Decision Trees with Queries Is NP-Hard](https://mlsanity.com/paper/2307.04093/) (2023)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)
- [Harnessing the Power of Choices in Decision Tree Learning](https://mlsanity.com/paper/2310.01551/) (2023)
- [Superfast Selection for Decision Tree Algorithms](https://mlsanity.com/paper/2405.20622/) (2024)
- [The Role of Depth, Width, and Tree Size in Expressiveness of Deep Forest](https://mlsanity.com/paper/2407.05108/) (2024)
- [Discovering Data Structures: Nearest Neighbor Search and Beyond](https://mlsanity.com/paper/2411.03253/) (2024)

## Abstract (arXiv)

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 2Omega(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 2Omega(k) before achieving high accuracy.