3
$\begingroup$

I am trying to characterize the sensitivity of a function $f: R^N\to{}R$ to the perturbations in the input vector $\mathbb{x}=\left[x_1,\dots{}x_N\right]$. For that purpose, I evaluate Cramer-Rao bound for Gaussian i.i.d. arguments.

The function has a singularity at the point $\mathbb{x}_0$ where $f(\mathbb{x}_0)=0$, in the sense that $\|\nabla{}f\|\sim{}1/f$ as $\mathbb{x}\to\mathbb{x}_0$

The Cramer-Rao bound then doesn't make sense, because it diverges at $\mathbb{x}_0$, while the variance of $f$, obviously, remains bounded. What I am looking for, I guess, some type of "concentration of measure"/"deviation inequality"-type sharp bound on the variance of $f$.

The literature on concentration of measure phenomenon is extensive and deals with fairly advanced topics, whereas I am looking for something rather more basic. If you could point towards some starting point, your help will be appreciated.

Improve this question
$\endgroup$
8
  • $\begingroup$ @tristes_tigres The hypothesis that $\|\nabla f(\mathbb{x})\|\to0$ and $f(\mathbb{x})\to0$ with $\|\nabla f(\mathbb{x})\|/f(\mathbb{x})\to1$ when $\mathbb{x}\to0$, is strange. Is this what you wanted to write? $\endgroup$
    – Did
    Feb 8, 2011 at 18:14
  • $\begingroup$ Didier - I mean that $f(\mathbf{x})=(\nabla{}f)\cdot{(\mathbf{x}-\mathbf{x}_0)}+O((\mathbf{x}-\mathbf{x}_0)^2)$ near $\mathbf{x}_0$, but my notation was somewhat erroneous. Fixed that. $\endgroup$
    – Mikhail Kagalenko
    Feb 8, 2011 at 20:26
  • $\begingroup$ The function is defined implicitly, so I mixed different gradients $\endgroup$
    – Mikhail Kagalenko
    Feb 8, 2011 at 20:33
  • $\begingroup$ @t_t The hypothesis $\|\nabla f\| f\to1$ is even stranger. If you want to say that $f$ is $C^2$ and that $\nabla f(\mathbb{x}_0)=\mathbb{0}$, you could just say so. $\endgroup$
    – Did
    Feb 8, 2011 at 22:57
  • $\begingroup$ Didier - It's not a hypothesis, it's a property of the specific function that I am analyzing. $\endgroup$
    – Mikhail Kagalenko
    Feb 8, 2011 at 23:22

1 Answer 1

Reset to default
2
$\begingroup$

Let $X_i$ and $X'_i$ be i.i.d random variables. Write $f = f(X_1, \dots, X_n),$ and define $$f_i = f(X_1, \dots, X'_i, \dots, X_n)$$ as the same function with the $i$th input replaced by the independent copy $X'_i$.

The Efron-Stein inequality states that $$\operatorname{Var}(f) \le \tfrac 1 2\sum_{i=1}^n \ \mathbb E(f - f_i)^2.$$

Since your random variables are Gaussians, the system satisfies the Poincaré inequality too: $$\operatorname{Var}(F) \le C \ \mathbb E |\nabla f|^2.$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. I'll need some time to digest the references, and not citing articles behind the paywall is definitely welcome :) $\endgroup$
    – Mikhail Kagalenko
    Feb 8, 2011 at 22:39
  • 2
    $\begingroup$ I mean, thank you for citing freely accessible articles $\endgroup$
    – Mikhail Kagalenko
    Feb 8, 2011 at 22:40
  • $\begingroup$ Right off the bat, the trouble with using Poincare inequality is that in my case, $\|\nabla{}f\|\to\infty$ at $\mathbb{x}_0$, so it's hard to see, how to get a useful bound from it. The actual analytic expression for $\mathbb{E}|\nabla{}f|^2$ doesn't seem to be easier to find than that for the $\mathbb{E}|f|^2$ $\endgroup$
    – Mikhail Kagalenko
    Feb 8, 2011 at 23:06
  • $\begingroup$ Although, may be I get, what you mean with Poincare inequality. Perhaps, it could do the job. $\endgroup$
    – Mikhail Kagalenko
    Feb 9, 2011 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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