Provable guarantees for decision tree induction: the agnostic setting

By Guy Blanc, Jane Lange, Li-Yang Tan. 2020

12 citations recorded by the source corpus.

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\in \mathbb{N}$, these heuristics construct a decision tree of size $s^{\tilde{O}((\log s)/\varepsilon^2)}$ that achieves error $\le \mathsf{opt}_s + \varepsilon$, where $\mathsf{opt}_s$ 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^{\tilde{\Omega}(\log s)}$ lower bound.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “Other related work includes heuristic meth-ods for multi-variate trees (Yang et al. (2019)), theoretical analysis of heuristic methods (Blanc et al. (2020)), a ﬁne-grained computational complexity study (Ordyniak and Szei-der (2021)), neural networks for decision trees (Kontschieder et al. (2015);…”