Estimating decision tree learnability with polylogarithmic sample
complexity
Estimating decision tree learnability with polylogarithmic sample
complexity
We show that top-down decision tree learning heuristics are amenable to highly efficient learnability estimation: for monotone target functions, the error of the decision tree hypothesis constructed by these heuristics can be estimated with polylogarithmically many labeled examples, exponentially smaller than the number necessary to run these heuristics, and indeed, …