# What good are Rademacher bounds?

VC complexity bounds are generally well-known for common hypothesis classes based on supervised learning ERM algorithms. However, VC bounds are independent of the distribution from which the data is assumed to be generated in an iid manner. This weak assumption suffices to prove that the gap between training and generalization error, $\varepsilon$, is bounded with high probability as: $$\varepsilon \le O(d/m),$$ where $d$ is the VC dimension of the class of functions whose complexity we're considering and $m$ is the training sample size.

Rademacher complexity is frequently touted to be an improvement over VC dimension (e.g., see the bottom two paragraphs of Section 1.1 here). The empirical Rademacher complexity $\hat{R}_S$ is taken wrt a sample of input/output pairs $S$. If $\mathcal{G}$ is the set of cost functions associated with fixing a hypothesis from our hypothesis class, $S$ consists of $m$ samples $z_i$, and $\sigma_i$ are uniformly drawn from $\{\pm1\}$, then the empirical Rademacher complexity effectively quantifies $\mathcal{G}$'s correlation with noise on $S$: $$\hat{R}_S(\mathcal{G})=\mathbb{E}_{\{\sigma_i\}}\frac{1}{m}\sup_{g\in\mathcal{G}}\sum_{i=1}^m g(z_i)\sigma_i$$

Let $R_m(\mathcal{G})=\mathbb{E}_S\hat{R}_S(\mathcal{G})$ be the true Rademacher complexity. We know that with high probability, assuming data was iid: $$\varepsilon \le O(R_m),\;\;\varepsilon\le O(\hat{R}_S).$$ However, if we try to derive distribution-independent bounds from the above, we would get the same learning bounds as VC dimension offers (we have to, since VC bounds are tight in that context). In what real settings does this actually yield an improvement over VC bounds, or even in what theoretical settings is this useful?

It seems like we would need these hard-to-attain conditions to get improvements:

• We have a sufficiently good approximation to $\hat{R}_S$, and $\hat{R}_S$ plus the approximation error still improves the bound.
• We have some knowledge of the data distribution, letting us find $R_m$, and $R_m$ improves $O(d/m)$.

In fact, $R_m$ seems like it might never be useful in practice, since it seems always as hard to compute as $\hat{R}_S$ but only requires more knowledge, and only improves the bound by constants. Finally, $\hat{R}_m$ is usually NP-hard to compute; for neural networks it seems that approximations are, too.