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.


Always fun to come back to these... :)

Rademacher bounds are still useful in theoretical settings precisely because they're distribution-dependent! While it's unrealistic to know the data distribution ahead of time, you can still use additional context from your setting and the Rademacher bounds to get sharper results than you could otherwise.

For instance:

Perhaps most practically and directly answering the question -- "don't we need knowledge of the data distribution for this to be useful?" -- is Bartlett and Mendelson 2002.

With a firm yes. In particular, Rademacher complexities observe structural regularities (Section 3.1), which enable us to express complexities of weird function classes (such as neural networks) in terms of simpler ones (such as perceptrons).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.