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.

  • $\begingroup$ Rademacher complexity is just another tool in your toolbox; and it can be useful if you know certain properties like bounded loss or lipschitz continuity of your loss. In particular, you can invoke things like Massart's Finite Lemma, which gives you a bound on the empirical rademacher complexity. Using the eRC, you then have theorems connecting the generalization error to RC: erdogdu.github.io/csc2532/lectures/lecture07.pdf $\endgroup$ – information_interchange Mar 11 '20 at 3:23
  • $\begingroup$ @information_interchange Yep; I've expanded my answer to more explicitly cover your point. $\endgroup$ – VF1 Mar 11 '20 at 4:16

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 -- "Is Rademacher complexity still useful without knowledge of the data distribution?" -- 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).

More precisely, using a technique called symmetrization you can show that your generalization error (or indeed, uniform convergence error for empirical processes) is bounded by Rademacher averages. These, in turn, allow for control through covering numbers on our functional space (so you can come up with bounds for very general classes of functions, from arbitrary parametric classes with a Lipschitz condition to nonparametric bounded Lipschitz or monotonic classes through fat-shattering dimension).

With VC dimension, parametric function classes will usually have similar bounds as those derived from the above, but you have to write a proof for each parametric function class you bound! With covering number bounds from Rademacher complexity, you can take advantage of structural results and know that as long as your function class has a certain type of regularity, you can use "building blocks" that let you build-a-complexity-bound, or even bound things you couldn't otherwise (like non-parametric classes with infinite VC dimension). Other approaches to bounding Rademacher averages exist as well, some of which give better bounds than covering numbers (e.g., bracketing).


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.