CSAIL Event Calendar: Previous Series

Agnostically Learning Decision Trees

Speaker: Adam Klivans , University of Texas at Austin
Date: February 26 2008
Time: 4:15PM to 5:25PM
Location: 32-155
Host: Ronitt Rubinfeld, MIT

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.

Conceptually, our algorithm parallels recent work towards agnostically learning halfspaces due to Kalai et al. Algorithmically, it is significantly more challenging. The core of our learning algorithm is a procedure to implicitly solve a convex optimization problem over the L_1 ball in 2^n dimensions using an approximate gradient projection method.

Joint work with Parikshit Gopalan and Adam Kalai.

See other events that are part of Theory Colloquium Spring 2008

See other events happening in February 2008