The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions |
| |
Authors: | Daniel M Kane |
| |
Affiliation: | 1. Department of Mathematics, Harvard University, Cambridge, MA, USA 2. Department of Mathematics, Stanford University, Stanford, CA, USA
|
| |
Abstract: | 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 e{\epsilon} is at most
\fracdarcsin(?{2e-e2})p{\frac{d\arcsin\left(\sqrt{2\epsilon-\epsilon^2}\right)}{\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
\fracd?{2p}{\frac{d}{\sqrt{2\pi}}} . Finally, we note that the later result implies bounds on the runtime of agnostic learning algorithms for polynomial threshold
functions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|