<p>(a) If you don't assume that you're "competing" against $f\in F$, you must make <em>some</em> 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.</p>

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

<p>(c) It looks like you're looking for a <em>lower</em> 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:
<a href="https://www.sciencedirect.com/science/article/pii/030439759190026X" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/030439759190026X</a></p>

CC BY-SA 3.0
2018-03-04T18:55:23.573Z
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
CC BY-SA 3.0
2018-03-04T18:55:28.510Z
(...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?..)
gradstudent
CC BY-SA 3.0
2018-03-04T22:18:42.810Z
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:https://www.princeton.edu/~rvan/APC550.pdf
Aryeh
CC BY-SA 3.0
2018-03-05T06:22:31.163Z
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, https://bcourses.berkeley.edu/courses/1409209/files/66290941/download?wrap=1 - though unfortunately the proof isnt here...)
gradstudent
CC BY-SA 3.0
2018-03-05T09:23:53.927Z
Gaussian and Rademacher complexities are intimately related; see Lemma 4 here: http://www.jmlr.org/papers/volume3/bartlett02a/bartlett02a.pdf
Aryeh
CC BY-SA 3.0
2018-03-04T09:20:14.530Z
2018-03-04T09:20:14.530Z
Aryeh
<p>The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, <a href="http://ttic.uchicago.edu/%7Etewari/lectures/lecture9.pdf" rel="nofollow noreferrer">http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf</a>. Here the quantity on the LHS that Rademacher complexity is trying to upperbound is given as, <span class="math-container">$L_{\phi}(\hat{f}_{\phi}^*)-\min_{f \in F} L_{\phi}(f)$</span> where <span class="math-container">$F$</span> is some &quot;hypothesis class&quot; of functions mapping <span class="math-container">$ f :X \rightarrow D$</span>, <span class="math-container">$\phi : D \times Y \rightarrow [0,1]$</span> is the &quot;loss function&quot;, &quot;<span class="math-container">$\phi-$</span>&quot;loss of any function <span class="math-container">$g : X \rightarrow D$</span> is defined as, <span class="math-container">$L_\phi(g) = \mathbb{E}[\phi(f(x),y)]$</span> - where the expectation is taken over some distribution over the points <span class="math-container">$(x,y) \in X \times Y$</span> and <span class="math-container">$\hat{f}_{\phi}^*$</span> is what the ERM returns over some <span class="math-container">$m$</span> samples i.e <span class="math-container">$\hat{f}_{\phi}^* = \mathrm{argmin}_{f \in F} \frac{1}{m} \sum_{i=1}^m \phi(f(x_i),y_i)$</span>.</p>
<p>The above setting is called ``agnostic&quot; because at no point was it assumed that, <span class="math-container">$\exists$</span> any ground-truth labelling function <span class="math-container">$L \in F$</span> such that <span class="math-container">$y = L(x)$</span> but rather the class <span class="math-container">$F$</span> is to be seen to be trying to learn via empirical risk minimization a distribution, say <span class="math-container">${\cal D}$</span>, over <span class="math-container">$X \times Y$</span>.</p>
<p>My question is 3 fold , is there any analogue of this Theorem <span class="math-container">$2.4$</span> when,</p>
<p>(a)
an existence of a <span class="math-container">$L$</span> is assumed with <span class="math-container">$L$</span> may or maynot be in <span class="math-container">$F$</span>. (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!..)</p>
<p>(b)
the loss function <span class="math-container">$\phi$</span> is not assumed to be bounded above but only assumed to be bounded below.</p>
<p>(c)
<em>AND</em> most importantly, say I have a class of labelling functions <span class="math-container">${\cal L}$</span> mapping <span class="math-container">$X \rightarrow Y$</span> and I want to say the following, <em>&quot;Given a loss function <span class="math-container">$\phi$</span>, irrespective of which member of <span class="math-container">${\cal L}$</span> labels the data (maybe also irrespective of the distribution over <span class="math-container">$X$</span> used to measure <span class="math-container">$L_{\phi}$</span>) the member of class <span class="math-container">$F$</span> obtained via ERM on the data, can never generalize well&quot;</em>. Is there a version of Rademacher complexity which captures this?</p>

<cc.complexity-theory><machine-learning><lg.learning><pac-learning><online-learning>
Rademacher complexity beyond the agnostic setting
gradstudent
# Rademacher complexity beyond the agnostic setting

(Asked by: username_0 on 2018-03-03)

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](http://ttic.uchicago.edu/%7Etewari/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?

**Tags:** cc.complexity-theory, machine-learning, lg.learning, pac-learning, online-learning


---

## 1 answers

### Answer by username_1 on 2018-03-04. Score: 3 | Accepted answer

(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>

> **Comments:**
> **username_0**: 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?  
> **username_0**: (...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?..)  
> **username_1**: 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:https://www.princeton.edu/~rvan/APC550.pdf  
> **username_0**: 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, https://bcourses.berkeley.edu/courses/1409209/files/66290941/download?wrap=1 - though unfortunately the proof isnt here...)  
> **username_1**: Gaussian and Rademacher complexities are intimately related; see Lemma 4 here: http://www.jmlr.org/papers/volume3/bartlett02a/bartlett02a.pdf  

---

