on Slepian's lemma and Gaussian comparison

Overview

This post examines Slepian’s Lemma (1962), a fundamental comparison principle in the theory of Gaussian processes. It formalizes the intuition that the more independent a set of Gaussian variables is, the larger their expected maximum will be. We explore the theorem’s rigorous statement, its generalization via the Sudakov-Fernique Inequality, and provide a detailed proof using the Gaussian Interpolation Method.

🏷️ The Intuition: Correlation and Supremum

Consider a collection of Gaussian random variables $\{X_1,\dots ,X_n\}$. We are interested in the behavior of the supremum $\mathbb{E}\max X_i$.

The Correlation Effect

• i.i.d. Case: If the variables are independent and $N(0,1)$, the expected maximum scales as $\sqrt{2\log n}$.
• Perfect Correlation: If $X_1=X_2=\cdots =X_n$, they move as a single unit, and $\mathbb{E}\max X_i=\mathbb{E}{X}_1=0$.

Slepian’s insight was that positive correlation between variables “pulls” them together, effectively reducing the effective volume they cover and thus shrinking the expected maximum.

🏷️ Slepian’s Inequality

Slepian’s Lemma (Slepian, 1962) provides a formal comparison between two Gaussian processes based on their covariance structures.

Slepian’s Lemma (1962)

Let $X=(X_1,\dots ,X_n)$ and $Y=(Y_1,\dots ,Y_n)$ be centered Gaussian random vectors in ${\mathbb{R}}^n$ such that for all $i$:

$$\mathbb{E}{X}_i^2=\mathbb{E}{Y}_i^2$$

and for all $i\ne j$:

$$\mathbb{E}{X}_i{X}_j\le \mathbb{E}{Y}_i{Y}_j$$

Then for any real numbers $a_1,\dots ,a_n$:

$$P(\max X_i\le a_i)\le P(\max Y_i\le a_i)$$

In particular, this implies $\mathbb{E}\max X_i\ge \mathbb{E}\max Y_i$.

🏷️ Detailed Proof: The Interpolation Method

The most powerful proof of Slepian-type inequalities relies on Gaussian Interpolation, a technique that allows us to continuously deform one process into another while tracking the evolution of the expectation.

Proof: The Smart Path

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a smooth approximation of the maximum function. We define the interpolated process $Z(t)$ for $t\in [0,1]$ as:

$$Z_i(t)=\sqrt{t}{Y}_i+\sqrt{1-t}{X}_i$$

where $X$ and $Y$ are independent. We study the function $\varphi (t)=\mathbb{E}f(Z(t))$.

1. The Derivative: By the chain rule:

$${\varphi }^{\prime }(t)=\sum _{i=1}^n\mathbb{E}\left[\frac{\partial f}{\partial z_i}(Z(t))\cdot \left(\frac{1}{2\sqrt{t}}{Y}_i-\frac{1}{2\sqrt{1-t}}{X}_i\right)\right]$$

2. Gaussian Integration by Parts (Stein’s Lemma): For any centered Gaussian $G$ and smooth $g$, $\mathbb{E}[Gg(G)]=\mathbb{E}[G^2]\mathbb{E}[g^{\prime }(G)]$. Applying this to the $X$ and $Y$ components:

$$\mathbb{E}\left[Y_i\frac{\partial f}{\partial z_i}\right]=\sqrt{t}\sum _{j=1}^n\mathbb{E}{Y}_i{Y}_j\mathbb{E}\left[\frac{{\partial }^{2}f}{\partial z_i\partial z_j}\right]$$ $$\mathbb{E}\left[X_i\frac{\partial f}{\partial z_i}\right]=\sqrt{1-t}\sum _{j=1}^n\mathbb{E}{X}_i{X}_j\mathbb{E}\left[\frac{{\partial }^{2}f}{\partial z_i\partial z_j}\right]$$

3. Combining Terms: Substituting these back into ${\varphi }^{\prime }(t)$:

$${\varphi }^{\prime }(t)=\frac{1}{2}\sum _{i,j=1}^n(\mathbb{E}{Y}_i{Y}_j-\mathbb{E}{X}_i{X}_j)\mathbb{E}\left[\frac{{\partial }^{2}f}{\partial z_i\partial z_j}(Z(t))\right]$$

4. The Sign Analysis:

• For $i=j$: The term is zero because $\mathbb{E}{Y}_i^2=\mathbb{E}{X}_i^2$.
• For $i\ne j$: By assumption, $(\mathbb{E}{Y}_i{Y}_j-\mathbb{E}{X}_i{X}_j)\ge 0$.
• The Max Function: For the maximum function $f(z)=\max z_k$, the second derivatives ${\partial }^{2}f/\partial z_i\partial z_j$ are non-positive for $i\ne j$.

Consequently, ${\varphi }^{\prime }(t)\le 0$, which implies $\mathbb{E}f(Y)=\varphi (1)\le \varphi (0)=\mathbb{E}f(X)$. This proves $\mathbb{E}\max Y_i\le \mathbb{E}\max X_i$.

🏷️ Generalization: Sudakov-Fernique Inequality

A significant limitation of Slepian’s original result is the requirement of equal variances. The Sudakov-Fernique Inequality [@fernique1975regularite] generalizes this to compare increments directly.

Sudakov-Fernique Inequality

Let $\{X_t{\}}_{t\in T}$ and $\{Y_t{\}}_{t\in T}$ be centered Gaussian processes such that for all $s,t\in T$:

$$\mathbb{E}(X_t-X_s{)}^2\le \mathbb{E}(Y_t-Y_s{)}^2$$

Then $\mathbb{E}{\sup }_{t\in T}{X}_t\le \mathbb{E}{\sup }_{t\in T}{Y}_t$.

Proof Insight: Variational Reformulation

The proof of Sudakov-Fernique follows the same interpolation logic but handles the variance terms by recognizing that:

$$\mathbb{E}(X_t-X_s{)}^2=\mathbb{E}{X}_t^2+\mathbb{E}{X}_s^2-2\mathbb{E}{X}_t{X}_s$$

Substituting this into the ${\varphi }^{\prime }(t)$ formula reveals that the increase in incremental variance compensates for any individual variance growth, maintaining the non-positivity of the derivative for the supremum functional.

🌊 Advanced Application: Random Matrix Theory

The Sudakov-Fernique inequality provides a remarkably simple proof for bounding the expected operator norm of a Gaussian random matrix.

Expected Operator Norm of a Gaussian Matrix

Let $G$ be an $n\times m$ matrix with i.i.d. $N(0,1)$ entries. The operator norm is:

$$\Vert G\Vert =\underset{u\in S^{m-1},v\in S^{n-1}}{\sup }⟨Gu,v⟩=\underset{u,v}{\sup }\sum _{i,j}{G}_{ij}{u}_j{v}_i$$

1. The $X$-process: Define $X_{u,v}={\sum }_{i,j}{G}_{ij}{u}_j{v}_i$. The increments are $\mathbb{E}(X_{u,v}-X_{u^{\prime },v^{\prime }}{)}^2=\Vert u{v}^T-u^{\prime }{v}^{\prime T}{\Vert }_F^2\le \Vert u-u^{\prime }{\Vert }^2+\Vert v-v^{\prime }{\Vert }^2$.

2. The $Y$-process: Let $g\sim N(0,I_n)$ and $h\sim N(0,I_m)$ be independent Gaussian vectors. Define $Y_{u,v}=⟨g,v⟩+⟨h,u⟩$. The increments are $\mathbb{E}(Y_{u,v}-Y_{u^{\prime },v^{\prime }}{)}^2=\Vert v-v^{\prime }{\Vert }^2+\Vert u-u^{\prime }{\Vert }^2$.

3. Comparison: By Sudakov-Fernique, $\mathbb{E}\Vert G\Vert \le \mathbb{E}{\sup }_v⟨g,v⟩+\mathbb{E}{\sup }_u⟨h,u⟩\le \sqrt{n}+\sqrt{m}$.

📉 Advanced Application: Sudakov Minoration

While on Dudley’s Theorem provides an upper bound via metric entropy, Slepian’s logic allows us to establish a Lower Bound.

Sudakov Minoration

If $T$ contains $M$ points that are at least $ϵ$-separated in the Gaussian metric $d(t,s)$, we can compare the process to $M$ independent Gaussians with variance ${ϵ}^2/2$.

$$\mathbb{E}\underset{t\in T}{\sup }{X}_t\gtrsim ϵ\sqrt{\log N(T,d,ϵ)}$$

Significance: This result (Sudakov, 1971) is the dual to Dudley’s integral. It proves that if a set has high metric entropy at a single scale, the process MUST fluctuate significantly. This is refined by Talagrand’s ${\gamma }_2$ functional, which “interpolates” between Sudakov and Dudley to achieve sharpness.

📝 Notes

• Gordon’s Inequality: A further refinement by Yehoram Gordon (Gordon, 1985) compares the expected value of $\mathbb{E}{\inf }_u{\sup }_v\dots$, which is essential for studying the smallest singular values of random matrices.
• The Max Functionality: The key to Slepian’s Lemma is that the “max” function is sub-modular (the off-diagonal second derivatives are $\le 0$). This ensures that increasing correlations (moving variables closer) always reduces the expected maximum.

🔗 See Also

• on Dudley’s Theorem --- Slepian/Sudakov provides the necessary lower bounds that complement Dudley’s chaining upper bound.
• on eigenvalue estimate of kernel --- Comparison inequalities are the primary tool for bounding the spectra of random operators.

📚 References

🐻  Gordon, Y. 1985. Some inequalities for Gaussian processes and applications. Israel Journal of Mathematics 50(4), 265–289.

🐻  Slepian, D.S. 1962. The one-sided barrier problem for Gaussian noise. Bell System Technical Journal 41(2), 463–501.

🐻  Sudakov, V.N. 1971. Gaussian random processes and measures of solid angles in Hilbert space. Doklady Akademii Nauk SSSR 197(1), 43–45.