Estimating decision tree learnability with polylogarithmic sample complexity

Neural Information Processing Systems 

We show that top-down decision tree learning heuristics (such as ID3, C4.5, and