3.2: A Brief Introduction on Rademacher Complexity

Introduction

In AI/ML, we are interested in how well a model performs on unseen data, and this ability is called generalization. The Rademacher complexity is a measure that quantifies how flexible or complex a model or class of models is, by evaluating how well it can fit random noise. It indicates how likely a model is to generalize well (i.e., perform accurately on new, unseen examples rather than just the training data). Models with lower Rademacher complexity are less likely to overfit the training data and tend to generalize better to real-world situations.

In this note, we will first define the Rademacher complexity. Then we will prove a key result relating generalization bounds and the Rademacher complexity.

In the final section, we outline an explicit calculation related to regression models.

Defining Rademacher Complexity

Rademacher complexity: it is a measure of how rich or complex a class of functions is, quantifying how well these functions can fit random noise.

• Setup:

  • Let ℱ be a class of real-valued functions f : 𝒵 → ℝ.¹ The space 𝒵 is known as the input space. E.g., if each z is a n-dimensional vector, then z ∈ ℝⁿ = 𝒵.

  • Let S = {z₁, z₂, ..., z_m} be a sample of m data points drawn i.i.d. from some distribution 𝒟. Sometimes this is written as S ∼ D^m.

• Rademacher random variables:

  • σ₁, σ₂, ..., σ_m are independent random variables.

  • Each σ_i takes values  ± 1 with equal probability 1/2.

• Empirical Rademacher complexity (on sample S) of ℱ: it is defined as follows:
  $$\label{03r=01} \widehat{\text{Rad}}_S(\mathcal{F}) := \mathbb{E}_\sigma \left[ \sup_{f \in \mathcal{F}} \frac{1}{m} \sum_{i=1}^m \sigma_i f(z_i) \right]$$

  • The sum, \( (1/m) \sum_{i=1}^m \sigma_i f(z_i), \) measures the correlation between the Rademacher variables, σ_i, and the output f(z_i).

  • The supremum means it looks for the maximum (or, the best possible) correlation with the random noise (represented by the Rademacher variables) that any function within the entire class ℱ can achieve. It finds the function in ℱ that is best at “fitting” this randomly generated noise.

  • The expectation 𝔼_σ is taken over all possible combinations of the Rademacher variables. The empirical Rademacher complexity to design to capture the expected ability of the function class to fit random noise.

  • A brief summary: \( \widehat{\text{Rad}}_S(\mathcal{F}) \) measures how well, on average, a set of functions (a class of functions, not just one function) can fit random noise on a given fixed sample of data points.

• Rademacher complexity. This is also known as the Population (or Expected) Rademacher complexity:
  $$\label{03r=02} \text{Rad}_m (\mathcal{F}) := \mathbb{E}_S \left[ \widehat{\text{Rad}}_S (\mathcal{F}) \right]$$
  The expectation 𝔼_S is over all samples S of size m drawn i.i.d. from 𝒟. It measures the expected or typical richness (capacity) of a function class with respect to the data distribution, rather than just its behavior on one fixed training sample.

• Interpretation:

  High Rademacher complexity means the function class can fit random noise well, indicating higher complexity and potential overfitting.

A Key Result regarding Rademacher Complexity

In this section, we prove a result that illusrates how the generalization gap is related to the the Rademacher complexity.

[Theorem 3.1] Let

• 𝒢 be a family of functions mapping from 𝒵 to [0, 1].

• Let D be a distribution of 𝒵 (so z ∼ D for z ∈ 𝒵).

Then, for any δ > 0, with probability at least 1 − δ, the following holds for each g ∈ 𝒢:
$$\label{03r=03} \mathbb{E}_D [ g ] \leq \frac{1}{m} \sum_{i=1}^m g(z_i) + 2 \text{\emph{Rad}}_m (\mathcal{G}) + \sqrt{ \frac{ \log( 1/ \delta) }{2m } } .$$

Note:

• 𝔼_D[g] is the mean of g over the true distribution D: \( \mathbb{E}_D[g]:= \int g(z) \, dD(z) \). Whereas \( \frac{1}{m} \sum_i g(z_i) \) is the empirical mean of g, which is an approximation of 𝔼_D[g].

• This theorem quantifies the difference between expected mean and empirical mean (an example of the generalization gap) in terms of the Rademacher complexity of the hypothesis class, 𝒢. We note that smaller Rademacher complexity implies stronger generalization guarantees (i.e., smaller generalization gaps).

Proof. Let S = {z₁, ⋯, z_m}. Define
$$\widehat{\mathbb{E}}_S [g] := \frac{1}{m} \sum_{i=1}^m g(z_i).$$
This is the first term of the RHS of ([03r=03]).

• Step 0. Note that, by the definition of supremum, we have
  $$\label{03r=04} \mathbb{E}_D [g] -\widehat{\mathbb{E}}_S [g] \leq \underbrace{ \sup_{g \in \mathcal{G}} \left( \mathbb{E}_D [g] -\widehat{\mathbb{E}}_S [g] \right) }_{:= \Phi(S)} .$$

• Step 1. We use McDiarmid’s inequality to bound Φ(S) (see the next section for details): for any δ > 0, with probability at least 1 − δ, the following is true
  $$\label{03r=05} \Phi (S) \leq \mathbb{E}_S [ \Phi (S) ] + \sqrt{ \frac{ \log (1/\delta) }{2m} } .$$

  Proof. To this end, we need to check the bounded difference property is satisfied. Consider a sample S′: it differs from S at exactly one data entry (say, at the i-th data entry). Then we have
  $$\begin{aligned} \Phi(S) -\Phi(S') &= \sup_{g \in \mathcal{G} } \left( \mathbb{E}_D[ g ] - \widehat{\mathbb{E}}_S [g] \right) - \sup_{g \in \mathcal{G} } \left( \mathbb{E}_D[ g ] - \widehat{\mathbb{E}}_{S'} [g] \right) \nonumber \\ & \leq \sup_{g \in \mathcal{G} } \left( \widehat{\mathbb{E}}_{S'} [g] - \widehat{\mathbb{E}}_S [g] \right) \nonumber \\ & = \sup_{g \in \mathcal{G} } \frac{ g(z'_i) - g(z_i) }{m} \leq \frac{1}{m} .\end{aligned}$$
  To obtain the last inequality, we have used the fact that g maps to the interval [0, 1]. Hence,
  $$\label{03r=06} \left| \Phi(S) -\Phi(S') \right| \leq \frac{1}{m},$$
  and the bounded difference properity is satisfied. Now we apply McDiarmid’s inequality with c_i = 1/m. With any ϵ > 0, $$ \text{Prob}\left( \Phi( S) - \mathbb{E}_S [ \Phi( S) ] \geq \epsilon \right) \leq \exp \left( -2 m \epsilon^2 \right). $$
  Setting δ := exp (−2mϵ²), this is the same as, for any δ > 0, with probability at least 1 − δ, the following is true:
  $$\Phi( S) \leq \mathbb{E}_S [ \Phi( S) ] + \sqrt{ \frac{ \log (1/\delta) }{ 2m } } ,$$
  the desired result.□

• Step 2. The key result of this step is $$ \mathbb{E}_S [ \Phi (S)  ] \leq 2 
  \text{Rad}_m (
  \mathcal{G}
  ) . $$

  Proof.
  $$\begin{aligned} \mathbb{E}_S [ \, \Phi (S) \, ] &= \mathbb{E}_S \left[ \, \sup_{g \in \mathcal{G} } \left( \mathbb{E}_D[ g ] - \widehat{\mathbb{E}}_S [g] \right) \, \right] \nonumber \\ &= \mathbb{E}_S \left[ \, \sup_{g \in \mathcal{G} } \mathbb{E}_{S'} \, \left( \, \widehat{\mathbb{E}}_{S'} [g]- \widehat{\mathbb{E}}_{S} [g] \, \right) \, \right]  \\ &\leq \mathbb{E}_{S,S'} \left[ \, \sup_{g \in \mathcal{G} } \left( \, \widehat{\mathbb{E}}_{S'} [g]- \widehat{\mathbb{E}}_{S } [g] \, \right) \, \right] \\ &= \mathbb{E}_{S,S'} \left[ \, \sup_{g \in \mathcal{G} } \frac{1}{m} \sum_{i=1}^m ( g(z'_i) - g(z_i) ) \, \right] \\ &= \mathbb{E}_{\sigma, S,S'} \left[ \, \sup_{g \in \mathcal{G} } \frac{1}{m} \sum_{i=1}^m \sigma_i ( g(z'_i) - g(z_i) ) \, \right]  \\ &\leq \mathbb{E}_{\sigma, S'} \left[ \, \sup_{g \in \mathcal{G} } \frac{1}{m} \sum_{i=1}^m \sigma_i g(z'_i ) \, \right] + \mathbb{E}_{\sigma, S} \left[ \, \sup_{g \in \mathcal{G} } \frac{1}{m} \sum_{i=1}^m (-\sigma_i) g(z_i ) \, \right]  \\ &=2 \mathbb{E}_{\sigma, S'} \left[ \, \sup_{g \in \mathcal{G} } \frac{1}{m} \sum_{i=1}^m \sigma_i g(z'_i ) \, \right] = 2 \text{Rad}_m ( \mathcal{G} ).\end{aligned}$$
  Note:

  • For the 2nd equality: S′ = {z′₁, ⋯, z′_m} is another set of sample of m elements, drawn i.i.d. from the same distribution (i.e., each z′_i ∼ D). S′ is called the ghost sample. We have used
    $$\begin{aligned} \mathbb{E}_{S'} \left[ \, \widehat{\mathbb{E}}_{S'} [g] \, \right] &= \mathbb{E}_{S'} \left[ \frac{1}{m} \sum_{i} g(z'_i) \right] = \frac{1}{m} \sum_{i} \mathbb{E}_D [g] \\ &= \left( \frac{1}{m} \sum_{i} 1 \right) \, \mathbb{E}_D [g] =\mathbb{E}_D [g] ,\end{aligned}$$
    as S and S′ are independent. Similarly, one can show that \( \widehat{\mathbb{E}}_S [g] = \mathbb{E}_{S'} \left[ \widehat{\mathbb{E}}_S [g] \right] \).

  • For the 1st inequality: use the sub-additivity of the supremum; the supremum of an expectation is at most the expectation of the supremum.

  • For the 4th equality: this is perhaps the most tricky part of the proof. Taking the average over all σ_i, does not change the expectation in the 3rd equality. The key idea is, the distribution of g(z′) − g(z) is the same as that of  ± (g(z′) − g(z)) (as z and z′ are independently and symmetrically distributed). To illustrate the idea, let us work out the situation with one pair of RVs, X and X′ that have the same distribution (say, given by the probability density p( ⋅ )), with only a single Rademacher variable. Let Θ : ℝ → ℝ be a function, and we want to show $$ \mathbb{E}_{X,X'} \left[ \Theta( g(X)-g(X') ) \right] = \mathbb{E}_{X,X', \sigma} \left[ \Theta( \sigma (g(X)-g(X')) ) \right]. $$
    To see this: the LHS is given by $$ \mathbb{E}_{X,X'} \left[ \Theta( \, g(X)-g(X') \,  ) \right] = \iint \Theta( \, g(x)-g(x') \,  ) \, p(x) p(x') \, dx dx'.$$
    The RHS is given by
    $$\begin{aligned} & \mathbb{E}_{X,X', \sigma} \left[ \Theta( \, \sigma (g(X)-g(X')) \, ) \right] \nonumber \\ &= \text{Prob}(\sigma = 1) \iint \Theta( \, g(x)-g(x') \, ) \, p(x) p(x') \, dx dx' \nonumber \\ & \quad \quad + \text{Prob}(\sigma = -1) \iint \Theta( \, -g(x)+g(x') \, )\, p(x) p(x') \, dx dx' \nonumber \\ &= \frac{1}{2} \iint \Theta( g(x)-g(x') ) \, p(x) p(x') \, dx dx' \nonumber \\ & \quad \quad + \frac{1}{2} \iint \Theta( -g(x)+g(x') ) \, p(x) p(x') \, dx dx' \nonumber \\ &= \frac{1}{2} \iint \Theta( g(x)-g(x') ) \, p(x) p(x') \, dx dx' \nonumber \\ & \quad \quad + \frac{1}{2} \iint \Theta( -g(u')+ g(u) ) \, p(u') p(u) \, du' du \label{03r=16} \\ &=\iint \Theta( g(x)-g(x') ) \, p(x) p(x') \, dx dx' \quad \text{(=the LHS)} . \nonumber\end{aligned}$$

  • For the last line: this is because both  − σ_i and σ_i have identical distribution, and both expectations equal Rad_m(𝒢).

  This completes the proof. □

• Step 3. Racing to the finish line. Together these imply the desired result.

1. For more info: see

   Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of machine learning (2nd ed.). MIT Press.

2. McDiarmid’s inequality: it is a concentration bound for functions of independent random variables that satisfy a bounded differences condition. Let X₁, X₂, …, X_m be independent random variables with X_i ∈ 𝒳_i, and let f : 𝒳₁ × … × 𝒳_m → ℝ satisfy, for each i: $$ \sup_{x_1, ..., x_m, x_i'} \left| 
   f(x_1, ..., x_i, ..., x_m) 
   - 
   f(x_1, ..., x_i', ..., x_m)  \right| \leq c_i. $$
   Then, for any ε > 0,
   $$\begin{aligned} \mathbb{P}\left( f(X_1, ..., X_m) - \mathbb{E}[f(X_1, ..., X_m)] \geq \varepsilon \right) & \leq \exp\left( -\frac{2\varepsilon^2}{\sum_{i=1}^m c_i^2} \right),  \\ \mathbb{P}\left( f(X_1, ..., X_m) - \mathbb{E}[f(X_1, ..., X_m)] \leq -\varepsilon \right) & \leq \exp\left( -\frac{2\varepsilon^2}{\sum_{i=1}^m c_i^2} \right). \end{aligned}$$
   See Mohri et al. (2018) for a proof.

3. The empirial Rademacher complex for linear regression models

   Consider the following function class (with M, W, X being constants): for x ∈ ℝ^d such that ∥x∥₂ ≤ X, define
   ℱ = {x → w ⋅ x : ∥w∥₂ ≤ W}
   Let S = {x₁, ⋯, x_m} be m data points. Then we have
   $$\label{03r=103} \widehat{\text{Rad}}_S ( \mathcal{F}) \leq \frac{W X}{\sqrt{m}}.$$
   To see this:
   $$\begin{aligned} \widehat{\text{Rad}}_S ( \mathcal{F}) &= \mathbb{E}_\sigma \left[ \, \sup_{f \in \mathcal{F}} \frac{1}{m} \sum_{i=1}^m \sigma_i f(\mathbf{x}_i) \, \right] && \text{(by definition)} \\ &= \frac{1}{m} \mathbb{E}_\sigma \left[ \, \sup_{\mathbf{w}, \, \lVert \mathbf{w} \rVert_2 \leq W } \, \sum_{i=1}^m \sigma_i \, ( \mathbf{w} \cdot \mathbf{x}_i ) \, \right]  \\ &= \frac{1}{m} \mathbb{E}_\sigma \left[ \, \sup_{\mathbf{w}, \, \lVert \mathbf{w} \rVert_2 \leq W } \, \mathbf{w} \cdot \sum_{i=1}^m \sigma_i \mathbf{x}_i \, \right]  \\ &\leq \frac{W}{m} \mathbb{E}_\sigma \left[ \, \left\lVert \sum_{i=1}^m \sigma_i \mathbf{x}_i \right\rVert_2 \, \right] && \text{(by Cauchy-Scwhartz ineq.)} \\ &= \frac{W}{m} \left( \mathbb{E}_\sigma \left[ \sum_{i=1}^m \sigma_i^2 \lVert \mathbf{x}_i \rVert_2^2 + 2 \sum_{i<j} \sigma_i \sigma_j \, (\mathbf{x}_i \cdot \mathbf{x}_j ) \right] \right)^{1/2} && \\ &= \frac{W}{m} \left( \mathbb{E}_\sigma \left[ \sum_{i=1}^m \sigma_i^2 \lVert \mathbf{x}_i \rVert_2^2 \right] \right)^{1/2} && \text{(as $\mathbb{E}[ \sigma_i \sigma_j ] =0$)} \\ &= \frac{W}{m} \left( \sum_{i=1}^m \lVert \mathbf{x}_i \rVert_2^2 \right)^{1/2} && \text{(as $\sigma_i^2 =1$)} \\ & \leq \frac{W}{m} \left( m X^2 \right)^{1/2} =\frac{W X}{\sqrt{m}}.\end{aligned}$$