# Top-down induction of decision trees: rigorous guarantees and inherent limitations

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2019.

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

- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Efficient Decompositional Rule Extraction for Deep Neural Networks](https://mlsanity.com/paper/2111.12628/) (2021)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)
- [Decision tree heuristics can fail, even in the smoothed setting](https://mlsanity.com/paper/2107.00819/) (2021)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)
- [Regularized impurity reduction: Accurate decision trees with complexity guarantees](https://mlsanity.com/paper/2208.10949/) (2022)
- [Harnessing the Power of Choices in Decision Tree Learning](https://mlsanity.com/paper/2310.01551/) (2023)
- [Learning stochastic decision trees](https://mlsanity.com/paper/2105.03594/) (2021)
- [Open Problem: Properly learning decision trees in polynomial time?](https://mlsanity.com/paper/2206.14431/) (2022)
- [Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules](https://mlsanity.com/paper/2503.01455/) (2025)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [Fast decision tree learning solves hard coding-theoretic problems](https://mlsanity.com/paper/2409.13096/) (2024)
- [Actively Learning Halfspaces without Synthetic Data](https://mlsanity.com/paper/2509.20848/) (2025)
- [Decision Tree Learning on Product Spaces](https://mlsanity.com/paper/2605.12983/) (2026)

## Abstract (arXiv)

Consider the following heuristic for building a decision tree for a function f : 0,1n → ± 1. Place the most influential variable xi of f at the root, and recurse on the subfunctions fxi=0 and fxi=1 on the left and right subtrees respectively; terminate once the tree is an varepsilon-approximation of f. We analyze the quality of this heuristic, obtaining near-matching upper and lower bounds: circ Upper bound: For every f with decision tree size s and every varepsilon ∈ (0,frac12), this heuristic builds a decision tree of size at most sO(log(s/varepsilon)log(1/varepsilon)). circ Lower bound: For every varepsilon ∈ (0,frac12) and s ≤ 2^tildeO(√n), there is an f with decision tree size s such that this heuristic builds a decision tree of size s^tildeOmega(log s). We also obtain upper and lower bounds for monotone functions: s^O(√log s/varepsilon) and s^tildeOmega(√[4]log s  ) respectively. The lower bound disproves conjectures of Fiat and Pechyony (2004) and Lee (2009). Our upper bounds yield new algorithms for properly learning decision trees under the uniform distribution. We show that these algorithms---which are motivated by widely employed and empirically successful top-down decision tree learning heuristics such as ID3, C4.5, and CART---achieve provable guarantees that compare favorably with those of the current fastest algorithm (Ehrenfeucht and Haussler, 1989). Our lower bounds shed new light on the limitations of these heuristics. Finally, we revisit the classic work of Ehrenfeucht and Haussler. We extend it to give the first uniform-distribution proper learning algorithm that achieves polynomial sample and memory complexity, while matching its state-of-the-art quasipolynomial runtime.