Theory Lunch 2008-05-07

Date: 2008-05-07 12:00
Speaker: Karl Wimmer
Title: Polynomial regression under arbitrary product spaces
Place: NSH 1507


Recently, Kalai et. al gave a variant of the “Low-Degree Algorithm” for agnostic learning (learning with arbitrary classification noise) under the uniform distribution on {0,1}^n. One result of their work is an agnostic learning algorithm with respect to the class of linear threshold functions under certain restricted instance distributions, including the uniform distribution on {0,1}^n.

In this talk, we extend these ideas to product distributions on instance spaces X_1 x … X_n. We develop a variant of the “Low-Degree Algorithm” for these distributions, and we show that our algorithm agnostically learns with respect to the class of threshold functions under these distributions. We prove this by extending the “noise sensitivity method” to arbitrary product spaces, showing that threshold functions over arbitrary product spaces are no more noise sensitive than their Boolean counterparts.

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>