Empirical Risk Minimization: Generalization, Rademacher Complexity, and Two-Layer Networks

These notes cover the first lecture of Day 6 by Andrea Montanari. The topic is the classical statistical learning theory framework: empirical risk minimization (ERM), the decomposition of risk into approximation and generalization error, and Rademacher complexity as the tool for controlling the generalization gap. The lecture culminates in a sharp bound on the Rademacher complexity of two-layer neural networks (Bartlett 1996), and an abstract detour into Banach-space approximation theory that leads to the Barron norm and explains why shallow networks can efficiently approximate a broad function class.

Supervised Learning Setup¶

We observe $n$ i.i.d. pairs $(x_i, y_i) \sim \mathbb{P}$, where

A model is a function $f : \mathbb{R}^d \to \mathbb{R}$. Given a new test pair $(x_{n+1}, y_{n+1})$ drawn from the same distribution, we want $f(x_{n+1}) \approx y_{n+1}$.

Loss, Risk, and Empirical Risk¶

Fix a loss function $\ell : \mathbb{R} \times \mathbb{R} \to \mathbb{R}_{\geq 0}$, mapping $(y, \hat{y}) \mapsto \ell(y, \hat{y})$. The canonical example is the square loss $\ell(y, \hat{y}) = (y - \hat{y})^2$.

The population risk (or test loss) of $f$ is

where the expectation is over $(x,y) \sim \mathbb{P}$. Since $\mathbb{P}$ is unknown, we cannot minimize $R(f)$ directly. We instead minimize the empirical risk

By the law of large numbers, $\hat{R}_n(f) \to R(f)$ almost surely for any fixed $f$.

This third point is the fundamental tension of learning: by interpolating the training data one can drive $\hat{R}_n(f)$ to zero, yet such a function generalizes arbitrarily poorly. Minimizing $\hat{R}_n$ over all measurable functions does not minimize $R$.

The Approximation–Generalization Decomposition¶

Let $\mathcal{F}$ be a hypothesis class (e.g. neural networks of a given architecture). Define

(Here $f_*$ minimizes the true risk within $\mathcal{F}$, while $\hat{f}_n$ minimizes the empirical risk; they differ because $\hat{R}_n$ is a random function of the data.) We decompose the excess risk:

Term (II) is $\leq 0$ because $\hat{f}_n$ minimizes $\hat{R}_n$ over $\mathcal{F}$, so it does no worse than $f_*$. Terms (I) and (III) are both instances of the fluctuation $|\hat{R}_n(f) - R(f)|$ at a particular $f$. Bounding them uniformly over $\mathcal{F}$ gives

If $f_*$ is not in $\mathcal{F}$, there is an additional approximation error term

representing the best-in-class deficit. The full bound therefore reads

The picture below (from the lecture) shows the risk landscape: $R(f)$ has a true minimizer $f^*$, while $\hat{R}_n$ has a jagged empirical minimizer $\hat{f}$ that may be far from $f^*$ if $\mathcal{F}$ is too rich.

Rademacher Complexity¶

The natural tool for bounding the generalization gap uniformly over $\mathcal{F}$ is the Rademacher complexity.

Definition¶

For a set $A \subseteq \mathbb{R}^n$, define

where $\sigma = (\sigma_1, \ldots, \sigma_n)$ are i.i.d. $\mathrm{Uniform}(\{+1,-1\})$ (Rademacher variables), independent of everything else. Geometrically, $\mathrm{Rd}_n(A)$ measures how well the set $A$ can be correlated with a random sign vector: it is large when $A$ contains vectors that “stick out” in every direction.

For a function class $G = \{g : S \to \mathbb{R}\}$ with data $z_1, \ldots, z_n \overset{\text{iid}}{\sim} \mathbb{P}$, define

The connection to the geometric definition is: fix $z_1, \ldots, z_n$ and let $A = \{(g(z_1), \ldots, g(z_n)) : g \in G\} \subseteq \mathbb{R}^n$ (the “evaluation set”), e.g. the output vectors of a neural network class on the training points. Then $\mathrm{Rd}_n(G) = \mathbb{E}_z[\mathrm{Rd}_n(A)]$.

Rademacher Complexity Controls Uniform Convergence¶

To apply this to learning, set $z_i = (y_i, x_i)$, $g(z_i) = \ell(y_i, f(x_i))$, and $G = \ell \circ \mathcal{F} := \{(y,x) \mapsto \ell(y,f(x)) : f \in \mathcal{F}\}$. Then $\hat{\mathbb{E}}_n g = \hat{R}_n(f)$ and $\mathbb{E} g = R(f)$, so the lemma gives

We want to compute $\mathrm{Rd}_n(\ell \circ \mathcal{F})$; the contraction lemma reduces this to $\mathrm{Rd}_n(\mathcal{F})$.

Contraction Inequality¶

Application. Assume $\ell$ is $L$-Lipschitz in its second argument. Using the triangle inequality to introduce the reference $\ell(y_i, 0)$ (which handles the $\phi_i(0)=0$ requirement):

The first term is $\mathcal{O}(1/\sqrt{n})$ (for square-integrable $y$). So the generalization gap is bounded by $\mathrm{Rd}_n(\mathcal{F})$ up to $\mathcal{O}(1/\sqrt{n})$ corrections.

Rademacher Complexity of Two-Layer Neural Networks¶

We now compute $\mathrm{Rd}_n(\mathcal{F})$ for a two-layer network class, following Bartlett (1996).

Setup¶

A two-layer network with $m$ hidden units and activation $\sigma$ has the form

We constrain the parameters by

Call this class $\mathcal{F}_m(C, r_0)$. The bound on $a$ in $\ell^1$ (rather than $\ell^2$) is the key structural choice; it limits the total variation of the output layer.

Computation of $\mathrm{Rd}_n(\mathcal{F}_m(C, r_0))$¶

Interchanging the sums and bounding by $\ell^1$–$\ell^\infty$ duality:

Taking supremum over $a$ at cost $r_0$, and then supremum over all $w$ collapses the max over $k$:

Applying the contraction inequality with the $L$-Lipschitz activation $\sigma$ (e.g. $L=1$ for ReLU):

The sup over $\|w\|_2 \leq C$ of a linear form is $C$ times the $\ell^2$ norm of the argument:

By Jensen’s inequality (concavity of the square root):

(The last step uses that $\sigma_i$ are independent mean-zero, so cross-terms vanish.) Assuming $\mathbb{E}\|x\|_2^2 \leq C' d$, we obtain the boxed result:

Crucially, this bound is independent of $m$ (the number of hidden units). Plugging back into the generalization bound:

This is the result of Bartlett (1996).

Abstract Detour: Banach-Space Approximation and Barron Spaces¶

The Rademacher bound above controls generalization given $r_0$ but leaves open: how large must $m$ be to make $\inf_{f \in \mathcal{F}_m(r_0)} R(f)$ small? The following abstract framework, due to Maurey and Pisier, gives a clean answer.

Convex Hulls in Banach Spaces¶

Let $(X, \|\cdot\|_X)$ be a Banach space, $G \subseteq X$ compact and centrosymmetric ($g \in G \Rightarrow -g \in G$). Define

the closed convex hull of $G$. Define also

The Atomic Norm¶

The atomic norm induced by $G$ is

where $|\mu| = \mu(G)$ is the total mass.

Example 1. $X = \mathbb{R}^n$, $G = \{\pm e_1, \ldots, \pm e_n\}$. Then $B_G = \{x : \|x\|_1 \leq 1\}$, so $\|x\|_G = \|x\|_1$ (the $\ell^1$ norm).

Example 2. $X = \mathrm{Sym}_n \subseteq \mathbb{R}^{n \times n}$, $G = \{\pm uu^\top : \|u\|_2 = 1\}$. Then $B_G = \{X : \sum_i |\lambda_i(X)| \leq 1\}$ (unit ball in the Schatten-1 / nuclear norm), so $\|X\|_G = \|X\|_*$ (the nuclear norm).

Maurey–Pisier Approximation Theorem¶

The rate $1/\sqrt{m}$ is the Monte Carlo rate: approximating an integral by a sample average.

Application: Barron Spaces and Two-Layer Networks¶

Set $X = L^2(\mathbb{R}^d; \mathbb{P})$ (the Hilbert space of square-integrable functions under the data distribution), and let

The induced atomic norm is the Barron norm:

where $\nu = \nu_+ - \nu_-$ is a signed measure on $G_+ = \{w : \|w\|_2 \leq 1\}$. Equivalently,

The class $\mathcal{F}_m(r_0)$ defined earlier corresponds to elements of $B_G(r_0)$ (the ball of Barron norm $\leq r_0$) approximated by $m$-neuron networks.

Combining with the Rademacher bound from the previous section, the total excess risk of the ERM estimator over $\mathcal{F}_m(r_0)$ satisfies

Balancing these two terms by choosing $m \asymp n/d$ gives $R(\hat{f}_n) - R(f_*) = \mathcal{O}(1/\sqrt{n/d})$, a rate independent of the ambient dimension $d$ (up to the implicit dependence in $\|f_*\|_\sigma$).

Physical interpretation. The Barron norm measures the “spectral complexity” of $f_*$ as a function of its Fourier/harmonic representation in the weight space. Functions that can be expressed as superpositions of neurons with bounded total variation in the weight space have small Barron norm. This is precisely the class for which shallow networks overcome the curse of dimensionality.