Rademacher Complexity

How well a class of functions can fit random signs on the sample, and why that number controls the gap between true and empirical risk uniformly over the class. Proves the symmetrization inequality and its reverse, the high-probability bounds through McDiarmid's inequality (data-dependent ones included), Massart's lemma for finite sets and from it the VC-dimension uniform convergence bound with its logarithmic factor, Talagrand's contraction lemma, the bound for linear functions in a Euclidean ball, and the margin bound for linear classifiers, with the radius fixed in advance or chosen after the fit. Computed by Monte Carlo for thresholds and intervals on the HbA1c of 5,210 NHANES adults over 30 seeds, against Massart's and Sauer's bounds and the observed uniform gap. Worked problems compute the complexity exactly on four adults and on two points in the plane, compare Massart's lemma with the exact value, and find the sample sizes the VC bound asks for.

Of 5,210 adults in the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 with a glycohemoglobin (HbA1c) result, 806 said a doctor had told them they have diabetes, a prevalence of 0.1547. The rule "predict diabetes when HbA1c is at least 6.7%" misclassifies 437 of them, a risk of 0.0839, the fewest of any threshold. Draw 200 of the adults at random, choose the threshold that misclassifies the fewest of the 200, and its error on the sample is usually a little below its error on all 5,210. A guarantee for that chosen threshold has to hold whichever threshold the sample picks, so it has to control the gap between the two errors for every threshold at once. How large can the largest of those gaps be, and can the sample itself tell us?

The Rademacher complexity of a class of functions answers both. It is the average, over random choices of a sign $+1$ or $-1$ for each sample point, of how well the best function in the class correlates with those signs. A class that can match any pattern of signs on the sample can also fit the noise in any sample, and the gap between its training and true errors can then be large; a class that cannot has its gap held down by the same amount. This article is the home of the definition and of its main bounds for the Statistical Learning Theory unit, and it contains the proof of the VC-dimension uniform convergence bound that The VC Dimension uses.

First we set up the uniform gap and define the complexity. Then we prove the symmetrization inequality, which bounds the expected uniform gap by twice the complexity, and its reverse, which shows the bound cannot be much improved. Next come the high-probability bounds through McDiarmid's inequality, Massart's lemma for finite sets, and from it the VC-dimension bound. Then we prove the contraction lemma and the bounds for linear functions and margins. Each result is computed on the HbA1c data. The article assumes Empirical Risk Minimization for the setting and Concentration Inequalities: Hoeffding and Bernstein for Hoeffding's and McDiarmid's inequalities.

The setting and the uniform gap

We follow the notation of the unit. Examples $z = (x, y)$ come from an unknown distribution $\mathcal{D}$ on $\mathcal{Z} = \mathcal{X} \times \mathcal{Y}$, and a training sample $S = (z_1, \ldots, z_m)$ is $m$ independent and identically distributed (i.i.d.) draws, written $S \sim \mathcal{D}^m$. A hypothesis $h$ from a class $\mathcal{H}$ has a loss $\ell(h, z)$, a risk $L_{\mathcal{D}}(h) = E_{z \sim \mathcal{D}}[\ell(h, z)]$ and an empirical risk $L_S(h) = \frac1m\sum_{i=1}^m \ell(h, z_i)$. For binary labels $y \in \{0, 1\}$ the 0-1 loss is $\mathbf{1}\{h(x) \ne y\}$.

Most results below concern a class of real functions on $\mathcal{Z}$. Write $\mathcal{F}$ for such a class, and for $f \in \mathcal{F}$ write $L_{\mathcal{D}}(f) = E[f(z)]$ and $L_S(f) = \frac1m\sum_i f(z_i)$. The case that matters is the loss class $\ell \circ \mathcal{H} = \{z \mapsto \ell(h, z) : h \in \mathcal{H}\}$, for which these are the risk and the empirical risk. The quantity to control is the uniform gap

$$\Phi(S) = \sup_{f \in \mathcal{F}}\big(L_{\mathcal{D}}(f) - L_S(f)\big).$$

Why the supremum? For a single fixed $f$ with values in $[0, 1]$, Hoeffding's inequality (Concentration Inequalities, Theorem 2) bounds $L_{\mathcal{D}}(f) - L_S(f)$ by $\sqrt{\ln(1/\delta)/(2m)}$ with probability at least $1 - \delta$. But the hypothesis $h_S$ returned by empirical risk minimization depends on the sample, and its gap is not that of a fixed function. Since $L_{\mathcal{D}}(h_S) - L_S(h_S) \le \Phi(S)$ for whatever $h_S$ is chosen, a bound on $\Phi(S)$ covers it. For a finite class, PAC Learning and Finite Hypothesis Classes bounds $\Phi$ by a union bound over the class, at a cost of $\ln|\mathcal{H}|$. The class of all thresholds on HbA1c is infinite, and a union bound over it is useless. The complexity defined next replaces $\ln|\mathcal{H}|$.

The running example takes the 5,210 adults as the whole population: $\mathcal{D}$ is the distribution of one adult drawn uniformly at random, and a sample of size $m$ is $m$ draws with replacement, so that the draws are exactly i.i.d. and every true risk is an exact fraction over 5,210. The class of thresholds is $h_t(x) = \mathbf{1}\{x \ge t\}$ for all real $t$, with $x$ the HbA1c in percent and $y = 1$ for diagnosed diabetes; the class of intervals is $h_{a,b}(x) = \mathbf{1}\{a \le x \le b\}$, the empty interval included. Their VC dimensions are 1 and 2 (The VC Dimension). The survey reports HbA1c to one decimal, and the 5,210 adults take 94 distinct values. Like the course pages, the example ignores the survey's sampling weights, so its risks describe these 5,210 adults and not the United States population.

Fitting random signs: the definition

Here is the idea in one sentence. If we flip a fair coin for each sample point and ask the class to agree with the coins as well as it can, the average agreement measures how much of what the class fits in any sample could be noise.

A Rademacher variable takes the values $+1$ and $-1$ with probability $\frac12$ each. Throughout, $\sigma = (\sigma_1, \ldots, \sigma_m)$ is a vector of independent Rademacher variables, independent of everything else. (The letter $\sigma$ is the standard name here, as in Shalev-Shwartz and Ben-David (2014) and Mohri, Rostamizadeh and Talwalkar (2018); in this article it never denotes a standard deviation.)

Definition (Rademacher complexity). For a bounded set $A \subset \mathbb{R}^m$,

$$\mathfrak{R}(A) = E_\sigma\Big[\sup_{a \in A}\frac1m\sum_{i=1}^m \sigma_i a_i\Big].$$

For a class $\mathcal{F}$ of real functions on $\mathcal{Z}$ and a sample $S = (z_1, \ldots, z_m)$, let $\mathcal{F}_S = \{(f(z_1), \ldots, f(z_m)) : f \in \mathcal{F}\}$ be the set of value vectors the class produces on the sample. The empirical Rademacher complexity of $\mathcal{F}$ on $S$ is $\hat{\mathfrak{R}}_S(\mathcal{F}) = \mathfrak{R}(\mathcal{F}_S)$, and the Rademacher complexity at sample size $m$ is its expectation over samples, $\mathfrak{R}_m(\mathcal{F}) = E_{S \sim \mathcal{D}^m}[\hat{\mathfrak{R}}_S(\mathcal{F})]$.

This is the definition of Shalev-Shwartz and Ben-David (2014, eqs. 26.4 and 26.5) and Mohri et al. (2018, Definitions 3.1 and 3.2). Bartlett and Mendelson (2002, Definition 2) put an absolute value inside the expectation and a factor $2/n$ in place of $1/m$, so their complexity of a class closed under negation is twice this one, and their constants differ from ours by that factor. Like Mohri et al. (2018, §3.1, footnote 3), we assume that every supremum over a class is measurable; it is, for every class in this article, because on any sample the class produces only finitely many value vectors or the supremum has a closed form.

The empirical complexity depends only on the sample's inputs and the class, and it can be computed from the sample. The inner product $\frac1m\sum_i\sigma_i f(z_i)$ is the correlation of the function's values with the noise vector, and the supremum picks the function that correlates best with this particular noise.

For a classifier with values in $\{0, 1\}$ we write its $\pm 1$ version as $\tilde h = 2h - 1$, and $\tilde{\mathcal{H}}$ for the class of these; labels likewise become $\tilde y = 2y - 1$.

Lemma 1 (elementary properties). Let $A, A' \subset \mathbb{R}^m$ be bounded and nonempty.

  1. If $A \subseteq A'$ then $\mathfrak{R}(A) \le \mathfrak{R}(A')$.
  2. For a real $c$ and a fixed vector $a_0$, $\mathfrak{R}(\{ca + a_0 : a \in A\}) = |c|\,\mathfrak{R}(A)$.
  3. $\mathfrak{R}(A) \ge 0$. If $A \subseteq \{-1, +1\}^m$, then $\mathfrak{R}(A) \le 1$, with equality exactly when $A = \{-1, +1\}^m$.

Proof. (1) A supremum over a larger set is at least as large, for every $\sigma$. (2) For each $\sigma$, $\sup_{a}\sum_i\sigma_i(ca_i + a_{0i}) = \sum_i\sigma_i a_{0i} + \sup_a\sum_i\sigma_i c a_i$, and $E[\sum_i\sigma_i a_{0i}] = 0$. If $c \ge 0$ the remaining supremum is $c\sup_a\sum_i\sigma_i a_i$. If $c < 0$ it is $|c|\sup_a\sum_i(-\sigma_i)a_i$, and $-\sigma$ has the same distribution as $\sigma$, so its expectation is again $|c|\,m\,\mathfrak{R}(A)$. (3) For any fixed $a \in A$ the supremum is at least $\sum_i\sigma_i a_i$, whose expectation is 0. If every coordinate is $\pm1$, each sum $\sum_i\sigma_i a_i$ is at most $m$, with equality only for $a = \sigma$. So the supremum equals $m$ exactly when $\sigma \in A$, and its expectation equals $m$ exactly when every one of the $2^m$ sign vectors is in $A$. $\square$

Part 3 is the first thing to know about a class of classifiers: its complexity on a sample is 1, the largest value, exactly when it realizes every labeling of the sample, that is, when it shatters the sample in the language of The VC Dimension. For 0-1 loss the complexity of the loss class reduces to that of the classifiers themselves, and the labels drop out.

Lemma 2 (the 0-1 loss). Let $S = ((x_1, y_1), \ldots, (x_m, y_m))$ with $y_i \in \{0, 1\}$, and let $S_x = (x_1, \ldots, x_m)$. For the 0-1 loss,

$$\hat{\mathfrak{R}}_S(\ell_{0\text{-}1} \circ \mathcal{H}) = \tfrac12\,\hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}}).$$

Proof. For $\pm1$ values, $\mathbf{1}\{h(x_i) \ne y_i\} = (1 - \tilde y_i\tilde h(x_i))/2$. So the loss vectors are $\frac12\mathbf{1} - \frac12(\tilde y_1\tilde h(x_1), \ldots, \tilde y_m\tilde h(x_m))$, and Lemma 1(2) with $c = -\frac12$ gives half the complexity of the set of vectors $(\tilde y_i\tilde h(x_i))_i$. For fixed labels, the vector $(\sigma_1\tilde y_1, \ldots, \sigma_m\tilde y_m)$ has the same distribution as $\sigma$, because each $\tilde y_i$ is a fixed sign. Hence $E_\sigma\sup_h\sum_i\sigma_i\tilde y_i\tilde h(x_i) = E_\sigma\sup_h\sum_i\sigma_i\tilde h(x_i)$. $\square$

This is Lemma 3.4 of Mohri et al. (2018). The labels do not enter the complexity of a 0-1 loss class at all. That will matter in Why Classical Bounds Do Not Explain Deep Networks: replacing the true labels by random ones cannot change it.

Example (thresholds on a sample). On a sample whose inputs take $k$ distinct values, the thresholds realize $k + 1$ labelings: put $t$ below all values, or just above the smallest, and so on up to above the largest. Adults with the same HbA1c always receive the same label. For a sign vector $\sigma$, let $s_1, \ldots, s_k$ be the sums of $\sigma_i$ over the sample points at each distinct value, in increasing order of value. The threshold that predicts 1 from the $j$th value on gives $\sum_i\sigma_i\tilde h(x_i) = 2(s_j + \cdots + s_k) - (s_1 + \cdots + s_k)$, so the supremum is twice the largest suffix sum (the empty suffix counts as 0) minus the total. For intervals the supremum is twice the largest sum over a run of consecutive values (the empty run counts) minus the total. These are the formulas the script uses.

Symmetrization: why fitting signs controls the gap

The idea in plain words: the true risk is the average of the empirical risk over an imaginary second sample, a ghost sample, drawn independently. The gap between the two samples' errors does not change in distribution if we swap any point of one sample with the corresponding point of the other. Swapping a random set of pairs is the same as multiplying the differences by random signs, and the signs then turn the gap into twice a correlation with noise.

Theorem 1 (symmetrization). For every class $\mathcal{F}$ of real functions on $\mathcal{Z}$ whose suprema are measurable and for which the expectations below are finite,

$$E_S\Big[\sup_{f \in \mathcal{F}}\big(L_{\mathcal{D}}(f) - L_S(f)\big)\Big] \le 2\,\mathfrak{R}_m(\mathcal{F}) \quad\text{and}\quad E_S\Big[\sup_{f \in \mathcal{F}}\big(L_S(f) - L_{\mathcal{D}}(f)\big)\Big] \le 2\,\mathfrak{R}_m(\mathcal{F}).$$

Proof. Let $S' = (z'_1, \ldots, z'_m)$ be a second sample from $\mathcal{D}^m$, independent of $S$. For each $f$, $L_{\mathcal{D}}(f) = E_{S'}[L_{S'}(f)]$, so

$$L_{\mathcal{D}}(f) - L_S(f) = E_{S'}\big[L_{S'}(f) - L_S(f)\big].$$

A supremum of expectations is at most the expectation of the supremum, because for each $g$ the expectation $E_{S'}[\cdot]$ at $g$ is at most $E_{S'}[\sup_f \cdot]$. Taking the supremum over $f$ and then the expectation over $S$,

$$E_S\big[\sup_f(L_{\mathcal{D}}(f) - L_S(f))\big] \le E_{S, S'}\Big[\sup_f\frac1m\sum_{i=1}^m\big(f(z'_i) - f(z_i)\big)\Big].$$

Fix a sign vector $s \in \{-1, +1\}^m$, and let $(S^s, S'^s)$ be the pair of samples obtained by exchanging $z_i$ and $z'_i$ for every $i$ with $s_i = -1$. The $2m$ points $z_1, \ldots, z_m, z'_1, \ldots, z'_m$ are i.i.d., so the exchanged pair has the same joint distribution as $(S, S')$. In the exchanged pair, the $i$th difference $f(z'_i) - f(z_i)$ becomes $s_i(f(z'_i) - f(z_i))$. Hence for every fixed $s$,

$$E_{S, S'}\Big[\sup_f\sum_i\big(f(z'_i) - f(z_i)\big)\Big] = E_{S, S'}\Big[\sup_f\sum_i s_i\big(f(z'_i) - f(z_i)\big)\Big].$$

Averaging over $s$ drawn as a Rademacher vector $\sigma$ independent of the samples leaves the left side unchanged. The supremum of a sum is at most the sum of the suprema, so

$$\sup_f\sum_i\sigma_i\big(f(z'_i) - f(z_i)\big) \le \sup_f\sum_i\sigma_i f(z'_i) + \sup_f\sum_i(-\sigma_i)f(z_i).$$

The vector $-\sigma$ has the distribution of $\sigma$, and $S$ and $S'$ have the same distribution, so each term on the right has expectation $m\,\mathfrak{R}_m(\mathcal{F})$. Dividing by $m$ gives the first inequality. The second follows by applying the first to the class $-\mathcal{F} = \{-f : f \in \mathcal{F}\}$, since $L_S(f) - L_{\mathcal{D}}(f) = L_{\mathcal{D}}(-f) - L_S(-f)$ and $\mathfrak{R}_m(-\mathcal{F}) = \mathfrak{R}_m(\mathcal{F})$ by Lemma 1(2). $\square$

The proof is that of Shalev-Shwartz and Ben-David (2014, Lemma 26.2) and Mohri et al. (2018, proof of Theorem 3.3), with the exchange of points made for all coordinates at once. For 0-1 loss, Lemma 2 turns the bound into $E_S[\sup_h(L_{\mathcal{D}}(h) - L_S(h))] \le \mathfrak{R}_m(\tilde{\mathcal{H}})$, and in particular the expected optimism of empirical risk minimization, $E_S[L_{\mathcal{D}}(h_S) - L_S(h_S)]$, is at most $\mathfrak{R}_m(\tilde{\mathcal{H}})$.

The bound cannot be much better

Is twice the complexity a large overestimate of the uniform gap? The same ghost sample shows that it is not, up to a factor of 4 and a term of order $1/\sqrt m$. This reverse inequality is what Why Classical Bounds Do Not Explain Deep Networks needs to show that a class that fits every labeling cannot have small uniform gaps.

Theorem 2 (the reverse inequality). Under the conditions of Theorem 1, and with $c = \sup_{f \in \mathcal{F}}|L_{\mathcal{D}}(f)|$ finite,

$$E_S\Big[\sup_{f \in \mathcal{F}}\big|L_{\mathcal{D}}(f) - L_S(f)\big|\Big] \ge \tfrac12\,\mathfrak{R}_m(\mathcal{F}) - \frac{c}{2\sqrt m}.$$

Proof. Write $g_f(z) = f(z) - L_{\mathcal{D}}(f)$, so that $\frac1m\sum_i g_f(z_i) = L_S(f) - L_{\mathcal{D}}(f)$. Since $E_{S'}[g_f(z'_i)] = 0$, for each $\sigma$, $S$ and $f$,

$$\sum_i\sigma_i g_f(z_i) = E_{S'}\Big[\sum_i\sigma_i\big(g_f(z_i) - g_f(z'_i)\big)\Big] = E_{S'}\Big[\sum_i\sigma_i\big(f(z_i) - f(z'_i)\big)\Big],$$

the constants $L_{\mathcal{D}}(f)$ cancelling inside the difference. As in Theorem 1, the supremum of the expectation is at most the expectation of the supremum, and the exchange argument removes the signs:

$$E_{\sigma, S}\Big[\sup_f\sum_i\sigma_i g_f(z_i)\Big] \le E_{S, S'}\Big[\sup_f\sum_i\big(f(z_i) - f(z'_i)\big)\Big].$$

Split $f(z_i) - f(z'_i) = g_f(z_i) - g_f(z'_i)$ and use the subadditivity of the supremum: the right side is at most $m\,E_S[\sup_f(L_S(f) - L_{\mathcal{D}}(f))] + m\,E_{S'}[\sup_f(L_{\mathcal{D}}(f) - L_{S'}(f))]$, and each of these is at most $m\,E_S[\sup_f|L_{\mathcal{D}}(f) - L_S(f)|]$. On the left, $\sum_i\sigma_i g_f(z_i) = \sum_i\sigma_i f(z_i) - L_{\mathcal{D}}(f)\sum_i\sigma_i \ge \sum_i\sigma_i f(z_i) - c\,|\sum_i\sigma_i|$, so the left side is at least $m\,\mathfrak{R}_m(\mathcal{F}) - c\,E|\sum_i\sigma_i|$. By the Cauchy–Schwarz inequality (Probability Inequalities), $E|\sum_i\sigma_i| \le (E[(\sum_i\sigma_i)^2])^{1/2} = \sqrt m$, since $E[\sigma_i\sigma_j]$ is 1 for $i = j$ and 0 otherwise. Combining and dividing by $2m$ gives the result. $\square$

For the 0-1 loss class, $c \le 1$ and Lemma 2 give $E_S[\sup_h|L_{\mathcal{D}}(h) - L_S(h)|] \ge \frac14\mathfrak{R}_m(\tilde{\mathcal{H}}) - \frac{1}{2\sqrt m}$. So the expected one-sided gap is at most twice the complexity of the loss class (Theorem 1), and the expected two-sided gap is at least half of it, less $c/(2\sqrt m)$ (Theorem 2). For 0-1 loss, in terms of $\tilde{\mathcal{H}}$, these read: at most $\mathfrak{R}_m(\tilde{\mathcal{H}})$, and at least $\frac14\mathfrak{R}_m(\tilde{\mathcal{H}}) - \frac{1}{2\sqrt m}$. The lower bound is informative only when the complexity is large compared with $1/\sqrt m$, as for the rich classes of Why Classical Bounds Do Not Explain Deep Networks. For thresholds on HbA1c at $m = 200$ it is negative: $\frac14 \cdot 0.099 - 1/(2\sqrt{200}) = -0.011$. For such small classes Theorem 2 says nothing, and the complexity is known only to bound the gap from above.

High probability: McDiarmid's inequality

Theorem 1 bounds an expectation. A guarantee for the sample we actually have needs the gap to be close to its expectation with high probability. The idea: $\Phi(S)$ is a function of $m$ independent points, and changing one point changes it by at most $1/m$, so it concentrates like an average.

McDiarmid's inequality (Concentration Inequalities, Theorem 5, proved there for independent variables with any distributions; also Mohri et al., 2018, Theorem D.8) says: if $X_1, \ldots, X_m$ are independent and a measurable function $\phi$ changes by at most $c_i$ when its $i$th argument alone is changed, then $P(\phi - E\phi \ge \varepsilon) \le \exp(-2\varepsilon^2/\sum_i c_i^2)$, and the same bound holds for $P(\phi - E\phi \le -\varepsilon)$.

Theorem 3 (bounds with high probability). Let $\mathcal{F}$ be a class of functions with values in $[0, 1]$ whose suprema are measurable, as in Theorem 1, and let $\delta \in (0, 1)$. With probability at least $1 - \delta$ over $S \sim \mathcal{D}^m$, every $f \in \mathcal{F}$ satisfies

$$L_{\mathcal{D}}(f) \le L_S(f) + 2\,\mathfrak{R}_m(\mathcal{F}) + \sqrt{\frac{\ln(1/\delta)}{2m}}. \tag{1}$$

With probability at least $1 - \delta$, every $f \in \mathcal{F}$ satisfies

$$L_{\mathcal{D}}(f) \le L_S(f) + 2\,\hat{\mathfrak{R}}_S(\mathcal{F}) + 3\sqrt{\frac{\ln(2/\delta)}{2m}}. \tag{2}$$

Proof. Let $S$ and $\bar S$ differ only in the $i$th point, $z_i$ in $S$ and $\bar z_i$ in $\bar S$. A difference of suprema is at most the supremum of the differences, so $\Phi(\bar S) - \Phi(S) \le \sup_f(L_S(f) - L_{\bar S}(f)) = \sup_f(f(z_i) - f(\bar z_i))/m \le 1/m$, and symmetrically. McDiarmid's inequality with $c_i = 1/m$ gives $P(\Phi(S) - E\Phi(S) \ge \varepsilon) \le \exp(-2m\varepsilon^2)$, which equals $\delta$ at $\varepsilon = \sqrt{\ln(1/\delta)/(2m)}$. With Theorem 1, $E\Phi(S) \le 2\mathfrak{R}_m(\mathcal{F})$, which proves (1).

For (2), the empirical complexity also has bounded differences $1/m$: for each $\sigma$ the two suprema differ by at most $\sup_f|\sigma_i(f(z_i) - f(\bar z_i))|/m \le 1/m$, since the values lie in $[0, 1]$, and averaging over $\sigma$ keeps the bound. By McDiarmid's inequality in the lower direction, $\mathfrak{R}_m(\mathcal{F}) \le \hat{\mathfrak{R}}_S(\mathcal{F}) + \sqrt{\ln(2/\delta)/(2m)}$ with probability at least $1 - \delta/2$. Use (1) with $\delta/2$ in place of $\delta$, substitute, and apply the union bound to the two events: with probability at least $1 - \delta$, $\Phi(S) \le 2\hat{\mathfrak{R}}_S(\mathcal{F}) + 2\sqrt{\ln(2/\delta)/(2m)} + \sqrt{\ln(2/\delta)/(2m)}$. $\square$

This is Theorem 3.3 of Mohri et al. (2018); Shalev-Shwartz and Ben-David (2014, Theorem 26.5) prove the same with larger constants. The bound (2) is data-dependent: everything in it can be computed from the sample.

For classifiers under 0-1 loss, Lemma 2 halves the complexity term: with probability at least $1 - \delta$, for every $h \in \mathcal{H}$,

$$L_{\mathcal{D}}(h) \le L_S(h) + \mathfrak{R}_m(\tilde{\mathcal{H}}) + \sqrt{\frac{\ln(1/\delta)}{2m}}, \qquad\text{or}\qquad L_{\mathcal{D}}(h) \le L_S(h) + \hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}}) + 3\sqrt{\frac{\ln(2/\delta)}{2m}}, \tag{3}$$

which is Mohri et al. (2018, Theorem 3.5). Two-sided versions follow the same way. The class $\{1 - f : f \in \mathcal{F}\}$ also takes values in $[0, 1]$, has the same complexity by Lemma 1(2), and its gap is $L_S(f) - L_{\mathcal{D}}(f)$. Applying (1) to both classes with $\delta/2$ each gives, with probability at least $1 - \delta$, $\sup_f|L_{\mathcal{D}}(f) - L_S(f)| \le 2\mathfrak{R}_m(\mathcal{F}) + \sqrt{\ln(2/\delta)/(2m)}$.

Example (the estimation error of ERM). Let $h^*$ minimize the risk over $\mathcal{H}$ and $h_S$ the empirical risk. With probability at least $1 - \delta/2$, (3) holds at $\delta/2$; with probability at least $1 - \delta/2$, Hoeffding's inequality for the fixed $h^*$ gives $L_S(h^*) \le L_{\mathcal{D}}(h^*) + \sqrt{\ln(2/\delta)/(2m)}$. Since $L_S(h_S) \le L_S(h^*)$, on both events

$$L_{\mathcal{D}}(h_S) - L_{\mathcal{D}}(h^*) \le \mathfrak{R}_m(\tilde{\mathcal{H}}) + 2\sqrt{\frac{\ln(2/\delta)}{2m}}.$$

This bounds the estimation error of Empirical Risk Minimization by the complexity of the class.

Computing it: Massart's lemma

The complexity is an expectation over $2^m$ sign vectors and a supremum over the class. For a class of classifiers the supremum runs over finitely many value vectors on the sample, and a bound in terms of their number is what ties the complexity to counting. The idea: the maximum of $N$ sums of independent signs is controlled through the exponential moment of each sum, which is at most that of a normal variable, and a maximum of $N$ such variables grows only like $\sqrt{2\ln N}$.

Lemma 3. For every real $x$, $\cosh x = (e^x + e^{-x})/2 \le e^{x^2/2}$.

Proof. Both sides have power series with only even powers: $\cosh x = \sum_{k \ge 0}x^{2k}/(2k)!$ and $e^{x^2/2} = \sum_{k \ge 0}x^{2k}/(2^k k!)$. Compare term by term: $(2k)! = \prod_{j=1}^{k}(2j)(2j - 1) \ge \prod_{j=1}^{k}2j = 2^k k!$. $\square$

Theorem 4 (Massart's lemma). Let $A \subset \mathbb{R}^m$ be finite with $N = |A| \ge 2$ elements, and let $r = \max_{a \in A}\lVert a\rVert_2$. Then

$$\mathfrak{R}(A) \le \frac{r\sqrt{2\ln N}}{m}.$$

Proof. Fix $\lambda > 0$. Since $u \mapsto \frac1\lambda\ln u$ is increasing and a maximum of positive numbers is at most their sum,

$$\max_{a \in A}\sum_i\sigma_i a_i = \frac1\lambda\ln\max_{a}e^{\lambda\sum_i\sigma_i a_i} \le \frac1\lambda\ln\sum_{a \in A}e^{\lambda\sum_i\sigma_i a_i}.$$

Take expectations. The logarithm is concave, so by Jensen's inequality (Probability Inequalities) $E[\ln U] \le \ln E[U]$. The $\sigma_i$ are independent, so the expectation of the product $\prod_i e^{\lambda\sigma_i a_i}$ is the product of the expectations, $\prod_i\cosh(\lambda a_i) \le \prod_i e^{\lambda^2a_i^2/2} = e^{\lambda^2\lVert a\rVert^2/2}$ by Lemma 3. Hence

$$m\,\mathfrak{R}(A) \le \frac1\lambda\ln\Big(N e^{\lambda^2r^2/2}\Big) = \frac{\ln N}{\lambda} + \frac{\lambda r^2}{2}.$$

The right side is smallest at $\lambda = \sqrt{2\ln N}/r$, where it equals $r\sqrt{2\ln N}$. $\square$

Massart (2000, Lemma 5.2, p. 300) proved this inequality, in the form $E[\sup_{a \in A}\sum_i\sigma_i a_i] \le r\sqrt{2\ln N}$ for finite sets of vectors and Rademacher variables, by the same argument; this is Theorem 4 multiplied by $m$. The form and proof above are also those of Shalev-Shwartz and Ben-David (2014, Lemma 26.8) and Mohri et al. (2018, Theorem 3.7). For $N = 1$ the complexity is 0, since $E[\sum_i\sigma_i a_i] = 0$, which agrees with the formula.

From Massart to the VC dimension

For a class of classifiers, every value vector of $\tilde{\mathcal{H}}$ on a sample is a vector of $\pm1$, of length $\sqrt m$. Let $\tilde{\mathcal{H}}_{S_x}$ be the set of labelings the class realizes on the inputs of the sample, and $\tau_{\mathcal{H}}(m)$ the growth function, the largest number of labelings the class realizes on any $m$ points. The VC Dimension defines it and proves Sauer's lemma, $\tau_{\mathcal{H}}(m) \le \sum_{i=0}^{d}\binom{m}{i}$ when $\mathrm{VCdim}(\mathcal{H}) = d$ (its Theorem 5), and the closed form $\tau_{\mathcal{H}}(m) \le (em/d)^d$ for $m \ge d \ge 1$ (its Corollary 1; Mohri et al., 2018, Corollary 3.18). Massart's lemma with $r = \sqrt m$ gives

$$\hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}}) \le \sqrt{\frac{2\ln|\tilde{\mathcal{H}}_{S_x}|}{m}} \le \sqrt{\frac{2\ln\tau_{\mathcal{H}}(m)}{m}}. \tag{4}$$

Combining (3), (4) and the closed form proves the uniform convergence bound for classes of finite VC dimension.

Corollary 1 (the VC uniform convergence bound). Let $\mathcal{H}$ have VC dimension $d \ge 1$, let $m \ge d$, and use the 0-1 loss. With probability at least $1 - \delta$ over $S \sim \mathcal{D}^m$, every $h \in \mathcal{H}$ satisfies

$$L_{\mathcal{D}}(h) \le L_S(h) + \sqrt{\frac{2d\ln(em/d)}{m}} + \sqrt{\frac{\ln(1/\delta)}{2m}},$$

and with probability at least $1 - \delta$, every $h \in \mathcal{H}$ satisfies

$$\big|L_{\mathcal{D}}(h) - L_S(h)\big| \le \sqrt{\frac{2d\ln(em/d)}{m}} + \sqrt{\frac{\ln(2/\delta)}{2m}}.$$

Proof. By Lemma 2 and (4), $2\hat{\mathfrak{R}}_S(\ell_{0\text{-}1} \circ \mathcal{H}) = \hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}}) \le \sqrt{2\ln\tau_{\mathcal{H}}(m)/m}$ for every sample, so the same bound holds for $2\mathfrak{R}_m(\ell_{0\text{-}1} \circ \mathcal{H})$. The closed form from Sauer's lemma gives $\ln\tau_{\mathcal{H}}(m) \le d\ln(em/d)$. Substituting into (1) gives the first statement, and into the two-sided form after Theorem 3 gives the second. $\square$

This is Mohri et al. (2018, Corollary 3.19); Shalev-Shwartz and Ben-David (2014, §28.1) derive the same bound with larger constants, by the same route. It is the bound that The VC Dimension cites. Turned around, it says that the uniform gap is at most $\varepsilon$ with probability at least $1 - \delta$ once $m$ is of order $(d\ln(m/d) + \ln(1/\delta))/\varepsilon^2$.

Two things are not proved here. The factor $\ln(em/d)$ can be removed: Shalev-Shwartz and Ben-David (2014, Theorem 6.8) state that the uniform convergence sample complexity is between $C_1(d + \ln(1/\delta))/\varepsilon^2$ and $C_2(d + \ln(1/\delta))/\varepsilon^2$ for absolute constants $C_1$ and $C_2$, and they note (§28.1) that the upper bound without the logarithm needs a finer analysis of the Rademacher complexity by chaining, which they do not give. Bartlett and Mendelson (2002, Theorem 1) state the log-free bound $c\sqrt{\mathrm{VCdim}/n}$ with an unspecified absolute constant $c$. The lower constant $C_1$ shows that the dependence on $d/\varepsilon^2$ cannot be improved; its proof, for agnostic PAC learning (which uniform convergence implies), is in Shalev-Shwartz and Ben-David (2014, §28.2) and is cited, not proved, here.

The first inequality in (4) is sharper than the second whenever the sample realizes fewer labelings than the worst case. That is the case on the HbA1c data. Because the survey rounds HbA1c to one decimal, a sample of 200 adults typically holds about 38 distinct values, so the thresholds realize about 39 labelings rather than the 201 that Sauer's lemma allows. Bartlett and Mendelson (2002, Theorem 6) make a related point in general: they bound the empirical Gaussian complexity, which their Lemma 4 relates to their Rademacher complexity ($c\,R_n^{\mathrm{BM}} \le G_n^{\mathrm{BM}} \le C\ln n\,R_n^{\mathrm{BM}}$ for the expected complexities in their normalization of Definition 2, with absolute constants $c$ and $C$), by $O(\sqrt{d/n})$ with $d$ the empirical VC dimension, and by $O(\sqrt{E/n})$ with $E$ the base-2 logarithm of the number of labelings on the sample.

Rademacher complexity on the HbA1c data

For each sample size $m$ of 50, 200 and 1,000 the script draws 30 samples of adults with replacement, from NumPy generators seeded with $s + 1000m$ for $s$ = 16,001,001 to 16,001,030 (so 16,051,001 to 16,051,030 at $m = 50$); the same generator then draws the sign vectors. For each sample it estimates the empirical complexity of thresholds and intervals by Monte Carlo over 4,000 sign vectors, using the suffix-sum and run-sum formulas of the example above. It also computes the two Massart bounds of (4), from the sample's own number of labelings and from Sauer's lemma, and the uniform gap $\sup_h(L_{\mathcal{D}}(h) - L_S(h))$ exactly, over all thresholds or all intervals. Each cell shows the median over the 30 samples, with the interquartile range in parentheses.

Sample size $m$ 50 200 1,000
Distinct HbA1c values $k$ (median) 20 38 66
Thresholds: $\hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}})$ 0.192 (0.190 to 0.193) 0.099 (0.098 to 0.099) 0.045 (0.044 to 0.045)
Thresholds: Massart, $k + 1$ labelings 0.349 (0.346 to 0.356) 0.191 (0.190 to 0.193) 0.092 (0.091 to 0.092)
Thresholds: Massart with Sauer, $m + 1$ 0.397 0.230 0.118
Thresholds: uniform gap 0.082 (0.052 to 0.100) 0.041 (0.032 to 0.052) 0.019 (0.011 to 0.030)
Intervals: $\hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}})$ 0.283 (0.280 to 0.286) 0.146 (0.145 to 0.147) 0.066 (0.066 to 0.066)
Intervals: Massart, $k(k+1)/2 + 1$ labelings 0.463 (0.458 to 0.473) 0.257 (0.255 to 0.259) 0.124 (0.123 to 0.125)
Intervals: Massart with Sauer 0.535 0.315 0.162
Intervals: uniform gap 0.134 (0.114 to 0.152) 0.063 (0.053 to 0.070) 0.032 (0.025 to 0.041)
Rademacher complexity of the thresholds on HbA1c, its two Massart bounds and the observed uniform gap, against the sample size on logarithmic axes (median of 30 samples, bars from the first to the third quartile). Notice that every curve falls with slope about one half (0.49 for the complexity and the gap, a little less, 0.45 and 0.41, for the two Massart bounds, which carry a logarithm), that Massart's bound from the sample's own labelings sits about twice as high as the complexity, and that the uniform gap stays below the complexity, as Theorem 1 requires of their means.
Rademacher complexity of the thresholds on HbA1c, its two Massart bounds and the observed uniform gap, against the sample size on logarithmic axes (median of 30 samples, bars from the first to the third quartile). Notice that every curve falls with slope about one half (0.49 for the complexity and the gap, a little less, 0.45 and 0.41, for the two Massart bounds, which carry a logarithm), that Massart's bound from the sample's own labelings sits about twice as high as the complexity, and that the uniform gap stays below the complexity, as Theorem 1 requires of their means.

Five things can be read from the table.

  • The complexity falls like $1/\sqrt m$. The median complexity of the thresholds times $\sqrt m$ is 1.35, 1.39 and 1.41 at the three sizes, nearly constant, with no visible trace of the logarithmic factor in Massart's bound.
  • Massart's lemma is about a factor of 2 loose here. From the sample's own count of labelings it gives 0.191 at $m = 200$ against a complexity of 0.099.
  • Ties help. The bound from the sample's labelings is below the one from Sauer's lemma at every size, since $k + 1 \le m + 1$.
  • A richer class has a larger complexity. Intervals, with VC dimension 2, have complexity about one and a half times that of thresholds, and their uniform gaps are larger by a similar factor.
  • The gap is below the bound. Theorem 1 says the mean uniform gap is at most twice the complexity of the loss class, which by Lemma 2 is the complexity $\hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}})$ shown. The script checks that the mean gap over the 30 samples is below the mean complexity at every size, for both classes; the medians in the table are below it too, by a factor of 2 or more.

The Monte Carlo estimates have a largest standard error of 0.0015 over all 90 samples. A sharper statement follows from McDiarmid's inequality applied to the $4{,}000 \times m$ signs: each sign changes the Monte Carlo average by at most $2/(4{,}000\,m)$, so the estimate exceeds the exact complexity by more than 0.0083 at $m = 50$ with probability at most 0.001, and by less at the larger sizes.

The bounds, evaluated

Back to the 200 adults of the opening. The threshold chosen by empirical risk minimization (with ties broken toward the smallest threshold) had, over the 30 samples, median empirical risk 0.075 (interquartile range 0.065 to 0.090) and median true risk 0.086 (0.086 to 0.088). What do the bounds promise for it at $\delta = 0.05$? The data-dependent bound (3), with the Monte Carlo complexity in place of the exact one, has median 0.462 (0.450 to 0.478). The VC bound of Corollary 1 with $d = 1$ has median 0.413 (0.403 to 0.428).

$m$ $L_S(h_S)$ $L_{\mathcal{D}}(h_S)$ Data-dependent bound (3) VC bound (Corollary 1)
50 0.070 (0.040 to 0.080) 0.092 (0.086 to 0.104) 0.837 (0.807 to 0.849) 0.686 (0.656 to 0.696)
200 0.075 (0.065 to 0.090) 0.086 (0.086 to 0.088) 0.462 (0.450 to 0.478) 0.413 (0.403 to 0.428)
1,000 0.083 (0.077 to 0.087) 0.086 (0.084 to 0.086) 0.256 (0.250 to 0.260) 0.247 (0.241 to 0.251)

Both bounds hold, and both are several times the true risk. The complexity term is not what makes them loose. At $m = 200$ the data-dependent bound spends 0.099 on complexity and 0.288 on its confidence term $3\sqrt{\ln(2/\delta)/(2m)}$, and Problem 3 below takes the VC bound apart in the same way. The data-dependent bound has the smaller complexity term at every size but the larger total, because its confidence term pays three times for the price of estimating the complexity from the same sample.

Example (a misreading of the bound). "The bound says the chosen threshold's error could be as high as 0.41, so it is probably much worse than the 0.075 we see." The bound says no such thing about likelihood. It is a guarantee that holds for every distribution on which the class could be used, at confidence 0.95, and the true risk of the chosen threshold here is 0.086. A bound this far above the truth means that this distribution is far from the worst case the bound is built for, not that the truth is near the bound.

Contraction: composing with a Lipschitz function

Many losses are a fixed function applied to the output of a hypothesis: the hinge loss and the ramp loss are functions of the margin $\tilde y\langle w, x\rangle$, and the absolute loss is a function of $\langle w, x\rangle - y$. If that outer function is $\rho$-Lipschitz, it cannot spread the value vectors further apart than $\rho$ times their spread, and the complexity grows by at most the factor $\rho$. The proof changes one coordinate at a time and uses, for that coordinate, the two values of its sign.

Theorem 5 (contraction lemma). Let $A \subset \mathbb{R}^m$ be bounded, and for each $i$ let $\phi_i: \mathbb{R} \to \mathbb{R}$ be $\rho$-Lipschitz: $|\phi_i(u) - \phi_i(v)| \le \rho|u - v|$. Let $\phi \circ A = \{(\phi_1(a_1), \ldots, \phi_m(a_m)) : a \in A\}$. Then $\mathfrak{R}(\phi \circ A) \le \rho\,\mathfrak{R}(A)$.

Proof. If $\rho = 0$ each $\phi_i$ is constant and both sides are 0 by Lemma 1(2) with $c = 0$. Otherwise $\phi_i/\rho$ is 1-Lipschitz and $\mathfrak{R}(\phi \circ A) = \rho\,\mathfrak{R}((\phi/\rho) \circ A)$ by Lemma 1(2), so it suffices to treat $\rho = 1$. It also suffices to replace one coordinate at a time: let $A_1 = \{(\phi_1(a_1), a_2, \ldots, a_m) : a \in A\}$; if we show $\mathfrak{R}(A_1) \le \mathfrak{R}(A)$ for every bounded $A$ and every 1-Lipschitz $\phi_1$, then applying the same step to coordinate 2 of $A_1$, and so on through coordinate $m$, gives the theorem.

Fix $\sigma_2, \ldots, \sigma_m$ and write $u(a) = \sum_{i \ge 2}\sigma_i a_i$. Averaging over the two values of $\sigma_1$,

$$E_{\sigma_1}\sup_{a \in A}\big(\sigma_1\phi_1(a_1) + u(a)\big) = \tfrac12\sup_{a}\big(\phi_1(a_1) + u(a)\big) + \tfrac12\sup_{a'}\big(-\phi_1(a'_1) + u(a')\big) = \tfrac12\sup_{a, a' \in A}\big(\phi_1(a_1) - \phi_1(a'_1) + u(a) + u(a')\big).$$

By the Lipschitz condition the last expression is at most $\frac12\sup_{a, a'}(|a_1 - a'_1| + u(a) + u(a'))$. In this supremum the absolute value can be dropped: the expression $u(a) + u(a')$ is unchanged when $a$ and $a'$ are exchanged, so for any pair with $a_1 < a'_1$ the exchanged pair gives $a'_1 - a_1 + u(a') + u(a)$, the same value without the absolute value. So the supremum equals $\frac12\sup_{a, a'}(a_1 - a'_1 + u(a) + u(a'))$, which by the same splitting as before is $E_{\sigma_1}\sup_a(\sigma_1 a_1 + u(a))$. Taking the expectation over $\sigma_2, \ldots, \sigma_m$ gives $m\,\mathfrak{R}(A_1) \le m\,\mathfrak{R}(A)$. $\square$

This is the contraction lemma in the form of Shalev-Shwartz and Ben-David (2014, Lemma 26.9), who attribute the proof to Kakade and Tewari, and of Mohri et al. (2018, Lemma 5.7, "Talagrand's lemma"). Mohri et al. (2018, §5.5) credit the result to Ledoux and Talagrand (1991). With the absolute value inside the definition, as in Bartlett and Mendelson (2002, Theorem 12, part 4), the statement needs $\phi(0) = 0$ and loses a factor of 2.

Linear classes and margins

Consider the class of linear functions with weight vectors in a Euclidean ball, $\mathcal{H}_B = \{x \mapsto \langle w, x\rangle : \lVert w\rVert_2 \le B\}$, with $x$ in $\mathbb{R}^p$ (or any space with an inner product). It is infinite and its VC dimension grows with $p$ (The VC Dimension), but its Rademacher complexity depends on the norms, not on the dimension. The supremum over the ball has a closed form, which is why.

Theorem 6 (linear functions in a ball). For points $x_1, \ldots, x_m$,

$$\hat{\mathfrak{R}}_S(\mathcal{H}_B) = \frac Bm\,E_\sigma\Big\lVert\sum_{i=1}^m\sigma_i x_i\Big\rVert \le \frac Bm\sqrt{\sum_{i=1}^m\lVert x_i\rVert^2} \le \frac{BR}{\sqrt m},$$

where $R = \max_i\lVert x_i\rVert$.

Proof. For each $\sigma$, $\sum_i\sigma_i\langle w, x_i\rangle = \langle w, v\rangle$ with $v = \sum_i\sigma_i x_i$. By the Cauchy–Schwarz inequality $\langle w, v\rangle \le \lVert w\rVert\,\lVert v\rVert \le B\lVert v\rVert$, with equality at $w = Bv/\lVert v\rVert$ when $v \ne 0$, so the supremum over the ball is exactly $B\lVert v\rVert$. That is the equality. Jensen's inequality for the concave square root gives $E\lVert v\rVert \le (E\lVert v\rVert^2)^{1/2}$, and $E\lVert v\rVert^2 = \sum_{i,j}E[\sigma_i\sigma_j]\langle x_i, x_j\rangle = \sum_i\lVert x_i\rVert^2$, since $E[\sigma_i\sigma_j] = 0$ for $i \ne j$. The last inequality uses $\lVert x_i\rVert \le R$. $\square$

This is Shalev-Shwartz and Ben-David (2014, Lemma 26.10) and Mohri et al. (2018, Theorem 5.10). The middle bound is close to the truth: by the Khintchine–Kahane inequality, which Mohri et al. (2018, Theorem D.9) state and prove and which is cited here, $(E\lVert v\rVert)^2 \ge \frac12E\lVert v\rVert^2$, so the complexity is at least $1/\sqrt2$ times the middle bound.

A classifier $x \mapsto \mathrm{sign}\langle w, x\rangle$ errs on $(x, y)$ when the margin $\tilde y\langle w, x\rangle$ is at most 0. The 0-1 loss is not Lipschitz, so contraction does not apply to it directly. The ramp loss at margin $\gamma > 0$ replaces it from above:

$$\phi_\gamma(u) = \min\big(1, \max(0, 1 - u/\gamma)\big),$$

which is 1 for $u \le 0$, 0 for $u \ge \gamma$, linear in between, and $(1/\gamma)$-Lipschitz. Its empirical average $\hat L_{S,\gamma}(w) = \frac1m\sum_i\phi_\gamma(\tilde y_i\langle w, x_i\rangle)$ is at most the fraction of training points with margin below $\gamma$.

Corollary 2 (the margin bound). Suppose $\lVert x\rVert \le R$ with probability 1, and fix $B$ and $\gamma > 0$ before seeing the sample. With probability at least $1 - \delta$, every $w$ with $\lVert w\rVert \le B$ satisfies

$$P\big(\tilde y\langle w, x\rangle \le 0\big) \le \hat L_{S,\gamma}(w) + \frac{2BR}{\gamma\sqrt m} + \sqrt{\frac{\ln(1/\delta)}{2m}},$$

and with probability at least $1 - \delta$ the same holds with $\frac{2B}{\gamma m}\sqrt{\sum_i\lVert x_i\rVert^2} + 3\sqrt{\ln(2/\delta)/(2m)}$ in place of the last two terms.

Proof. The class $\mathcal{G} = \{(x, y) \mapsto \phi_\gamma(\tilde y\langle w, x\rangle) : \lVert w\rVert \le B\}$ takes values in $[0, 1]$, so Theorem 3 applies to it. Its value vectors are $\phi_\gamma$ applied coordinatewise to the vectors $(\tilde y_i\langle w, x_i\rangle)_i$, so by Theorem 5 its complexity is at most $1/\gamma$ times theirs. Their complexity equals $\hat{\mathfrak{R}}_S(\mathcal{H}_B)$, by the argument of Lemma 2: the vector $(\sigma_i\tilde y_i)_i$ has the distribution of $\sigma$. Theorem 6 bounds it. Finally $\mathbf{1}\{u \le 0\} \le \phi_\gamma(u)$, so the risk under the ramp loss bounds the probability of error. $\square$

This is Mohri et al. (2018, Theorem 5.8 and Corollary 5.11) and Shalev-Shwartz and Ben-David (2014, Theorem 26.12). The bound contains the dimension of $x$ nowhere: only the ratio of the weight norm to the margin, and the size of the inputs. For a support vector machine that separates the training data with functional margins at least 1, the geometric margin is $1/\lVert w\rVert$, and with $\gamma = 1$ the bound is controlled by $\lVert w\rVert R/\sqrt m$, the ratio of the data's radius to the margin, over $\sqrt m$. Koltchinskii and Panchenko (2002) proved bounds of this kind, in terms of the empirical distribution of margins, for combinations of classifiers such as boosting and neural networks.

The radius $B$ must be fixed before the sample is seen. A bound for a radius chosen after the fit costs little more.

Corollary 3 (the radius chosen after the fit). Under the conditions of Corollary 2 with $\gamma$ fixed, with probability at least $1 - \delta$, every $w$ satisfies

$$P\big(\tilde y\langle w, x\rangle \le 0\big) \le \hat L_{S,\gamma}(w) + \frac{2 \cdot 2^{k}R}{\gamma\sqrt m} + \sqrt{\frac{\ln(k(k+1)/\delta)}{2m}}, \qquad k = \max\big(1, \lceil\log_2\lVert w\rVert\rceil\big).$$

Proof. For $k = 1, 2, \ldots$ apply Corollary 2 with $B_k = 2^k$ and $\delta_k = \delta/(k(k + 1))$. Since $\frac{1}{k(k+1)} = \frac1k - \frac1{k+1}$, the $\delta_k$ sum to $\delta$, and by the union bound all the events hold together with probability at least $1 - \delta$. A given $w$ lies in the ball of radius $2^k$ for the $k$ in the statement, and the event for that $k$ gives the bound. $\square$

The device is the one Shalev-Shwartz and Ben-David (2014, Theorem 26.14) use for the norm of the hard-margin solution, with a different sequence $\delta_k$. Since $2^k < 2\lVert w\rVert$ when $\lVert w\rVert > 1$, the price of choosing the radius from the data is at most a factor of 2 in the complexity term and a logarithmic term in the confidence.

The linear class on the data

Take as inputs $x = (1, z_{\mathrm{HbA1c}}, z_{\mathrm{age}})$, where each $z$ is standardized to mean 0 and standard deviation 1 over the 5,210 adults; the constant 1 plays the part of an intercept. The largest norm among the 5,210 is $R = 9.56$, from an adult with an extreme HbA1c. The script estimates $\frac1m E\lVert\sum_i\sigma_i x_i\rVert$ (the complexity at $B = 1$) by Monte Carlo over 4,000 sign vectors for each of 30 samples at each size (generators seeded with $s + 7000 + 1000m$, $s$ = 16,001,001 to 16,001,030), and compares it with the two bounds of Theorem 6.

$m$ Complexity at $B = 1$ $\frac1m\sqrt{\sum\lVert x_i\rVert^2}$ Ratio $R/\sqrt m$
50 0.2256 (0.2147 to 0.2420) 0.2436 (0.2335 to 0.2638) 0.921 (0.915 to 0.930) 1.3524
200 0.1100 (0.1073 to 0.1141) 0.1196 (0.1170 to 0.1241) 0.918 (0.914 to 0.922) 0.6762
1,000 0.0502 (0.0496 to 0.0510) 0.0545 (0.0540 to 0.0555) 0.918 (0.916 to 0.922) 0.3024

The complexity is about 92% of the middle bound of Theorem 6 at every size, well inside the factor $\sqrt2$ that the Khintchine–Kahane inequality allows. The bound $BR/\sqrt m$ is about six times the complexity, because $R$ is set by the most extreme adult while the middle bound averages the squared norms, which are 3 on average here by construction (each standardized coordinate has mean square 1, plus the constant). A bound through the largest norm pays for the outliers of the distribution, not of the sample.

Margins: the bound for a fitted linear classifier

What do the margin bounds promise for a classifier fitted to data? Fix $B = 4$ and $\gamma = 1$ before seeing any sample. For each sample (30 at each size, generators seeded with $s + 9000 + 1000m$, $s$ = 16,001,001 to 16,001,030), the script minimizes the average hinge loss $\max(0, 1 - \tilde y_i\langle w, x_i\rangle)$ over the ball $\lVert w\rVert \le 4$ with SciPy's SLSQP method. The hinge loss is not smooth, so the fit is approximate; that does not affect the bounds, which hold for every $w$ in the ball. The script then evaluates the ramp loss on the sample, the error rate of $\mathrm{sign}\langle w, x\rangle$ on all 5,210 adults, and the two bounds of Corollary 2 at $\delta = 0.05$.

$m$ Ramp loss on sample Error on population Bound with $R$ Data-dependent bound
50 0.105 (0.065 to 0.149) 0.090 (0.084 to 0.101) 11.10 (11.06 to 11.14) 2.69 (2.58 to 2.81)
200 0.127 (0.111 to 0.153) 0.090 (0.087 to 0.097) 5.62 (5.61 to 5.65) 1.39 (1.35 to 1.42)
1,000 0.136 (0.129 to 0.141) 0.092 (0.088 to 0.093) 2.59 (2.59 to 2.60) 0.70 (0.69 to 0.71)

A bound above 1 says nothing about a probability: it is vacuous. The bound through the largest norm is vacuous at every size here; its complexity term $2BR/\sqrt m$ would fall to 0.05 only at $m$ = 2,341,157. The data-dependent bound, which uses the sample's own norms, first says something at $m = 1{,}000$, where it is 0.70 against a true error of about 0.09. These bounds are proved and valid. They are loose for the same reasons as before, and in addition the radius $B$ multiplies the complexity term whatever the fitted norm turns out to be. Corollary 3, which uses the fitted norm instead, is the version Why Classical Bounds Do Not Explain Deep Networks applies to an interpolating model.

How the definition arrived

Rademacher averages are the expected suprema, over a class, of sums of function values multiplied by random signs; Koltchinskii and Panchenko (2002, abstract) describe their own tools (comparison inequalities, symmetrization, concentration) as "methods of the theory of Gaussian and empirical processes". Koltchinskii and Panchenko (2002) and Bartlett and Mendelson (2002) made them a standard complexity measure of learning theory; Shalev-Shwartz and Ben-David (2014, §26.5) credit the idea to papers of Koltchinskii and Panchenko and of Bartlett and Mendelson from 2000 to 2002. Koltchinskii and Panchenko bounded the generalization error of combined classifiers, such as those produced by boosting or by neural networks, in terms of the empirical distribution of their margins, by symmetrization, comparison and concentration inequalities (their abstract). Bartlett and Mendelson proved risk bounds in terms of Rademacher and Gaussian complexities for classification, for margins and for general losses (their Theorems 5, 7 and 8), showed that the empirical complexity concentrates around its mean (Theorem 11), and gave structural rules for computing it for compositions of classes (Theorem 12), with examples for decision trees, neural networks and support vector machines (their abstract). Their introduction cites evidence that error bounds with a fixed complexity penalty, one that does not depend on the training data, such as the VC bound, "cannot be universally effective", while the empirical Rademacher complexity can be estimated from the sample itself.

What is proved here, what is cited, and what the experiments show

Proved on this page: the elementary properties of the Rademacher complexity, including the value 1 exactly for a shattered sample (Lemma 1); the reduction of the 0-1 loss class to the classifiers, without the labels (Lemma 2); the symmetrization inequality in both directions (Theorem 1) and its reverse, which bounds the expected two-sided gap below by half the complexity of the loss class minus a term of order $1/\sqrt m$ (Theorem 2); the high-probability bounds with the expected and the empirical complexity, their two-sided forms, and the estimation error of empirical risk minimization (Theorem 3); $\cosh x \le e^{x^2/2}$ (Lemma 3) and Massart's lemma (Theorem 4); the VC uniform convergence bound with its logarithmic factor (Corollary 1); the contraction lemma (Theorem 5); the exact complexity of a Euclidean ball of linear functions and its upper bounds (Theorem 6); the margin bound with the radius fixed in advance (Corollary 2) and chosen after the fit (Corollary 3).

Cited: McDiarmid's and Hoeffding's inequalities and Jensen's and the Cauchy–Schwarz inequalities, proved in the linked articles; Sauer's lemma and its closed form $(em/d)^d$, proved in The VC Dimension (Theorem 5 and Corollary 1 there); the uniform convergence sample complexity without the logarithmic factor and its lower bound (Shalev-Shwartz and Ben-David, 2014, Theorem 6.8, proved in their chapter 28 except for the chaining step they omit; Bartlett and Mendelson, 2002, Theorem 1); the Khintchine–Kahane lower bound (Mohri et al., 2018, Theorem D.9); the bound of the empirical Gaussian complexity through the empirical VC dimension (Bartlett and Mendelson, 2002, Theorem 6, with Lemma 4 there for its relation to the Rademacher complexity); the attribution of the contraction lemma to Ledoux and Talagrand (1991) as Mohri et al. (2018) report it, and of the finite-set lemma to Massart (2000, Lemma 5.2), whose statement and proof, in his appendix, match Theorem 4.

What the experiments show: on samples of 50 to 1,000 of the 5,210 adults, the complexity of thresholds on HbA1c fell like $1/\sqrt m$, Massart's lemma overstated it by about a factor of 2, the observed uniform gap stayed below it, and the bounds for the chosen threshold, though valid, were about three to nine times its true risk. For a linear class the dimension-free bound with the sample's own norms was within 9% of the Monte Carlo complexity, and the margin bound for a fitted classifier was vacuous below 1,000 observations. These are observations on one population and one set of classes.

Worked problems

The problems are posed on small exact cases and on the HbA1c data of this article; this unit has no course assignments. The script tools/experiments/statistics/rademacher-complexity.py checks every number.

Problem 1 (an exact complexity by enumeration). Four adults have HbA1c 5.4, 5.4, 6.1 and 7.2. Compute the empirical Rademacher complexity of the thresholds and of the intervals ($\pm1$ versions) on these four inputs exactly, and compare with Massart's lemma. What changes if the second adult has 5.5 instead?

Solution. The inputs take $k = 3$ distinct values, with bin sums $s_1 = \sigma_1 + \sigma_2$, $s_2 = \sigma_3$, $s_3 = \sigma_4$ and total $T = s_1 + s_2 + s_3$. By the example of the definition section, for thresholds the supremum is $2\max(0, s_3, s_2 + s_3, T) - T$. The thresholds realize $k + 1 = 4$ labelings: $(-,-,-,-)$, $(-,-,-,+)$, $(-,-,+,+)$ and $(+,+,+,+)$. For these four sign vectors the supremum is $m = 4$. The other twelve go as follows, each by the formula.

  • The eight with $\sigma_1 \ne \sigma_2$: the two tied adults disagree, so no threshold can match all four signs. Six of them give 2 (a threshold agrees with three of the four). The other two, $(-,+,+,-)$ and $(+,-,+,-)$, give 0.
  • The four with $\sigma_1 = \sigma_2$ that are not labelings of the class: $(-,-,+,-)$, $(+,+,-,+)$ and $(+,+,+,-)$ give 2, and $(+,+,-,-)$ gives 0.

So the supremum is 4 for 4 vectors, 2 for 9 and 0 for 3, with mean $(16 + 18 + 0)/16 = 17/8$, and the complexity is $\frac14\cdot\frac{17}{8} = 17/32 = 0.5313$.

For intervals the supremum is $2\max(0, \text{largest run sum}) - T$. The intervals realize every labeling of the three values in which the 1s form a run of consecutive values, $3 \cdot 4/2 + 1 = 7$ labelings, and for those 7 sign vectors (all with $\sigma_1 = \sigma_2$) the supremum is 4. The remaining 9 are the eight with $\sigma_1 \ne \sigma_2$ and $(+,+,-,+)$, whose 1s at the first and third values do not form a run; for each of these an interval agrees with three of the four points, a supremum of 2. The mean is $(28 + 18)/16 = 23/8$, and the complexity is $23/32 = 0.7188$.

Massart's lemma with $r = \sqrt4 = 2$ gives $2\sqrt{2\ln 4}/4 = 0.8326$ for the 4 labelings of the thresholds and $2\sqrt{2\ln 7}/4 = 0.9864$ for the 7 of the intervals. Both hold, and both are well above the exact values. With 5.5 in place of the second 5.4, the four inputs are distinct and the thresholds realize 5 labelings; the same enumeration, which the script performs, gives $19/32 = 0.5938$. Ties lower the complexity because tied adults must share a label.

Problem 2 (the linear class on two points). Let $x_1 = (1, 0)$ and $x_2 = (1, 1)$ and $B = 1$. Compute $\hat{\mathfrak{R}}_S(\mathcal{H}_1)$ exactly, and compare with the bounds of Theorem 6 and the Khintchine–Kahane lower bound.

Solution. By Theorem 6 the complexity is $\frac12E\lVert\sigma_1x_1 + \sigma_2x_2\rVert$. The four sign vectors give $\pm(x_1 + x_2) = \pm(2, 1)$, of norm $\sqrt5$, and $\pm(x_1 - x_2) = \pm(0, -1)$, of norm 1. The mean norm is $(\sqrt5 + 1)/2$, and the complexity is $(\sqrt5 + 1)/4 = 0.8090$. The middle bound is $\frac12\sqrt{\lVert x_1\rVert^2 + \lVert x_2\rVert^2} = \frac12\sqrt{1 + 2} = 0.8660$, and the lower bound is that divided by $\sqrt2$, 0.6124. The bound $BR/\sqrt m$ with $R = \lVert x_2\rVert = \sqrt2$ is $\sqrt2/\sqrt2 = 1.0000$. The exact value lies between the lower and middle bounds, as it must.

Problem 3 (the VC bound for thresholds at $m = 200$). Evaluate the complexity and confidence terms of Corollary 1 for thresholds ($d = 1$) at $m = 200$ and $\delta = 0.05$, and compare the confidence term of the data-dependent bound (3).

Solution. The complexity term is $\sqrt{2\ln(200e)/200} = \sqrt{2(1 + \ln 200)/200} = 0.2510$. The confidence term is $\sqrt{\ln 20/400} = 0.0865$. Their sum, 0.3375, is what Corollary 1 adds to the empirical risk; added to the median empirical risk 0.075 it gives about the median bound 0.413 of the table. The data-dependent bound (3) adds the empirical complexity, about 0.099, and $3\sqrt{\ln 40/400} = 0.2881$. The data-dependent complexity term is less than half the VC term, but its confidence term is more than three times as large, and the total is larger. At larger $m$ both terms shrink like $1/\sqrt m$ and the comparison keeps its direction up to the logarithmic factor.

Problem 4 (how many adults does the VC bound need?). Find the smallest $m$ for which the two terms of Corollary 1 (one-sided, $\delta = 0.05$) add to at most 0.05, for thresholds and for intervals.

Solution. For thresholds the condition is $\sqrt{2\ln(em)/m} + \sqrt{\ln 20/(2m)} \le 0.05$. The left side decreases in $m$ for $m \ge 1$, and the script finds the first $m$ that satisfies it by counting up: $m$ = 13,497. For intervals, with $d = 2$, the condition is $\sqrt{4\ln(em/2)/m} + \sqrt{\ln 20/(2m)} \le 0.05$, first met at $m$ = 23,501. Both exceed the 5,210 adults of the survey, so on these data the VC bound cannot certify a gap of 0.05 even for the simplest class, although the observed uniform gap of the thresholds was already about 0.02 at $m = 1{,}000$.

Problem 5 (Massart's lemma on three vectors). Let $A = \{(1, 1, 1), (1, -1, 1), (-1, -1, -1)\}$ in $\mathbb{R}^3$. Compute $\mathfrak{R}(A)$ exactly and compare with Theorem 4.

Solution. For each of the 8 sign vectors $\sigma = (s_1, s_2, s_3)$ take the largest of the three inner products $s_1 + s_2 + s_3$, $s_1 - s_2 + s_3$ and $-(s_1 + s_2 + s_3)$. Split the vectors by whether $s_1 = s_3$.

  • If $s_1 \ne s_3$, then $s_1 + s_3 = 0$ and the products are $s_2$, $-s_2$ and $-s_2$, so the largest is $|s_2| = 1$. Four vectors, total 4.
  • If $s_1 = s_3$, the vector is one of $(1, 1, 1)$, $(1, -1, 1)$, $(-1, -1, -1)$ and $(-1, 1, -1)$. The first three are elements of $A$ (the third is $a_3$ itself), and an element of $A$ has inner product 3 with itself, the largest possible; so each gives 3. For $(-1, 1, -1)$ the products are $-1$, $-3$ and $1$, and the largest is 1. Total $3 + 3 + 3 + 1 = 10$.

The mean of the largest products is $(4 + 10)/8 = 7/4$, and $\mathfrak{R}(A) = \frac13\cdot\frac74 = 7/12 = 0.5833$. Theorem 4 with $N = 3$ and $r = \sqrt3$ gives $\sqrt3\sqrt{2\ln 3}/3 = 0.8558$, which holds and is about one and a half times the exact value.

Summary

Result Statement
Definition $\hat{\mathfrak{R}}_S(\mathcal{F}) = E_\sigma\sup_f\frac1m\sum_i\sigma_i f(z_i)$; $\mathfrak{R}_m = E_S\hat{\mathfrak{R}}_S$
Shattering a class of classifiers has complexity 1 on a sample exactly when it realizes every labeling (Lemma 1)
0-1 loss $\hat{\mathfrak{R}}_S(\ell_{0\text{-}1} \circ \mathcal{H}) = \frac12\hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}})$, free of the labels (Lemma 2)
Symmetrization $E\sup_f(L_{\mathcal{D}} - L_S) \le 2\mathfrak{R}_m$ (Theorem 1); $E\sup_f|L_{\mathcal{D}} - L_S| \ge \frac12\mathfrak{R}_m - c/(2\sqrt m)$ (Theorem 2)
High probability $L_{\mathcal{D}} \le L_S + 2\mathfrak{R}_m + \sqrt{\ln(1/\delta)/2m}$, or $+ 2\hat{\mathfrak{R}}_S + 3\sqrt{\ln(2/\delta)/2m}$ (Theorem 3)
Massart $\mathfrak{R}(A) \le r\sqrt{2\ln|A|}/m$ for finite $A$ (Theorem 4)
VC bound $\lvert L_{\mathcal{D}} - L_S\rvert \le \sqrt{2d\ln(em/d)/m} + \sqrt{\ln(2/\delta)/2m}$ uniformly (Corollary 1)
Contraction $\rho$-Lipschitz maps multiply the complexity by at most $\rho$ (Theorem 5)
Linear ball $\hat{\mathfrak{R}}_S = \frac BmE\lVert\sum\sigma_ix_i\rVert \le B\sqrt{\sum\lVert x_i\rVert^2}/m \le BR/\sqrt m$ (Theorem 6)
Margins error $\le$ ramp loss $+ 2BR/(\gamma\sqrt m) + \sqrt{\ln(1/\delta)/2m}$ (Corollaries 2 and 3)
HbA1c thresholds complexity 0.192, 0.099, 0.045 at $m$ = 50, 200, 1,000; uniform gap 0.082, 0.041, 0.019

What we have learned

The Rademacher complexity measures how well a class fits random signs on the sample, and by symmetrization it controls the gap between true and empirical risk uniformly over the class: the expected one-sided gap is at most twice the complexity of the loss class, and the expected two-sided gap is at least half of it less a term of order $1/\sqrt m$, a lower bound that matters only for rich classes. McDiarmid's inequality turns the expected statement into one with high probability, and the empirical version can be computed from the data. Massart's lemma links it to the number of labelings and so, through Sauer's lemma, to the VC dimension; contraction and the Cauchy–Schwarz inequality give dimension-free bounds for linear classes in terms of norms and margins. On the HbA1c data the complexity of thresholds fell like $1/\sqrt m$ and stayed above the observed gaps, and the resulting bounds were valid but several times the truth.

The same tools say what to expect of a class that can fit every labeling of its training set: complexity 1, uniform gaps at least about a quarter, and bounds no better than trivial. Modern neural networks are such classes, and they still predict well. Why Classical Bounds Do Not Explain Deep Networks reproduces that observation, derives an exact double descent curve, and reviews what has been proposed instead.

References

  • Bartlett, P. L., and Mendelson, S. (2002). Rademacher and Gaussian complexities: risk bounds and structural results. Journal of Machine Learning Research, 3, 463–482. Definition 2; Lemma 4; Theorems 1, 5, 6, 7, 8, 11 and 12. record
  • Koltchinskii, V., and Panchenko, D. (2002). Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1), 1–50. https://doi.org/10.1214/aos/1015362183 (preprint arXiv:math/0405343). record
  • Ledoux, M., and Talagrand, M. (1991). Probability in Banach Spaces: Isoperimetry and Processes. Springer. Pp. 112–114, cited by Mohri et al. (2018, §5.5) for the contraction principle; not consulted. record
  • Massart, P. (2000). Some applications of concentration inequalities to statistics. Annales de la Faculté des Sciences de Toulouse, série 6, 9(2), 245–303. Lemma 5.2 (p. 300). record
  • Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018). Foundations of Machine Learning (2nd ed.). MIT Press. Definitions 3.1 and 3.2 (and §3.1, footnote 3); Theorems 3.3, 3.5 and 3.7; Lemma 3.4; Corollaries 3.18 and 3.19; Lemma 5.7 and §5.5; Theorems 5.8 and 5.10; Corollary 5.11; Theorems D.8 and D.9. record · 5 pages
  • National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J), Glycohemoglobin (GHB_J) and Diabetes (DIQ_J) data files. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 106 pages
  • Shalev-Shwartz, S., and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press. Eqs. 26.4 and 26.5; Theorem 6.8; §26.5; Lemmas 26.2, 26.8, 26.9 and 26.10; Theorems 26.5, 26.12 and 26.14; §§28.1 and 28.2. record · 6 pages