Efron-Stein inequality

Let $X_1,\dots ,X_n$ be independent random variables and let $f:{\mathcal{X}}^n\to \mathbb{R}$ obey $\mathbb{E}[f^2(X)]<\infty$ where $X=(X_1,\dots ,X_n)$. The Efron-Stein inequality states that,

$$\mathbb{V}(f(X))\le \underset{f_i}{\inf }\sum _{i=1}^n\mathbb{E}[(f(X)-\mathbb{E}[f(X)|X^{(i)}]{)}^2]=v,$$

where the infimum is over all such functions $f_i$. We can write $v$ in several different ways. First we can write it as a function of $f$ acting on iid copies:

$$v=\frac{1}{2}\sum _{i=1}^n\mathbb{E}[(f(X)-f({\mathbf{X}}_i^{\prime }){)}^2],$$

where ${\mathbf{X}}_i^{\prime }=(X_1,\dots ,X_{i-1},X_i^{\prime },X_{i+1},\dots ,X_n)$ and $X_i^{\prime }$ is an iid copy of $X_i$. Next we can write it as

$$v=\underset{f_i}{\inf }\sum _{i=1}\mathbb{E}[(f(X)-f_i(X^{(i)}{)}^2],$$

where $f_i:{\mathcal{X}}^{n-1}\to \mathbb{R}$ and the infimum is over all such functions.

todo figure out some way to remember this/why it’s useful/what’s the intuition.

References

• Concentration Inequalities by Boucheron, Lugosi, Massart, Chapter 3.1