Lecture 19: The Lower Bound and the Matrix Deviation Inequality
Trees, Sudakov with a remainder, and random matrices on arbitrary sets
Lecture 18 stated the majorizing measure theorem and proved its upper half, the generic chaining bound \(\mathbb E\sup X\leq C\gamma_2(T,d)\). This lecture does two things with the lower half. It explains the mechanism of the proof, a tree of well-separated subsets of \(T\) along which Sudakov’s minoration is applied at every branching, and it uses the theorem in the form that matters for applications: any process with sub-Gaussian increments is dominated by the Gaussian process with the same increments. The application is the matrix deviation inequality, which controls \(\|Ax\|_2-\sqrt m\|x\|_2\) uniformly over an arbitrary set of vectors \(x\) by the Gaussian width of the set, for a matrix \(A\) with independent sub-Gaussian rows. It is the tool that Lecture 9 lacked.
1 Sudakov’s minoration with a remainder
The lower bound in Sudakov’s minoration (Lecture 12) says that \(\varepsilon\)-separated points force \(\mathbb E\sup X\geq c\varepsilon\sqrt{\log N}\). For an iterative argument one needs more: the separated points should carry subsets of \(T\), and the process should pay \(\varepsilon\sqrt{\log N}\) in addition to whatever the subsets themselves force.
Lemma 1 (Sudakov with a remainder) There are absolute constants \(c,c'>0\) with the following property. Let \((X_t)_{t\in T}\) be a centered Gaussian process with canonical metric \(d\), and let \(T_1,\ldots,T_N\subseteq T\) be subsets, \(N\geq2\), such that \[ \operatorname{diam}(T_j)\leq c\,\varepsilon \quad\text{for all }j, \qquad d(T_j,T_k)\geq\varepsilon \quad\text{for all }j\neq k . \] Then \[ \mathbb E\sup_{t\in T}X_t\geq c'\varepsilon\sqrt{\log N}+\min_{j\leq N}\mathbb E\sup_{t\in T_j}X_t . \]
Let \(T'=\bigcup_jT_j\); it suffices to bound \(\mathbb E\sup_{T'}X\) from below. We build a comparison process. Let \(g_1,\ldots,g_N\) be i.i.d. \(N(0,1)\), and for each \(j\) let \((Z^{(j)}_t)_{t\in T_j}\) be an independent copy of the process \((X_t)_{t\in T_j}\), all independent of one another and of the \(g_j\). For \(t\in T_j\) define \[ Y_t:=\frac\varepsilon4g_j+Z^{(j)}_t . \] We compare increments. For \(s,t\) in the same \(T_j\), \(\mathbb E(Y_t-Y_s)^2=\mathbb E(X_t-X_s)^2\). For \(t\in T_j\) and \(s\in T_k\) with \(j\neq k\), independence gives \[ \mathbb E(Y_t-Y_s)^2=\frac{\varepsilon^2}8+\mathbb E(Z^{(j)}_t)^2+\mathbb E(Z^{(k)}_s)^2 \leq\frac{\varepsilon^2}8+2c^2\varepsilon^2 , \] if we normalize so that the processes \(Z^{(j)}\) are centered at a point of \(T_j\), which changes nothing, so that \(\mathbb E(Z^{(j)}_t)^2\leq\operatorname{diam}(T_j)^2\leq c^2\varepsilon^2\); while \(\mathbb E(X_t-X_s)^2=d(t,s)^2\geq\varepsilon^2\). Choosing \(c\) small enough that \(\frac18+2c^2\leq1\) gives \(\mathbb E(Y_t-Y_s)^2\leq\mathbb E(X_t-X_s)^2\) for all \(s,t\in T'\). By the Sudakov–Fernique inequality of Lecture 12, \[ \mathbb E\sup_{t\in T'}X_t\geq\mathbb E\sup_{t\in T'}Y_t =\mathbb E\max_{j\leq N}\Big(\frac\varepsilon4g_j+\sup_{t\in T_j}Z^{(j)}_t\Big). \] Condition on \(g_1,\ldots,g_N\). The suprema \(\sup_{T_j}Z^{(j)}\) are independent of the \(g_j\), and by Jensen’s inequality applied to the convex function \(\max_j\), replacing each of them by its expectation \(\mathbb E\sup_{T_j}X\) can only decrease the conditional expectation: \[ \mathbb E\max_j\Big(\frac\varepsilon4g_j+\sup_{T_j}Z^{(j)}\Big) \geq\mathbb E\max_j\Big(\frac\varepsilon4g_j+\mathbb E\sup_{T_j}X\Big) \geq\frac\varepsilon4\,\mathbb E\max_jg_j+\min_j\mathbb E\sup_{T_j}X . \] Finally \(\mathbb E\max_{j\leq N}g_j\geq c_0\sqrt{\log N}\) for \(N\geq2\), as in the proof of Sudakov’s minoration.
The lemma is Sudakov’s minoration when the \(T_j\) are single points. The gain is the second term: whatever the process achieves inside the pieces is added to, not replaced by, the separation cost at the coarse scale. This is what allows the bound to be iterated down a tree of scales.
2 Trees and the lower bound
Fix \(\alpha\in(0,1)\), a fixed ratio between consecutive scales; \(\alpha=\tfrac14\) will do. A tree on \(T\) is a collection \(\mathcal T\) of nonempty subsets of \(T\), containing \(T\) itself, such that any two members are either disjoint or nested. Each member \(A\) has a depth \(k(A)\), the length of the chain \(T=A_0\supsetneq A_1\supsetneq\cdots\supsetneq A_{k(A)}=A\) of members above it, and a set of children, the members of depth \(k(A)+1\) contained in \(A\).
Definition 1 (Packing tree) A tree \(\mathcal T\) on \((T,d)\) is an \(\alpha\)-packing tree if for every member \(A\), \[ \operatorname{diam}(A)\leq c\,\alpha^{k(A)}\operatorname{diam}(T), \] and any two children \(B,B'\) of \(A\) satisfy \(d(B,B')\geq\alpha^{k(A)+1}\operatorname{diam}(T)\), with \(c\) the constant of Lemma 1. For such a tree define \[ \gamma_2'(\mathcal T):=\inf_{T=A_0\supsetneq A_1\supsetneq\cdots}\ \sum_{k\geq0}\alpha^k\operatorname{diam}(T)\sqrt{\log\big(\#\text{children of }A_k\big)}, \] the infimum over all maximal chains in the tree, and \(\gamma_2'(T,d):=\sup_{\mathcal T}\gamma_2'(\mathcal T)\) over all \(\alpha\)-packing trees.
The functional \(\gamma_2'\) is dual to \(\gamma_2\) in shape. In \(\gamma_2\) one chooses nets and takes the worst point; in \(\gamma_2'\) one chooses a tree and takes the cheapest branch. A good tree branches heavily at every depth along every path, so that no path is cheap.
Theorem 1 (Trees bound the supremum from below) For every centered Gaussian process with separable canonical metric, \[ \mathbb E\sup_{t\in T}X_t\geq c''\,\gamma_2'(T,d). \]
Let \(\mathcal T\) be a finite \(\alpha\)-packing tree; the general case follows by taking suprema over finite subtrees. We prove by downward induction on the depth that for every member \(A\), \[ \mathbb E\sup_{t\in A}X_t\geq c''\inf_{\text{chains from }A}\sum_{k\geq k(A)}\alpha^k\operatorname{diam}(T)\sqrt{\log(\#\text{children of }A_k)}, \] where the chains run \(A=A_{k(A)}\supsetneq A_{k(A)+1}\supsetneq\cdots\) to a leaf. For a leaf the right side is \(0\) and the left side is nonnegative, since \(X\) is centered. For a member \(A\) with children \(B_1,\ldots,B_N\), \(N\geq2\), the children have diameters at most \(c\alpha^{k(A)+1}\operatorname{diam}(T)\) and are pairwise at distance at least \(\varepsilon:=\alpha^{k(A)+1}\operatorname{diam}(T)\), so Lemma 1 applies with this \(\varepsilon\): \[ \mathbb E\sup_AX\geq c'\alpha^{k(A)+1}\operatorname{diam}(T)\sqrt{\log N}+\min_j\mathbb E\sup_{B_j}X . \] By induction each \(\mathbb E\sup_{B_j}X\) dominates \(c''\) times the cheapest chain from \(B_j\), and the minimum over \(j\) of the cheapest chain from \(B_j\), plus the first term, is \(c''\) times the cheapest chain from \(A\) once \(c''\leq c'\alpha\). For a member with a single child the lemma is not needed, as \(\log1=0\) and the supremum over \(A\) dominates that over the child. Taking \(A=T\) finishes the proof.
The proof is Sudakov’s minoration applied once at every branching, with the remainders passed down the tree. In the language of the handwritten notes, the Gaussian process is being compared with a branching process: the comparison process \(Y\) of Lemma 1, iterated along the tree, is a Gaussian random walk on the tree in which each edge at depth \(k\) carries an independent Gaussian of size \(\alpha^k\operatorname{diam}(T)\), and \(\mathbb E\sup X\) dominates the expected maximum of this branching random walk over the ends of the tree. Lecture 10 introduced exactly this process, the Gaussian branching random walk, as an example.
What remains for the majorizing measure theorem is the purely metric statement \[ \gamma_2(T,d)\leq C\gamma_2'(T,d), \tag{1}\] that a space with no expensive packing tree admits a cheap admissible sequence. This is the genuinely hard step of Talagrand’s theorem and we do not prove it. The argument in van Handel’s notes (Handel 2016) proceeds by showing that the functional \(G(A):=\mathbb E\sup_AX\), or abstractly any functional satisfying the growth inequality of Lemma 1, can be used to build the admissible sequence greedily, choosing at each stage the points where \(G\) is largest. Granting Equation 1, the chain \[ c\gamma_2(T,d)\leq c\,C\gamma_2'(T,d)\leq C'\,\mathbb E\sup X\leq C''\gamma_2(T,d) \] is the majorizing measure theorem.
A different reformulation, from the handwritten notes of 2023, makes the theorem concrete for subsets of \(\mathbb R^n\). Suppose \(T\subseteq\operatorname{conv}\{t_1,t_2,\ldots\}\) for a sequence of points \(t_j\), and fix any \(s\in\mathbb R^n\). Since width ignores convex hulls and translations (Lecture 3), and the union bound of Lecture 4 gives \(\mathbb E\sup_j\langle g,t_j-s\rangle\leq C\sup_j\|t_j-s\|_2\sqrt{\log(j+1)}\) by comparing each \(\langle g,t_j-s\rangle\) with a Gaussian of variance \(\|t_j-s\|_2^2\) against the threshold \(\|t_j-s\|_2\sqrt{2\log(j+1)}\), one finds \[ w(T)\leq C\inf_{(t_j)}\ \inf_s\ \sup_j\|t_j-s\|_2\sqrt{\log(j+1)} . \] Talagrand’s theorem implies that this is sharp: the right side is at most \(C'w(T)\) for every bounded \(T\). The proof takes an admissible sequence realizing \(\gamma_2(T)\leq Cw(T)\), writes each \(t\in T\) as \(t=s+\sum_k(t_k-t_{k-1})\) along its chain, and rescales the increments \(t_k-t_{k-1}\) by \(2^{k/2}d(t_{k-1},t_k)/w(T)\) so that the rescaled increments have \(\ell^1\)-summable coefficients and \(t\) becomes a convex combination of them; the enumerated rescaled increments are the \(t_j\), and there are at most \(2^{2^{k+1}}\) of them at stage \(k\), which is what produces the \(\sqrt{\log j}\). So in \(\mathbb R^n\) the width of \(T\) is, up to constants, the smallest scale at which \(T\) fits in the convex hull of a sequence of points whose distances from a common center decay like \(1/\sqrt{\log j}\).
3 Comparison for sub-Gaussian processes
The form of the theorem used below is the following.
Corollary 1 (Talagrand’s comparison inequality) Let \((X_t)_{t\in T}\) be a centered process that is sub-Gaussian with respect to \(Kd\), where \(d\) is the canonical metric of some centered Gaussian process \((Y_t)_{t\in T}\) with \((T,d)\) separable. Then for every \(t_0\in T\), \[ \mathbb E\sup_{t\in T}|X_t-X_{t_0}|\leq CK\,\mathbb E\sup_{t\in T}Y_t . \]
By the generic chaining bound of Lecture 18 applied to the metric \(Kd\), \(\mathbb E\sup_t|X_t-X_{t_0}|\leq C\gamma_2(T,Kd)=CK\gamma_2(T,d)\), and by the lower half of the majorizing measure theorem \(\gamma_2(T,d)\leq C'\mathbb E\sup_tY_t\).
For \(T\subseteq\mathbb R^n\) and \(d\) the Euclidean metric, the Gaussian process is \(Y_x=\langle g,x\rangle\) and the right side is \(CKw(T)\). So a process indexed by vectors whose increments are sub-Gaussian at the scale of the Euclidean distance is controlled by the Gaussian width of the index set. This is a statement with no direct proof: the only known route runs through Talagrand’s theorem.
4 The matrix deviation inequality
Let \(A\) be an \(m\times n\) matrix whose rows \(A_1,\ldots,A_m\) are independent, mean-zero, isotropic, \(K\)-subgaussian random vectors, in the sense of Lecture 9. Consider the process \[ X_x:=\|Ax\|_2-\sqrt m\|x\|_2 , \qquad x\in\mathbb R^n . \] It is centered up to a bounded error, since \(\mathbb E\|Ax\|_2\) is within \(CK\|x\|_2\) of \(\sqrt m\|x\|_2\) by the concentration of the norm, and it is positively homogeneous: \(X_{\lambda x}=\lambda X_x\) for \(\lambda\geq0\).
Theorem 2 (Sub-Gaussian increments of the norm process) For all \(x,y\in\mathbb R^n\), \[ \|X_x-X_y\|_{\psi_2}\leq CK\|x-y\|_2 . \]
Recall from Lecture 9 that for a unit vector \(u\) the coordinates \(\xi_i=\langle A_i,u\rangle\) are independent, mean-zero, of variance \(1\), with \(\|\xi_i\|_{\psi_2}\leq2\sqrt K\) and \(\|\xi_i^2-1\|_{\psi_1}\leq6K\), and that isotropy forces \(K\geq1\). Throughout, \(c\) and \(C\) are absolute constants that may change from line to line.
Step 1: one unit vector. Let \(\|x\|_2=1\). Bernstein’s inequality (Lecture 6) for \(\|Ax\|_2^2-m=\sum_i(\xi_i^2-1)\) gives \[ \mathbb P\big\{|\|Ax\|_2^2-m|\geq r\big\}\leq2\exp\Big(-c\min\Big\{\frac rK,\frac{r^2}{mK^2}\Big\}\Big). \] If \(|\|Ax\|_2-\sqrt m|\geq s\) then \(|\|Ax\|_2^2-m|\geq\max\{s\sqrt m,s^2\}\), by the case analysis in the Gram-to-singular-value lemma of Lecture 9. With \(r=\max\{s\sqrt m,s^2\}\) both terms in the minimum are at least \(s^2/K^2\), so \[ \mathbb P\big\{|\|Ax\|_2-\sqrt m|\geq s\big\}\leq2e^{-cs^2/K^2}, \qquad\text{i.e.}\qquad \|X_x\|_{\psi_2}\leq CK . \] This is the claim for \(y=0\) and unit \(x\).
Step 2: two unit vectors, squared. Let \(\|x\|_2=\|y\|_2=1\), \(x\neq y\), and set \(u=(x-y)/\|x-y\|_2\), \(v=x+y\). Then \[ Z:=\frac{\|Ax\|_2^2-\|Ay\|_2^2}{\|x-y\|_2}=\langle Au,Av\rangle=\sum_{i=1}^m\langle A_i,u\rangle\langle A_i,v\rangle . \] The summands are independent. They are mean zero, because by isotropy \(\mathbb E\langle A_i,x-y\rangle\langle A_i,x+y\rangle=\mathbb E\langle A_i,x\rangle^2-\mathbb E\langle A_i,y\rangle^2=0\). By the Orlicz–Hölder inequality of Lecture 5 their \(\psi_1\) norms are at most \(\|\langle A_i,u\rangle\|_{\psi_2}\|\langle A_i,v\rangle\|_{\psi_2}\leq2\sqrt K\cdot2\sqrt K\|v\|_2\leq8K\). Bernstein’s inequality gives, for \(0\leq s\leq\sqrt m\), \[ \mathbb P\{|Z|\geq s\sqrt m\}\leq2\exp\Big(-c\min\Big\{\frac{s\sqrt m}K,\frac{s^2}{K^2}\Big\}\Big)\leq2e^{-cs^2/K^2}, \] since \(s\sqrt m\geq s^2\) and \(K\geq1\) in this range.
Step 3: two unit vectors, unsquared. Still with \(\|x\|_2=\|y\|_2=1\), let \(p(s):=\mathbb P\{|\|Ax\|_2-\|Ay\|_2|\geq s\|x-y\|_2\}\).
Case \(s\leq2\sqrt m\). Multiplying the defining inequality by \(\|Ax\|_2+\|Ay\|_2\geq\|Ax\|_2\) shows that the event implies \(|Z|\geq s\|Ax\|_2\). Hence \[ p(s)\leq\mathbb P\{|Z|\geq s\sqrt m/2\}+\mathbb P\{\|Ax\|_2\leq\sqrt m/2\} \leq2e^{-cs^2/4K^2}+2e^{-cm/4K^2}\leq4e^{-cs^2/16K^2}, \] using Step 2 for the first term, Step 1 for the second, and \(m\geq s^2/4\).
Case \(s>2\sqrt m\). Since \(|\|Ax\|_2-\|Ay\|_2|\leq\|A(x-y)\|_2=\|x-y\|_2\|Au\|_2\), \[ p(s)\leq\mathbb P\{\|Au\|_2\geq s\}\leq\mathbb P\{\|Au\|_2-\sqrt m\geq s/2\}\leq2e^{-cs^2/4K^2} \] by Step 1. In both cases \(p(s)\leq4e^{-cs^2/K^2}\), so \(\|X_x-X_y\|_{\psi_2}\leq CK\|x-y\|_2\) for unit \(x,y\), the \(\sqrt m\) terms cancelling because \(\|x\|_2=\|y\|_2\).
Step 4: general \(x,y\). By homogeneity and symmetry assume \(\|x\|_2=1\) and \(0<\|y\|_2\leq1\) (the case \(y=0\) is Step 1), and let \(\bar y=y/\|y\|_2\). Then \[ X_x-X_y=(X_x-X_{\bar y})+(X_{\bar y}-X_y)=(X_x-X_{\bar y})+(1-\|y\|_2)X_{\bar y}, \] using \(X_y=\|y\|_2X_{\bar y}\). By Step 3, \(\|X_x-X_{\bar y}\|_{\psi_2}\leq CK\|x-\bar y\|_2\leq2CK\|x-y\|_2\), since \(\|y-\bar y\|_2=1-\|y\|_2=\|x\|_2-\|y\|_2\leq\|x-y\|_2\). By Step 1, \(\|(1-\|y\|_2)X_{\bar y}\|_{\psi_2}\leq CK(1-\|y\|_2)\leq CK\|x-y\|_2\). The triangle inequality for the \(\psi_2\) norm finishes the proof.
Theorem 3 (Matrix deviation inequality) Let \(A\) be an \(m\times n\) matrix with independent, mean-zero, isotropic, \(K\)-subgaussian rows, and let \(T\subseteq\mathbb R^n\) be bounded with \(\operatorname{rad}(T):=\sup_{x\in T}\|x\|_2\). Then \[ \mathbb E\sup_{x\in T}\Big|\|Ax\|_2-\sqrt m\|x\|_2\Big|\leq CK\big(w(T)+\operatorname{rad}(T)\big), \] and for every \(u\geq0\), with probability at least \(1-2e^{-u^2}\), \[ \sup_{x\in T}\Big|\|Ax\|_2-\sqrt m\|x\|_2\Big|\leq CK(1+u)\big(w(T)+\operatorname{rad}(T)\big). \]
Fix \(x_0\in T\). By Theorem 2 the process \((X_x)_{x\in T}\) is sub-Gaussian with respect to \(CK\|x-y\|_2\), the canonical metric of the Gaussian width process \(\langle g,x\rangle\) up to the constant. The generic chaining tail bound of Lecture 18 and the majorizing measure theorem give, with probability at least \(1-2e^{-u^2}\), \[ \sup_{x\in T}|X_x-X_{x_0}|\leq CK(1+u)\gamma_2(T,\|\cdot\|_2)\leq C'K(1+u)w(T), \] where \(w(T)=\mathbb E\sup_{x\in T}\langle g,x\rangle\); the process \(X\) need not be exactly centered for the chaining argument, which only uses the increments. The base point contributes \(|X_{x_0}|\), and by Step 1 of the previous proof \(\|X_{x_0}\|_{\psi_2}\leq CK\|x_0\|_2\leq CK\operatorname{rad}(T)\), so \(|X_{x_0}|\leq CK(1+u)\operatorname{rad}(T)\) outside an event of probability \(2e^{-u^2}\). Adding the two bounds, and adjusting constants to merge the two exceptional events, gives the tail bound; integrating in \(u\) gives the expectation bound.
The inequality says that a random matrix with sub-Gaussian rows acts on an arbitrary set of vectors as \(\sqrt m\) times an isometry, up to an additive error measured by the Gaussian width of the set. Several results from earlier in the course are special cases.
The sphere. For \(T=S^{n-1}\), \(w(T)=\mathbb E\|g\|_2\leq\sqrt n\) and \(\operatorname{rad}(T)=1\), so \[ \mathbb E\sup_{\|x\|_2=1}\Big|\|Ax\|_2-\sqrt m\Big|\leq CK\sqrt n , \] which is the two-sided bound \(\sqrt m\pm CK\sqrt n\) on the singular values from Lecture 9, now obtained without a net.
Finite sets and Johnson–Lindenstrauss. For \(T\) the set of normalized differences of \(N\) points, \(w(T)\leq\sqrt{2\log N}\) by Lecture 3, and the inequality recovers the embedding dimension \(m\gtrsim\varepsilon^{-2}\log N\) of Lecture 6, for matrices with sub-Gaussian rows rather than independent entries.
Infinite sets. For a general bounded \(T\), taking \(T-T\) as the index set gives, with high probability, \[ (1-\varepsilon)\sqrt m\|x-y\|_2\leq\|Ax-Ay\|_2\leq(1+\varepsilon)\sqrt m\|x-y\|_2 \qquad\text{for all }x,y\in T\text{ with }\|x-y\|_2\geq\delta , \] as soon as \(\sqrt m\,\varepsilon\delta\gtrsim K\,w(T)\). So \(A/\sqrt m\) preserves all distances in \(T\) above a resolution \(\delta\), provided \(m\gtrsim K^2w(T)^2/(\varepsilon\delta)^2\): the Johnson–Lindenstrauss phenomenon with \(\log N\) replaced by the squared Gaussian width, which is the stable dimension of Lecture 13 when \(\delta\) is the diameter.
5 Where we go next
The matrix deviation inequality is a random-matrix statement whose only geometric input is the Gaussian width of the index set. The next lecture returns with it to the covariance estimation problem of Lecture 9 and proves the effective-rank theorem that was stated there: for Gaussian data, the sample covariance converges at the rate \(\sqrt{r(\Sigma)/m}\) with \(r(\Sigma)=\operatorname{tr}\Sigma/\|\Sigma\|_{\mathrm{op}}\), because the relevant index set is an ellipsoid whose width is \(\sqrt{\operatorname{tr}\Sigma}\). After that, the same inequality yields the sample complexity of sparse recovery.