pdf icon
Bounding the Sensitivity of Polynomial Threshold Functions
Received: July 16, 2012
Revised: November 11, 2013
Published: March 25, 2014
Download article from ToC site:
[PDF (306K)] [PS (1307K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: polynomial threshold function, average sensitivity
Categories: complexity theory, polynomials - multivariate, threshold, polynomial threshold, sensitivity, average sensitivity, special issue, Boolean special issue
ACM Classification: F.1.3
AMS Classification: 68Q17

Abstract: [Plain Text Version]

We give the first nontrivial upper bounds on the average sensitivity and noise sensitivity of polynomial threshold functions. More specifically, for a Boolean function $f$ on $n$ variables equal to the sign of a real, multivariate polynomial of total degree $d$, we prove

  • The average sensitivity of $f$ is at most $O(n^{1-1/(4d+6)})$. (We also give a combinatorial proof of the bound $O(n^{1-1/2^d})$.)
  • The noise sensitivity of $f$ with noise rate $\delta$ is at most $O(\delta^{1/(4d+6)})$.
Previously, only bounds for the degree $d = 1$ case were known ($O(\sqrt{n}$) and $O(\sqrt{\delta})$, for average and noise sensitivity, respectively).

We highlight some applications of our results in learning theory where our bounds immediately yield new agnostic learning algorithms and resolve an open problem of Klivans, O'Donnell and Servedio (FOCS'08).

The proof of our results use (i) the invariance principle of Mossel, O'Donnell and Oleszkiewicz (2010), (ii) the anti-concentration properties of polynomials in Gaussian space due to Carbery and Wright (2001) and (iii) new structural theorems about random restrictions of polynomial threshold functions obtained via hypercontractivity.

These structural results may be of independent interest, as they provide a generic template for transforming problems related to polynomial threshold functions defined on the Boolean hypercube to polynomial threshold functions defined in Gaussian space.

An extended abstract of this result, which was proved independently by two groups (the authors of this paper and Diakonikolas et al.) appeared in the Proc. 42nd ACM Symp. on Theory of Computing, 2010.