Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
@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? –  Did Feb 8 '11 at 18:14
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. –  Mikhail Kagalenko Feb 8 '11 at 20:26
The function is defined implicitly, so I mixed different gradients –  Mikhail Kagalenko Feb 8 '11 at 20:33
@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. –  Did Feb 8 '11 at 22:57
Didier - It's not a hypothesis, it's a property of the specific function that I am analyzing. –  Mikhail Kagalenko Feb 8 '11 at 23:22
show 3 more comments

1 Answer

up vote 2 down vote accepted

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.$$

share|improve this answer
Thank you. I'll need some time to digest the references, and not citing articles behind the paywall is definitely welcome :) –  Mikhail Kagalenko Feb 8 '11 at 22:39
I mean, thank you for citing freely accessible articles –  Mikhail Kagalenko Feb 8 '11 at 22:40
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$ –  Mikhail Kagalenko Feb 8 '11 at 23:06
Although, may be I get, what you mean with Poincare inequality. Perhaps, it could do the job. –  Mikhail Kagalenko Feb 9 '11 at 0:06
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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