The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions
We prove asymptotically optimal bounds on the Gaussian noise sensitivity and Gaussian surface area of degree-d polynomial threshold functions. In particular, we show that for f a degree-d polynomial threshold function that the Gaussian noise sensitivity of f with parameter epsilon is at most d arcsin (root 2 epsilon-epsilon(2))/pi)/pi. This bound translates into an optimal bound on the Gaussian surface area of such functions, namely that the Gaussian surface area is at most d/root 2 pi. Finally, we note that the later result implies bounds on the runtime of agnostic learning algorithms for polynomial threshold functions.
polynomial threshold functions gaussian noise machine learning