= Talagrand concentration inequality for certifiable functions
{c}
For a nonnegative integer-valued <certifiable function> $Z=f(X)$ of <independent random variables>, suppose changing one coordinate changes $f$ by at most $L>0$ and a value $f(x)\geq b$ has a certificate involving at most $rb$ coordinates, with $r>0$. Then for $0\leq a<b$,
$$
\mathbb P(Z\leq a)\mathbb P(Z\geq b)\leq
\exp\left[-\frac{(b-a)^2}{4L^2rb}\right].
$$
For a high-value input $x$, every low-value input must disagree with its certificate on at least $(b-a)/L$ coordinates: replacing its certificate positions by those of $x$ would change the low value by less than $b-a$ but force a value at least $b$. Uniform weights $1/\sqrt{rb}$ on certificate positions therefore give <Talagrand convex distance> at least $(b-a)/(L\sqrt{rb})$ from the low-value <event>. Apply <Talagrand's convex distance inequality> to that <event>.
The bound is useful when one of the two <events> has known nonnegligible <probability>, for example at a <median>. A certificate alone supplies no coordinate-change constant $L$; both hypotheses are used in the proof. The <two-threshold concentration for certifiable functions> article develops the resulting <mean>-<median> comparison.
Back to article page
