The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that Rademacher complexity is trying to upperbound is given as, $L_{\phi}(\hat{f}_{\phi}^*)-\min_{f \in F} L_{\phi}(f)$ where $F$ is some "hypothesis class" of functions mapping $ f :X \rightarrow D$, $\phi : D \times Y \rightarrow [0,1]$ is the "loss function", "$\phi-$"loss of any function $g : X \rightarrow D$ is defined as, $L_\phi(g) = \mathbb{E}[\phi(f(x),y)]$ - where the expectation is taken over some distribution over the points $(x,y) \in X \times Y$ and $\hat{f}_{\phi}^*$ is what the ERM returns over some $m$ samples i.e $\hat{f}_{\phi}^* = \mathrm{argmin}_{f \in F} \frac{1}{m} \sum_{i=1}^m \phi(f(x_i),y_i)$.

The above setting is called ``agnostic" because at no point was it assumed that, $\exists$ any ground-truth labelling function $L \in F$ such that $y = L(x)$ but rather the class $F$ is to be seen to be trying to learn via empirical risk minimization a distribution, say ${\cal D}$, over $X \times Y$.

My question is 3 fold , is there any analogue of this Theorem $2.4$ when,

(a) an existence of a $L$ is assumed with $L$ may or maynot be in $F$. (the later is I guess often called the ``realizable setting") (...I have seen some papers trying to bound generalization error of a specific algorithm in the realizable setting but I somehow dont see Rademacher complexity defined in those settings!..)

(b) the loss function $\phi$ is not assumed to be bounded above but only assumed to be bounded below.

(c) AND most importantly, say I have a class of labelling functions ${\cal L}$ mapping $X \rightarrow Y$ and I want to say the following, "Given a loss function $\phi$, irrespective of which member of ${\cal L}$ labels the data (maybe also irrespective of the distribution over $X$ used to measure $L_{\phi}$) the member of class $F$ obtained via ERM on the data, can never generalize well". Is there a version of Rademacher complexity which captures this?


1 Answer 1


(a) If you don't assume that you're "competing" against $f\in F$, you must make some assumption about the larger function class to which $f$ belongs -- otherwise, by standard no-free-lunch theorems, you will not be able to give any meaningful risk decay rates (which is what Rademacher complexities enable you to do). Alternatively, you could assume something about the distribution (trivial case: it has finite support). Then you can get distribution-dependent rates.

(b) For unbounded losses, you typically need additional assumptions such as convexity or tail decay. See, eg, https://papers.nips.cc/paper/3894-smoothness-low-noise-and-fast-rates and http://proceedings.mlr.press/v32/kontorovicha14.html

(c) It looks like you're looking for a lower bound on the risk in terms of Rademacher complexity. Any such result would have to be distribution-dependent. Since Rademacher complexity is majorized by covering numbers (via Dudley's integral) and also minorized by these (Sudakov inequality), you could probably use the covering-number characterization of learnability: https://www.sciencedirect.com/science/article/pii/030439759190026X

  • $\begingroup$ Thanks a lot for the comments! In case (a) by $f$ do you mean what I called $L$? (b) here you mean that addition assumptions become necessary even if we assume only lower boundedness and not upperboundedness? (..which is virtually all loss functions in real life!..) and (c) could you kindly give a reference for this Sudakov theorem you refer to? $\endgroup$ Commented Mar 4, 2018 at 18:55
  • $\begingroup$ (...this reminds me : a recent paper by Foster-Telgarsky-Bartlett found tight bounds on the covering number of neural nets : then why is that not the end of the story for Rademacher complexity of nets given that coverning number also lowerbounds Rademacher?..) $\endgroup$ Commented Mar 4, 2018 at 18:55
  • $\begingroup$ Yes, I meant that $F$ is the loss class (i.e., classifier/regressor composed with loss). For Sudakov's inequality, see, e.g., Thm. 6.5 here:princeton.edu/~rvan/APC550.pdf $\endgroup$
    – Aryeh
    Commented Mar 4, 2018 at 22:18
  • $\begingroup$ Not sure I am understanding why Theorem 6.5 applies here. This is about a Gaussian process. Whereas Rademacher complexity doesnt really have to be so : infact here the indexing set is a function class which can as well be uncountably infinite unlike the set "T" there. Shouldnt there be a different proof for Rademacher complexity? (..the Sudakov-for-Rademacher does seem to look a bit different as in page 26 here, bcourses.berkeley.edu/courses/1409209/files/66290941/… - though unfortunately the proof isnt here...) $\endgroup$ Commented Mar 5, 2018 at 6:22
  • $\begingroup$ Gaussian and Rademacher complexities are intimately related; see Lemma 4 here: jmlr.org/papers/volume3/bartlett02a/bartlett02a.pdf $\endgroup$
    – Aryeh
    Commented Mar 5, 2018 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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