Difference between revisions of "Noise sensitivity"
m |
(→Properties) |
||
| Line 5: | Line 5: | ||
*The connection between noise sensitivity and [[Stability]] is given by <math>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> | *The connection between noise sensitivity and [[Stability]] is given by <math>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 [[Linear threshold]] function (<math>f(x)=sgn(\sum_{i=1}^{n}\omega_{i}x_{i}-t)</math>), then <math>NS_{\delta}[f]\leq2\delta^{1/2}</math>. furthermore, <math>\underset{\delta\rightarrow0}{\limsup}\frac{\limsup_{n\rightarrow\infty}\sup_{\omega,t}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> | *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>NS_{\delta}[f]\leq2\delta^{1/2}</math>. furthermore, <math>\underset{\delta\rightarrow0}{\limsup}\frac{\limsup_{n\rightarrow\infty}\sup_{\omega,t}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/> | <references/> | ||
Revision as of 06:29, 30 October 2020
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]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].
Properties
- The connection between noise sensitivity and Stability is given by [math]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]NS_{\delta}[f]\leq2\delta^{1/2}[/math]. furthermore, [math]\underset{\delta\rightarrow0}{\limsup}\frac{\limsup_{n\rightarrow\infty}\sup_{\omega,t}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]
