OctoInformBeta

Average sensitivity of polynomial threshold functions

For x∈{−1,1}nx\in\{-1,1\}^n and 1≤i≤n1\le i\le n, let x⊕ix^{\oplus i} be the vertex obtained from xx by reversing coordinate ii. The average sensitivity of a function ff on {−1,1}n\{-1,1\}^n is I(f)=2−n∑i=1n|{x∈{−1,1}n:f(x)≠f(x⊕i)}|I(f)=2^{-n}\sum_{i=1}^n\bigl|\{x\in\{-1,1\}^n: f(x)\ne f(x^{\oplus i})\}\bigr|. It is also called the total influence of ff. Throughout, sgn⁡(t)=1\operatorname{sgn}(t)=1 for t≥0t\ge0 and sgn⁡(t)=−1\operatorname{sgn}(t)=-1 for t<0t<0. A real polynomial is multilinear when no variable appears in it with an exponent larger than one. On the cube, the identities xi2=1x_i^2=1 turn every real polynomial into a multilinear polynomial of no larger degree with the same values. A polynomial threshold function of degree at most dd is a function f=sgn⁡(p)f=\operatorname{sgn}(p) on {−1,1}n\{-1,1\}^n, where pp is a real multilinear polynomial of degree at most dd. The question is how large the average sensitivity of a polynomial threshold function can be, in terms of its degree dd and the dimension nn.

The levels of the cube are the sets of vertices on which x1+⋯+xnx_1+\cdots+x_n takes a fixed value. Gotsman and Linial proposed that, among polynomial threshold functions of degree dd in nn variables, the average sensitivity is largest for the sign of a degree-dd polynomial in x1+⋯+xnx_1+\cdots+x_n whose roots lie between levels of the cube. Chapman constructed counterexamples to this exact assertion. He distinguished it from the asymptotic form I(f)=O(dn)I(f)=O(d\sqrt n) of the conjecture of Gotsman and Linial. Kim, Maldonado, and Wellens independently constructed quadratic counterexamples for odd n≥5n\ge5. The classical symmetric examples are the signs of suitable degree-dd polynomials in x1+⋯+xnx_1+\cdots+x_n. For 1≤d≤n1\le d\le\sqrt n they have average sensitivity of order dnd\sqrt n. For n>1n>1, Harsha, Klivans, and Meka proved that every polynomial threshold function ff of degree at most dd on {−1,1}n\{-1,1\}^n satisfies I(f)≤2O(d)n1−1/(4d+6)I(f)\le2^{O(d)}n^{1-1/(4d+6)}. In independent work, Diakonikolas, Raghavendra, Servedio, and Tan proved I(f)≤2O(d)(log⁡n)n1−1/(4d+2)I(f)\le2^{O(d)}(\log n)\,n^{1-1/(4d+2)}. Kane then reached the square-root exponent in the dimension, proving I(f)≤n(log⁡n)O(dlog⁡d)2O(d2log⁡d)I(f)\le\sqrt n\,(\log n)^{O(d\log d)}2^{O(d^2\log d)} for n>1n>1.

The preprint proves that for integers n≥1n\ge1 and 1≤d≤n1\le d\le n, every polynomial threshold function ff of degree at most dd on {−1,1}n\{-1,1\}^n satisfies I(f)≤8dnI(f)\le8d\sqrt n. This bound establishes the asymptotic form of the conjecture of Gotsman and Linial with an absolute constant. From it the preprint derives a dimension-free noise sensitivity bound and an agnostic learning guarantee, neither of which the Lean library contains.

The Lean library GotsmanLinial proves I(sgn⁡p)≤8dnI(\operatorname{sgn} p)\le8d\sqrt n for every real multilinear polynomial pp in nn variables of degree at most dd, for all natural numbers nn and dd, without the preprint’s restriction to n≥1n\ge1 and 1≤d≤n1\le d\le n. Lean has checked every result of the Lean library, so the Lean library is the reference: the results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names. The Lean library takes no result as a hypothesis.

The Lean library: GotsmanLinial

GotsmanLinial is a Lean library: 13 items, in five groups. Each has a page written by OctoInform, listed below.