Codex @codex  0

Charles M. Stein changed the theory of estimation by showing that estimating several normal means together can permit improvement over their separate usual estimates under a combined squared-error loss. The James–Stein estimator expresses this phenomenon through shrinkage: introducing bias can lower the total mean squared error when variance is reduced sufficiently. The guarantee concerns the specified aggregate loss, rather than promising a better estimate for every coordinate in every dataset.

Stein also developed tools connecting normal distributions, derivatives and probability approximations. With Bradley Efron, he coauthored The Jackknife Estimate of Variance by Bradley Efron and Charles M. Stein, a source associated with the Efron–Stein inequality. His Stanford obituary records his mathematical career and death in 2016.^[ref]

The Efron–Stein inequality bounds the variance of a complicated output by the effect of replacing one input at a time. Let $X_1,\dots ,X_n$ be mutually independent random variables, not necessarily identically distributed, and $Z=f(X_1,\dots ,X_n)$ for a measurable function $f$, with $\mathbb{E}{Z}^2<\infty$. Take $X_1^{\prime },\dots ,X_n^{\prime }$ with $X_i^{\prime }$ having the same probability distribution as $X_i$, all $2n$ inputs mutually independent. DefineUse the same function $f$, keeping every other input fixed. ThenThe expected value averages over both the original inputs and their replacements. An infinite right side gives a trivial bound; under the stated square-integrable condition every term is finite.^[ref]

For a concrete four-state example, take independent Bernoulli random variables with $\mathbb{P}(X_1=1)=0.3$ and $\mathbb{P}(X_2=1)=0.6$, and set $Z=\max \{X_1,X_2\}$. This output records whether either input is one. The states $(0,0),(1,0),(0,1),(1,1)$ have respective probabilities $0.28,0.12,0.42,0.18$, soReplacing $X_1$ changes $Z$ only when $X_2=0$ and $X_1^{\prime }\ne X_1$. A fresh Bernoulli draw can repeat the old value: the replacement is not a forced flip. By independence, the expected value of the squared change isSimilarly,Thus Efron–Stein inequality gives $0.2016\le (0.168+0.336)/2=0.252$. The larger second contribution reflects both its replacement probability and how often the other input leaves the output sensitive to it.

For the same inputs, consider instead $W=X_1+2X_2$. The variance of a sum of independent random variables givesHere $\mathbb{E}[(W-W_1^{\prime }{)}^2]=0.42$ and $\mathbb{E}[(W-W_2^{\prime }{)}^2]=1.92$, so the Efron–Stein inequality is exact: $(0.42+1.92)/2=1.17$. More generally, for $W=c+{\sum }_i{g}_i(X_i)$ with square-integrable summands, each contribution $\frac{1}{2}\mathbb{E}[(W-W_i^{\prime }{)}^2]$ equals $\mathrm{Var}(g_i(X_i))$ and these variances add exactly.

Independence is essential. Let $X_1=X_2=B$ for a single Bernoulli random variable with parameter $1/2$, and take $W=X_1+X_2=2B$. Its variance is one. If each coordinate is nevertheless replaced by an independent draw from its marginal Bernoulli distribution, each squared-change expected value is $1/2$, giving the false proposed upper bound $1/2$. Replacement now creates off-diagonal states $(0,1)$ and $(1,0)$ that the original input never visits. The original coordinates fail the hypothesis of Efron–Stein inequality.

The attraction is local calculation: a function may involve many inputs, yet changing one can have a simple effect. Each half squared-change expected value supplies a coordinate's contribution to an upper budget for the total variance. Applying Chebyshev's inequality then bounds a tail probability using that budget. These contributions need not partition the actual variance, as the maximum example shows.

The name commemorates Bradley Efron and Charles M. Stein. Their 1981 paper The Jackknife Estimate of Variance appeared in The Annals of Statistics, volume 9, issue 3, pp. 586–596.^[ref]

The entropy method for certifiable functions turns short certificates into bounds on coordinate sensitivity. Suppose a nonnegative integer-valued certifiable function $f$ changes by at most $L$ when one coordinate changes and has certificates of size at most $g(k)$ at value $k$. Define the coordinate-deleted functionsassuming these functions are measurable. At an input of value $k$, changing a coordinate outside a chosen certificate cannot reduce the value below $k$. Hence $f_i=f$ outside that certificate, while $0\le f-f_i\le L$ on it. ConsequentlyFor independent random variables, the Efron–Stein inequality already gives $\mathrm{Var}(f(X))\le L^2\mathbb{E}g(f(X))$. When $L=1$ and $g(k)=k$, the stronger bound ${\sum }_i(f-f_i)\le f$ makes $f$ a self-bounding function. Tensorization of entropy and a modified logarithmic Sobolev inequality control exponential rather than quadratic variation, producing concentration inequalities. The certificate size alone needs this coordinate-change bound; an arbitrarily large change in one coordinate is not controlled by a short certificate.

Write $X_{-i}$ for all coordinates except $X_i$, let $X_i^{\prime }$ be an independent random variable with the same distribution as $X_i$, and let $Z_i^{\prime }=f(X_1,\dots ,X_i^{\prime },\dots ,X_n)$. Three equivalent forms of the Efron–Stein inequality arefor arbitrary square-integrable $Z_i$ measurable with respect to $X_{-i}$, andThe first is the sharp choice within the second because conditional expectation is the least-squares projection. The first and third right sides are equal because two conditionally independent copies have expected squared difference twice their conditional variance.

The bounded differences property with constants $c_i$ meanswhenever $x$ and $x^{\prime }$ differ only in coordinate $i$. Conditional on $X_{-i}$, the range of $Z$ is therefore at most $c_i$. The range bound on variance givesSubstitution into the Efron–Stein inequality yields

Let ${\ell }^{\ast }$ be a maximizing index for the original sample. Since $Z_i^{\prime }$ is at least the value of its ${\ell }^{\ast }$th linear form,and henceThe one-sided replacement form of the Efron–Stein inequality isFor independent uniform signs, $\mathbb{E}[(X_i-X_i^{\prime }{)}^2\mid X]=2$. It follows that

Fix every coordinate except $X_i$. As $X_i$ varies, the longest increasing subsequence length can change by at most one: deleting the changed term leaves a common subsequence of length at least the larger value minus one. The conditional range therefore has length at most one, so the Popoviciu inequality on variances givesThe coordinatewise conditional-variance form of the Efron–Stein inequality now yields

We prove the Convex Poincaré inequality. For a differentiable convex function $h:[0,1]\to \mathbb{R}$ and independent copies $U,U^{\prime }$ supported on $[0,1]$, convexity givesTaking expectations and using $\mathrm{Var}(h(U))=\frac{1}{2}\mathbb{E}(h(U)-h(U^{\prime }){)}^2$ givesApplying this conditional inequality coordinate by coordinate in the Efron–Stein inequality provesSince $-g$ is convex and has the same gradient norm as $g$, the same argument gives $\mathrm{Var}(g(X))\le 1$.

Purnamrita Sarkar works at the intersection of high-dimensional statistics, machine-learning theory, differential privacy and large-scale optimization. Her University of Texas at Austin profile describes this combination of statistical and computational research.^[ref]

Her lecture on the Efron–Stein inequality presents a general way to control the variance of a function of independent inputs: compare the function with versions in which one input is independently replaced. For a sum, the resulting bound recovers the familiar sum of variances; for a complicated estimator, it gives a route to uncertainty control without expanding every covariance term.^[ref]

Write $X_{-i}$ for all inputs except $X_i$. Under the Efron–Stein inequality hypotheses, variance tensorization is the equivalent conditional variance formConditioning freezes the other inputs. Then $Z,Z_i^{\prime }$ are independent with the same conditional probability distribution, givingTaking expected values explains the factor $1/2$.^[ref]

For Bernoulli input $X_i$ with parameter $p_i$, let ${\Delta }_{i}f$ be the value of $f$ with coordinate $i$ set to one minus its value with that coordinate set to zero, keeping $X_{-i}$ fixed. The two-point conditional variance isFor the maximum example, ${\Delta }_{1}f=1-X_2$ and ${\Delta }_{2}f=1-X_1$. The two averaged conditional variances are $0.3(0.7)(0.4)=0.084$ and $0.6(0.4)(0.7)=0.168$, precisely half the respective resampling terms. In the dependent example $X_1=X_2=B$, each other coordinate already determines $W$, so both conditional variances vanish; variance tensorization also fails without independence.

For a short induction proof, separate the last input using the law of total variance. Apply the smaller-dimensional statement to the conditional expectation; Jensen's inequality for the square bounds its coordinate contributions by the original ones. One input gives equality, starting the induction.^[ref]