Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
复制标题
限制多项式阈值函数的平均灵敏度和噪声灵敏度
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Li
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;P. Harsha;Adam R. Klivans;Raghu Meka;Prasad Raghavendra;Rocco A. Servedio;Li
我们给出了关于d次多项式阈值函数（PTF）的平均敏感度和噪声敏感度的首个非平凡上界。这些界对于布尔超立方体{-1, 1}^n上的PTF以及在标准n维高斯分布N(0, I_n)下的R^n上的PTF均成立。我们关于PTF的布尔平均敏感度的界朝着解决戈茨曼和利尼亚尔[17]的一个猜想迈进了一步，该猜想指出，对布尔超立方体中间d层进行切片的对称函数在所有d次PTF中具有最高的平均敏感度。通过卡莱等人[22]的L1多项式回归算法，我们关于高斯和布尔噪声敏感度的界针对这些输入分布下的常次PTF这一广泛类别产生了多项式时间的不可知学习算法。
在高斯设定下用于获得我们关于PTF的平均敏感度和噪声敏感度的界的主要要素是关于高斯随机变量中的低次多项式的尾界和反集中界[20, 7]。为了获得我们关于PTF的布尔平均敏感度的界，我们将[37]中的“关键指标”机制（在那项工作中适用于半空间，即1次PTF）推广到一般的PTF。结合[30]中的“不变性原理”，这使我们能够将我们的技术从高斯设定扩展到布尔设定。我们关于布尔噪声敏感度的界是通过一个简单的归约得到的，即从布尔PTF的平均敏感度上界归约到相应的噪声敏感度界。
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 N(0,In). Our bound on the Boolean average sensitivity of PTFs represents progress towards the resolution of a conjecture of Gotsman and Linial [17], 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. [22], 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.
The main ingredients used to obtain our bounds on both average and noise sensitivity of PTFs in the Gaussian setting are tail bounds and anti-concentration bounds on low-degree polynomials in Gaussian random variables [20, 7]. To obtain our bound on the Boolean average sensitivity of PTFs, we generalize the "critical-index" machinery of [37] (which in that work applies to halfspaces, i.e. degree-1 PTFs) to general PTFs. Together with the "invariance principle" of [30], 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.