Speaker: Karl Wimmer
Title: Polynomial regression under arbitrary product spaces

Abstract:
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.