Title :
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions
Author_Institution :
Dept. of Math., Harvard Univ., Cambridge, MA, USA
Abstract :
We prove asymptotically optimal bounds on the Gaussian noise sensitivity of degree-d polynomial threshold functions. These bounds translate into optimal bounds on the Gaussian surface area of such functions, and therefore imply new bounds on the running time of agnostic learning algorithms.
Keywords :
Gaussian noise; optimisation; polynomials; Gaussian noise sensitivity; agnostic learning algorithms; degree-d polynomial threshold functions; gaussian surface area; noise sensitivity; optimal bounds; Computational complexity; Density measurement; Gaussian distribution; Gaussian noise; Gaussian processes; Mathematics; Noise measurement; Polynomials; Random variables; Switches; Gaussian noise; Polynomials;
Conference_Titel :
Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
978-1-4244-7214-7
Electronic_ISBN :
1093-0159
DOI :
10.1109/CCC.2010.27
