线性阈值函数的逼近方法及其应用

2/3线性阈值函数逼近计算机科学纽约哥伦比亚大学ilias@cs.columbia.edu罗科A计算机科学系纽约哥伦比亚大学rocco@cs.columbia.edu二〇一八年十月二十九日摘要本文证明了n维布尔超立方体上任意线性阈值函数f（x）= sign（w·x-θ）如何用简单阈值函数逼近的两个主要结果。我们的第一个结果表明，每一个n元阈值函数f都是n-接近于只依赖于Inf（f）2·poly（1/n）多个变量的阈值函数，其中Inf（f）表示f的总影响或平均灵敏度. 这是Friedgut的著名定理[Fri98]的指数锐化，该定理指出，对于阈值函数的计算，每个布尔函数f是一个函数的整数倍，等于2 O（Inf（f）/n）m a n y v a r i a b l e s。我们补充这个上界，显示出，<$（Inf（f）2+ 1/<$2）的许多变量是必需的<$-近似阈值函数。第二个结果是证明了每个n元阈值函数都是n-接近于一个具有最小阈值（n）·2O（1/n）的最小阈值函数）的。 这是对误差参数λ的依赖性的一个明显改进，改进了[Ser 07]的一个较早的结果，其中λ为p（n）·2Oλ（1/λ2）boundd. 我们的改进是一种新的改进技术，它使用了概率论中的强反集中界限。新技术也给出了一个简单的和模块化的证明原始[Ser07]的结果，并扩展到给低权重的近似阈值函数的概率分布范围超出了均匀分布。这项工作的初步版本出现在第24届IEEE计算复杂性年会（CCC）[DS09]上。†由NSF资助CCF-0728736、CCF-0525260和Alexander S.Ontario Foundation- dation Fellowship.部分由NSF资助CCF-0347282、CCF-0523664和CNS-0716245以及DARPA奖HR 0011 -08-1-0069支持arXiv：0910.3719v1 [cs.CC] 2009年101我Σ√{−} → {−}/1介绍线性阈值函数（以下简称为阈值函数）是函数f：n{-1，1} → {-1，1}，形式为f（x）= sign（w·x-θ），其中权重w1，. . . ，w n和阈值θ可以是任意实值。 阈值函数是布尔函数的一种基本类型，几十年来在计算机科学中发挥了重要作用，参见[Der65，Mur71，SRK95]。近年来，从理论计算机科学的许多角度来看，对阈值函数的研究活动非常活跃，包括学习难度[FGKP 06，KS 08]，各种模型中的有效学习算法[Kal07，OS 08，KKMS 08]，属性测试[MORS 09，GS07]，通信复杂性和电路复杂性[She07]，单调计算[BW 06]，去随机化[RS 09，DGJ+09]等。尽管它们看起来很简单，但阈值函数可以有令人惊讶的丰富结构，并且关于它们的基本问题可能出乎意料地具有挑战性。作为一个例子，片刻的思考表明，每个阈值函数f可以用整数权重w1，. . .，w n：这些整数权重需要多大？一个相当直接的论证给出了一个2 O（nlogn）的界，但是这个上界至少从1961年开始就被知道了[MTT61]，并被重新发现了几次（例如[Hon87，Rag88]），在经过三十多年之后，通过一个相当简单的方法和程序最终得到了一个匹配的下界2 O（nlogn）[Has94，AV97]。本文是关于使用“简单”阈值函数来近似任意阈值函数的，这意味着依赖于少数变量或具有小整数权重的阈值函数。对于均匀分布，我们使用一个自然的近似概念：本文（除非另有说明，否则x∈ {−1， 1}n上的所有概率在第4节中，我们将考虑更一般的近似概念。也适用于其他分布）。我们证明了两个主要结果近似阈值函数，我们激励和描述如下。1.1第一个主要结果：最佳逼近阈值函数的juntas。以下代码的后续操作：1，1n1，1是Inf（f）d=efPr[f（x）=f（x<$i）]，其中x<$i表示第i位翻转的x。f的总影响，记作Inf（f），是i Inf i（f）;它是超立方体中被f呈现双色的边的比例的归一化度量，等于f的“平均灵敏度”。众所周知（见[FK96]或[BT96]对于一个x ppprof），在f（f）≤n，nd2、函数f（f）= 0（Inf（f）在所有阈值（甚至所有unate）函数上。在[Fri98]中，Friedgut证明了以下内容：n）-实际上最大化你好。每一个布尔函数都是一个由2O（Inf（f ）/n）-junta表示的多项式，即. e. 一个有效的方法是在2O（Inf（f）/N）的时间内完成一个新的可执行程序。Friedgut2≪仿真[DS05，CKK+06，KR 08]，度量嵌入[KR 06]和学习理论[OS 07]。在第2.5节中，我们讨论了这个定理在布尔函数的傅里叶表示的一系列结果中的作用。Friedgut证明了他的界对于一般布尔函数是最好的可能的，给出了一个函数的新的推广公式，其中的一个函数的二阶（Inf（f ）/n）-j是一个布尔函数的二阶-prxi ma t i m at i man. f（f ）/f（f）的一个boundd是不严格的，如果f（f）logn，其中hi ch很小;因此，很自然地会问各种受限的函数类（例如阈值函数）是否可以允许更强的边界。我们的第一个主要结果是一个指数更强的版本Friedgut定理1（第一主要定理）。 每个阈值函数f都由一个在f（f）2·p（1/n）-junta中（它是一个简单的函数）.它是一种简单的可逼近;它是一种简单的可逼近方法，因为可逼近可能需要（Iinf（f）2+1 /1/2）许多变量（见第2.5节）。我们猜想定理1扩展到d次多项式阈值函数，在界中对d具有指数依赖性，并且还猜想定理1的不同扩展，这是由Bourgain定理启发的;见第2.5节。技术. Friedgut定理的证明主要利用了Bonami-Gross- Beckner超压缩不等式[Bon 70，Gro 75，Bec 75]。我们对定理1的证明采取了完全不同的路线，并且没有使用超收缩性;相反，主要成分是[OS08]中关于阈值函数的最近傅立叶结果和概率性的非线性。这让人想起Bruck和Smolensky的更详细地说，我们的证明中的一个关键概念是常规阈值函数;粗略地说，这是一个阈值函数，其中每个权重wi相对于权重向量的2-范数是给定一个正则阈值函数g= sign（w·x−θ），我们使用权重wi来定义g的逼近器的概率分布（这与[BS 92]类似我们证明了（引理8和9），从这个分布中随机抽取的近似器具有很高的预期精度，并且不依赖于太多的变量（上限是根据权重wi和正则性参数给出的）。用这种构造来逼近任意阈值函数的一个明显问题是，不是每个阈值函数都是正则的。为了解决这个问题，我们使用了[OS 08]最近的一个结果，该结果表明每个阈值函数f都可以很好地近似为具有两个关键性质的阈值函数f′：f′几乎是正则的（在这个意义上，它只有几个“大”权重），其“小”权重是f中相应变量的影响（适当缩放版本）。对于固定f ′的大权重变量的每个限制ρ，则我们可以使用f′|ρ作为前一段中的正则阈值函数g，并且我们得到了f ′的逼近器的分布|其中，可用于一个可压缩机的最小可压缩量为m_（max）/n_f（f）2·p（1/n）。 基于此，使用概率方法，我们能够论证存在一个单一的高精度算法，用于在f（f）2·p（1/n）变量中确定f（f）的独立性。3··− ···{−}·1.2第二个主要结果：近似阈值函数，以更高的精度。本文的第二个主要结果是关于用小整数权的阈值函数g来逼近任意n元阈值函数f。Goldberg[Gol 06]和Servedio[Ser07]已经研究了这一点，因为使用2 π （ nlogn ）低限整数权重[Heas94]来精确地表示任意阈值函数，所以在一般情况下不可能实现一个简单的多项式（n，1/n）。 Servedio[Ser07]给出了第一个肯定的结果，通过表明对于每个阈值函数f，存在一个近似阈值函数g，其中每个权重是至多为p〇 l y（n）2Of（1/n2）的整数。 它的研究成果在以后的阈值函数研究中具有重要的作用，如[OS 08，MORS 09，DGJ +09]。考虑到[Ser 07]的有用性和其边界对α的依赖性很差，自然会寻求一个更强的定量边界，对α的依赖性更好;事实上，这是[Ser 07]中提出的一个主要开放问题。我们的第二个主要结果在这个方向上取得了进展：第二大定理（Second Main Theorem）对于任意n元阈值函数f，用fuctiong=sign（wxθ），其中hw1，. . . ，其中所有的数据都是3/22O位（1/22/3）。[Ser07]中提出的另一个问题是关于均匀分布之外的其他概率分布的小整数权重近似器。如下所述，定理2可以被推广为在非均匀分布的范围下成立定理2证明使用一种新的方法，我们相信这可能会导致更好的边界的范围内考虑的问题[OS 08，MORS 09，DGJ+ 09]，其中使用的方法从[Ser07]。粗略地说，[Ser07]中的证明和[OS08，MORS 09，DGJ+ 09]中的应用都依赖于这样一个事实，即对于合适的权重向量w，随机变量w x（x在1， 1n上均匀分布）可以用高斯近似。这样的近似提供了关于w x的大量信息，但缺点是高斯仅是w x的相当粗略的近似器，即使对于表现良好的权重向量w=（1，. . . ，1），并且它可以在1/102中有效地观察到该点的存在（如[Ser 07，OS 08，DGJ +09]）。现在我们简要地描述一下我们的新方法如何绕过这个障碍，从而得到定理2技术. 我们的新方法与[Ser07]中的方法之间的主要概念差异在于此。[Ser 07]中的证明从表示某个阈值函数的任意权重向量开始;直观地说，这可能是有问题的，因为这些权重可能为底层函数提供了不方便的表示相反，我们专注于函数本身，并证明每个阈值函数都有一个“漂亮”的这使我们能够利用仅在某些权重假设下适用的强反集中界限[Hal 77];我们在下面详细说明。反集中的概念是我们方法中的一个重要组成部分：如果随机变量没有给实数线的任何小区间分配太多的质量，则它具有良好的反集中反集中的研究在概率论中有着丰富的历史，见例如[DL36，Kol60，KL68，Rog73，RV08]。已知w·x形式的离散随机变量的反集中不等式4··一个人的世界。对于sign（x）的测试和预处理，·√不等式（即1我 们 注 意 到 ， [Ser 07] 也 （ 隐 式 地 ） 使 用 反 集 中 界 限 ， 特 别 是 在Gaussianapproximation的基础上（从Berry-Es ss'eenTheorem;se定理4开始）。事后可以看出，在[Ser07 ]的论证中没有更强的反集中界限可以使用，因为该证明考虑了符号（w·x− θ）形式的所有可能表示，其中w在所有R n上。举个例子，考虑大多数我我根据Berry-E的说法，这是一个非常简单的问题，因此，在这方面，包含原点的概率质量为<$（1/ n）。另一方面，也有可能为多数函数提出具有更好的反集中性的替代表示sign（w x）;这就是我们的证明所做的 我们证明了一个结构定理，该定理指出每个阈值函数都有一个表示，其中“许多”权重是“良好分离的”;在这个条件下的权重，我们得到了强反集中使用的一个r e u lt of f H al 'a s z [ H al 77]。最后，我们如何将一个新的整数近似值转换为一个低权重整数近似值，以获得我们最终想要的结果。讨论：我们的一般方法是模块化和鲁棒的。它从[ S e r 07 ]的基础上给出了一个简单而又比较持久的po l y（n）2O∞（1/n 2）up p o l y（n）2 O ∞（1/n 2）uppoly（n）Viaaratherelabratecasana l y s. 此外，新的多项式（n）2O∞（1/1~2/3）boundd及其证明易于推广到更广泛的分布.这些分布包括常数偏置乘积分布，并利用[DGJ+ 09]的最新结果对于最大的K（K=0×（1 /2））幂次幂，K =0 ×（1/2）），Organization. 我们在第2节中证明了定理1，在第3节中证明了定理2。第4节将定理2推广到某些非均匀分布。2定理1：最佳逼近阈值函数的junta本节的结构如下：在给出一些数学表达式后，在第2.2节中，我们描述了正则阈值函数的逼近器的随机构造。在第2.3节中，我们回顾了[OS 08]的结果，该结果让我们用“几乎”正则的阈值函数来近似任何阈值函数。在第2.4节中，我们把这些部分放在一起来证明定理1。我们在2.5节中给出了一些讨论和说明。2.1你的助手。2.1.1基本概率不等式我们首先回顾以下标准加性Hoeffding界限：[1]粗略地说，如果我们在wi中[Vu08，TV08]和[TV06]的第75Σ我nQf（i）而不是f（{i}）。^^对于每一个f：{−1， 1}n→ {− 1， 1}，我们有<$Sf^（S）2= 1。我的天^^^^X j在[a j，b j]上支集，其中a j，b j∈ R，a j≤ b j. 设X =t >0，nj=1 X j. 然后，对于任何|≥ t| ≥ t≤2次暴露我我我我w2，anddassume|wi|对于所有i∈[n]，/ σ ≤ τ。这是一个很好的选择5.coro llary. Letx1，. . . ，xndenteni . . ，wn∈. Pr[a ≤ w1x1+···+w n x n≤ b] −Φ（[a，b]）. ≤2 τ，1nσ在由y_f生成的Q中，g_f=E[f（x）g（x）]。这是一个有趣的故事，nj=1 （bj）-aj）2XR. 写σ =第三章. LetX1，. . . ，Xn是一个独立的变量，它可以满足对于一个j∈[n]的所有条件，好吧−2t2Berry-Essentererem erent e rer en t e r e re n t e r e r e n t er e r e n t e r e r e tr e r e n t e r er e n t e rer e n tr er e第四章. （Berry-Es'een）LetX1，. . . ，Xn是独立的数据库，并且可以进行动态访问对于所有i∈ [n]，E [ X i ] = 0，E [X2]=σ，且E [|X i|3]=ρ3。 设S=（X1+· · ·+Xn）/σ设F表示S的累积分布函数（cdf）。 然后sup |F（x）−Φ（x）|≤Cρ3/σ3，其中Φ是标准高斯随机变量的cdf，C是通用常数。[Shi86]已经证明可以取C=。七九一五[a，b] A..σ σdef其中Φ（[c，d]）= Φ（d）-Φ（c）。特别是Pr[a≤w x +· · ·+w x≤b] ≤|b−a|+2 τ。2.1.2{-1，1}n上的傅里叶分析我们考虑函数f：{− 1，1}n → R（尽管我们经常关注映射到{− 1，1}的布尔值函数），我们认为输入x到f是按照均匀概率分布分布的。这些函数的集合形成了一个二维的（χS）S[n]定义为χS（x）=i∈Sxi构成了这个空间的一个完备的标准正交基我们对于i ∈ S x i，通常会简单地写为xS。ndef给定 函数f：{-1，1}→ R，我们定义其傅立叶系数为f^（S）=E[f（x）xS]，且f（x）=Sf（S）xS. 我们为这座城市感到骄傲|S|设f（S）的傅立叶阶为所有非零f（S）。 当|S|我们通常滥用记谱法，作为正交正规性的一个简单的推论，我们有Plancherel恒等式f，g = f（S）g（S），其中有一个特殊的Plancherel恒等式，E [ f（x）2 ] = Plancherel f（S）2。从那以后，我们回顾一下众所周知的事实（例如， [KKL88]）任何布尔函数的总影响Inf（f）等于S f（S）2|S|. 此外，对于每个阈值函数f（实际上对于每个unate函数），我们有Inf i（f）= |f（i）|.PR.1n6i=1i=1我i=1i=1我i=1DuΣu的范数，即：i=1Mi=1 |.|. 我们写1τ2D| | ≤∈u2.1.3其他技术人员。一个函数f：{− 1，1}n → {− 1，1}被称为“J上的junta”，如果f只依赖于J上的坐标。 如前所述，我们说f是J-junta，0 ≤ J ≤ n，如果它是一个junta关于f的任意集合，在一个任意的junta中J是任意的。对于一个vectou∈Rm，我们将其定义为n=1，而不是L1按分布进行分配。最后，我们给出了“正则”阈值函数概念的精确定义定义6. 设f（x）= sign（w0+nwixi）是一个阈值函数，其中nw2= 1.我们说f是τ-正则的，如果|w i|对于所有i∈ [n]，22.2随机构造正则阈值函数的逼近器。固定h θ（x）=sign（θ+ m u i x i）是τ-正则阈值函数，因此 u2=1，对于所有i[m]，ui τ 我们的符号强调阈值参数θ，因为它将发挥一个重要的角色。我们首先定义线性形式L（x）= m c i x i上的分布D。分布-tion类似于Bruck和Smolensky [BS 92]如何定义使用布尔函数的傅立叶系数的多项式分布。从D中提取L（x）如下：首先将L（x）初始化为0。则如下是独立地独立地独立于Nd=efΘ（τu∈2·1·ln（1/τ））的时间序列：概率|ui|，并且sign（u i）xi被添加到L（x）。固定任何z∈ {−1， 1}m。 对于L← D，我们可以将L（z）看作是Ni.i.d.的和。 ±1值范围dom变量Z1（z），. . . ，Z N（z），其中每个Z j（z）的期望为|ui| sign（ui）zi=1u·z。因此，我们有：EL←D[L（z）]=Nj=1NE[Zj（z）]=ui=1u1（u·z）。（一）有了D，我们用以下自然的方式定义阈值函数gθ上的分布D′：为了画一个函数gθ←D′，我们画L← D，并设置g（x）= sign（θ +<$u<$1L（x））。（二）θN我们想证明，对于gθ← D′，gθ（z）与hθ（z）不一致的概率是 但是这样的界不能对每个z∈ {−1， 1}m都成立，因为如果θ+u·z的值任意接近0，那么在（2）中签名的自变量的期望值可以任意接近0。 对于z使得θ+u·z不太接近0， 可以说gθ（z）只有在很小的概率下是不正确的（在2严格地说，τ-正则性是一个特定的表示符号（w0+nwixi）的性质，而不是一个阈值函数f，它可以有不同的表示，其中一些是τ-正则的，一些不是。我们所关注的特定表示将始终从上下文中清楚。定义7也是如此。7i=1θu乌鲁河{−}{−}Σ我i=1我gθ← D′）。此外，hθ的正则性让我们认为只有一小部分输入z的θ+u·z接近于0，因此我们可以得出gθ的预期误差很低的结论。我们现在提供细节。我们将使用以下输入相对于阈值函数的“裕度”概念：定义7. 令f（x）=sign（w0+nwi xi）是阈值函数，其中权重为缩放，使得nw2= 1。 给定一个特定的输入z ∈ {-1，1}n，我们定义marg（f，z）def=|.|.让MARGθ，τd=ef{z∈{−1，1}m：marg（h，z）≥τ}de不等于{−1，1}m中的points的集合在h θ下保证金至少为τ。我们现在证明，一个随机的gθ← D′具有很高的期望，每个点z∈MARGθ，τ的精度：我是8号。 对于achz∈M ARGθ，τ有Prgθ←D′[hθ（z）=/gθ（z）]≤τ。Morreoverr，eachg θ← D′ 是一个军政府。证据后 一种说法是直接的，因此足以证明前者。 固定任何z ∈ MARG θ ， τ，所以|θ+u·z|≥τ。 我们需要从上面的“坏”事件的概率（在g θ ← D ′的随机选择上）限制关键的主张是，如果B发生，那么它必须是这样的情况，|L（z）−EL←D [L（z）] |≥Nτ。 因为假设hθ（z）= 1且gθ（z）= −1（另一种情况类似处理）。根据定义，我们有θ+u·z≥0和θ+（<$u<$1/N）L（z）0。<由于z属于MARGθ，τ，第一个不等式给出θ+u·z≥τ，这意味着，通过（1），E[L（z）]≥（N/u<$1）（τ−θ）。等式中的等式等于L（z）<−θN/θu1，因此我们有E [L（z）]−L（z）≥Nτ/θu1。我们有一个Prgθ <$D′[hθ（z）=/gθ（z）]≤PrL<$D[|L（z）−E[L（z）]|≥Nτ]。现在我们1再次将L（z）视为Ni.i.d.1，1随机变量 赫夫丁界限（定理3）NτPL←D[|L（z）−E[L（z）] |≥100%]≤ 2 exp.−2（Nτ/u1）24N≤τ，其中第二个不等式由我们的选择N所遵循。这就完成了引理的证明。接下来我们注意到，通过h θ的正则性，1， 1m中的大多数点都有很大的边界（因此被引理8所覆盖）：我是9号。 Prx∈{−1，1}m[x∈/M ARGθ，τ]≤4τ.Proof. 该公式是一个由Berry-Ess eeMi=1 u2= 1。结合引理8和9，我们得到本小节的主要结果引理10. Egθ←D′ [Prx∈{−1，1}m[g θ（x）]h θ（x）]] ≤5 τ。i=11Σ8^.ΣΣ.^^·2Σ||def我们可以进一步假设T=[n]\H具有w2=1。2i∈T我2.3使用它们的影响作为（几乎所有的）权重来近似阈值函数。我们的下一个工具是关于近似阈值函数的以下定理 粗略地说，每个阈值函数f都可以由阈值函数f ′很好地近似，其中f ′具有两个阈值函数f ′的p（1/n）lag ： uptosign，they是值Infi（f）。（回想一下，对于阈值函数f，我们有|f（i）|= Inf i（f）;见第2.1.2节。）定理11. [[OS 08]的定理17]存在固定多项式κ（λ）= Θ（λ144）3，使得以下成立：设f（x）= sign w0+ λi∈H w ixi+ λi∈T w ixi是阈值函数头上指数H和尾上指数 T，其中 Hw2= 1。 然后选择：={i：|f^（i）|≥κ（π）}且T满足i∈ Ti(i) f是O（π）-接近H上的军政府;或者，(ii) f是O（n）- 接近阈值函数f′（x）=signw+nwx+Bf（i）x= 0，0i∈Hi ii∈TσTiwhichhereσTdenotes.f^（i）2. 此外，在此情况下，我们有σT=σ（σ2）。4注意，<$i∈T（f（i）/σT）2= 1，由于σT=<$（<$2），对于每个i∈T，我们有|κ （λ）2 / σ T ≤ O（λ 2 8 8）/λ（λ 2）= O（λ 2 8 6）.|<κ(ǫ)2/σT≤O(ǫ288)/Ω(ǫ2)=O(ǫ286).（三）这意味着，对于固定H中变量的任何限制ρ，函数f ′|ρ是poly（π）-正则的;这一点很重要，因为它允许我们将2.2节的结果应用于这些限制。2.4定理1现在我们来证明定理1。本文首先证明了每个阈值函数f都是O（n）-由a（1+lnf（f）2）p（1/n）-j（n）- j（n）表示的pp（n）x，并由此得到定理1. 为了简洁起见，在本小节的其余部分，我们将Inf（f）写成I设0 <≠<1，f为任意n元阈值函数. W.l.o.g. 我们可能n考虑表示f（x）= sign（w0+i=1wi xi），其中每个wii= 0，并且通过缩放Σ我们要去11个地方。PARSEVAL的icanhave|f（ i ） |≥κ （ ε ） 2 ， 因 此 具 有 |H|≤1/κ （ λ ） 4=po l y （ 1/λ ） 。 IinCase （ i ）weimmdiately证明了f是O（λ）-逼近于（1/λ）-junta的逼近子，从而给出了C（ii）hol d s，并讨论了C（ii）hol ds中的O（λ）-逼近子f′。我们将所有2个概率（1/2）的概率通过固定H. 我们还要把2.2节的结果应用于函数f ′ρ。 如2.3节所述，对于每个限制ρ，T中尾变量上的结果函数f ′ρ是τ（τ）正则阈值函数，其中τ（τ）= O（τ286）是（3）的RHS中隐含的函数（为了简洁起见，我们将τ（τ）写为τ）。此外，所有这些限制都是定义的阈值函数[3]参见[OS 08]方程（24）之前的讨论;我们的κ（κ）是[OS 08]的τ（τ）4参见[OS 08]的等式（24）91|| ≤ σ^·L（x））。对于每个g← D的结果DΣ···^ ^您的位置：^ΣΣi=1我0我我为了与2.2节的符号保持一致，对于每个限制ρ，我们写hθρ来表示f（i）T i=1|≤I ·pol y（1 /μ m）。|≤I·po ly(1/ǫ).1τ2g<$D′′的绘制通过绘制L<$D并设置g（x）= sign（w0+Σi∈Hwi xi+i∈T′′通过T中变量的相同线性形式：它们仅在阈值上不同即θ值d=efw+fw ρ。f′|，即h（x）d=efsign（θ+θ）x）其中xd=ef Bf（i）和xd=ef（x）.我们观察到ρ θρTρi∈Ti iiσTT i i∈T我的天其中最后一个不等式使用Inf i（f）= |f（i）|σ T= σ（σ2）。回想一下N等于Θ（θu=2·1·ln（1/τ）），我们知道N是最小的I2·p（1/τ）。我们将IDERDISTRIBUTIOND′′OVRESHHOL DFFNSON{−1，1}NDEFFASFWWuNT（1+12）（1/2）多变量。，函数g最多取决于|H|+ N =只需要论证从"is“得出的某个g是O（n）-接近于f”。 经由′概率方法，要做到这一点，它足以表明，Eg←D′′[Prx∈{−1，1}n[g（x）O（τ）（回忆τ）。 我们现在使用2.2节的结果来做这件事。将ρ赋值给H中的变量。 通过引理10，我们有f（x）=Eg←D′′ PrxT←{−1，1}|不|[f′|ρ（xT）G|ρ（x T）] τ ≤ 5 τ。对所有ρ求平均，我们得到Eg←D′′ Prx<${−1，1}n[f′（x）]，这是期望的边界。g（x）]τ≤ 5τ因此，我们证明了这两个函数的时间复杂度为O（λ）-closetoa（1+I2）p（1/λ）-我们发现，通过分析这一点，我们可以发现，1号或1号证券的发行是一个非常复杂的（1/2）证券化过程。 Letcbeanabol eso les olesoa（1+I2）（1/1）c-junta的复杂性，我们可以根据I的大小来确定复杂性。 当I>1时，它是cl at（1+I2）（1/n）kf∈（S）2≤（λ/k）1/2+o（1）是ε-cloesetoa2O（k）·poly（1/λ）-junta.让我们考虑一下，当我们把注意力限制在上述定理中的阈值函数时，每个军政府的规模界限是如何变化的。我们首先观察到，在这种情况下，[NS 9417号提案 每个具有（最大）傅立叶次数k的阈值函数是一个（2 k − 1）- junta。（这是从一个简单的事实得出的，即任何具有r个相关变量的阈值函数都包含一个子函数，该子函数是（r+1）路AND或OR。当然，我们的定理1告诉我们，如果f是阈值函数，Friedgut定理也可以指数锐化。这激发了一个自然的问题，即布尔甘定理是否可以类似地对阈值函数进行锐化。我们声明如下：Conjecture2. 每一个人都有自己的幸福，|S|>kf（S）2≤（k/k）1/2+o（1）is-closetooapoly（k/n）-junta.3定理2：逼近阈值函数到更高的精度。如第1.2节所述，我们的新方法可以在概念上分为以下步骤：12·∈∈v∈R则pr（a）≤KK/2三分之二时间复杂度O（k−1）1. 证明每个阈值函数都有一个表示，其中许多权重是2. 使用权重的3. 最后，使用w x的反集中来获得具有小整数权重的近似器请注意，前两步之间存在微妙的关系：第一步中建立的权重的结构结果必须与第二步中反集中的必要条件相第三步是一个简单的通用引理，将反集中转化为低权重近似。本节的结构如下：在第3.1节中，我们回顾了我们需要在上面的证明模板中实现步骤2的反集中结果，并证明了在我们的证明模板中实现步骤3的简单引理。 在第3.2节中，我们通过使用模板对[Ser07 ]的主要结果进行了一个干净的模块化证明，从而为我们的主要结果提供了一个在第3.3节中，我们展示了模板如何产生定理2的一个变体，其中hi chaannO（1/n2/3）bond。 这是对第3节新的门限函数表示的一个新结果引理26的补充。粗略地说，这个引理说每个阈值函数都有一个表示，使得连续权重之间的许多差异不会太小。那么在3.4节中我们证明了h是nO（1/n）的情形）可以进行预处理，以充分预处理第2项。最后，本节的所有结果都可以适当地推广到常数偏置乘积分布和K-独立分布（但正如我们所展示的，它们不能被推广到每个分布）。我们在第4节中给出这些扩展。3.1伯努利随机变量加权和的反集中我们从反集中的正式定义开始18. biggest biggest biggest biggest LetaRnbeaweigt - v e c t o r r a n d r R +.a的L′evydefp r（a）=sup Prx←U[|a·x-v|≤ r]。因此，权重向量a的反集中是a·x位于任何小区间（长度为2r）的概率的上限。一个早期的和重要的结果，对反竞争的新的是由Er d. D. D. E rd. D. D.Of. D. O f. D. D.Of. D. D. Of.D. D.19.第19章.（Erdos）. Leta=（a1，. . . ，ak）∈Rk，r∈R+besuchthat|a我|对于所有的i∈[k]，≥ r。随后的大量工作以许多不同的方式推广了这一结果（见例如[TV 06]的第7章）;这种一般风味的抗浓度结果已经达到13k+1nk+1ni=1√√√sign（ni=1 vixi−θ/α）是一个proxi mator。 我很清楚，我知道|vi|时间复杂度为O（maxi）|wi|/α），对于第一个事件，我们有Pr [|e·x| ≥r] ≤Pr [|e·x| ≥ 100%- 是的这一经济发展的基础设施是由基础设施建设所建立的。[|w·x−θ|≤r]≤pr（w）≤p。2ln（ 2/n）]≤n，其中f是被称为 我们将需要定理19的一个推广，它是由于Hal′asz[Hal77]，即在Erdos-Moser[Erd65]和S′ark′ zy-Szemer′edi[SS65]中的推广。当Erddos的计算结果表明，由于权重较长，因此存在最大（最小）概率和最小值时，H20岁的孩子。 Leta=（a1，. . . ，ak）∈Rk，r∈R+besuchthat|ai−aj|≥rforalli/= j∈[k]。时间复杂度为O（k−3/2）。展望未来，我们注意到“3/2”指数而不是“1/2”是我们从2 O（1 /2）到2 O（1/2 / 3）的改进的关键。我们需要的关于反集中的最后一个事实是下面的简单引理，它说如果我们通过增加更多的权重来扩展权重向量a，它的反集中只会得到改善：引理21（扩展）。 设a ∈ Rk是任意k维权向量，r ∈ R+是任意非负实数 对任意n> k，设a′∈ Rn为向量（a1，. . . ，ak，a′，. . . ，a′）其中权值a′，. . . ，a′可以是任何实数。 则pr（a′）≤ pr（a）。证明是通过一个简单的平均参数，使用的事