Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
Authors:
- Ilias DiakonikolasIDIlias Diakonikolas
- Prasad RaghavendraPRPrasad Raghavendra
- Rocco A. ServedioRSRocco A. Servedio
- Li-Yang TanLTLi-Yang Tan
- 1 January 2014
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 43 (1) , 231-253
Abstract
We give the first nontrivial upper bounds on the Boolean average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs). Our bound on the Boolean average sensitivity of PTFs represents the first progress toward the resolution of a conjecture of Gotsman and Linial [Combinatorica, 14 (1994), pp. 35--50], 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 $L_1$ polynomial regression algorithm of Kalai et al. [SIAM J. Comput., 37 (2008), pp. 1777--1805], our bound on Boolean noise sensitivity yields the first polynomial-time agnostic learning algorithm for the broad class of constant-degree PTFs under the uniform distribution. To obtain our bound on the Boolean average sensitivity of PTFs, we generalize the “critical-index” machinery of [R. Servedio, Comput. Complexity, 16 (2007), pp. 180--209] (which in that work applies to halfspaces, i.e., degree-1 PTFs) to general PTFs. Together with the “invariance principle” of [E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Ann. of Math. (2), 171 (2010), pp. 295--341], this allows us to essentially reduce the Boolean setting to the Gaussian setting. The main ingredients used to obtain our bound in the Gaussian setting are tail bounds and anticoncentration bounds on low-degree polynomials in Gaussian random variables [S. Janson, Gaussian Hilbert Spaces, Cambridge University Press, Cambridge, UK, 1997; A. Carbery and J. Wright, Math. Res. Lett., 8 (2001), pp. 233--248]. 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.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Agnostically Learning HalfspacesSIAM Journal on Computing, 2008
- Learning intersections and thresholds of halfspacesJournal of Computer and System Sciences, 2004
- Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in ${\Bbb R}^n$Mathematical Research Letters, 2001
- Noise sensitivity of boolean functions and applications to percolationPublications mathématiques de l'IHÉS, 1999
- Boolean Functions With Low Average Sensitivity Depend On Few CoordinatesCombinatorica, 1998
- Influences of Variables and Threshold Intervals under Group SymmetriesGeometric and Functional Analysis, 1997
- On the Fourier spectrum of monotone functionsJournal of the ACM, 1996
- Spectral properties of threshold functionsCombinatorica, 1994
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993
- Étude des coefficients de Fourier des fonctions deAnnales de l'institut Fourier, 1970