Difference between revisions of "Noise sensitivity"
Or elmackias (talk | contribs) (→Properties) |
|||
| (7 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
| − | For <math>f:\{-1,1\}^{n}\longrightarrow\{-1,1\}</math> and <math>\delta\in[0,1]</math>, the noise sensitivity of <math>f</math> at <math>\delta</math>, <math> | + | === Uniform case === |
| + | For <math>f:\{-1,1\}^{n}\longrightarrow\{-1,1\}</math> and <math>\delta\in[0,1]</math>, the '''noise sensitivity''' of <math>f</math> at <math>\delta</math>, <math>\mathbf{NS}_{\delta}[f]</math>, is the probability that <math>f(x)\neq f(y)</math> when <math>x\sim\{-1,1\}^{n}</math> is uniformly random and <math>y</math> is formed from <math>x</math> by reversing each bit independently with probability <math>\delta</math>: | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math>\mathbf{NS}_{\delta}[f] = \mathbb{P}[f(x)\neq f(y)]</math> | ||
| + | |} | ||
| + | |||
| + | A series of functions <math>f_n:\{-1,1\}^n \to \{-1,1\}</math> is said to be '''noise sensitive''' if for every <math>\delta > 0</math>, we have <math>\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 \to 0</math> as <math>n \to \infty </math>. | ||
| + | |||
| + | === <math>p</math>-biased case === | ||
| + | A similar concept can be defined for a <math>p</math>-biased measure, i.e when the random vector <math>x</math> has iid entries which are 1 with probability <math>p</math> and 0 with probability <math>1-p</math>. In this case, the random vector <math>y</math> is defined so that the bit 1 is reversed with probability <math>2\delta p</math> and the bit 0 is reversed with probability <math>2\delta (1-p)</math>. (the definition only makes sense for <math>\delta</math> which doesn't make the probability larger than 1). | ||
| + | |||
| + | A series of functions <math>f_n:\{-1,1\}^n \to \{-1,1\}</math> is then said to be '''noise sensitive''' with respect to <math>p_n</math> if for every <math>\delta > 0</math>, we have <math>\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 \to 0</math> as <math>n \to \infty </math>. | ||
== Properties == | == Properties == | ||
| − | *The connection between noise sensitivity and [[ | + | *The connection between noise sensitivity and [[stability]] is given by <math>\mathbf{NS}_{\delta}[f]=\frac{1}{2}-\frac{1}{2}Stab_{1-2\delta}[f]</math>. <ref>Ryan O'Donnell, Analysis of Boolean functions, Chapter 2.4 [http://www.contrib.andrew.cmu.edu/~ryanod/?p=2245]</ref> |
| − | *For <math>\delta\leq\frac{1}{2}</math>, and <math>f</math> is [[ | + | *For <math>\delta\leq\frac{1}{2}</math>, and <math>f</math> is [[linear threshold]] function (<math>f(x)=sgn(\sum_{i=1}^{n}\omega_{i}x_{i}-t)</math>), then <math>\mathbf{NS}_{\delta}[f]\leq2\delta^{1/2}</math>. furthermore, <math>\underset{\delta\rightarrow0}{\limsup}\frac{\limsup_{n\rightarrow\infty}\sup_{\omega,t}\mathbf{NS}_{\delta}[f]}{\sqrt{\delta}}\leq\sqrt{\frac{2}{\pi}}</math>. <ref>Peres (2004). "Noise Stability of Weighted Majority" [http://www.contrib.andrew.cmu.edu/~ryanod/?p=2245]</ref> |
| + | * The noise sensitivity can be lower-bounded by the total [[influence]] of a function: <math>\mathbf{NS}_{1/n}(f) \geq \mathrm{Inf}(f)/ne</math>.<ref>Prahladh Harsha, Adam Klivans, Raghu Meka, [http://theoryofcomputing.org/articles/v010a001/v010a001.pdf Bounding the Sensitivity of Polynomial Threshold Functions], Lemma 8.1</ref> | ||
== References == | == References == | ||
| − | < | + | <references/> |
| − | |||
Latest revision as of 08:24, 2 November 2020
Definition
Uniform case
For [math]f:\{-1,1\}^{n}\longrightarrow\{-1,1\}[/math] and [math]\delta\in[0,1][/math], the noise sensitivity of [math]f[/math] at [math]\delta[/math], [math]\mathbf{NS}_{\delta}[f][/math], is the probability that [math]f(x)\neq f(y)[/math] when [math]x\sim\{-1,1\}^{n}[/math] is uniformly random and [math]y[/math] is formed from [math]x[/math] by reversing each bit independently with probability [math]\delta[/math]:
[math]\mathbf{NS}_{\delta}[f] = \mathbb{P}[f(x)\neq f(y)][/math]
A series of functions [math]f_n:\{-1,1\}^n \to \{-1,1\}[/math] is said to be noise sensitive if for every [math]\delta \gt 0[/math], we have [math]\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 \to 0[/math] as [math]n \to \infty [/math].
[math]p[/math]-biased case
A similar concept can be defined for a [math]p[/math]-biased measure, i.e when the random vector [math]x[/math] has iid entries which are 1 with probability [math]p[/math] and 0 with probability [math]1-p[/math]. In this case, the random vector [math]y[/math] is defined so that the bit 1 is reversed with probability [math]2\delta p[/math] and the bit 0 is reversed with probability [math]2\delta (1-p)[/math]. (the definition only makes sense for [math]\delta[/math] which doesn't make the probability larger than 1).
A series of functions [math]f_n:\{-1,1\}^n \to \{-1,1\}[/math] is then said to be noise sensitive with respect to [math]p_n[/math] if for every [math]\delta \gt 0[/math], we have [math]\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 \to 0[/math] as [math]n \to \infty [/math].
Properties
- The connection between noise sensitivity and stability is given by [math]\mathbf{NS}_{\delta}[f]=\frac{1}{2}-\frac{1}{2}Stab_{1-2\delta}[f][/math]. [1]
- For [math]\delta\leq\frac{1}{2}[/math], and [math]f[/math] is linear threshold function ([math]f(x)=sgn(\sum_{i=1}^{n}\omega_{i}x_{i}-t)[/math]), then [math]\mathbf{NS}_{\delta}[f]\leq2\delta^{1/2}[/math]. furthermore, [math]\underset{\delta\rightarrow0}{\limsup}\frac{\limsup_{n\rightarrow\infty}\sup_{\omega,t}\mathbf{NS}_{\delta}[f]}{\sqrt{\delta}}\leq\sqrt{\frac{2}{\pi}}[/math]. [2]
- The noise sensitivity can be lower-bounded by the total influence of a function: [math]\mathbf{NS}_{1/n}(f) \geq \mathrm{Inf}(f)/ne[/math].[3]
