The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions
复制标题
d次多项式阈值函数的高斯表面积和噪声灵敏度
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Kane
中科院分区：
文献类型：
--
作者：
D. Kane
证明了d次多项式阈值函数的高斯噪声灵敏度和高斯表面积的渐近最优界。特别地，我们证明了对于f -d次多项式阈值函数，参数为$${\epsilon}$$的f的高斯噪声灵敏度最多为$${\frac{d\arcsin\left(\sqrt{2\epsilon-\epsilon^2}\right)}{\pi}}$$。这个边界转化为这些函数的高斯表面积的最优边界，即高斯表面积最多为$${\frac{d}{\sqrt{2\pi}}}$$。最后，我们注意到后面的结果暗示了多项式阈值函数的不可知论学习算法的运行时间界限。
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 $${\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 $${\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.