6.1 Rademacher Complexity
6.1.1 Empirical Process Theory
Suppose \((X_i)_{i \in [n]} \overset {\text {iid}}{\sim } X \sim \mathbb {P}\), and suppose we have a function class \(\mathcal {F} \subseteq \{f : \mathcal {X} \to \mathbb {R} : \mathbb {E}[|f(X)|] < \infty \}\).
Define \[ \|\mathbb {P}_n - \mathbb {P}\|_{\mathcal {F}} := \sup _{f \in \mathcal {F}} \left | \frac {1}{n} \sum _{i=1}^n f(X_i) - \mathbb {E}[f(X)] \right |. \] Here, \(\mathbb {P}_n = \frac {1}{n} \sum _{i=1}^n \delta _{X_i}\) is the empirical measure. This is the object we will study for the next portion of the course. If there is only one function \(f\), we can deal with this using the law of large numbers and concentration inequalities. We will learn how to deal with this object using empirical process theory.
Why do we care about the maximum of the empirical process in statistics and machine learning? Recall the following setup:
| Data distribution | \((X_i)_{i \in [n]} \overset {\text {iid}}{\sim } \mathbb {P}\) |
| Loss function | \(L : \mathcal {X} \times \Theta \to \mathbb {R}\) |
| Empirical risk | \(\widehat {R}(\theta ) = \frac {1}{n} \sum _{i=1}^n \ell (X_i; \theta )\) |
| Population risk | \(R(\theta ) = \mathbb {E}_{X \sim \mathbb {P}}[\ell (X; \theta )]\) |
| Empirical risk minimizer | \(\hat {\theta } = \arg \min _\theta \widehat {R}(\theta )\) |
| Population risk minimizer | \(\theta _* = \arg \min _\theta R(\theta )\) |
| Excess risk | \(E = R(\hat {\theta }) - R(\theta _*)\) |
We train \(\hat {\theta }\) on the empirical risk, so we want the empirical risk to be close to the population risk. So to make sure training on our training data is accurate, we want to make the excess risk small. The excess risk has the following decomposition: \[ E = \underbrace {(R(\hat {\theta }) - \widehat {R}_n(\hat {\theta }))}_{\text {Gap}} + \underbrace {(\widehat {R}_n(\hat {\theta }) - \widehat {R}_n(\theta _*))}_{\leq 0} + \underbrace {(\widehat {R}_n(\theta _*) - R(\theta _*))}_{\text {bound using Hoeffding}} \] The Gap is \[ \text {Gap} = \frac {1}{n} \sum _{i=1}^n \mathbb {E}[\ell (X; \hat {\theta }) - \ell (X_i; \hat {\theta })]. \] We cannot use the strong law of large numbers to examine this because the \(\ell (X_i; \hat {\theta })\) are not independent random variables. We can fix this by replacing \(\hat {\theta }\) by the sup over \(\theta \): \[ \leq \sup _{\theta } \left | \frac {1}{n} \sum _{i=1}^n \mathbb {E}[\ell (X; \theta ) - \ell (X_i; \theta )] \right |. \] Here, \(f(X) = \ell (X; \theta )\), so we want to look at the function class \(\mathcal {F} = \{\ell (\cdot ; \theta ) : \theta \in \Theta \}\).
6.1.2 Rademacher Complexity Bounds
Recall that the Rademacher complexity of a set \(A \subseteq \mathbb {R}^n\) is \[ \mathcal {R}(A) := \mathbb {E}_{\varepsilon \overset {\text {iid}}{\sim } \text {Unif}(\{\pm 1\})} \left \{ \sup _{a \in A} \langle a, \varepsilon \rangle \right \} \]
If we write \(\mathcal {A} = \pm \mathcal {F}(x_{1:n})/n\), then we can relate Rademacher complexity of sets and function classes by \[ \widetilde {\mathcal {R}}(A) = \mathcal {R}(\mathcal {F}(x_{1:n})/n), \] where \(\widetilde {\mathcal {R}}\) denotes the Rademacher complexity of a set.
First, observe that if \(\mathcal {F}_1 \subseteq \mathcal {F}_2\), then \(\mathcal {R}_n(\mathcal {F}_1) \leq \mathcal {R}_n(\mathcal {F}_2)\), so this is a measure of the size of a function class.
Proof. Let \(Y_i \overset {\text {iid}}{\sim } X_i\) be independent of \(X_i\). Then \begin{align*} \mathbb {E}[\|\mathbb {P}_n - \mathbb {P}\|_{\mathcal {F}}] &= \mathbb {E} \left [ \sup _{f \in \mathcal {F}} \left | \frac {1}{n} \sum _{i=1}^n f(X_i) - \mathbb {E}[f(X_i)] \right | \right ] \\ &= \mathbb {E}_{X_{1:n}} \left [ \sup _{f \in \mathcal {F}} \left | \frac {1}{n} \sum _{i=1}^n f(X_i) - \mathbb {E}_{Y_{1:n}}[f(Y_i)] \right | \right ] \\ &\leq \mathbb {E}_{X_{1:n}, Y_{1:n}} \left [ \sup _{f \in \mathcal {F}} \left | \frac {1}{n} \sum _{i=1}^n (f(X_i) - f(Y_i)) \right | \right ] \end{align*}
We can introduce a Rademacher random variable without changing the distribution. \begin{align*} &= \mathbb {E}_{X_{1:n}, Y_{1:n}, \varepsilon _{1:n}} \left [ \sup _{f \in \mathcal {F}} \left | \frac {1}{n} \sum _{i=1}^n \varepsilon _i (f(X_i) - f(Y_i)) \right | \right ] \\ &\leq \mathbb {E}_{X_{1:n}, Y_{1:n}, \varepsilon _{1:n}} \left [ \sup _{f \in \mathcal {F}} \left | \frac {1}{n} \sum _{i=1}^n \varepsilon _i f(X_i) \right | - \left | \frac {1}{n} \sum _{i=1}^n \varepsilon _i f(Y_i) \right | \right ] \\ &\leq 2\mathcal {R}_n(\mathcal {F}). \end{align*} □
Define \[ \|\mathbb {S}_n\|_{\mathcal {F}} = \sup _{f \in \mathcal {F}} \left | \frac {1}{n} \sum _{i=1}^n \varepsilon _i f(X_i) \right |. \] Here is an upgraded version.
Suppose that for all \(f \in \mathcal {F}\), \(\|f\|_\infty \leq b\). Then \(\|\mathbb {P}_n - \mathbb {P}\|_{\mathcal {F}}\) is \((2b/n, \ldots , 2b/n)\)-bounded difference. The bounded difference inequality then gives that \(\|\mathbb {P}_n - \mathbb {P}\|_{\mathcal {F}}\) is \(\mathrm {sG}(b/\sqrt {n})\). In other words, \[ \big | \|\mathbb {P}_n - \mathbb {P}\|_{\mathcal {F}} - \mathbb {E}[\|\mathbb {P}_n - \mathbb {P}\|_{\mathcal {F}}] \big | \leq b \sqrt {\frac {\log (2/\delta )}{n}} \quad \text {with probability } 1 - \delta . \]
How do we upper bound the Rademacher complexity? Let’s take a higher level picture and try to bound \(\mathbb {E}[\sup _{\theta \in \Theta } X_\theta ]\). In many cases, \(X_\theta \) is sub-Gaussian for each fixed \(\theta \).
The simplest case is when \(\Theta \) is finite. In this case, we have a maximal inequality: If for all \(\theta \in \Theta \), \(X_\theta \in \mathrm {sG}(\sigma )\), then \[ \mathbb {E}\left [ \max _{\theta \in \Theta } X_\theta \right ] \leq \sigma \sqrt {2 \log |\Theta |}. \] However, typically, this set \(\Theta \) is infinite, so the maximal inequality cannot handle this case.
6.1.3 VC Dimension
Note that \(|\mathcal {F}(X_{1:n})| \leq 2^n\) always. So we want \(\mathcal {F}\) to be able to distinguish between points in a maximal sense.
By this proposition, we immediately have \[ \mathcal {R}_n(\mathcal {F}) \leq D \sqrt {\frac {\nu \log (n+1)}{n}}. \]