Lecture 11: Gaussian Concentration
Lipschitz functions, the sphere, and the Borell–TIS inequality
Lecture 10 ended with two questions about the supremum of a Gaussian process: how large is it, and how concentrated is it around its mean? This lecture answers the second, and the answer is remarkably clean. The supremum fluctuates on the scale of the largest standard deviation of a single \(X_t\), whatever the index set. The mechanism is a concentration inequality for Lipschitz functions of a Gaussian vector, proved with Stein’s lemma, and the passage from Lipschitz functions to suprema is the observation that a maximum of linear functions is Lipschitz.
1 The Gaussian concentration inequality
Throughout, \(\|h\|_{\mathrm{Lip}}\) denotes the Lipschitz constant of a function \(h:\mathbb R^d\to\mathbb R\) with respect to the Euclidean norm. For such \(h\), \(\nabla h\) exists almost everywhere and \(\|\nabla h\|_2\leq\|h\|_{\mathrm{Lip}}\) wherever it exists.
Theorem 1 (Gaussian concentration) Let \(X\sim N(0,I_d)\) and let \(h:\mathbb R^d\to\mathbb R\) be Lipschitz. Then for every \(\lambda\in\mathbb R\), \[ \mathbb Ee^{\lambda(h(X)-\mathbb Eh(X))}\leq\exp\Big(\frac{\lambda^2\|h\|_{\mathrm{Lip}}^2}2\Big), \] and consequently, for every \(t\geq0\), \[ \mathbb P\big\{|h(X)-\mathbb Eh(X)|\geq t\big\}\leq2\exp\Big(-\frac{t^2}{2\|h\|_{\mathrm{Lip}}^2}\Big). \]
In the language of Lecture 4, \(h(X)-\mathbb Eh(X)\) is sub-Gaussian with variance proxy \(\|h\|_{\mathrm{Lip}}^2\). The dimension \(d\) does not appear. A \(1\)-Lipschitz function of a standard Gaussian vector in \(\mathbb R^{10^6}\) fluctuates no more than a \(1\)-Lipschitz function of a single standard Gaussian, which is to say no more than \(N(0,1)\) itself. The linear function \(h(x)=x_1\) shows that the constant in the exponent cannot be improved.
The proof rests on an interpolation identity for covariances. For \(\alpha\in[0,1]\) and independent \(X,Y\sim N(0,\Sigma)\), set \[ X_\alpha:=\alpha X+\sqrt{1-\alpha^2}\,Y . \] Then \(X_\alpha\sim N(0,\Sigma)\) for every \(\alpha\), since \(\alpha^2+(1-\alpha^2)=1\), while \(X_1=X\) and \(X_0=Y\) is independent of \(X\). The path \(\alpha\mapsto X_\alpha\) moves from a copy of \(X\) to an independent copy without leaving the distribution \(N(0,\Sigma)\).
Lemma 1 (Covariance interpolation) Let \(X,Y\) be independent \(N(0,\Sigma)\) vectors in \(\mathbb R^d\), let \(f\) be Lipschitz, and let \(g\) be \(C^1\) and Lipschitz. Then \[ \operatorname{Cov}\big(f(X),g(X)\big) =\int_0^1\mathbb E\big\langle\Sigma\nabla f(X),\nabla g(X_\alpha)\big\rangle\,d\alpha . \]
Since \(X_1=X\) and \(X_0=Y\) is independent of \(X\), \[ \operatorname{Cov}\big(f(X),g(X)\big) =\mathbb Ef(X)g(X_1)-\mathbb Ef(X)g(X_0) =\mathbb E\Big[f(X)\int_0^1\frac d{d\alpha}g(X_\alpha)\,d\alpha\Big]. \] For \(0<\alpha<1\), the chain rule gives \[ \frac d{d\alpha}g(X_\alpha) =\Big\langle\nabla g(X_\alpha),\,X-\frac\alpha{\sqrt{1-\alpha^2}}Y\Big\rangle =\frac1{\sqrt{1-\alpha^2}}\big\langle\nabla g(X_\alpha),W_\alpha\big\rangle, \qquad W_\alpha:=\sqrt{1-\alpha^2}\,X-\alpha Y . \] The pair \((X_\alpha,W_\alpha)\) is a rotation of \((X,Y)\) by an angle: both are \(N(0,\Sigma)\), and \[ \mathbb EX_\alpha W_\alpha^{\mathsf T} =\alpha\sqrt{1-\alpha^2}\,\Sigma-\sqrt{1-\alpha^2}\,\alpha\,\Sigma=0, \] so by the independence remark of Lecture 10 they are independent. Inverting the rotation, \(X=\alpha X_\alpha+\sqrt{1-\alpha^2}\,W_\alpha\).
Fix \(\alpha\) and condition on \(X_\alpha\). The function \(w\mapsto f(\alpha X_\alpha+\sqrt{1-\alpha^2}\,w)\) is Lipschitz with gradient \(\sqrt{1-\alpha^2}\,\nabla f(X)\), and \(W_\alpha\sim N(0,\Sigma)\) is independent of \(X_\alpha\). The multivariate Stein lemma of Lecture 10, applied coordinate by coordinate to \(W_\alpha\), gives \[ \mathbb E\big[f(X)\langle\nabla g(X_\alpha),W_\alpha\rangle\,\big|\,X_\alpha\big] =\sqrt{1-\alpha^2}\,\mathbb E\big[\langle\nabla g(X_\alpha),\Sigma\nabla f(X)\rangle\,\big|\,X_\alpha\big]. \] Taking expectations, dividing by \(\sqrt{1-\alpha^2}\), and integrating in \(\alpha\) gives the identity. The interchange of \(\int_0^1d\alpha\) and \(\mathbb E\) is justified by Fubini, since the integrand is bounded by \(|f(X)|\,\|g\|_{\mathrm{Lip}}\,\|W_\alpha\|_2/\sqrt{1-\alpha^2}\), whose expectation is integrable in \(\alpha\) on \((0,1)\).
Replacing \(h\) by \(h-\mathbb Eh(X)\) we may assume \(\mathbb Eh(X)=0\). Write \(L=\|h\|_{\mathrm{Lip}}\). Assume first that \(h\) is \(C^1\) and bounded, so that \(g:=e^{\lambda h}\) is \(C^1\) and Lipschitz for every \(\lambda\).
Let \(M(\lambda):=\mathbb Ee^{\lambda h(X)}\), so that \(M(0)=1\) and \(M'(\lambda)=\mathbb Eh(X)e^{\lambda h(X)}\). Since \(\mathbb Eh(X)=0\), this is a covariance, and Lemma 1 with \(\Sigma=I_d\), \(f=h\) and \(g=e^{\lambda h}\) gives \[ M'(\lambda)=\operatorname{Cov}\big(h(X),e^{\lambda h(X)}\big) =\lambda\int_0^1\mathbb E\Big[\big\langle\nabla h(X),\nabla h(X_\alpha)\big\rangle e^{\lambda h(X_\alpha)}\Big]d\alpha . \] For \(\lambda\geq0\), Cauchy–Schwarz gives \(\langle\nabla h(X),\nabla h(X_\alpha)\rangle\leq L^2\) pointwise, and \(X_\alpha\sim N(0,I_d)\) for every \(\alpha\), so \[ M'(\lambda)\leq\lambda L^2\int_0^1\mathbb Ee^{\lambda h(X_\alpha)}\,d\alpha=\lambda L^2M(\lambda). \] Hence \((\log M)'(\lambda)\leq\lambda L^2\), and integrating from \(0\), \[ M(\lambda)\leq\exp\Big(\frac{\lambda^2L^2}2\Big) \qquad(\lambda\geq0). \] Applying this to \(-h\) handles \(\lambda<0\). So \(h(X)\) is sub-Gaussian with variance proxy \(L^2\), and the tail bound is the sub-Gaussian tail bound of Lecture 4.
For a general Lipschitz \(h\), the extra assumptions are removed by approximation; see the aside below.
Let \(h\) be Lipschitz with constant \(L\) and mean zero under \(N(0,I_d)\). First truncate: \(h_M:=\max\{\min\{h,M\},-M\}\) is bounded and still \(L\)-Lipschitz. Then smooth: for \(\varepsilon>0\) let \(h_{M,\varepsilon}:=h_M*\varphi_\varepsilon\) be the convolution with the density of \(N(0,\varepsilon^2I_d)\). Convolution with a probability density preserves the Lipschitz constant and the bound \(M\), and makes the function \(C^\infty\). So the moment generating function bound holds for \(h_{M,\varepsilon}-\mathbb Eh_{M,\varepsilon}(X)\) with the same \(L\).
As \(\varepsilon\to0\), \(h_{M,\varepsilon}\to h_M\) uniformly, because \(|h_{M,\varepsilon}(x)-h_M(x)|\leq L\,\mathbb E\|\varepsilon Z\|_2\leq L\varepsilon\sqrt d\). As \(M\to\infty\), \(h_M\to h\) pointwise with \(|h_M|\leq|h|\), and \(h(X)\) has Gaussian tails since \(|h(x)|\leq|h(0)|+L\|x\|_2\). Dominated convergence passes the bound \(\mathbb Ee^{\lambda(h_{M,\varepsilon}(X)-\mathbb Eh_{M,\varepsilon}(X))}\leq e^{\lambda^2L^2/2}\) to the limit in each step.
Two immediate applications recover, and sharpen, results seen earlier.
The norm. The function \(x\mapsto\|x\|_2\) is \(1\)-Lipschitz, so \[ \mathbb P\big\{\big|\|X\|_2-\mathbb E\|X\|_2\big|\geq t\big\}\leq2e^{-t^2/2} \qquad(t\geq0). \] Lecture 3 and Exercise Sheet 3 obtained this for Gaussian vectors by a Bernstein argument on \(\|X\|_2^2\). Here it is a one-line consequence of a general principle, with an explicit constant.
The Gaussian width process. Let \(T\subseteq\mathbb R^d\) be bounded with \(R:=\sup_{t\in T}\|t\|_2\), and let \(h_T(x)=\sup_{t\in T}\langle x,t\rangle\) be its support function. For every \(t\in T\), \(\langle x,t\rangle\leq\langle y,t\rangle+R\|x-y\|_2\leq h_T(y)+R\|x-y\|_2\), so \(h_T\) is \(R\)-Lipschitz. Therefore \[ \mathbb P\Big\{\Big|\sup_{t\in T}\langle g,t\rangle-w(T)\Big|\geq u\Big\}\leq2\exp\Big(-\frac{u^2}{2R^2}\Big). \] The mean of the supremum is the Gaussian width, a quantity that reflects the whole geometry of \(T\). The fluctuations depend on \(T\) only through its radius. These are different pieces of information, and the second is far cruder than the first: for \(T=B_2^d\) the mean is about \(\sqrt d\) while the fluctuations are of order \(1\).
2 Concentration on the sphere
The uniform distribution on the sphere inherits concentration from the Gaussian, because a normalized Gaussian vector is uniform on the sphere and the normalization is nearly constant.
Theorem 2 (Concentration on the sphere) There are absolute constants \(c,C>0\) such that the following holds. Let \(\omega\) be uniform on \(S^{d-1}\) and let \(f:S^{d-1}\to\mathbb R\) be Lipschitz with respect to the Euclidean distance, with constant \(L\). Then for every \(t\geq0\), \[ \mathbb P\big\{|f(\omega)-\mathbb Ef(\omega)|\geq t\big\}\leq C\exp\Big(-\frac{c\,dt^2}{L^2}\Big). \]
The point is the factor \(d\) in the exponent. A \(1\)-Lipschitz function on the sphere of radius \(1\) fluctuates by about \(1/\sqrt d\), which is the scale on which the sphere looks flat. This is the same phenomenon as the volume concentration of Lecture 1: the sphere of radius \(\sqrt d\), on which a \(1\)-Lipschitz function fluctuates by \(O(1)\), is the sphere on which the standard Gaussian vector lives.
By homogeneity take \(L=1\), and by subtracting a constant assume \(|f|\leq2\), which is possible because \(f\) is \(1\)-Lipschitz on a set of diameter \(2\). Let \(Z\sim N(0,I_d)\); by rotation invariance, \(\omega\) has the law of \(Z/\|Z\|_2\), and we work with this representation.
Step 1: a Lipschitz extension. Let \(\varphi:[0,\infty)\to[0,1]\) be the piecewise linear function equal to \(1\) on \([\sqrt d/2,2\sqrt d]\), equal to \(0\) outside \([\sqrt d/4,3\sqrt d]\), and linear in between; its Lipschitz constant is \(4/\sqrt d\). Define \[ F(z):=\varphi(\|z\|_2)\,f\Big(\frac z{\|z\|_2}\Big), \qquad F(0):=0 . \] We claim \(F\) is \((16/\sqrt d)\)-Lipschitz on \(\mathbb R^d\). For \(z_1,z_2\neq0\), \[ |F(z_1)-F(z_2)| \leq\big|\varphi(\|z_1\|_2)-\varphi(\|z_2\|_2)\big|\cdot2 +\varphi(\|z_2\|_2)\,\Big\|\frac{z_1}{\|z_1\|_2}-\frac{z_2}{\|z_2\|_2}\Big\|_2 . \] The first term is at most \((8/\sqrt d)\|z_1-z_2\|_2\). For the second, the elementary inequality \(\|a/\|a\|_2-b/\|b\|_2\|_2\leq2\|a-b\|_2/\|b\|_2\) and the fact that \(\varphi(\|z_2\|_2)\neq0\) forces \(\|z_2\|_2\geq\sqrt d/4\) bound it by \((8/\sqrt d)\|z_1-z_2\|_2\). The cases involving \(z=0\) are similar.
Step 2: concentration of \(F(Z)\). By Theorem 1, \[ \mathbb P\big\{|F(Z)-\mathbb EF(Z)|\geq s\big\}\leq2\exp\Big(-\frac{ds^2}{512}\Big). \]
Step 3: comparing \(F(Z)\) with \(f(\omega)\). Let \(E=\{\sqrt d/2\leq\|Z\|_2\leq2\sqrt d\}\). On \(E\), \(F(Z)=f(\omega)\). By the Bernstein bound on \(\|Z\|_2^2\) from Lecture 6, \(\mathbb P\{E^c\}\leq2e^{-c_0d}\) for an absolute \(c_0>0\). Since \(|F(Z)-f(\omega)|=(1-\varphi(\|Z\|_2))|f(\omega)|\leq2\) always, \[ |\mathbb EF(Z)-\mathbb Ef(\omega)|\leq2\,\mathbb P\{E^c\}\leq4e^{-c_0d}. \] Hence for \(t\geq8e^{-c_0d}\), \[ \mathbb P\big\{|f(\omega)-\mathbb Ef(\omega)|\geq t\big\} \leq\mathbb P\{E^c\}+\mathbb P\big\{|F(Z)-\mathbb EF(Z)|\geq t/2\big\} \leq2e^{-c_0d}+2e^{-dt^2/2048}. \] Since \(|f(\omega)-\mathbb Ef(\omega)|\leq2\), only \(t\leq2\) matters, and for such \(t\) we have \(e^{-c_0d}\leq e^{-c_0dt^2/4}\). This gives the claim for \(t\geq8e^{-c_0d}\) with \(c=\min\{c_0/4,1/2048\}\) and \(C=4\). For smaller \(t\), the right-hand side of the claim exceeds \(1\) once \(C\) is increased to an absolute constant, because \(dt^2\leq64de^{-2c_0d}\) is bounded uniformly in \(d\).
The constants here are far from optimal. The sharp statement, due to Lévy, is that spherical caps are the extremal sets, which gives the exponent \(-(d-2)t^2/(2L^2)\). The proof above trades the constant for the convenience of deducing the sphere from the Gaussian, which is the pattern we follow throughout.
3 The Borell–TIS inequality
The Gaussian width process was concentrated because its supremum is a Lipschitz function of \(g\). The same is true of every Gaussian process, via the Karhunen–Loève representation of Lecture 10, and the Lipschitz constant is the largest standard deviation.
Theorem 3 (Borell–TIS inequality) Let \((X_t)_{t\in T}\) be a centered Gaussian process whose canonical metric space \((T,d)\) is separable. Suppose \[ \sigma^2:=\sup_{t\in T}\mathbb EX_t^2<\infty \qquad\text{and}\qquad \mathbb E\sup_{t\in T}X_t<\infty . \] Then for every \(x\geq0\), \[ \mathbb P\Big\{\sup_{t\in T}X_t-\mathbb E\sup_{t\in T}X_t\geq x\Big\}\leq e^{-x^2/(2\sigma^2)}, \qquad \mathbb P\Big\{\sup_{t\in T}X_t-\mathbb E\sup_{t\in T}X_t\leq-x\Big\}\leq e^{-x^2/(2\sigma^2)}. \]
Finite index sets. Let \(T'=\{t_1,\ldots,t_n\}\subseteq T\) be finite and let \(\Sigma\) be the covariance matrix of \((X_{t_i})_{i\leq n}\). By the square-root representation of Lecture 10, this vector has the law of \(\Sigma^{1/2}Z\) with \(Z\sim N(0,I_n)\). Define \[ \varphi(z):=\max_{i\leq n}\big(\Sigma^{1/2}z\big)_i , \] so that \(\sup_{t\in T'}X_t\) has the law of \(\varphi(Z)\). Each coordinate function \(z\mapsto(\Sigma^{1/2}z)_i=\langle(\Sigma^{1/2})_{i\cdot},z\rangle\) is Lipschitz with constant \(\|(\Sigma^{1/2})_{i\cdot}\|_2=\sqrt{(\Sigma)_{ii}}=\sqrt{\mathbb EX_{t_i}^2}\leq\sigma\), and a maximum of \(\sigma\)-Lipschitz functions is \(\sigma\)-Lipschitz. By Theorem 1, both one-sided bounds hold for \(T'\), each with the single-tail constant \(1\) in front (the proof of the concentration theorem bounds each tail separately by \(e^{-x^2/(2\sigma^2)}\)).
Passage to the limit. Let \(T_0\) be a countable dense subset of \((T,d)\) and let \(T_1\subseteq T_2\subseteq\cdots\) be finite sets increasing to \(T_0\). By the convention of Lecture 10, \(\sup_TX=\sup_{T_0}X\), and \(S_n:=\sup_{T_n}X\) increases to \(S:=\sup_{T_0}X\) almost surely. By monotone convergence, \(\mathbb ES_n\uparrow\mathbb ES\), which is finite by hypothesis. Fix \(x\geq0\) and \(\varepsilon>0\), and let \(n\) be large enough that \(\mathbb ES_n\geq\mathbb ES-\varepsilon\). Then \[ \{S_n-\mathbb ES>x\}\subseteq\{S_n-\mathbb ES_n\geq x-\varepsilon\}, \] so \(\mathbb P\{S_n-\mathbb ES>x\}\leq e^{-(x-\varepsilon)^2/(2\sigma^2)}\) for all large \(n\). The events \(\{S_n-\mathbb ES>x\}\) increase to \(\{S-\mathbb ES>x\}\), hence \(\mathbb P\{S-\mathbb ES>x\}\leq e^{-(x-\varepsilon)^2/(2\sigma^2)}\). Let \(\varepsilon\to0\), then replace \(x\) by \(x-\varepsilon'\) and let \(\varepsilon'\to0\) to pass from \(>x\) to \(\geq x\). The lower tail is the same argument with the inequalities reversed, using \(S_n\leq S\) and \(\mathbb ES_n\leq\mathbb ES\) directly.
The theorem is the answer to the concentration question. Whatever the index set, the supremum of a Gaussian process is sub-Gaussian around its mean with variance proxy \(\sigma^2\), the largest variance of a single \(X_t\). Some remarks.
The mean dominates the fluctuations. Applying the theorem to the process \((\varepsilon X_t)_{(t,\varepsilon)\in T\times\{\pm1\}}\), whose supremum is \(\sup_t|X_t|\), gives the same bounds for \(\sup_t|X_t|\). But \(\mathbb E\sup_t|X_t|\geq\sup_t\mathbb E|X_t|=\sqrt{2/\pi}\,\sigma\), so the mean of \(\sup|X_t|\) is always at least a constant multiple of the scale \(\sigma\) on which it fluctuates. The supremum of a Gaussian process is therefore never much more spread out than it is large. This is why the remaining problem, taken up in Lecture 12, is the mean alone.
Finiteness of the mean is a genuine hypothesis. For i.i.d. standard Gaussians indexed by \(\mathbb N\) we have \(\sigma=1\) but \(\sup_tX_t=+\infty\), and the theorem says nothing. Conversely, when \(\mathbb E\sup X<\infty\), the theorem shows that \(\sup X\) has Gaussian tails, so all its moments are finite.
No independence, no structure. The proof used nothing about \(T\). Every concentration statement earlier in the course, from Hoeffding to Bernstein, required independent summands. Here the \(X_t\) may be arbitrarily correlated.
Let \(G\sim N(0,I_d)\) and consider \(\|G\|_\infty=\max_i|G_i|\), a Gaussian supremum with \(\sigma=1\) over the index set \(\{\pm e_1,\ldots,\pm e_d\}\). Lecture 3 gives \(\mathbb E\|G\|_\infty\leq\sqrt{2\log(2d)}\), and it is also at least \(\sqrt{2\log d}-o(1)\).
Upper tail by a union bound. Using the Gaussian tail \(\mathbb P\{|Z|\geq s\}\leq e^{-s^2/2}\), \[ \mathbb P\big\{\|G\|_\infty\geq\sqrt{2\log d}+t\big\} \leq d\,e^{-(\sqrt{2\log d}+t)^2/2} =e^{-t\sqrt{2\log d}-t^2/2}. \]
Both tails by Borell–TIS. With \(m=\mathbb E\|G\|_\infty\), \[ \mathbb P\big\{|\|G\|_\infty-m|\geq t\big\}\leq2e^{-t^2/2}. \]
The union bound gives the better upper tail, which is not surprising: it used the independence of the coordinates and the exact Gaussian tail, while Borell–TIS used only \(\sigma=1\). What Borell–TIS adds is the lower tail, \(\mathbb P\{\|G\|_\infty\leq m-t\}\leq e^{-t^2/2}\), which no union bound can produce, and which it produces with no independence at all.
Both bounds miss the truth. In fact \(\|G\|_\infty-\sqrt{2\log d}\to0\) in probability, and the fluctuations of \(\|G\|_\infty\) are of order \(1/\sqrt{\log d}\), not order \(1\). Borell–TIS is sharp for some processes (a single \(X_t\), for instance) but it is a worst-case statement over all index sets with a given \(\sigma\), and it cannot see the finer structure of a particular one.
4 Where we go next
Concentration reduces the study of \(\sup_tX_t\) to the study of its mean. The next lecture develops the main tool for the mean, Gaussian comparison. Slepian’s inequality and the Sudakov–Fernique inequality say that if the canonical metric of one process is dominated by that of another, then so is the expected supremum. The proof is again Stein’s lemma along an interpolation between two Gaussian vectors, now with two different covariances at the endpoints. The first application is the norm of a Gaussian random matrix, where comparison gives the sharp bound \(\sqrt m+\sqrt n\) and Borell–TIS turns it into a tail bound.