6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks @Kaveh, I was wondering what top level tag to add and couldn't think of one :) $\endgroup$ – Suresh Venkat Sep 12 '11 at 22:03
  • 4
    $\begingroup$ 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. $\endgroup$ – Mahdi Cheraghchi Sep 12 '11 at 23:23
  • $\begingroup$ Thanks @MCH, I'll check that reference out. Maybe make it an answer so I can upvote ? $\endgroup$ – Suresh Venkat Sep 13 '11 at 10:50
  • $\begingroup$ Just made it an answer. $\endgroup$ – Mahdi Cheraghchi Sep 13 '11 at 14:45
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.