We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-d polynomial threshold functions (PTFs). These bounds hold both for PTFs over the Boolean hypercube {-1, 1}n and for PTFs over Rn under the standard n-dimensional Gaussian distribution. Our bound on the Boolean average sensitivity of PTFs represents progress towards the resolution of a conjecture of Gotsman and Linial \cite{GL:94}, which states that the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d PTFs. Via the L1 polynomial regression algorithm of Kalai et al. \cite{KKMS:08}, our bounds on Gaussian and Boolean noise sensitivity yield polynomial-time agnostic learning algorithms for the broad class of constant-degree PTFs under these input distributions.
Our bounds on both average and noise sensitivity of PTFs in the Gaussian setting are obtained using fairly simple arguments; the main ingredients are tail bounds and anti-concentration bounds on low-degree polynomials in Gaussian random variables \cite{Janson:97,CW:01}. To obtain our bound on the Boolean average sensitivity of PTFs, we generalize the .critical-index. machinery of \cite{Servedio:07cc} (which in that work applies to halfspaces, i.e. degree-1 PTFs) to general PTFs. Together with the .invariance principle. of \cite{MOO:05}, this lets us extend our techniques from the Gaussian setting to the Boolean setting. Our bound on Boolean noise sensitivity is achieved via a simple reduction from upper bounds on average sensitivity of Boolean PTFs to corresponding bounds on noise sensitivity.
Note: The STOC version of this paper is a merger of independent works by [DRST] and [HKM].
pdf of conference version
Link to full ArXiV version of original [DRST] paper