Rademacher and Gaussian Complexity
Gaussian and Rademacher processes have comparable upper-bound techniques, but their lower bounds can differ. On the coordinate vectors, a random-sign maximum stays bounded while a Gaussian maximum grows. This example explains why a Rademacher version of Sudakov’s inequality needs an additional restriction. We then compare Gaussian complexity with Rademacher complexity directly and use Gaussian comparison to estimate matrix norms.
Here \(\varepsilon_i\) are independent Rademacher signs and \(g_i\) are independent standard normal variables. We compare sums with these two kinds of multipliers; the Gaussian supremum bounds will be useful.
Let \(S(T)=\mathbb E_\varepsilon\sup_{t\in T}|\langle\varepsilon,t\rangle|\) and \(b(T)=\sup_{t\in T}\|t\|_\infty\), for a nonempty bounded subset of \(\mathbb R^n\). Unlike a Gaussian maximum, the Rademacher maximum on \(T=\{e_1,\ldots,e_n\}\) is exactly one even though the Euclidean covering number at any fixed radius below \(1/2\) is \(n\). A Gaussian-style lower bound therefore needs an additional condition on individual coordinates.
Theorem 1 (Rademacher Sudakov bound). There exist universal constants \(c_*,C>0\) such that, for every nonempty bounded \(T\subset\mathbb R^n\) and every \(a>0\), the condition
implies \(a\sqrt{\log N(a,T,\|\cdot\|_2)}\le C S(T)\). The constants are fixed independently of \(T,n,a\). The product formulation also covers \(T=\{0\}\), without dividing by a zero coordinate bound.
Lemma 2. For \(Z=\sum_i\varepsilon_it_i\),
Proof. Independence and symmetry leave only terms with even multiplicities in the fourth moment:
Hölder, applied to \(|Z|^{2/3}|Z|^{4/3}\) with exponents \(3/2,3\), gives \(\mathbb EZ^2\le(\mathbb E|Z|)^{2/3}(\mathbb EZ^4)^{1/3}\). If \(\mathbb EZ^2>0\), divide by its two-thirds power and raise to the power \(3/2\). If the second moment is zero the claim is immediate. In particular, \(\sup_{t\in T}\|t\|_2\le\sqrt3S(T)\). ◻
Lemma 3 (Truncated Gaussian mgf). If \(g\sim \mathcal{N}(0,1)\), \(h=g\mathbf1\{|g|>w\}\), and \(w>0\), then for \(|\lambda|\le w/4\),
Proof. The mgf \(M\) has \(M(0)=1\), \(M'(0)=0\), by symmetry. On \(|x|>w\) and \(|\lambda|\le w/4\), we have \(\lambda x\le x^2/4\). Hence
Integrating twice proves the bound, for positive and negative \(\lambda\). All differentiation is justified by Gaussian exponential moments. This direct estimate avoids changing a tail domain to a smaller set, which would reverse the required inequality. ◻
Proof of Theorem 1: local estimate. First let \(U\subset B_2(0,1)\), write \(S=S(U)\), \(b=b(U)\), and suppose \(bS\le c_0\), for a sufficiently small universal \(c_0\). We prove
Take any finite \(1/2\)-separated family \(V\subset U\) of size \(m\ge2\), and put \(L=\log m\). Gaussian Sudakov gives \(c\sqrt L\le\mathbb E\max_{v\in V}|\langle g,v\rangle|\), for a universal \(c>0\). Decompose \(g_i=m_i+h_i\), with \(h_i=g_i\mathbf1\{|g_i|>w\}\). Conditional on their magnitudes, the \(m_i\) have independent symmetric signs (a zero magnitude causes no difficulty). The expected absolute supremum is a convex even function of each multiplier, hence nondecreasing in its magnitude. Since \(|m_i|\le w\), its expectation is at most \(wS\).
For the tail part, Lemma 3 and independence imply, for \(|\lambda|\le w/(4b)\),
If \(b=0\), the local claim is trivial. Otherwise log-sum-exp over \(2m\) signed sums, with \(\lambda\) the smaller of a constant multiple of \(e^{w^2/16}\sqrt{\log(2m)}\) and \(w/(8b)\), gives
Combining the two parts yields
Here \(S>0\), because the separated family contains a nonzero vector and Lemma 2 applies. Set \(q=\sqrt L/S\). Choose a fixed \(\kappa>0\) with \(\kappa<c/4\), and take \(w=\kappa q\). If \(q\) exceeds a sufficiently large universal threshold, the middle term is below \(c/4\). The last term is \(CbS/\kappa\), below \(c/4\) when \(c_0\) is small enough. The first term is \(\kappa\). This contradicts the displayed inequality. Therefore \(q\) is universally bounded, proving \(\log m\le C_0S^2\) for every such finite packing. A maximal packing covers \(U\) at radius \(1/2\), proving the local estimate.
Proof of Theorem 1: refinement. Fix \(t_0\in T\). Lemma 2 gives \(T\subset B(t_0,R)\) with \(R=2\sqrt3S(T)\). If \(S(T)=0\), then \(T=\{0\}\). If \(a\ge R\), one ball suffices. Otherwise successively halve \(R\) until the first radius \(r_k=R2^{-k}\le a\); then \(a/2<r_k\le a\). At a parent ball of radius \(r>a\) centered at \(t\in T\), form
Translation is essential in this step. The product of the first two bounds is at most \(4c_*a^2/r^2\le4c_*\). Choose \(c_*\le c_0/4\). The local estimate then bounds the logarithm of each refinement count by \(4C_0S(T)^2/r^2\). Centers can be chosen in their cells. Multiplying counts and summing the geometric series gives
The final inequality uses \(R2^{-(k-1)}>a\). This proves the theorem, with the same absolute-supremum convention and all scale factors accounted for. ◻
1. Gaussian Complexity
For comparison with one-sided suprema, define the Gaussian width \(\mathcal G(T)=\mathbb E\sup_{t\in T}\langle g,t\rangle\). Bounded subsets of finite-dimensional Euclidean space have a countable dense subset and the linear processes are continuous, so these suprema are measurable. Absolute suprema correspond to replacing \(T\) by \(T\cup(-T)\).
Example 4 (\(\ell^q\)-balls). Let \(1\le q\le\infty\), \(1/p+1/q=1\), and \(B_q^d(1)=\{\theta:\|\theta\|_q\le1\}\). Duality gives \(\mathcal G(B_q^d(1))=\mathbb{E}\|w\|_p\). For \(1<q\le\infty\), so that \(p<\infty\), Jensen and a choice of coordinate signs yield
For the lower bound take \(\theta_i=d^{-1/q}\operatorname{sign}(w_i)\); for the upper bound apply concavity of the \(p\)th root to \(\sum_i|w_i|^p\). In particular \(\mathcal G(B_\infty^d(1))=d\sqrt{2/\pi}\). At the remaining endpoint \(q=1\), the exact expression is \(\mathbb{E}\max_i|w_i|\), bounded above by \(\sqrt{2\log(2d)}\), as proved below. A finite-\(p\) moment formula cannot be substituted at \(p=\infty\).
Lemma 5 (Rademacher and Gaussian comparison). Let \(d\ge1\) and let \(T\subset\mathbb R^d\) be nonempty and bounded. To match the one-sided Gaussian width defined above, write \(\mathcal R_+(T)=\mathbb{E}_\varepsilon\sup_{\theta\in T}\langle\varepsilon,\theta\rangle\). Then
For the absolute-supremum convention used earlier, apply both bounds to \(T\cup(-T)\). Both widths must use the same convention: a singleton already distinguishes the one-sided and absolute versions.
Proof. Write a standard Gaussian vector as \(w=\varepsilon\circ r\), where \(r_i=|w_i|\) are iid half-normal magnitudes and the signs are independent of the magnitudes. Put \(\varphi(r)=\mathbb{E}_\varepsilon\sup_{\theta\in T}\sum_i r_i\varepsilon_i\theta_i\). This is convex, and \(\mathbb{E}r_i=\sqrt{2/\pi}\). Jensen and homogeneity give
For the other direction, sign symmetry makes \(\varphi\) even in each coordinate. An even convex function is nondecreasing on the nonnegative half-line. Therefore, for \(M=\max_i r_i\), coordinatewise comparison yields \(\varphi(r)\le\varphi(M\mathbf1)=M\mathcal R_+(T)\). Finally, for \(\lambda>0\),
Minimizing at \(\lambda=\sqrt{2\log(2d)}\) proves the upper bound, including \(d=1\). The lower constant is attained for \(T=\{-1,1\}\) in dimension one. □
Lemma 6 (Gaussian contraction). Let \(T\subset\mathbb R^d\) be nonempty and bounded, and let each \(\varphi_j\) be 1-Lipschitz with \(\varphi_j(0)=0\). Then \(\mathcal G(\varphi(T))\le\mathcal G(T)\).
Proof. The two indexed processes \(X_t=\langle g,\varphi(t)\rangle\), \(Y_t=\langle g,t\rangle\) are centered Gaussian, and
Apply Sudakov–Fernique on finite subsets. A countable dense subset of \(T\) determines both suprema because the maps are continuous. Finite maxima converge, and are dominated by an integrable constant times \(\|g\|_2\), proving the assertion. The same finite-subset interpretation extends it to unbounded sets. ◻
Example 7 (Subgaussian matrix norm). Let \(W\in\mathbb R^{n\times d}\) have independent centered entries with \(\mathbb Ee^{\lambda W_{ij}}\le e^{\lambda^2/2}\). Write \(\|W\|_{\mathrm{op}}\) for its largest singular value and \(\|W\|_F^2=\sum_j\sigma_j(W)^2\). They need not agree. For the compact set \(\mathcal M=\{uv^\top:u\in S^{n-1},v\in S^{d-1}\}\),
The first identity follows from singular vectors; the second follows by multiplying the independent entry mgfs. In particular the indexed process has Frobenius-subgaussian increments.
Choose \(\delta/2\)-nets of the two unit spheres with cardinalities at most \((1+4/\delta)^n\) and \((1+4/\delta)^d\), respectively. The volumetric bound follows by placing disjoint balls of radius \(\delta/4\) around a maximal separated set and comparing their volumes with the ball of radius \(1+\delta/4\). For unit vectors,
The product net therefore gives an internal \(\delta\)-cover of \(\mathcal M\) with \(N\le(1+4/\delta)^{n+d}\) centers. Comparing every matrix to its center gives
For any matrix \(A\) of rank at most two, its singular-value decomposition gives
Here \(\Theta-\pi\Theta\) has rank at most two and Frobenius norm at most \(\delta\). Thus the residual is at most \(\sqrt2\delta\mathbb E\|W\|_{\mathrm{op}}\). This expectation is finite already, since it is at most \(\mathbb E\|W\|_F\le\sqrt{nd}\). Set \(\delta=1/(2\sqrt2)\) and absorb the residual to obtain
This explicit finite-net calculation supplies the scaling without the erroneous Gram-matrix factorization or numerical simplification in the source.
Example 8 (Gaussian matrix norm). For independent \(\mathcal{N}(0,1)\) entries, the sharp leading upper bound is
To prove it, compare \(Z_{u,v}=u^\top Wv\) with \(Y_{u,v}=\langle g,u\rangle+\langle h,v\rangle\), where \(g,h\) are independent standard Gaussian vectors. For \(a=\langle u,u'\rangle\), \(b=\langle v,v'\rangle\),
The second minus the first is \(2(1-a)(1-b)\ge0\). Sudakov–Fernique therefore gives the comparison, first on finite subsets and then on the compact product of spheres by continuity and integrable Frobenius domination. Since \(\sup_{u,v}Y_{u,v}=\|g\|_2+\|h\|_2\), Jensen proves the displayed bound.
Finally \(|\|W\|_{\mathrm{op}}-\|W'\|_{\mathrm{op}}|\le\|W-W'\|_F\), so the operator norm is 1-Lipschitz in the independent Gaussian entries. Gaussian concentration gives, for \(t\ge0\),
This uses the Gaussian Lipschitz concentration theorem, not the rank-two trace estimate. The leading constant one is necessary uniformly in dimensions: already for one column, \(\mathbb E\|g\|_2/\sqrt n\to1\), by the law of large numbers and uniform integrability. Taking \(d=1\), \(n\to\infty\), rules out any smaller universal coefficient multiplying \(\sqrt n+\sqrt d\).