Gaussian concentration inequality

For a Gaussian random vector $X\sim N(m,\Sigma )$ and an $L$-Lipschitz function $f$ in the Euclidean norm, put $v=L^2\Vert \Sigma {\Vert }_{\mathrm{op}}$. If $v>0$, the Gaussian concentration inequality givesand thereforeWrite $X=m+{\Sigma }^{1/2}G$ with a standard Gaussian random vector $G$. The composed function has Lipschitz constant at most $L\Vert \Sigma {\Vert }_{\mathrm{op}}^{1/2}$. The Gaussian logarithmic Sobolev inequality and Herbst argument give the exponential bound, and the Chernoff bound supplies the tails.^[ref]

For example, $f(x)=\Vert x\Vert$ has $L=1$, so its deviations depend on the largest covariance eigenvalue rather than directly on the number of coordinates. The center $\mathbb{E}\Vert X\Vert$ can still grow with dimension. If $v=0$, $f(X)$ is constant almost surely and every positive deviation has probability zero.

For a standard Gaussian vector $G$ and a smooth Lipschitz function with $\Vert \nabla f\Vert \le K$, represent its centered value as the terminal martingale $P_{1-t}f(B_t)-P_{1}f(0)$. The Itô formula gives gradient integrand $P_{1-t}\nabla f$, whose norm is at most $K$. Its terminal quadratic variation is therefore at most $K^2$. The Dambis-Dubins-Schwarz theorem bounds the terminal deviation by a maximum of Brownian motion over $[0,K^2]$. Symmetry, the Brownian reflection principle, and the Gaussian tail bound give the displayed inequality. The square on the Lipschitz constant is essential by scaling.

For independent and identically distributed random variables $X,Y$ with a centered multivariate normal distribution, a continuously differentiable function $f$ with bounded gradient, and a convex function $\Psi$ for which the expressions are integrable, the displayed inequality holds. First apply Jensen inequality conditionally to $f(X)-f(Y)$. For the Gaussian rotation of independent copies, the chain rule gives $f(X)-f(Y)={\int }_0^{\pi /2}⟨\nabla f(U_{\theta }),V_{\theta }⟩d\theta$. A second application of Jensen inequality to the uniform measure on $[0,\pi /2]$, followed by the Gaussian rotation of independent copies, proves the inequality. The useful choice $\Psi (v)=e^{\lambda |v|}$ yields a Gaussian concentration inequality through an exponential moment of an absolute standard normal variable.