Why we use Rademacher complexity for generalization error when we can have a trained function?

Question

Let $G$ be a family of functions mapping from $Z$ to $[a, b]$ and $S=\left(z_{1}, \ldots, z_{m}\right)$ a fixed sample of size $m$ with elements in $Z$ . Then, the empirical Rademacher complexity of $G$ with respect to the sample $S$ is defined as : $$ \widehat{\Re}_{S}(G)=\underset{\boldsymbol{\sigma}}{\mathrm{E}}\left[\sup _{g \in G} \frac{1}{m} \sum_{i=1}^{m} \sigma_{i} g\left(z_{i}\right)\right] \text { . } $$ where $\boldsymbol{\sigma}=\left(\sigma_{1}, \ldots, \sigma_{m}\right)^{\top},$ with $\sigma_{i} s$ independent uniform random variables taking values in ${-1,+1}.

Empirical Rademacher complexity is commonly used in bounding the generalization error. From definition of empirical Rademacher complexity I found that it is data-dependent and irrelevant to the training algorithm - it depends on the complexity of hypotheses set.

My concern is that: we will usually get a fixed function by a training algorithm on a training set, and we can give the generalization error regarding this function directly by Hoeffding's inequality. Why we need to calculate Rademacher complexity for a generalization error bound which involves a hypotheses set?

Answer 1

We will usually get a fixed function by a training algorithm on a training set, and we can give the generalization error regarding this function directly by Hoeffding's inequality.

Nope! The function is special because you used the data to pick it, i.e. it's correlated. By this same reasoning, you could draw samples uniformly from $[0,1]$, then take that set of samples and argue by Hoeffding's that any future draw from $U[0,1]$ is likely to be in this finite set (after all, every one of the initial samples was!).

So we need to bound the probability of the learning process outputting a bad hypothesis, or in other words, treat the hypothesis as a random variable. The straightforward approach is to take a small set of hypotheses as our class, use Hoeffding on all of them, then take a union bound. This gives a high probability that all the hypotheses have empirical loss close to to true expected loss on the sample. Therefore, no matter what the training algorithm is, the hypothesis it outputs will have expected loss close to empirical loss.

VC-dimension and Rademacher complexity are just improvements on this straightforward approach.