Provable guarantees for decision tree induction: the agnostic setting

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.