The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions

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.

Saved in:
Bibliographic Details
Main Author: Kane, Daniel M
Format: Conference Proceeding
Language:English
Subjects:
Computational complexity
Density measurement
Gaussian distribution
Gaussian noise
Gaussian processes
Mathematics
Noise measurement
Polynomials
Random variables
Switches
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1093-0159
2575-8403
DOI:10.1109/CCC.2010.27