Agnostically learning decision trees
Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans · 2008
We give a query algorithm for agnostically learning decision trees with respect to the uniform distribution on inputs. Given black-box access to an *arbitrary* binary function f on the n-dimensional hypercube, our algorithm finds a function that agrees with f on almost (within an epsilon fraction) as many inputs as the best size-t decision tree, in time poly(n,t,1ε).