Lecture 3: Gaussian Width
Random directions as a measure of geometric complexity
Covering numbers describe a set at a chosen resolution. Gaussian width instead asks how far the set extends in a random direction. It is a single number, but it remembers surprisingly subtle information about geometry, convexity, and statistical complexity.
Throughout, \(g\sim N(0,I_d)\) is a standard Gaussian vector in \(\mathbb R^d\).
1 Definition and first properties
Definition 1 (Gaussian width) For a bounded set \(T\subseteq\mathbb R^d\), its Gaussian width is \[ w(T)=\mathbb E\sup_{t\in T}\langle g,t\rangle. \] The support function \[ h_T(x)=\sup_{t\in T}\langle x,t\rangle \] therefore satisfies \(w(T)=\mathbb Eh_T(g)\).
The width is translation invariant. Indeed, \[ w(T+a)=w(T)+\mathbb E\langle g,a\rangle=w(T). \] It is also monotone, homogeneous for nonnegative scalars, and subadditive under Minkowski addition: \[ w(S+T)=w(S)+w(T). \]
Proposition 1 (Width ignores convexification) For every bounded \(T\subseteq\mathbb R^d\), \[ w(T)=w(\operatorname{conv}T)=w(\overline{\operatorname{conv}}T). \]
For every fixed \(x\), a linear functional takes the same supremum over \(T\) and over its convex hull: \[ \sup_{y\in\operatorname{conv}T}\langle x,y\rangle =\sup_{t\in T}\langle x,t\rangle. \] Continuity of the functional gives the same statement after closure. Apply this pointwise with \(x=g\) and take expectations.
By Carathéodory’s theorem, every \(t\in\operatorname{conv}T\) is a finite convex combination \(t=\sum_i\lambda_it_i\) with \(t_i\in T\), \(\lambda_i\geq0\), \(\sum_i\lambda_i=1\). For fixed \(g\), \[ \langle g,t\rangle=\sum_i\lambda_i\langle g,t_i\rangle \leq\sum_i\lambda_i\sup_{s\in T}\langle g,s\rangle =\sup_{s\in T}\langle g,s\rangle. \] Taking the supremum over \(t\in\operatorname{conv}T\) and then expectations gives \(w(\operatorname{conv}T)\leq w(T)\); the reverse inequality holds because \(T\subseteq\operatorname{conv}T\).
This is an important contrast with covering numbers. Convexification can add many points and greatly change the covering number at a fine scale, but it does not change Gaussian width at all.
Proposition 2 (Width and the symmetrized set) For every bounded \(T\subseteq\mathbb R^d\), \[ w(T)=\frac12w(T-T). \]
The set \(T-T\) is the Minkowski sum \(T+(-T)\), so by the additivity noted above, \[ w(T-T)=w(T)+w(-T). \] Since \(-g\stackrel{d}{=}g\), \[ w(-T)=\mathbb E\sup_{t\in T}\langle g,-t\rangle =\mathbb E\sup_{t\in T}\langle -g,t\rangle=w(T). \] Combining the two displays gives \(w(T-T)=2w(T)\).
2 Convex bodies, norms, and dual norms
A closed, convex, centrally symmetric set \(B\subseteq\mathbb R^d\) with \(0\) in its interior is called a convex body. Convex bodies correspond exactly to norms: a body \(B\) determines the norm \[ \|x\|_B=\inf\{t>0:x/t\in B\}, \] and every norm \(\|\cdot\|\) determines the body \(B=\{x:\|x\|\leq1\}\). To a convex body \(B\) we also associate its polar set \[ B^\circ=\{x:\langle x,y\rangle\leq1\text{ for all }y\in B\}, \] which is again a convex body, and is exactly the unit ball of the dual norm: \[ \|y\|_*=\sup_{\|x\|\leq1}\langle x,y\rangle,\qquad B^\circ=\{y:\|y\|_*\leq1\}. \] In this language, \[ w(B)=\mathbb E\sup_{x\in B}\langle g,x\rangle=\mathbb E\|g\|_{B^\circ}. \] Thus the Gaussian width of a convex body is the expected dual norm of a Gaussian vector.
Example 1 (Widths of standard sets) The following estimates hold with universal implicit constants: \[ \begin{aligned} w(B_2^d)&=\mathbb E\|g\|_2\asymp\sqrt d,\\ w(B_1^d)&=\mathbb E\|g\|_\infty\asymp\sqrt{\log d},\\ w(B_\infty^d)&=\mathbb E\|g\|_1\asymp d. \end{aligned} \]
These three sets live in the same ambient space but have very different Gaussian sizes. Width sees geometry that dimension alone cannot distinguish.
The order-of-magnitude estimates above hide genuine structure that is worth computing exactly. A moment computation for \(\|g\|_2^2\) gives \[ w(B_2^d)=\sqrt d-O(1/\sqrt d), \] and a sharp Gaussian tail bound applied to \(\mathbb E\|g\|_\infty=\int_0^\infty\mathbb P(\max_i|g_i|\geq t)\,dt\) gives \[ w(B_1^d)=\sqrt{2\log d}-\frac{\log\log d}{\sqrt{2\log d}} +O\!\left(\frac1{\sqrt{\log d}}\right). \] More generally, work out the exact rate of \(w(B_p^d)\) as a function of \(d\) for each \(1\leq p\leq\infty\); it interpolates between the \(\sqrt{\log d}\) rate at \(p=1\) and the linear rate at \(p=\infty\), passing through \(\sqrt d\) at \(p=2\).
3 Finite sets and Gaussian maxima
The basic calculation for a finite set is an exponential-moment argument.
Proposition 3 (Width of a finite set) Suppose \(T=\{t_1,\ldots,t_m\}\subseteq RB_2^d\) and \(m\geq2\). Then \[ w(T)\leq R\sqrt{2\log m}. \]
For every \(\lambda>0\), \[ \begin{aligned} \exp\left(\lambda\mathbb E\max_i\langle g,t_i\rangle\right) &\leq \mathbb E\exp\left(\lambda\max_i\langle g,t_i\rangle\right)\\ &\leq \sum_{i=1}^m\mathbb Ee^{\lambda\langle g,t_i\rangle}\\ &=\sum_{i=1}^m e^{\lambda^2\|t_i\|_2^2/2}\\ &\leq m e^{\lambda^2R^2/2}. \end{aligned} \] Taking logarithms gives \[ w(T)\leq\frac{\log m}{\lambda}+\frac{\lambda R^2}{2}. \] The choice \(\lambda=\sqrt{2\log m}/R\) minimizes the right-hand side.
For the vertices \(T=\{\pm e_1,\ldots,\pm e_d\}\), the proposition gives the correct \(\sqrt{\log d}\) scale. By Proposition 1, the same scale is the width of the entire \(\ell^1\) ball.
4 A harder example: sparse vectors
Example 2 (Sparse unit vectors) Let \[ U_s=\{x\in B_2^d:|\operatorname{supp}(x)|\leq s\} \] be the set of unit-norm vectors supported on at most \(s\) coordinates, for a fixed \(s\leq d\). Then \[ w(U_s)\asymp\sqrt{s\log(ed/s)}. \]
Unlike the examples above, \(U_s\) resists both of our tools at once: it is neither finite (so Proposition 3 does not apply) nor convex (so we cannot reduce to a ball via Proposition 1). In fact \[ w(U_s)=\mathbb E\sqrt{(g_{(1)}^*)^2+\cdots+(g_{(s)}^*)^2}, \] where \(g_{(1)}^*\geq\cdots\geq g_{(d)}^*\) is the decreasing rearrangement of \(|g_1|,\ldots,|g_d|\) — not an expression we can evaluate with the tools built so far. Bounding suprema of Gaussian processes over sets that are neither finite nor convex is exactly the problem that chaining, developed later in the course, is built to solve.
This raises the natural question behind the rest of the lecture: how do we estimate the supremum of a general Gaussian process from the geometry of the index set alone? Sudakov’s inequality is the first, one-scale answer.
5 Width and metric entropy
A well-separated set forces a Gaussian process to have a large maximum. The result that formalizes this principle is Sudakov’s minoration.
Theorem 1 (Sudakov minoration) There is a universal constant \(c>0\) such that every bounded \(T\subseteq\mathbb R^d\) satisfies \[ w(T)\geq c\varepsilon \sqrt{\log N(T,\|\cdot\|_2,\varepsilon)} \] for every \(\varepsilon>0\). Equivalently, \[ \log N(T,\varepsilon) \leq C\frac{w(T)^2}{\varepsilon^2} \] for a universal \(C\).
Choose a maximal \(\varepsilon\)-packing \(t_1,\ldots,t_m\). The Gaussian variables \(X_i=\langle g,t_i\rangle\) satisfy \[ \mathbb E(X_i-X_j)^2=\|t_i-t_j\|_2^2>\varepsilon^2. \] A Gaussian comparison argument reduces the problem to the expected maximum of \(m\) independent Gaussians with variance of order \(\varepsilon^2\), which is of order \(\varepsilon\sqrt{\log m}\). The comparison theorem and its proof will be developed in the Gaussian-process part of the course.
Sudakov’s inequality says that width controls the entropy at each individual scale. There is a companion principle in the other direction, Dudley’s inequality, which aggregates the entropy at every scale into a single bound on \(w(T)\). We postpone even stating it until we have built chaining, the technique that both proves it and that will let us finally bound quantities like \(w(U_s)\) from Example 2 above.
6 Looking ahead
Sudakov’s proof, once completed, will rest on a comparison theorem for Gaussian processes — a way to compare \(\mathbb E\sup_tX_t\) across two processes from a comparison of their covariance structures. Before we can prove that, we need sharper control of individual Gaussian and sub-Gaussian tails. The next lecture builds exactly that: a reusable calculus of exponential moments for sums and maxima of random variables.