We give strengthened provable guarantees on the performance of widely employed and empirically successful top-down decision tree learning heuristics. While prior works have focused on the realizable setting, we consider the more realistic and challenging agnostic setting. We show that for all monotone functions f and s∈, these heuristics construct a decision tree of size s^Õ((log s)/^2) that achieves error <_s +, where _s denotes the error of the optimal size-s decision tree for f. Previousl…