Agnostically learning decision trees

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ε).

Authors

• Parikshit Gopalan
• Adam Tauman Kalai
• Adam R. Klivans

Keywords

• agnostic learning
• decision trees
• learning in the presence of noise