Take the 2-minute tour ×

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

1 Answer 1

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

Your Answer


