Learning Monotone Functions in Polynomial Time
Speaker: Rocco Servedio , Columbia University
Date: November 8 2005
Time: 4:15PM to 5:30PM
Location: G449 Patil/Kiva
Host: Ronitt Rubinfeld, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: One of the most tantalizing open questions in computational learning
theory is the following: can monotone DNF formulas be learned in
polynomial time using uniform random examples only?
In this work we give an algorithm that learns monotone decision trees (a
weaker representation scheme than DNF formulas) to any constant accuracy
in polynomial time. Equivalently, our algorithm learns any n-variable
monotone Boolean function f to any constant accuracy, using only uniformly
distributed random examples, in time polynomial in n and in the decision
tree size of f. This is the first algorithm that can learn any monotone
Boolean function to high accuracy, using random examples only, in time
which is polynomial in a reasonable measure of the complexity of f.
A key ingredient of the result is a new upper bound showing that the
average sensitivity of any monotone function computed by a decision tree
of size s is at most \sqrt{log s}.
Joint work with Ryan O'Donnell (Microsoft).
See other events that are part of Theory Colloquium Fall 2005
See other events happening in November 2005
