<p>One possible definition for a given point and ϵ would be the following: perturb each coordinate of the input independently with a Gaussian with mean 0 and variance $\epsilon^2/n$ and then look at the variance of the function's value with respect to this input distribution. It's also possible to perturb a specific coordinate this way and keep the rest fixed, depending on your application.</p>

<p>You may also find this paper of interest: "Noise stability of functions with low influences: invariance and optimality" by E. Mossel, R. O'Donnell, K. Oleszkiewicz.</p>

CC BY-SA 3.0
2011-09-13T14:45:21.937Z
2011-09-13T14:45:21.937Z
Mahdi Cheraghchi
<p>If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a single bit of $w$ and changing the value of $f$. The sensitivity of $f, s(f)$ is then the maximum sensitivity with respect to any $w \in \{0,1\}^n$.</p>

<p>If on the other hand we're given a real-valued function $f : \mathbb{R}^n \rightarrow \mathbb{R}$, we can talk about its Lipschitz constants: specifically, the maximum value (wrt $x,\epsilon$) of the ratio $\frac{|f(x+\epsilon) - f(x)|}{\epsilon}$ as a kind of "smooth sensitivity".</p>

<p>What if we combine the two ? Suppose we have a function that takes parameters in a continuous domain, but whose output is discrete (one example might be a binary classifier, where the function is the sign of an appropriate hyperplane evaluation for example). Is there a natural notion that captures sensitivity in such a setting ? Boolean sensitivity doesn't work itself because you have to choose how much to perturb the inputs. Smooth perturbations don't quite work because the function is not continuous, and so any ratio would be rather unstable. </p>

<p>I suspect that either such a notion is very well known, or follows directly from the above, and so I'd be grateful for suggestions to reformulate the question/make it more precise. </p>

CC BY-SA 3.0
2011-09-12T22:03:12.243Z
Thanks @Kaveh, I was wondering what top level tag to add and couldn't think of one :)
Suresh Venkat
CC BY-SA 3.0
2011-09-12T23:23:59.177Z
One possible definition for a given point and $\epsilon$ would be the following: perturb each coordinate of the input independently with a Gaussian with mean 0 and variance $\epsilon^2/n$ and then look at the variance of the function's value with respect to this input distribution. It's also possible to perturb a specific coordinate this way and keep the rest fixed, depending on your application. You may also find this paper of interest: "Noise stability of functions with low influences: invariance and optimality" by E. Mossel, R. O'Donnell, K. Oleszkiewicz.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-09-13T10:50:08.733Z
Thanks @MCH, I'll check that reference out. Maybe make it an answer so I can upvote ?
Suresh Venkat
CC BY-SA 3.0
2011-09-13T14:45:40.110Z
Just made it an answer.
Mahdi Cheraghchi
<co.combinatorics><terminology><boolean-functions><function>
Combining (block)-sensitivity and Lipschitz conditions?
Suresh Venkat
# Combining (block)-sensitivity and Lipschitz conditions?

(Asked by: username_0 on 2011-09-12)

If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a single bit of $w$ and changing the value of $f$. The sensitivity of $f, s(f)$ is then the maximum sensitivity with respect to any $w \in \{0,1\}^n$.

If on the other hand we're given a real-valued function $f : \mathbb{R}^n \rightarrow \mathbb{R}$, we can talk about its Lipschitz constants: specifically, the maximum value (wrt $x,\epsilon$) of the ratio $\frac{|f(x+\epsilon) - f(x)|}{\epsilon}$ as a kind of "smooth sensitivity".

What if we combine the two ? Suppose we have a function that takes parameters in a continuous domain, but whose output is discrete (one example might be a binary classifier, where the function is the sign of an appropriate hyperplane evaluation for example). Is there a natural notion that captures sensitivity in such a setting ? Boolean sensitivity doesn't work itself because you have to choose how much to perturb the inputs. Smooth perturbations don't quite work because the function is not continuous, and so any ratio would be rather unstable.

I suspect that either such a notion is very well known, or follows directly from the above, and so I'd be grateful for suggestions to reformulate the question/make it more precise.

**Tags:** co.combinatorics, terminology, boolean-functions, function

> **Comments:**
> **username_0**: Thanks @Kaveh, I was wondering what top level tag to add and couldn't think of one :)  
> **username_1**: One possible definition for a given point and $\epsilon$ would be the following: perturb each coordinate of the input independently with a Gaussian with mean 0 and variance $\epsilon^2/n$ and then look at the variance of the function's value with respect to this input distribution. It's also possible to perturb a specific coordinate this way and keep the rest fixed, depending on your application. You may also find this paper of interest: "Noise stability of functions with low influences: invariance and optimality" by E. Mossel, R. O'Donnell, K. Oleszkiewicz.  
> **username_0**: Thanks @MCH, I'll check that reference out. Maybe make it an answer so I can upvote ?  
> **username_1**: Just made it an answer.  

---

## 1 answers

### Answer by username_1 on 2011-09-13. Score: 4 | Accepted answer

One possible definition for a given point and ϵ would be the following: perturb each coordinate of the input independently with a Gaussian with mean 0 and variance $\epsilon^2/n$ and then look at the variance of the function's value with respect to this input distribution. It's also possible to perturb a specific coordinate this way and keep the rest fixed, depending on your application.

You may also find this paper of interest: "Noise stability of functions with low influences: invariance and optimality" by E. Mossel, R. O'Donnell, K. Oleszkiewicz.


---

