2009/12/14 by Kane, Daniel M.
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.0912.2709
We provide asymptotically sharp bounds for the Gaussian surface area and the Gaussian noise sensitivity of polynomial threshold functions. In particular we show that if f is a degree-d polynomial threshold function, then its Gaussian sensitivity at noise rate ε is less than some quantity asymptotic to \fracd√(2ε)π and the Gaussian surface area is at most (d)/(√(2π)). Furthermore these bounds are asymptotically tight as ε→ 0 and f the threshold function of a product of d distinct homogeneous linear functions.