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 &quot;hypothesis class&quot; of functions mapping $ f :X \rightarrow D$, $\phi : D \times Y \rightarrow [0,1]$ is the &quot;loss function&quot;, &quot;$\phi-$&quot;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&quot; 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&quot;) (...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, &quot;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&quot;. 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.

(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