# Provable guarantees for decision tree induction: the agnostic setting

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2020.

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

- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [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)
- [Efficient Quantum Agnostic Improper Learning of Decision Trees](https://mlsanity.com/paper/2210.00212/) (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)

## Abstract (arXiv)

We give strengthened provable guarantees on the performance of widely employed and empirically successful sl top-down decision tree learning heuristics. While prior works have focused on the realizable setting, we consider the more realistic and challenging sl agnostic setting. We show that for all monotone functions~f and parameters s∈ mathbbN, these heuristics construct a decision tree of size s^tildeO((log s)/varepsilon2) that achieves error ≤ mathsfopts + varepsilon, where mathsfopts denotes the error of the optimal size-s decision tree for f. Previously, such a guarantee was not known to be achievable by any algorithm, even one that is not based on top-down heuristics. We complement our algorithmic guarantee with a near-matching s^tildeOmega(log s) lower bound.