A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 1 · The asymptotic Gotsman–Linial conjecture
Average sensitivity of polynomial threshold functions
expertly designed by an internal OpenAI model · released 2026-09-25
· original PDF
IntroductionA polynomial threshold function assigns a sign to each vertex of the Boolean cube by evaluating a real polynomial. On the cube, the identities \(x_i^2=1\) allow every polynomial to be replaced by a multilinear polynomial of no larger degree without changing its values. Average sensitivity measures the expected number of coordinate changes that reverse that sign. For \(x\in\{-1,1\}^n\), let \(x^{\oplus i}\) be obtained by reversing coordinate \(i\). For \(f:\{-1,1\}^n\to\{-1,1\}\), define \[ I(f)=\sum_{i=1}^n\mathbb P\{f(X)\ne f(X^{\oplus i})\}, \qquad X\text{ uniform on }\{-1,1\}^n. \tag{1}\] This quantity is also called the total influence of \(f\). Throughout, \[\operatorname{sgn}(t)=\begin{cases}1,&t\ge0,\\-1,&t<0.\end{cases}\] We prove the following estimate. Theorem 1. Let \(n\ge1\) and \(1\le d\le n\) be integers. Let \(p\) be a real multilinear polynomial of degree at most \(d\), and define \(f:\{-1,1\}^n\to\{-1,1\}\) by \(f(x)=\operatorname{sgn}(p(x))\), with \(\operatorname{sgn}(0)=1\). Then, for average sensitivity under the uniform law, \[I(f)\le 8d\sqrt n.\] The constant is independent of both \(d\) and \(n\). In particular, the degree may grow with the dimension. The polynomial may vanish on the cube, and no regularity condition is imposed on \(p\). Gotsman and Linial proposed an exact extremal bound for average sensitivity [4]. Their candidate is symmetric: it is the sign of a degree-\(d\) polynomial in \(x_1+\cdots+x_n\) whose roots lie between the central levels of the cube. The proposal asserts that this function maximizes influence among all degree-\(d\) polynomial threshold functions in \(n\) variables. Chapman constructed counterexamples to this exact assertion and explicitly distinguished it from the asymptotic bound \(I(f)=O(d\sqrt n)\) [2]. Kim, Maldonado, and Wellens independently constructed quadratic counterexamples for odd \(n\ge5\) and proved influence bounds for quadratic polynomials with restricted support graphs [9]. Theorem 1 establishes the asymptotic bound with an absolute constant; it makes no assertion about exact maximizers. Numbered locators in references with a listed preprint refer to that preprint version. The classical symmetric examples explain the scale of the theorem. Let \(1\le d\le\sqrt n\), let \(J\) consist of the \(d\) indices nearest \((n-1)/2\) in \(\{0,\ldots,n-1\}\), breaking a tie arbitrarily, and put \[t(x)=\frac{n+x_1+\cdots+x_n}{2},\qquad p_J(x)=\prod_{j\in J}\bigl(t(x)-j-\tfrac12\bigr).\] Here \(t(x)\) is the number of coordinates of \(x\) equal to \(+1\). Multilinearization preserves the values of \(p_J\) on the cube and has degree at most \(d\). Its sign changes exactly across the boundaries between Hamming weights \(j\) and \(j+1\) for \(j\in J\). There are \((n-j)\binom nj=n\binom{n-1}j\) unoriented edges at such a boundary, so the ordered-edge normalization in (1) gives \[I(\operatorname{sgn}p_J)=n\,2^{-(n-1)}\sum_{j\in J}\binom{n-1}j \asymp d\sqrt n.\] Here the comparison constants are absolute. The central-binomial estimate from Stirling’s formula, together with the ratios of consecutive binomial coefficients, shows that the binomial masses are comparable to \(n^{-1/2}\) within \(\sqrt n/2\) of the center, which includes all selected indices; the case \(n=1\) follows directly from the count. Thus the order \(d\sqrt n\) is sharp throughout this degree range; see also [9]. For every Boolean function, the additional bound \(I(f)\le n\) holds. Early general bounds established sublinear influence for every fixed degree. For \(n>1\), Harsha, Klivans, and Meka proved \(I(f)\le2^{O(d)}n^{1-1/(4d+6)}\) [5], while the independent work of Diakonikolas, Raghavendra, Servedio, and Tan gave \(I(f)\le2^{O(d)}(\log n)n^{1-1/(4d+2)}\) [3]. These results first circulated in 2009, before their 2014 journal publications. Their proofs use regularity and invariance arguments to compare sufficiently regular Boolean polynomials with Gaussian ones. Kane subsequently established the square-root exponent in the dimension: \[ I(f)\le\sqrt n\,(\log n)^{O(d\log d)}2^{O(d^2\log d)} \qquad(n>1) \tag{2}\] [8]. For each fixed \(d\ge2\), this is an \(n^{1/2+o(1)}\) bound with a polylogarithmic loss. His proof combines random restrictions, regularity, and invariance estimates. Theorem 1 removes that loss and gives linear dependence on \(d\) with an absolute constant. Small moments of the local sensitivity \(s_f(x)=|\{i:f(x)\ne f(x^{\oplus i})\}|\) give further information about its distribution. Chang, Slote, Volberg, and Zhang bounded the Boolean surface area \(\mathbb E\sqrt{s_f(X)}\) by a polynomial in \(\log(en)\) for each fixed degree [1]. Tseng and Volberg studied a wider range of sensitivity moments [11]. For comparison with the first moment, the pointwise inequality \(s_f\le\sqrt n\sqrt{s_f}\) converts the surface-area estimate into an influence bound with a logarithmic loss. At moment order one, the estimate in [11] is \(C(d)\sqrt n(\log n)^{Cd\log d}\) for \(n>1\), which likewise retains a logarithmic factor for \(d\ge2\). Proof strategy.The proof separates a probability estimate from a finite-dimensional operator construction. The probability estimate says that equal-law random variables of variance \(\sigma^2\) satisfy \(\mathbb E(U-V)^2\le8a\sigma\) whenever \(V-U\le a\) almost surely. A bound on increments in the opposite direction is not assumed. Equality of the marginal laws supplies the needed balance through an increasing function whose increments dominate squared displacement. Section 2 proves this estimate directly. For the operator construction, begin with the spaces of cube polynomials of degrees at most \(k\), for \(0\le k\le n\). Multiply these spaces by \(\sqrt w\) for a positive weight \(w\), and take their successive orthogonal increments in the counting inner product. The increments have dimensions \(\binom nk\), although the weight changes their positions. Give the \(k\)th increment eigenvalue \(k-n/2\); this defines a self-adjoint operator \(M\) with fixed squared Hilbert–Schmidt norm \(n2^n/4\). Its squared Hilbert–Schmidt norm is the sum of the squared moduli of all matrix entries. Multiplication by a coordinate connects only equal or adjacent grades, because it raises polynomial degree by at most one and is self-adjoint. These are the two features of the grading used in the proof: fixed dimensions and locality under coordinate multiplication (Section 3). When \(w\equiv1\), \(M\) is minus one-half of the cube adjacency matrix. For a general weight, some edge entries may have smaller squared modulus, and other entries may appear. Section 4 shows that the total squared entry mass between vertices at distance at least two is bounded by the mass on the diagonal. Together with a bound on each edge entry, this controls the total deficit from the unweighted squared edge value \(1/4\). If \(H\) multiplies by a sign function \(h\), the anticommutator \(MH+HM\) retains diagonal entries and equal-sign edge entries, multiplying them by \(2\) or \(-2\). Its squared norm therefore bounds the number of equal-sign edges even for an arbitrary positive weight. Finally, multiply \(f\) by full parity to obtain \(h(x)=(\prod_{i=1}^n x_i)f(x)\), and use \(w=|p|\) after removing zeros without changing signs. The equal-sign edges of \(h\) are exactly the sensitive edges of \(f\). Moreover, multiplication by parity turns the Fourier support of \(p\) into degrees at least \(n-d\). This forces the block of \(H\) between grades \(r\) and \(s\) to vanish when \(r+s<n-d\). The normalized squared block norms define a probability law for \((R,S)\) whose two marginals are \(\operatorname{Bin}(n,1/2)\). Reflecting one index gives \(U=S\) and \(V=n-R\), with the same marginals and \(V-U\le d\). The coupling estimate then bounds the anticommutator norm, and the edge estimate gives the theorem. Section 5 performs this assembly, keeping track of ordered edges. Consequences.Section 6 derives a dimension-free Boolean noise sensitivity bound and a quantitative learning guarantee from the influence estimate. The learning statement concerns independent labeled samples whose input marginal is uniform, while the labels may be arbitrary. It follows by combining noise smoothing with polynomial regression. A one-sided coupling estimateThe next lemma controls mean square displacement from an upper bound in only one direction. Large downward displacements are permitted, so bounding the positive and negative displacements separately would lose information. Equality of the marginal laws instead balances the expected change of any integrable function applied to the two variables. We use an increasing function whose increments dominate squared displacement; its increments in the bounded direction can be estimated using the common variance. Neither independence nor exchangeability is assumed. Lemma 2. Let \(U,V\) be real random variables with the same distribution, finite mean \(m\), and finite variance \(\sigma^2\). If \(V-U\le a\) almost surely, where \(a\ge0\), then \[\mathbb E(U-V)^2\le 8a\sigma.\] Proof. The function \(|t-m|\) grows linearly away from the common mean. Its primitive is the increasing function \[g(t)=\int_m^t\lvert z-m\rvert\,dz=\tfrac12(t-m)\lvert t-m\rvert.\] For \(u<v\), we have \[ \frac{(v-u)^2}{4}\le g(v)-g(u) \le \frac{v-u}{2}\bigl(\lvert u-m\rvert+\lvert v-m\rvert\bigr). \tag{3}\] For the lower bound, if \(u\le m\le v\), the integral is \(\bigl((m-u)^2+(v-m)^2\bigr)/2\ge(v-u)^2/4\); if the interval lies on one side of \(m\), the integral is at least \((v-u)^2/2\). For the upper bound, convexity places \(\lvert z-m\rvert\) below the chord joining its endpoint values, whose integral is the displayed upper bound. The second-moment assumption makes \(g(U)\) and \(g(V)\) integrable. Their expectations agree. For the integrable random variable \(Y=g(V)-g(U)\), write \(Y_+=\max\{Y,0\}\). The identity \(\mathbb EY=0\) implies \(\mathbb E|Y|=2\mathbb EY_+\). Since \(g\) is strictly increasing, \(Y>0\) exactly when \(V>U\), and hence \[\begin{align*} \mathbb E\lvert g(U)-g(V)\rvert &=2\mathbb E\bigl[\mathbf1_{\{V>U\}}(g(V)-g(U))\bigr]\\ &\le a\mathbb E\bigl[\lvert U-m\rvert+\lvert V-m\rvert\bigr] \le 2a\sigma. \end{align*}\] The first inequality uses (3) and \(V-U\le a\) on \(\{V>U\}\); the last is Cauchy–Schwarz. The lower bound in (3), with the endpoints put in increasing order, gives \((U-V)^2\le4|g(U)-g(V)|\) pointwise. Taking expectations proves the lemma. ◻ The cancellation \(\mathbb E[g(V)-g(U)]=0\) uses only equality of marginal laws. Primitive differences with this property also appear in Röllin’s formulation of Stein’s method [10]. The present one-sided second-moment estimate follows from the elementary increment bounds above. Weighted Fourier gradingWe next construct an operator whose spectrum is fixed by the dimensions of polynomial spaces, while its matrix entries respond to an arbitrary positive weight. The construction is the cube instance of the usual degree filtration for discrete multivariate orthogonal polynomials, whose coordinate multipliers satisfy a three-term recurrence; compare Xu [12]. We give the finite-dimensional argument in the present notation. Write \(\Omega=\{-1,1\}^n\) and \(N=2^n\). We work in \(\mathcal H=\mathbb C^\Omega\) with the counting inner product \[\langle a,b\rangle=\sum_{x\in\Omega}\overline{a(x)}b(x).\] Thus the point masses \(\delta_x\) form an orthonormal basis. For an operator \(B\), write \(B_{xy}=\langle \delta_x,B\delta_y\rangle\) and let \[\lVert B\rVert_{\mathrm{HS}}^2=\sum_{x,y\in\Omega}\lvert B_{xy}\rvert^2\] be its Hilbert–Schmidt norm squared; \(\lVert B\rVert_{\mathrm{op}}\) denotes its operator norm. The Hilbert–Schmidt norm is independent of the orthonormal basis. For \(S\subseteq[n]=\{1,\ldots,n\}\), set \(\chi_S(x)=\prod_{j\in S}x_j\). These real characters satisfy \[\langle \chi_S,\chi_T\rangle=N\mathbf1_{\{S=T\}},\qquad \chi_S\chi_T=\chi_{S\mathbin\triangle T}.\] Indeed, a nonconstant character sums to zero by pairing vertices that differ in one of its coordinates. The displayed product rule therefore gives orthogonality, and the \(N\) characters form a basis of the \(N\)-dimensional space \(\mathcal H\). Let \[V_k=\operatorname{span}\{\chi_S:\lvert S\rvert\le k\},\qquad 0\le k\le n,\] and set \(V_k=\mathcal H\) for \(k\ge n\). Membership in \(V_k\) means that a function has Fourier degree at most \(k\). The character multiplication rule shows that \(a\in V_r\) and \(b\in V_s\) imply \(\overline b a\in V_{r+s}\). Fix any function \(w:\Omega\to(0,\infty)\), and let \(D\) be multiplication by \(\sqrt w\). The identity \[\langle Da,Db\rangle=\sum_{x\in\Omega}w(x)\overline{a(x)}b(x)\] identifies the weighted inner product with the counting inner product after applying \(D\). We can therefore orthogonalize polynomial degrees for the weight \(w\) while retaining the orthonormal point basis used to count edges. Form the nested subspaces \[K_k=DV_k,\qquad K_{-1}=\{0\},\qquad E_k=K_k\cap K_{k-1}^{\perp}\quad(0\le k\le n).\] Let \(\Pi_k\) be the orthogonal projection onto \(E_k\). The spaces \(K_k\) are nested, and \(K_k=K_{k-1}\oplus E_k\). Since \(D\) is invertible, \(\dim K_k=\dim V_k=\sum_{j=0}^k\binom nj\) and \(K_n=\mathcal H\). Subtracting consecutive dimensions gives \[\mathcal H=\bigoplus_{k=0}^n E_k,\qquad \dim E_k=\binom nk.\] Choosing an orthonormal basis in each \(E_k\) and decomposing the image of each basis vector gives, for every operator \(B\), \[ \lVert B\rVert_{\mathrm{HS}}^2 =\sum_{r,s=0}^n\lVert \Pi_s B\Pi_r\rVert_{\mathrm{HS}}^2. \tag{4}\] Define the grading operator and its centered version by \[ L=\sum_{k=0}^n k\Pi_k,\qquad M=L-\frac n2\mathrm{Id}. \tag{5}\] They are self-adjoint. Their prescribed eigenvalue multiplicities give \[ \lVert M\rVert_{\mathrm{HS}}^2=\sum_{k=0}^n\binom nk\left(k-\frac n2\right)^2 =\frac{nN}{4}. \tag{6}\] The last equality is the variance identity for a sum of \(n\) independent Bernoulli random variables of parameter \(1/2\). Let \(\rho(x,y)\) denote Hamming distance. All pairs of vertices in what follows are ordered. When \(w\equiv1\), the identity \(\sum_{y:\rho(x,y)=1}\chi_S(y)=(n-2\lvert S\rvert)\chi_S(x)\) shows that \(M\) is minus one-half of the cube adjacency matrix. Thus every edge entry has squared modulus \(1/4\); the proof below controls the total deficit from this value for arbitrary positive weights. The key local property is that multiplying by a coordinate connects only equal or adjacent grades. For each \(i\in[n]\), let \(Z_i\) be multiplication by \(x_i\). It is a self-adjoint unitary and commutes with \(D\). Multiplication by \(x_i\) raises Fourier degree by at most one, so \(Z_iK_r\subseteq K_{r+1}\). For \(s>r+1\), the inclusion \(K_{r+1}\subseteq K_{s-1}\) and the orthogonality \(E_s\perp K_{s-1}\) give \(\Pi_sZ_i\Pi_r=0\). Taking adjoints gives the opposite triangular vanishing, so \[ \Pi_sZ_i\Pi_r=0\qquad\text{whenever }\lvert s-r\rvert>1. \tag{7}\] Together with the fixed total energy in (6), this restriction will control the entries of \(M\) between vertices at Hamming distance at least two. Recovering edges from the anticommutatorKeep the grading of Section 3, with no restriction on the positive weight \(w\). For an operator \(H\) that multiplies by a sign, the anticommutator \(MH+HM\) vanishes between opposite signs and multiplies entries of \(M\) by \(2\) or \(-2\) between equal signs. The following lemma turns this observation into an edge count even though an arbitrary weight can change the individual edge entries. Lemma 3 (Recovering edges from the grading). Let \(n\ge1\), \(\Omega=\{-1,1\}^n\), and \(w:\Omega\to(0,\infty)\). Let \(M\) be the centered grading operator (5) constructed from \(w\). For \(h:\Omega\to\{-1,1\}\), let \(H\) be multiplication by \(h\) and set \[\mathcal E_h=\{(x,y)\in\Omega^2:\rho(x,y)=1,\ h(x)=h(y)\}.\] Then, counting ordered pairs, \[ \lvert \mathcal E_h\rvert\le 2\lVert MH+HM\rVert_{\mathrm{HS}}^2. \tag{8}\] Proof. We compare \(M\) with the unweighted grading, whose edge entries have squared modulus \(1/4\). First we show that every edge entry of \(M\) has squared modulus at most \(1/4\). We then bound the sum of the deficits by diagonal energy, which the anticommutator detects for every choice of signs. A bound for each off-diagonal entry. Write \(C_i=[L,Z_i]=[M,Z_i]\), where \([A,B]=AB-BA\). Its grade blocks are \[\Pi_sC_i\Pi_r=(s-r)\Pi_sZ_i\Pi_r.\] We will prove \(\lVert C_i\rVert_{\mathrm{op}}\le1\). The commutator keeps only adjacent-grade blocks, with opposite signs in the two directions. We first remove the equal-grade blocks by a norm-nonincreasing average, then supply those opposite signs, up to a common phase, by unitary conjugation. Introduce the unitaries \[J=\sum_{k=0}^n(-1)^k\Pi_k,\qquad W=\sum_{k=0}^n\mathrm i^k\Pi_k, \qquad \mathrm i^2=-1.\] Set \(O_i=(Z_i-JZ_iJ)/2\). The triangle inequality gives \(\lVert O_i\rVert_{\mathrm{op}}\le(\lVert Z_i\rVert_{\mathrm{op}}+\lVert JZ_iJ\rVert_{\mathrm{op}})/2=1\). In the \((s,r)\) block, the factor defining \(O_i\) is \((1-(-1)^{s+r})/2\). It is zero on the diagonal and one when \(|s-r|=1\). By (7), \(O_i\) therefore consists precisely of the blocks of \(Z_i\) with \(\lvert s-r\rvert=1\). On these blocks, conjugation by \(W\) multiplies by \(\mathrm i^{s-r}=\mathrm i(s-r)\). Therefore \[WO_iW^*=\mathrm i C_i, \qquad\text{and hence}\qquad \lVert C_i\rVert_{\mathrm{op}}\le1.\] In the point basis, \((C_i)_{xy}=(y_i-x_i)M_{xy}\). If \(x\ne y\), choose \(i\) with \(x_i\ne y_i\) to obtain \[2\lvert M_{xy}\rvert=\lvert (C_i)_{xy}\rvert\le\lVert C_i\rVert_{\mathrm{op}}\le1.\] In particular, each neighbor deficit \(1/4-\lvert M_{xy}\rvert^2\) is nonnegative. The total neighbor deficit. The same grade blocks also give an aggregate bound. By (4) and (7), \[\lVert C_i\rVert_{\mathrm{HS}}^2 =\sum_{r,s=0}^n(s-r)^2\lVert \Pi_sZ_i\Pi_r\rVert_{\mathrm{HS}}^2 \le\lVert Z_i\rVert_{\mathrm{HS}}^2=N.\] Summing the squared point-basis entries of \(C_i\) over coordinates gives \[ \sum_{x,y}\rho(x,y)\lvert M_{xy}\rvert^2 =\frac14\sum_{i=1}^n\lVert C_i\rVert_{\mathrm{HS}}^2 \le\frac{nN}{4}=\sum_{x,y}\lvert M_{xy}\rvert^2, \tag{9}\] where the last equality is (6). Set \[A_0=\sum_x\lvert M_{xx}\rvert^2,\qquad F=\sum_{\rho(x,y)\ge2}\lvert M_{xy}\rvert^2.\] The difference between the outermost sums in (9) is \(-A_0+\sum_{\rho(x,y)\ge2}(\rho(x,y)-1)|M_{xy}|^2\le0\). Thus energy beyond neighboring pairs is bounded by diagonal energy: \[ F\le\sum_{\rho(x,y)\ge2}(\rho(x,y)-1)\lvert M_{xy}\rvert^2\le A_0. \tag{10}\] There are \(nN\) ordered neighbor pairs, and thus \[\begin{align*} \sum_{\rho(x,y)=1}\left(\frac14-\lvert M_{xy}\rvert^2\right) &=\frac{nN}{4}-\sum_{\rho(x,y)=1}\lvert M_{xy}\rvert^2\\ &=A_0+F\le2A_0. \tag{11}\end{align*}\] Here we used (6) and (10). The fixed total energy consequently controls the full deficit from the unweighted edge value \(1/4\). Recovering the equal-sign edges. Let \(A_h=\sum_{(x,y)\in\mathcal E_h}\lvert M_{xy}\rvert^2\). Because the individual deficits are nonnegative, their sum over \(\mathcal E_h\) is at most the full sum in (11). Hence \[ \frac{\lvert \mathcal E_h\rvert}4\le A_h+2A_0\le2(A_h+A_0). \tag{12}\] For \(T=MH+HM\) we have \(T_{xy}=(h(x)+h(y))M_{xy}\). On both the diagonal and \(\mathcal E_h\), the squared factor is \(4\), so \[4(A_0+A_h)\le\lVert T\rVert_{\mathrm{HS}}^2.\] Together with (12), this proves (8). ◻ Parity and the binomial couplingWe now choose the weight from the polynomial. Parity will convert the sensitivity problem into the equal-sign edge count of Lemma 3, while the polynomial degree will produce the one-sided constraint needed for Lemma 2. Proof of Theorem 1. We may assume that \(p(x)\ne0\) for every \(x\in\Omega\). Indeed, if \(p\) takes negative values, add a positive constant smaller than \(\min\{\lvert p(x)\rvert:p(x)<0\}\); otherwise add any positive constant. Negative values remain negative, while zero values become positive and positive values stay positive. Thus the perturbation preserves \(f\) under our convention \(\operatorname{sgn}(0)=1\), does not increase the degree, and makes \(p\) nonzero at every vertex. We henceforth use \(p\) for the perturbed polynomial. Let \(\chi=\chi_{[n]}\) be full parity and set \[w=\lvert p\rvert,\qquad h=\chi f,\qquad q=\chi p.\] Full parity changes sign across every edge, so \(h(x)=h(y)\) for neighbors \(x,y\) exactly when \(f(x)\ne f(y)\). Consequently \[ I(f)=\frac{\lvert \mathcal E_h\rvert}N. \tag{13}\] Here both sides count sensitive edges in both directions. We have \(w>0\) and \(hw=q\). Construct the weighted grading (5) from \(w\), and let \(H\) be multiplication by \(h\). Since \(\chi\chi_S=\chi_{[n]\setminus S}\) and \(\deg p\le d\), the Fourier support of \(q\) lies in degrees at least \(n-d\). We claim that \[ \Pi_sH\Pi_r=0\qquad\text{if }r+s<n-d. \tag{14}\] To see this, write elements of \(E_r\subseteq DV_r\) and \(E_s\subseteq DV_s\) as \(Da\) and \(Db\), with \(a\in V_r\) and \(b\in V_s\). Then \[\langle Db,HDa\rangle=\sum_{x\in\Omega}\overline{b(x)}a(x)w(x)h(x) =\sum_{x\in\Omega}\overline{b(x)}a(x)q(x)=0.\] The last equality follows from character orthogonality: the product \(\overline b a\) has Fourier degree at most \(r+s<n-d\). Set \(T=MH+HM\). Its blocks are \[ \Pi_sT\Pi_r=(s+r-n)\Pi_sH\Pi_r. \tag{15}\] Thus the anticommutator energy is a weighted second moment of the sum of the two grade indices: \[\frac1N\lVert T\rVert_{\mathrm{HS}}^2 =\sum_{r,s=0}^n(s+r-n)^2\, \frac{\lVert \Pi_sH\Pi_r\rVert_{\mathrm{HS}}^2}{N}.\] The coefficients on the right define a probability distribution. Indeed, because \(H\) is unitary and the projections are orthogonal, \[\sum_s\lVert \Pi_sH\Pi_r\rVert_{\mathrm{HS}}^2 =\lVert H\Pi_r\rVert_{\mathrm{HS}}^2=\binom nr.\] Decomposing the domain into grades and taking adjoints likewise gives \[\sum_r\lVert \Pi_sH\Pi_r\rVert_{\mathrm{HS}}^2 =\lVert \Pi_sH\rVert_{\mathrm{HS}}^2 =\lVert H^*\Pi_s\rVert_{\mathrm{HS}}^2=\binom ns.\] Since \(\sum_r\binom nr=N\), we may therefore define random indices \(R,S\in\{0,\ldots,n\}\) by \[ \mathbb P\{R=r,S=s\}=\frac1N\lVert \Pi_sH\Pi_r\rVert_{\mathrm{HS}}^2. \tag{16}\] Both marginals are \(\operatorname{Bin}(n,1/2)\), and the preceding energy identity becomes \[\frac1N\lVert T\rVert_{\mathrm{HS}}^2=\mathbb E(R+S-n)^2.\] To use Lemma 2, reflect the first index: put \(U=S\) and \(V=n-R\). Binomial symmetry gives \(U\) and \(V\) the same distribution, with mean \(n/2\) and variance \(n/4\). Meanwhile, (14) gives \(R+S\ge n-d\) almost surely, which becomes \(V-U\le d\). Figure 1 shows how the zero-block region becomes this one-sided support constraint. \[\mathbb P\{R=r,S=s\} =2^{-n}\|\Pi_sH\Pi_r\|_{\mathrm{HS}}^2, \qquad r+s-n=u-v.\] Apply Lemma 2 with \(a=d\) and \(\sigma=\sqrt n/2\) to obtain \[ \frac1N\lVert T\rVert_{\mathrm{HS}}^2 =\mathbb E(R+S-n)^2=\mathbb E(U-V)^2\le4d\sqrt n. \tag{17}\] Finally, (13) and Lemma 3 give \[I(f)=\frac{\lvert \mathcal E_h\rvert}N \le\frac2N\lVert T\rVert_{\mathrm{HS}}^2 \le8d\sqrt n.\] This completes the proof. ◻ Noise sensitivity and agnostic learningThe influence bound has two consequences that are independent of the weighted grading used to prove it. A random-bucketing construction transfers the bound from one-bit changes to independent noise. Smoothing by this noise then gives low-degree polynomial approximants, which yield an agnostic learner by \(L_1\) regression. Noise sensitivityFor \(0\le\eta\le1/2\), define the noise sensitivity \(\operatorname{NS}_{\eta}(f)=\mathbb P\{f(X)\ne f(Y)\}\), where \(X\) is uniform on the cube and \(Y\) is obtained by flipping each coordinate of \(X\) independently with probability \(\eta\). Corollary 4 (Boolean noise sensitivity). Let \(n\ge1\) and \(d\ge0\) be integers. If \(f=\operatorname{sgn}(p)\) on \(\{-1,1\}^n\) for a real polynomial \(p\) of degree at most \(d\), with \(\operatorname{sgn}(0)=1\), then \[\operatorname{NS}_{\eta}(f)\le C d\sqrt\eta \qquad(0<\eta\le1/2),\] where \(C\) is an absolute constant. Proof. Constants have zero noise sensitivity. For an integer \(q\ge2\), use the random-bucketing reduction of Diakonikolas, Raghavendra, Servedio, and Tan [3]: choose independent uniform signs \(a_i\) and independent uniform buckets \(b(i)\in\{1,\ldots,q\}\), and set \[g(z)=f(a_1z_{b(1)},\ldots,a_nz_{b(n)}), \qquad z\in\{-1,1\}^q.\] Multilinearizing the substituted polynomial preserves its cube values, including zeros, and gives degree at most \(\min(d,q)\). Theorem 1 therefore gives \(I(g)\le8d\sqrt q\); a constant substitution contributes zero. Independently choose uniform \(z\in\{-1,1\}^q\) and \(J\in\{1,\ldots,q\}\). Put \(X_i=a_i z_{b(i)}\) and \(Y_i=X_i(-1)^{\mathbf1_{\{b(i)=J\}}}\). Conditional on \(J\), the flip indicators are independent Bernoulli variables of parameter \(1/q\), and their joint law does not depend on \(J\). Conditional on \(b,J,z\), the random signs make \(X\) uniform, so \(X\) is independent of the flip vector. Thus \((X,Y)\) has exactly the noise law at rate \(1/q\). Since replacing \(z\) by \(z^{\oplus J}\) produces \(Y\), averaging first over \(z,J\) gives \[\operatorname{NS}_{1/q}(f)=\frac{\mathbb E_{a,b}I(g)}q \le\frac{8d}{\sqrt q}.\] For the rest of this section, Fourier coefficients and \(L_1,L_2\) norms are normalized by uniform probability on the cube. In particular, \(\widehat f(S)=\mathbb E[f(X)\chi_S(X)]\) and \[\operatorname{NS}_{\eta}(f) =\frac12\sum_{S\subseteq[n]} \bigl(1-(1-2\eta)^{|S|}\bigr)\widehat f(S)^2.\] This expression is nondecreasing for \(0\le\eta\le1/2\). Taking \(q=\lfloor1/\eta\rfloor\), so that \(\eta\le1/q\le1/2\) and \(q\ge1/(2\eta)\), proves the claim with \(C=8\sqrt2\). ◻ For comparison, Kane proved an absolute \(O(d\sqrt\varepsilon)\) noise sensitivity bound for degree-\(d\) polynomial threshold functions under standard Gaussian noise [7]. Here \(0<\varepsilon\le1\), and the input pair is \(X\) and \((1-\varepsilon)X+\sqrt{2\varepsilon-\varepsilon^2}\,Z\), with \(X,Z\) independent standard Gaussian vectors. His proof counts sign changes along Gaussian rotations. Corollary 4 gives the same dependence on degree and noise rate for independent coordinate flips on the Boolean cube. Agnostic learningIn agnostic learning the labels may be arbitrary: the objective is to predict nearly as well as the best function in a specified class. We use the \(L_1\) polynomial regression method of Kalai, Klivans, Mansour, and Servedio [6], which was applied to polynomial threshold functions in [3]. Corollary 5 (Uniform-marginal agnostic learning). Let \(n,d\ge1\) be integers, and let \(\mathcal C_{n,d}\) be the class of functions \(\operatorname{sgn}(p)\) on \(\{-1,1\}^n\) with \(\deg p\le d\). Let \(D\) be any distribution on \(\{-1,1\}^n\times\{-1,1\}\) whose first marginal is uniform, and set \[\mathrm{OPT}=\min_{f\in\mathcal C_{n,d}}\mathbb P_{(X,Y)\sim D}\{f(X)\ne Y\}.\] There is an absolute constant \(A\) such that, for \(0<\alpha,\delta<1\), a learner using independent labeled samples from \(D\) returns, with probability at least \(1-\delta\), a Boolean hypothesis \(h\) satisfying \[\mathbb P_{(X,Y)\sim D}\{h(X)\ne Y\}\le\mathrm{OPT}+\alpha.\] Its running time and sample size are polynomial in \((n+1)^k\), \(1/\alpha\), and \(\log(1/\delta)\), where \[k=\min\left\{n,\left\lceil A d^2\alpha^{-2}\log(4/\alpha)\right\rceil\right\}.\] The labels are unrestricted, and \(h\) need not belong to \(\mathcal C_{n,d}\). Proof. We first construct an \(L_1\) approximant to each \(f\in\mathcal C_{n,d}\). For \(0<\eta<1/2\) and \(\rho=1-2\eta\), the noise operator is \[T_\rho f=\sum_{S\subseteq[n]}\rho^{|S|}\widehat f(S)\chi_S.\] Equivalently, \(T_\rho f(x)\) is the expected value of \(f\) after independent noise of rate \(\eta\) is applied to \(x\). Since \(f\) is Boolean and \(T_\rho f\) takes values in \([-1,1]\), \(|f-T_\rho f|=1-fT_\rho f\) pointwise. Corollary 4 therefore gives, with \(C=8\sqrt2\), \[\lVert f-T_\rho f\rVert_1=2\operatorname{NS}_\eta(f)\le2Cd\sqrt\eta.\] Take \(\eta=(\alpha/(8Cd))^2\) and \(K=\lceil\log(4/\alpha)/(2\eta)\rceil\). Let \(q\) be the Fourier truncation of \(T_\rho f\) to degrees at most \(\min(K,n)\). If \(K<n\), Parseval’s identity gives \[\lVert T_\rho f-q\rVert_1\le\lVert T_\rho f-q\rVert_2 \le\rho^{K+1}\le e^{-2\eta(K+1)}\le\alpha/4;\] if \(K\ge n\), the truncation error is zero. The first error is also at most \(\alpha/4\), so \[ \lVert f-q\rVert_1\le\alpha/2. \tag{18}\] Taking \(A=32C^2\) makes \(\min(K,n)=k\) in the statement. For completeness, we explain how this direct \(L_1\) estimate enters the regression argument of [6]. Use the \(M=\sum_{j=0}^k\binom nj\le(n+1)^k\) characters of degree at most \(k\) as features. On a training sample \(Z\) of size \(m\), fit a polynomial \(P\) in these features by minimizing empirical absolute loss, then choose \(t\in[-1,1]\) to minimize the empirical error of \(h=\operatorname{sgn}(P-t)\). The fit is a linear program, and the threshold is found by sorting the fitted values. Write \(\widehat{\mathbb E}_Z\) and \(\widehat{\operatorname{err}}_Z\) for empirical means and errors. A uniformly random threshold has error at most half the absolute loss, so the minimizing threshold satisfies \[\widehat{\operatorname{err}}_Z(h) \le\tfrac12\widehat{\mathbb E}_Z|Y-P(X)| \le\tfrac12\widehat{\mathbb E}_Z|Y-q(X)|.\] Choose an optimal \(f\in\mathcal C_{n,d}\) and its fixed approximant \(q\). The triangle inequality and (18) imply \(\mathbb E_Z\widehat{\operatorname{err}}_Z(h)\le\mathrm{OPT}+\alpha/4\). These hypotheses are halfspaces in the \(M\) character features, so their VC dimension is at most \(M+1\). The usual expected uniform generalization bound, as used in [6], makes \(\mathbb E_Z\operatorname{err}_D(h)\le\mathrm{OPT}+3\alpha/8\) for \(m\) polynomial in \(M\) and \(1/\alpha\). Apply Markov’s inequality to the nonnegative random variable \(\operatorname{err}_D(h)\). Since \(\mathrm{OPT}\le1\) and \(\alpha<1\), \[\mathbb P_Z\{\operatorname{err}_D(h)>\mathrm{OPT}+\alpha/2\} \le\frac{\mathrm{OPT}+3\alpha/8}{\mathrm{OPT}+\alpha/2} \le1-\alpha/12.\] Thus one trial succeeds with probability at least \(\alpha/12\). Repeat independently \(r=\lceil(12/\alpha)\log(2/\delta)\rceil\) times. With probability at least \(1-\delta/2\), one candidate has this error. On an independent validation sample of size \(\lceil8\alpha^{-2}\log(4r/\delta)\rceil\), Hoeffding’s inequality and a union bound estimate all \(r\) errors within \(\alpha/4\), except with probability \(\delta/2\). Selecting the best validation score therefore gives error at most \(\mathrm{OPT}+\alpha\). All the training, regression, repetition and validation costs have the stated polynomial bounds. ◻
|
| ||||||||
|