CSAIL Event Calendar: Previous Series
Agnostically Learning Decision Trees
Speaker: Adam Klivans , University of Texas at Austin
Relevant URL: http://theory.csail.mit.edu/theory-seminars/calendar.html
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 eps fraction) as many inputs as the best size-t decision tree in time poly(n,t,1/eps). This is the first polynomial-time algorithm for learning decision trees in a harsh noise model.