On the statistical query complexity of learning monotone functions
Speaker: Vitaly Feldman , IBM Almaden
Date: February 25 2010
Time: 1:30PM to 2:30PM
Location: 32-D463 STAR conf rm
Host: Scott Aaronson, CSAIL, MIT
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL: Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the unknown function instead of the random examples. I will describe two results that address the complexity of learning in the SQ model.
The first result is a new and simple characterization of the complexity of SQ learning and the second one is monotone hardness amplification for SQ learning based on O'Donnell's (2002) celebrated technique.
I'll also demonstrate how these results can be used to derive the first unconditional lower bounds for SQ learning of monotone depth-3 and depth-4 formulas.
Parts of the talk are based on a joint work with Lee and Servedio.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in February 2010
