Rademacher Complexity Bounds for Concrete Models and Losses

Ma’s chapter 5 has two main focuses:

1. Rademacher complexity for two important hypothesis classes: linear models and two-layer neural networks.
2. Develop margin theory for bounding the generalization gap for binary classifiers.

📌 Scope note. The running setting of this chapter is binary classification — \(y\in\{\pm1\}\), \(0/1\) loss — and generalization always enters through margin theory: every final “generalization loss \(\le\)” display below, (5.13), (5.40), (5.76), (5.102), is a bound on classification error.

📌 What is a hypothesis class? A set \(\mathcal{H}\) of candidate predictors \(h:\mathcal{X}\to\mathcal{Y}\), fixed before seeing the data. In our setting it is almost always a parametric family \(\mathcal{H} = \{h_\theta : \theta\in\Theta\}\), and the constraint defining \(\Theta\) (a norm ball, say) is what all the complexity bounds below are actually measuring. The “fixed before seeing the data” part is not us trying to be unnecessarily precise. Remark 5.4 is a great illustration of a subltle place where you lose this property in the middle of a seeminlgy innocent analysis.

Since everything in this chapter is stated in terms of Rademacher complexity, we include two important defintions. The primary reference is my STAT 210B notes, §7 (“Concentration Inequalities for Gaussian and Rademacher Processes”), where the quantity arises via symmetrization as a bound on the excess risk of empirical risk minimization; see also Ma, Ch. 4.

Definition (Empirical (sample) Rademacher complexity). Let \(\mathcal{F}\) be a class of real-valued functions on a domain \(\mathcal{Z}\), and let \(S = (z_1,\dots,z_n) \in \mathcal{Z}^n\) be a fixed sample. The empirical Rademacher complexity of \(\mathcal{F}\) with respect to \(S\) is

where \(\sigma_1,\dots,\sigma_n\) are i.i.d. Rademacher signs, \(\mathbb{P}(\sigma_i = 1) = \mathbb{P}(\sigma_i = -1) = \tfrac12\), independent of everything else.

Definition (Average (population) Rademacher complexity). If the sample is drawn as \(z_1,\dots,z_n \overset{\mathrm{iid}}{\sim} P\), the average Rademacher complexity of \(\mathcal{F}\) at sample size \(n\) is

i.e. the empirical Rademacher complexity averaged over the draw of the sample.

📌 What does it measure? \(R_S(\mathcal{F})\) measures how well \(\mathcal{F}\) can line up with the \(2^n\) possible sign patterns of \((\sigma_1,\dots,\sigma_n)\). The idea is that a more expressive class can correlate with more of these random directions, so it has larger Rademacher complexity. Since the Rademacher sign’s are just random noise, we can also think of the Rademacher complexity as a measure of the model classes ability to fit (or overfit) to random noise.

📌 One observation about Rademacher Complexity which is relevant to §5.3.1 later. \(R_S(\mathcal{F})\) depends on \(\mathcal{F}\) only through the output set \(Q = \{(f(z_1),\dots,f(z_n))^\top : f\in\mathcal{F}\}\subseteq\mathbb{R}^n\), since \(R_S(\mathcal{F}) = \mathbb{E}_\sigma\big[\sup_{v\in Q}\frac1n\langle\sigma,v\rangle\big]\) (Ma, (4.98)–(4.99)). So Rademacher complexity sees the functions a class can realize and nothing about how they are parameterized. Two parameterizations with the same \(Q\) have the same complexity.

Margin theory

Assumption 1. The dataset \(D = ((x^{(1)},y^{(1)}),\dots,(x^{(n)},y^{(n)}))\) is completely separable. That is, there exists some \(h_\theta\in\mathcal{H}\) such that \(y^{(i)} = \operatorname{sgn}(h_\theta(x^{(i)}))\) for all \(i=1,\dots,n\).

Here \(\mathcal{H}\) is a parametric family indexed by \(\theta\). Separability is not a necessary condition, but it makes the final bound derivation cleaner.

Definition ((Unnormalized) margin; Ma 5.1). Fix the hypothesis \(h_\theta\). The (unnormalized) margin for the example \((x,y)\) is

Margin is only defined on examples where \(\operatorname{sgn}(h_\theta(x)) = y\). Under Assumption 1, \(\operatorname{margin}(x)\ge 0\) on the training set.

Context: \(y\in\{1,-1\}\) and \(h_\theta(x)\in\mathbb{R}\).

📌 Why does this definition make sense? Because \(h_\theta(x)\) carries two pieces of information that the sign alone throws away: which side of the boundary we are on, and how far. Multiplying by \(y\in\{\pm1\}\) keeps the magnitude and converts the sign into a correctness indicator, so \(yh_\theta(x)>0\) means correct and, heuristically speaking, \(\lvert yh_\theta(x)\rvert\) measures confidence. In this definition we are taking \(h_\theta\) to be a hypothesis that separates the data, whose existence Assumption 1 asserts.

Definition (Minimum margin; Ma 5.2). Given a dataset \(D\), the minimum margin over the dataset is

Looking ahead, the final bound will be of the form

This is generic: many bounds are available depending on which margin we use. Here we use \(\gamma_{\min}\), but other settings use \(\gamma_{\text{average}}\), the average margin over the dataset.

📌 Intuition. Classifiers with larger margins are better, in terms of generalization, even if the training loss does not change. The picture I have in mind is the one dimension SVM perfectly separating data. You can choose many possible models which separate the data but the one with the largest margin intuitivley feels strongest. To be precise, under Assumption 1 every hypothesis we are comparing has training \(0/1\) error exactly zero, so training loss cannot distinguish them at all. The bound (5.13) still separates them, and it does so using a quantity (\(\gamma_{\min}\)). This is the same phenomenon as the AdaBoost observation that test error keeps falling after training error hits zero.

Surrogate loss

The idea of a surrogate loss is that it approximates the \(0/1\) loss but takes the scale of the margin into account. The margin loss (or ramp loss) is defined as

📌 Two things the picture makes obvious. (i) \(\ell_\gamma \ge \ell_{0\text{-}1}\) pointwise, which is (5.2) and is the only property used to pass to the population bound. (ii) \(\ell_\gamma\) is \(\frac1\gamma\)-Lipschitz because the only sloped piece has slope \(\tfrac{-1}{\gamma}\), whereas \(\ell_{0\text{-}1}\) is not Lipschitz at all — it is discontinuous at \(0\). That is the trade: we give up tightness of the loss function on \([0,\gamma]\) and buy bound in terms of a finite Lipschitz constant. Smaller \(\gamma\) means a tighter surrogate but a worse Lipschitz constant, and the tradeoff between those two is resolved by taking \(\gamma = \gamma_{\min}\), the largest \(\gamma\) that still zeroes out the empirical term.

Define \(\ell_\gamma((x,y),h) \triangleq \ell_\gamma(yh(x))\).

We can think of \(\ell_\gamma\) as a continuous version of the \(0/1\) loss that is sensitive to what the margin is. For all \((x,y)\),

Thus

so we can use the surrogate risk to bound the risk we care about.

The empirical version of the margin loss is

📌 Notation, since \(\ell\) and \(L\) are both overloaded. There are three distinct objects and \(\gamma\) is a subscript on all of them:

• \(\ell_\gamma:\mathbb{R}\to[0,1]\) is the scalar function drawn above, (5.1). Its argument is a real number.
• \(\ell_\gamma((x,y),h)\) is that same function evaluated at the margin, \(t = yh(x)\). This is a per-example loss, so it takes an example and a hypothesis and returns a number in \([0,1]\).
• \(L_\gamma(h) = \mathbb{E}\,\ell_\gamma((x,y),h)\) is the population margin risk and \(\widehat L_\gamma(h)\) is its empirical average. Capital \(L\) is a risk (an average of losses), lowercase \(\ell\) is a loss (one example).

By the Rademacher generalization bound (Ma, Thm. 4.18 and Cor. 4.19), with probability at least \(1-\delta\),

where \(\mathcal{F} = \{(x,y)\mapsto \ell_\gamma((x,y),h) : h\in\mathcal{H}\}\).

Lemma (Talagrand’s lemma / contraction; Ma 5.3). Let \(\phi:\mathbb{R}\to\mathbb{R}\) be \(\kappa\)-Lipschitz. Then

where \(\phi\circ\mathcal{H} = \{z\mapsto \phi(h(z)) : h\in\mathcal{H}\}\). See my STAT 210B notes, §7 (“Ledoux–Talagrand construction”), for a proof of the \(1\)-Lipschitz version over \(T\subseteq\mathbb{R}^n\); (5.6) follows by rescaling and taking \(T=\{(h(z_1),\dots,h(z_n)):h\in\mathcal{H}\}\).

Apply this with \(\phi(t) = \ell_\gamma(t)\), which is \(\tfrac1\gamma\)-Lipschitz, and \(\mathcal{F} = \ell_\gamma\circ\mathcal{H}’\) where \(\mathcal{H}’ = \{(x,y)\mapsto yh(x) : h\in\mathcal{H}\}\). The full derivation:

📌 Interpretation of the one step that is not bookkeeping: (5.8) to (5.9) drops the labels entirely. This works because \(y^{(i)}\in\{\pm1\}\) and \(\sigma_i\) is a symmetric sign, so \(\sigma_i y^{(i)} \overset{d}{=} \sigma_i\), and the two collections are equal in joint distribution since the \(\sigma_i\) are independent. So \(R_S\) of the label-weighted class equals \(R_S\) of the raw class: Rademacher complexity of \(\mathcal{H}\) does not see the labels at all. The complexity term measures how well the hypothesis class can correlate with pure noise on the given inputs, which is why the same \(R_S(\mathcal{H})\) shows up regardless of what the \(y^{(i)}\) are.

Putting it together, for \(\gamma = \gamma_{\min}\),

with probability at least \(1-\delta\), where \(R_S(\mathcal{H})\) is the empirical Rademacher complexity of \(\mathcal{H}\).

📌 Spelling out the \(0\), since it kinda just deletes a term and I wanna be clear on why its valid. Rearranging (5.5) gives \(L_\gamma(h) \le \widehat L_\gamma(h) + 2R_S(\mathcal{F}) + 3\sqrt{\log(2/\delta)/2n}\); the leading term is the empirical margin risk, not \(0\). It becomes \(0\) only after we choose \(\gamma = \gamma_{\min}\):

\[\widehat L_{\gamma_{\min}}(h) = \frac1n\sum_{i=1}^n \ell_{\gamma_{\min}}\big(y^{(i)}h(x^{(i)})\big) = 0\]

because every training margin satisfies \(y^{(i)}h(x^{(i)})\ge\gamma_{\min}\) by definition of the minimum, and \(\ell_\gamma(t) = 0\) for \(t\ge\gamma\) — the flat right piece of the ramp in the figure. So \(\gamma_{\min}\) is exactly the largest threshold at which every point still sits in the 0 region. Then note where \(\gamma\) goes in the second term: (5.7) contributed a factor \(1/\gamma\), so choosing \(\gamma\) large shrinks the complexity term. The two effects pull in opposite directions — larger \(\gamma\) shrinks \(R_S(\mathcal{F})\) but eventually makes \(\widehat L_\gamma > 0\) — and \(\gamma = \gamma_{\min}\) is the corner where the first term is still exactly zero. That single choice is what turns (5.5) into (5.13), and it is why \(\gamma_{\min}\) rather than any other margin appears in the denominator.

In summary,

“This bound states that simpler models will generalize better beyond the training data, particularly for data that is strongly separable.”

Remark (Ma 5.4). If the dataset is random, so is \(\gamma_{\min}\). This is not valid when thinking about Rademacher complexity.

📌 Why it is not valid, spelled out. Two separate failures, both from the same cause. (i) We applied Talagrand’s lemma with \(\kappa = 1/\gamma\), but the lemma requires a deterministic Lipschitz constant — a random \(\kappa\) means the function class \(\mathcal{F} = \ell_\gamma\circ\mathcal{H}’\) is itself data-dependent, and \(R_S\) is only defined for a class fixed in advance. (ii) The concentration inequality behind (5.5) needs the summands \(\ell_\gamma((x^{(i)},y^{(i)}),h)\) to be independent, which fails once \(\gamma\) is a function of the whole sample. This is the same pathology as term (1) of the excess-risk decomposition: the moment the object depends on the sample, you cannot use a pointwise inequality, and you have to pay for uniformity.

There is a fix via a union bound argument. Take \(\Gamma = \{2^k : k\in[-B,B]\}\). For each fixed \(\gamma\in\Gamma\) the bound (5.5) holds with probability \(\ge 1-\delta\); a union bound over \(\Gamma\) gives, for all \(\gamma\in(0,B)\),

Then choose the largest \(\gamma\in\Gamma\) with \(\gamma\le\gamma_{\min}\). The extra \(\widetilde O(\sqrt{\log B/n})\) is the price of the uniform convergence argument needed to correct the heuristic bound (5.13).

Takeaways from the union-bound fix

The full proof of the fix is written out in my LaTeX notes but omitted here (I haven’t read it in full myself yet). Two structural takeaways are worth keeping:

📌 How is randomness causing a problem? Random data makes \(\gamma\) random which means the function class \(\mathcal{F}_\gamma\) is also random, and every tool in Chapter 4 — symmetrization, the contraction lemma, the definition of \(R_S\) itself — presupposes a class fixed before the draw. The union bound repairs exactly this: each \(\mathcal{F}_\gamma\) for \(\gamma\) in the grid is deterministic, and the only randomness in the final step is which of finitely many deterministic statements we invoke.

📌 The fix is cheap. The union bound argument takes quite a bit of ink to spell out but for now just know we don’t have to worry too much about it ruining the main takeaways we are trying to get from this section.

Linear models

Weights bounded in \(\ell_2\) norm

Theorem (Ma 5.5). Let the hypothesis class be \(\mathcal{H} = \{x\mapsto \langle w,x\rangle : w\in\mathbb{R}^d,\ \lVert w\rVert_2\le B\}\). Moreover assume \(\mathbb{E}_{x\sim P}[\lVert x\rVert_2^2]\le C^2\), where \(P\) is some distribution and \(C>0\) is a constant. Then

and

Generally, there are two methods for bounding the Rademacher complexity of a model.

1. First, we can discretize the space of possible outputs from our hypothesis class, and then use a union bound or covering number argument to bound the Rademacher complexity of the model. This method gives bounds which depend on the \(\log(\text{size of discretized output space})\), which depends on the data size \(n\).
2. The second method is more limited but does not depend on the discretization. We follow this second path below:

Proof.

My annotations on the steps:

• (5.18) is by definition of \(R_S(\mathcal{H})\).
• (5.19) by linearity — pull the sum inside the inner product, and the \(1/n\) outside the sup.
• (5.20) sup characterization of the norm: \(\sup_{\lVert w\rVert_2\le B}\langle w,v\rangle = B\lVert v\rVert_2\), attained at \(w = Bv/\lVert v\rVert_2\). This is Cauchy–Schwarz with equality, i.e. \(\ell_2\) is self-dual.
• (5.21) Jensen’s inequality for \(a\mapsto a^2\) (equivalently, \(\mathbb{E} Z\le\sqrt{\mathbb{E} Z^2}\)).
• (5.22) algebraic expansion of the norm\(^2\) of a sum.
• (5.23) \(\sigma_i^2 = 1\), and the cross terms vanish because the \(\sigma_i\) are independent with \(\mathbb{E}[\sigma_i] = 0\).

Proof of the empirical Rademacher complexity done. For the average Rademacher complexity just take expectations of both sides w.r.t. \(x\sim P\):

where the first inequality is Jensen again and the second uses \(\mathbb{E}\lVert x\rVert_2^2\le C^2\).

Observation. Both the empirical and average Rademacher complexities scale with \(B\), which motivates model regularization. But smaller weights may reduce \(\gamma_{\min}\), which can hurt generalization according to the bound

📌 Ma’s Remark 5.6 makes the scaling consistent: if you rescale the data by a constant, \(R_S(\mathcal{H})\) scales by that constant, but so does \(\gamma_{\min}\), so the ratio — and hence the bound — is unchanged. Good sanity check that the bound is measuring something real rather than an artifact of units.

Weights bounded in \(\ell_1\) norm

Theorem (Ma 5.7). Let \(\mathcal{H} = \{x\mapsto\langle w,x\rangle : w\in\mathbb{R}^d,\ \lVert w\rVert_1\le B\}\) for some \(B>0\). Also assume \(\lVert x^{(i)}\rVert_\infty\le C\) for some \(C>0\) and all points in \(S = \{x^{(i)}\}_{i=1}^n\subseteq\mathbb{R}^d\). Then

Lemma (Massart’s lemma; Ma 5.8). Suppose \(Q\subset\mathbb{R}^n\) is finite and contained in the \(\ell_2\)-norm ball of radius \(M\sqrt n\), i.e. \(Q\subseteq\{v\in\mathbb{R}^n : \lVert v\rVert_2\le M\sqrt n\}\). Then for Rademacher variables \(\sigma = (\sigma_1,\dots,\sigma_n)\),

As a corollary, if \(\mathcal{F}\) is a set of real-valued functions with \(\sup_{f\in\mathcal{F}}\frac1n\sum_i f(z^{(i)})^2 \le M^2\), then \(R_S(\mathcal{F})\le M\sqrt{2\log\lvert\mathcal{F}\rvert/n}\) and likewise for \(R_n\).

📌 Ma states it as Lemma 5.8 and, in the \(Q\) formulation, as Proposition 4.6.1 and Corollary 4.21, and omits the proof both times. In my 210B notes the engine is Proposition 2.40: for zero-mean \(\sigma\)-sub-Gaussian \(X_1,\dots,X_n\) (not necessarily independent), \(\mathbb{E}\max_i X_i \le \sigma\sqrt{2\log n}\), proved by the exponential-moment / Jensen argument and optimizing in \(\lambda\). Remark 2.41(2) upgrades it to \(\mathbb{E}\max_i\lvert X_i\rvert\le\sigma\sqrt{2\log(2n)}\). Massart’s lemma is exactly this applied to \(X_v = \frac1n\langle\sigma,v\rangle\) for \(v\in Q\): each \(X_v\) is \(\frac{\lVert v\rVert_2}{n}\)-sub-Gaussian by Hoeffding, so \(\mathbb{E}\sup_v X_v \le \frac{M\sqrt n}{n}\sqrt{2\log\lvert Q\rvert}\). So 210B Prop. 2.40 gives the machinery, Ma Lemma 5.8 gives the statement in the form we see it here.

Proof of Ma 5.7. By definition,

Here (5.30) is by definition of \(R_S(\mathcal{H})\), (5.31) is linearity, and (5.32) is \(\ell_1\)–\(\ell_\infty\) duality, \(\sup_{\lVert w\rVert_1\le B}\langle w,v\rangle = B\lVert v\rVert_\infty\), a consequence of Hölder’s inequality.

It is hard to simplify the \(\ell_\infty\)-norm term further, so we can use something else: \(\sup_{\lVert w\rVert_1\le1}\langle w,v\rangle\) is attained at a vertex,

To use this, define the restricted hypothesis class \(\overline{\mathcal{H}} = \{x\mapsto\langle w,x\rangle : w\in W\}\subseteq\mathcal{H}\), which gives

\(\overline{\mathcal{H}}\) is bounded and has cardinality \(2d\), so we apply Massart. Check that Massart’s hypotheses are verified: since the inner product of \(x^{(i)}\) with a coordinate vector \(e_j\) just selects the \(j\)th coordinate,

for any \(w\in W\). Then

∎

Comparing bounds for other \(\mathcal{H}\)

• For this hypothesis class of linear models we can get upper bounds proportional to \(\sqrt{d/n}\) using VC dimension.
• Our bounds do not have a strong dependence on \(d\), so they are better in this sense.
• To determine which hypothesis class is better, consider the bounds \(\lVert w\rVert_2\lVert x\rVert_2\) vs. \(\lVert w\rVert_1\lVert x\rVert_\infty\) and see how they compare in different settings.

Summary of the three settings:

1. Generic entries. Suppose \(w\) and \(x\) have entries close to \(\{-1,1\}\). Then we compare \(\sqrt d\cdot\sqrt d\) versus \(d\cdot 1\). There is no difference between the two hypothesis classes.

2. Sparse \(w\). If additionally \(w\) has at most \(k\) nonzero entries, we compare \(\sqrt k\cdot\sqrt d\) versus \(k\cdot 1\). For \(d\gg k\) we have \(\sqrt{kd}\gg k\), so \(\ell_1\) regularization gives the better bound. Formally, \(\sqrt d\lVert x\rVert_\infty\approx\lVert x\rVert_2\) when the entries of \(x\) are roughly uniform, so

   \[\lVert w\rVert_2\lVert x\rVert_2 \ge \sqrt d\,\lVert w\rVert_2\lVert x\rVert_\infty \ge \lVert w\rVert_1\lVert x\rVert_\infty. \tag{5.38}\]

3. Dense \(w\). If \(w\) is dense in the sense that \(\lVert w\rVert_2\approx\frac{1}{\sqrt d}\lVert w\rVert_1\) (all entries close in magnitude), then

   \[\lVert w\rVert_2\lVert x\rVert_2 \le \frac{1}{\sqrt d}\lVert w\rVert_1\cdot\sqrt d\,\lVert x\rVert_\infty \le \lVert w\rVert_1\lVert x\rVert_\infty, \tag{5.39}\]

   and it makes sense to regularize the \(\ell_2\) norm instead.

In practice other multiplicative factors enter the bound, so regularizing both norms is preferable.

If we consider the bounded \(\ell_2\)-norm hypothesis class we get

The presence of \(\lVert w\rVert_2/\gamma_{\min}\) motivates the minimum-norm and max-margin formulations of the SVM problem as good methods to improve the generalization performance of binary classifiers.

Two-layer neural networks

Goal: compute the Rademacher complexity of two-layer neural networks.

Notation.

• \(\theta = (w,U)\) are the parameters, with \(w\in\mathbb{R}^m\) and \(U\in\mathbb{R}^{m\times d}\), where \(m\) is the number of hidden units. We write \(u_j\in\mathbb{R}^d\) for the \(j\)th row of \(U\), viewed as a column vector.
• \(\phi(z) = \max(z,0)\) is the ReLU, applied element-wise.
• \(f_\theta(x) = \langle w,\phi(Ux)\rangle = w^\top\phi(Ux)\) is the model.
• \(\{(x^{(i)},y^{(i)})\}_{i=1}^n\) is the training set, \(x^{(i)}\in\mathbb{R}^d\), \(y^{(i)}\in\mathbb{R}\).

📌 What a two-layer net looks like, concretely. Input \(x\in\mathbb{R}^d\). The first layer applies \(m\) separate linear maps \(x\mapsto\langle u_j,x\rangle\), one per hidden unit, giving the vector \(Ux\in\mathbb{R}^m\). Each coordinate is then passed through the ReLU, producing the hidden layer \(\phi(Ux)\in\mathbb{R}^m\). A hidden unit (or neuron) is one coordinate \(j\) of that vector: it computes \(\phi(u_j^\top x)\), a single ridge function — linear in \(x\) along direction \(u_j\), clipped at zero. The output layer takes a linear combination of the \(m\) hidden units with weights \(w\), giving a scalar. So the model is a weighted sum of \(m\) clipped ridge functions, \(f_\theta(x) = \sum_{j=1}^m w_j\phi(u_j^\top x)\), and \(m\) is the width. There is no nonlinearity on the output, and biases are suppressed throughout.

Theorem (Weak bound; Ma 5.9). For some constants \(B_w>0\) and \(B_u>0\), let

and suppose \(\mathbb{E}[\lVert x\rVert_2^2]\le C^2\). Then

This bound is not ideal since it depends on the number of neurons \(m\). Empirically, it has been found that more neurons actually improves generalization error.

Proof.

Applying Theorem 5.5 to the linear class in (5.50),

Taking expectations with respect to \(x\sim P\) completes the proof:

∎

My annotations on the steps:

• (5.43) by definition of \(R_S(\mathcal{H})\).
• (5.44) linearity, plus expanding the sup by each parameter — the joint sup over \(\theta = (w,U)\) splits into nested sups because the constraints on \(w\) and \(U\) are separate.
• (5.45) sup characterization of the \(\ell_2\) norm, as in (5.20).
• (5.46) \(\ell_\infty\) bound of the \(\ell_2\) norm: \(\lVert v\rVert_2\le\sqrt m\lVert v\rVert_\infty\) for \(v\in\mathbb{R}^m\). This is where the \(\sqrt m\) enters, and it is the step responsible for the undesirable width dependence.
• (5.47) definition of the \(\ell_\infty\) norm.
• (5.48) each \(u_j\) ranges over the same set, so the max over \(j\) collapses into a single sup over \(\lVert u\rVert_2\le B_u\) — collapse of notation, no loss.
• (5.49) by Lemma 5.12, which removes the absolute value at the cost of a factor of 2.
• (5.50) Talagrand’s lemma plus the fact that ReLU is \(1\)-Lipschitz. Note (5.49) is the Rademacher complexity of \(\{x\mapsto\phi(u^\top x) : \lVert u\rVert_2\le B_u\}\), which is the family we apply the contraction lemma to; then (5.50) is a Rademacher complexity of bounded-\(\ell_2\)-norm linear models.

Refined bounds

Theme: functional invariance of two-layer neural networks under a class of rescaling transformations.

Key: positive homogeneity of ReLU,

This implies that for any \(\lambda_i>0\), \(i\in[m]\), the transformation

has no net effect on the network’s functionality: \(f_\theta = f_{\theta’}\). So we want a new complexity measure which is invariant under such transformations.

Theorem (Ma 5.10). Let \(C(\theta) = \sum_{j=1}^m \lvert w_j\rvert\lVert u_j\rVert_2\) and for some \(B>0\) consider

If \(\lVert x^{(i)}\rVert_2\le C\) for all \(i\in[n]\), then

No dependence on \(m\) — except maybe arguably through \(B\). So it is possible to use more neurons and still maintain a tight bound if the value of the new complexity measure \(C(\theta)\) is reasonable.

• One can show this new theorem is strictly stronger than the weak-bound theorem. By Cauchy–Schwarz,

  \[\sum_j \lvert w_j\rvert\lVert u_j\rVert_2 \le \Big(\sum_j\lvert w_j\rvert^2\Big)^{1/2}\Big(\sum_j\lVert u_j\rVert_2^2\Big)^{1/2} \le \lVert w\rVert_2\cdot\sqrt m\cdot\max_j\lVert u_j\rVert_2, \tag{5.60}\]

  so with \(\mathcal{H}_1 = \{f_\theta : \sum\lvert w_j\rvert\lVert u_j\rVert_2\le B’\}\) and \(\mathcal{H}_2 = \{f_\theta : \lVert w\rVert_2\sqrt m\max_j\lVert u_j\rVert_2\le B’\}\), both theorems give \(O(B’/\sqrt n)\) but \(\mathcal{H}_1\supset\mathcal{H}_2\).

• One can also get a generalization guarantee which decreases as \(m\) increases.

Proof of Theorem 5.10. Put \(\bar u_j = u_j/\lVert u_j\rVert_2\), so that \(\phi(u_j^\top x) = \lVert u_j\rVert_2\,\phi(\bar u_j^\top x)\). Then

where \(\mathcal{H}’ = \{x\mapsto\phi(\bar u^\top x) : \bar u\in\mathbb{R}^d,\ \lVert\bar u\rVert_2\le1\}\). By Talagrand’s lemma and \(\phi\) being \(1\)-Lipschitz, \(R_S(\mathcal{H}’)\le R_S(\mathcal{H}’’)\) where \(\mathcal{H}’’ = \{x\mapsto\bar u^\top x : \lVert\bar u\rVert_2\le 1\}\) is a linear hypothesis space. Then \(R_S(\mathcal{H}’’)\le C/\sqrt n\) by the previous theorem, which concludes the proof. ∎

My annotations on the steps:

• (5.61) by definition of \(R_S(\mathcal{H})\), plus linearity.
• (5.62) by definition of \(f_\theta\).
• (5.63) positive homogeneity of \(\phi\).
• (5.64) linearity (swap the order of the two sums).
• (5.65) since \(\sum_j\alpha_j\beta_j \le \sum_j\lvert\alpha_j\rvert\max_k\lvert\beta_k\rvert\).
• (5.66) since \(C(\theta) = \sum_j\lvert w_j\rvert\lVert u_j\rVert_2 \le B\).
• (5.67) since \(w\) is gone and \(\bar u\) is isolated — the sup over \(\theta\) and \(\max_k\) together are just a sup over unit vectors.
• (5.68) sup over a larger set.
• (5.69) Lemma 5.12.
• (5.70) definition of \(R_S(\mathcal{H}’)\).

Lemma (Ma 5.12). Let \(\sigma = (\sigma_1,\dots,\sigma_n)\) and \(f_\theta(x) = (f_\theta(x^{(1)}),\dots,f_\theta(x^{(n)}))\). Suppose that for any \(\sigma\in\{\pm1\}^n\) we have \(\sup_\theta\langle\sigma,f_\theta(x)\rangle\ge 0\). Then

Proof. The assumption implies \(\sup_\theta\phi(\langle\sigma,f_\theta(x)\rangle) = \sup_\theta\langle\sigma,f_\theta(x)\rangle\) for any \(\sigma\). Using \(\lvert z\rvert = \phi(z) + \phi(-z)\),

Take expectations over \(\sigma\) and use \(\sigma \overset{d}{=} -\sigma\). ∎

📌 I looked for this in the 210B notes and did not find it — it is specific to Ma, and the proof above is his. The hypothesis \(\sup_\theta\langle\sigma,f_\theta(x)\rangle\ge0\) does hold in both places we use it, since \(\bar u = 0\) (resp. \(u = 0\)) is admissible and gives \(0\). The nearest 210B relative is the two-sided maximal inequality, Remark 2.41(2), which is the same “pay a factor of 2 to handle absolute values” move.

More implications of the refined bound

Recall margin theory gave the bound: for all \(\theta\), with probability \(\ge1-\delta\),

So Theorem 5.10 motivates us to minimize \(R_S(\mathcal{H})/\gamma_{\min}\) by regularizing \(C(\theta)\). We have two possible formulations as optimization problems:

One can show the optimal network in (I) is functionally equivalent to the new problem

because of the positive homogeneity of \(\phi\).

📌 The mechanism, in one line, since it is the invariance discussion cashed out. By AM–GM, \(\lvert w_j\rvert\lVert u_j\rVert_2 \le \frac12\big(\lvert w_j\rvert^2 + \lVert u_j\rVert_2^2\big)\) with equality iff \(\lvert w_j\rvert = \lVert u_j\rVert_2\), so \(C(\theta)\le C_{\ell_2}(\theta)\) always. But the rescaling \(T_\lambda\) lets us enforce \(\lvert w_j\rvert = \lVert u_j\rVert_2\) for every \(j\) without changing \(f_\theta\) or \(\gamma_{\min}\) — take \(\lambda_j = \sqrt{\lVert u_j\rVert_2/\lvert w_j\rvert}\). Minimizing over each orbit therefore makes the two objectives agree, and the constraint \(\gamma_{\min}\ge1\) is itself orbit-invariant. So the two programs have the same optimal value and the same optimal functions. This is what lets you replace an unfamiliar homogeneous penalty by the ordinary weight decay everyone actually runs.

✏️ Josh (TODO): Section 5.4.3 (equivalence to an \(\ell_1\)-SVM in the \(m\to\infty\) limit) is super interesting and deserves its own post.

Deep neural nets (via covering numbers)

First, a covering number bound for linear models.

Theorem (Zhang, 2002; Ma 5.16). Suppose \(x^{(1)},\dots,x^{(n)}\in\mathbb{R}^d\) are \(n\) data points and \(p,q\) satisfy \(\frac1p+\frac1q = 1\) with \(2\le p\le\infty\). Assume \(\lVert x^{(i)}\rVert_p\le C\) for all \(i\). Let \(\mathcal{F}_q = \{x\mapsto\langle x,w\rangle : \lVert w\rVert_q\le B\}\) and let \(\rho = L_2(P_n)\). Then

When \(p = q = 2\) we get

Note that applying localized Dudley to the covering number bound above with \(R = B^2C^2\), we conclude

Theorem 5.5 proves this without relying on Dudley.

📌 Found it. STAT 210B §9.7, Proposition 9.19 (Dudley’s entropy integral, localized form): with the localization \(T_n(\delta) = \{g\in\mathcal{F} : \lVert g\rVert_n\le\delta\}\), the localized Gaussian complexity satisfies

\[G_n(\delta;\mathcal{F}) \;\le\; \frac{C}{\sqrt n}\int_0^\delta \sqrt{\log N\big(T_n(\delta),\ \lVert\cdot\rVert_n,\ \epsilon\big)}\,d\epsilon .\]

The proof there is the one to cite: the increments \(X_g = \frac1n\sum_i w_i g(X_i)\) form a Gaussian process whose canonical metric is \(\frac{1}{\sqrt n}\lVert\cdot\rVert_n\), star-shapedness gives \(0\in T_n(\delta)\), and \(\operatorname{diam} \le 2\delta/\sqrt n\) caps the integral. The rougher first pass is at §9.6, Prop. 9.16 (“he erased the rest of the proof immediately after writing it”). Downstream: Cor. 9.21 is the critical-radius fixed point, Thm. 9.23 converts polynomial entropy \(\log N \le A\epsilon^{-p}\) into the rate \(\delta_n \asymp (\sigma^2/n)^{1/(p+2)}\), and Remark 9.20 gives the chaining intuition.

Worth pairing with 210B Remark 9.25: the Dudley integral \(\int_0^\delta \epsilon^{-p/2}d\epsilon\) converges iff \(p<2\). Ma’s covering bound here is \(\log N \le R/\epsilon^2\), i.e. exactly \(p = 2\), the borderline case — which is why Ma calls it “the worst dependency on \(\epsilon\) that we can tolerate,” and why (5.95) is stated with a \(\widetilde O\) rather than an \(O\): the log factor hidden in the tilde is precisely the logarithmic divergence at the \(p=2\) endpoint. The localization is what makes the borderline usable.

Theorem (Ma 5.18). Notation: let \(M = (M_1,\dots,M_n)\in\mathbb{R}^{m\times n}\) and \(\lVert M\rVert_{2,1} = \sum_{i=1}^n\lVert M_i\rVert_2\); then \(\lVert M^\top\rVert_{2,1}\) is the sum of the \(\ell_2\) norms of the rows of \(M\).

Let \(\mathcal{F} = \{x\mapsto Wx : W\in\mathbb{R}^{m\times d},\ \lVert W^\top\rVert_{2,1}\le B\}\) and let \(c = \sqrt{\frac1n\sum_{i=1}^n\lVert x^{(i)}\rVert_2^2}\). Then

Remark. This result arises from treating each dimension of the multivariate problem independently. If \(W\) has rows \(w_1^\top,\dots,w_m^\top\) then \(Wx = (w_1^\top x,\dots,w_m^\top x)^\top\), and \(\lVert W^\top\rVert_{2,1} = \sum_i\lVert w_i\rVert_2\).

Deep neural nets

Notation. \(W_i\) is the linear weight matrix at the \(i\)th layer of the network, we have \(r\) layers, and \(\sigma\) is the activation function, which is \(1\)-Lipschitz (e.g. ReLU, softmax, or sigmoid):

Theorem (Bartlett et al., 2017; Ma 5.20). Suppose \(\lVert x^{(i)}\rVert_2\le c\) for all \(i\) and let \(\mathcal{F} = \{f_\theta : \lVert W_i\rVert_{\mathrm{op}}\le\kappa_i,\ \lVert W_i^\top\rVert_{2,1}\le b_i\}\). Then

(I), a product of matrix norms, dominates the bound since (II) is more of a sum of matrix norms.

📌 It does not dominate automatically, and the “product beats sum” slogan is about how the two scale with depth, not about products beating sums in general. Set all \(\kappa_i = \kappa\) and \(b_i = b\). Then

\[(\mathrm{I}) = \kappa^r,\qquad (\mathrm{II}) = \left(r\,\frac{b^{2/3}}{\kappa^{2/3}}\right)^{3/2} = r^{3/2}\,\frac{b}{\kappa}, \qquad (\mathrm{I})\cdot(\mathrm{II}) = r^{3/2}\,b\,\kappa^{r-1}.\]

So (II) grows polynomially in depth, \(r^{3/2}\), while (I) grows geometrically, \(\kappa^r\). For any \(\kappa > 1\) — and trained networks have layer operator norms comfortably above \(1\) — the product swamps the sum once \(r\) is moderate. (If \(\kappa<1\) the product decays and the whole bound is small anyway, so the interesting regime is the one where (I) dominates.)

The reason this matters rather than being a curiosity: (I) is precisely an upper bound on the Lipschitz constant of the whole network, \(\prod_i\lVert W_i\rVert_{\mathrm{op}}\), and that product is the known weakness of the Bartlett et al. bound — it is typically astronomically larger than any quantity you would measure on a trained net. Ma’s Chapter 6 (all-layer margin) is built to remove exactly this factor; his Remark 6.8 shows the all-layer margin bound is strictly better because \(\frac{1}{m_f(x,y)} \lesssim \frac{1}{yf(x)}\prod_i\lVert W_i\rVert_{\mathrm{op}}\), i.e. the new bound is at worst the old one and generally much smaller.

Rf. Recall \(f(x) = Wx\) is \(\lVert W\rVert_{\mathrm{op}}\)-Lipschitz, since \(\lVert Wx - Wy\rVert_2 \le \lVert W\rVert_{\mathrm{op}}\lVert x-y\rVert_2\).

Corollary.

Proof, main ideas.

1. High level: show the covering number \(N(\epsilon,\mathcal{F},\rho)\) for a dense neural network is \(\le R/\epsilon^2\). Then we could use localized Dudley to get a Rademacher complexity bound.
2. To bound the covering number for a dense NN, we \(\epsilon\)-cover each layer separately and then combine to cover the original function \(f_\theta\).
3. Combining covers of each layer uses Lipschitzness.
4. Control and approximate the error propagation that is introduced by using an \(\epsilon\)-cover of each layer, to get a reasonable final \(\epsilon\).

Proof prelude: lots of covering and Lipschitz details. Maybe just give a quick summary of each step above.

📌 One concrete detail worth keeping if I do write it up: abstract each layer as \(\mathcal{F}_i\) (multiplication by \(W_i\) then \(\sigma\)), so \(\mathcal{F} = \mathcal{F}_r\circ\cdots\circ\mathcal{F}_1\). Assuming \(f_i\) is \(\kappa_i\)-Lipschitz with \(f_i(0)=0\) and \(\lVert x^{(j)}\rVert_2\le c\), the outputs at depth \(i\) satisfy \(\lVert f_i(\cdots f_1(x^{(j)}))\rVert_2 \le \kappa_i\kappa_{i-1}\cdots\kappa_1 c \triangleq c_i\), which is (5.105) and is exactly the quantity that propagates the covering error forward. Note \(c_r\) is (I) again, times \(c\) — the product of operator norms is not an artifact of the proof technique, it is the size of the network’s output. The \(2/3\) exponents in (II) come out of optimizing how much \(\epsilon\)-budget to spend on each layer.