# Rademacher complexity beyond the agnostic setting

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?

(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.
• 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? – gradstudent Mar 4 '18 at 18:55
• 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 – Aryeh Mar 4 '18 at 22:18