<p>First, let's distinguish between <em>empirical</em> end <em>expected</em> Rademacher complexities. The former is defined for a function class $F$ and sequence of points $X_1,\ldots, X_n$, by
$$ \hat R_n(F;X_1,\ldots,X_n) = E_\sigma \sup_{f\in F}\frac1n\sum_{i=1}^n
\sigma_i f(X_i).$$
The latter is defined for a function class $F$ and distribution $D$, by
$$ R_n(F;D) = E_{(X_1,\ldots,X_n)\sim D^n}[\hat R_n(F;X_1,\ldots,X_n)].
$$</p>

<p>It's known that for any function class with VC-dimension $d$, we have
$\hat R_n(F;X)=O(\sqrt{d/n})$ (for any sequence $X$) -- and hence the bound carries over to $R_n(F;D)$ for all distributions $D$.</p>

<p>It's also known that the Rademacher complexity upper bounds the generalization error for agnostic PAC (plus a confidence term decaying as $\sqrt{\log(1/\delta)/n}$). On the other hand there exist adversarial distributions that force any learner to have a generalization error of $\Omega(\sqrt{d/n})$;
see, e.g., my course notes
<a href="https://www.cs.bgu.ac.il/~asml162/Class_Material" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~asml162/Class_Material</a>
.</p>

<p>From these considerations alone, we can conclude that for any function class with VC-dimension $d$, there is a distribution for which $R_n(F;D)=\Omega(\sqrt{d/n})$. </p>

<p>Edit: I also like to give the following exercise. Let $F$ be the set of all $\{\pm1\}$-valued functions on the integers. Prove that there exists a sequence of distributions $D_n$ such that $\lim_{n\to\infty}R_n(F;D_n)=1$.</p>

CC BY-SA 3.0
2017-08-01T16:00:10.913Z
Thanks for the write-up. It seems there is a "wiki-files" page where all your lecture note pdf files exist and to some of which the above links to. Could you maybe link to that repository of the pdf files? Its a bit messy to render this HTML file.
gradstudent
CC BY-SA 3.0
2017-08-01T16:40:36.017Z
I'm afraid the pdf files are internal to the wiki system, so I can't link to it externally. But the links should all point to working PDF files -- the HTML just gives a very rough outline. Also, if you agree with the answer, feel free to "accept" it.
Aryeh
CC BY-SA 3.0
2017-07-27T04:49:54.027Z
2017-07-28T09:07:13.027Z
2017-07-28T09:07:13.027Z
Aryeh
<ul>
<li><p>Is there any function class known whose Rademacher complexity has a non-trivial lowerbound? </p></li>
<li><p>Can the Rademacher complexity be used to lowerbound the generalization error in any learning situation?</p></li>
</ul>

CC BY-SA 3.0
2017-07-26T21:33:55.870Z
I'm not sure what you mean by 'non-trivial'.  Chapter 26 of understanding machine learning [(available free online here)](https://encrypted.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwjXza6S86fVAhXD5lQKHY-2BP0QFggwMAE&url=http%3A%2F%2Fwww.cs.huji.ac.il%2F~shais%2FUnderstandingMachineLearning%2F&usg=AFQjCNFlJPUGNgkMQrpZIcuwVTNQZ8lyMQ) has a reasonable introduction to rademacher complexity.
Mike Izbicki
CC BY-SA 3.0
2017-08-01T16:03:52.947Z
In that book I don't see any discussion about lowerbounds for Rademacher complexity. Am I missing something?
gradstudent
CC BY-SA 4.0
2020-02-19T16:05:30.563Z
@gradstudent Did you ever find anything about lowerbounds for the Rademacher complexity?

Besides this fact:
https://math.stackexchange.com/questions/2230255/supremum-of-expectation-le-expectation-of-supremum
ABIM
<cc.complexity-theory><lg.learning><pac-learning>
Rademacher complexity and lowerbounds in learning theory
gradstudent
# Rademacher complexity and lowerbounds in learning theory

(Asked by: username_0 on 2017-07-25)

* Is there any function class known whose Rademacher complexity has a non-trivial lowerbound?
* Can the Rademacher complexity be used to lowerbound the generalization error in any learning situation?

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

> **Comments:**
> **username_1**: I'm not sure what you mean by 'non-trivial'.  Chapter 26 of understanding machine learning [(available free online here)](https://encrypted.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwjXza6S86fVAhXD5lQKHY-2BP0QFggwMAE&url=http%3A%2F%2Fwww.cs.huji.ac.il%2F~shais%2FUnderstandingMachineLearning%2F&usg=AFQjCNFlJPUGNgkMQrpZIcuwVTNQZ8lyMQ) has a reasonable introduction to rademacher complexity.  
> **username_0**: In that book I don't see any discussion about lowerbounds for Rademacher complexity. Am I missing something?  
> **username_2**: @username_0 Did you ever find anything about lowerbounds for the Rademacher complexity?  Besides this fact: https://math.stackexchange.com/questions/2230255/supremum-of-expectation-le-expectation-of-supremum  

---

## 1 answers

### Answer by username_3 on 2017-07-27. Score: 6 | Accepted answer

First, let's distinguish between *empirical* end *expected* Rademacher complexities. The former is defined for a function class $F$ and sequence of points $X\_1,\ldots, X\_n$, by
$$ \hat R\_n(F;X\_1,\ldots,X\_n) = E\_\sigma \sup\_{f\in F}\frac1n\sum\_{i=1}^n
\sigma\_i f(X\_i).$$
The latter is defined for a function class $F$ and distribution $D$, by
$$ R\_n(F;D) = E\_{(X\_1,\ldots,X\_n)\sim D^n}[\hat R\_n(F;X\_1,\ldots,X\_n)].
$$

It's known that for any function class with VC-dimension $d$, we have
$\hat R\_n(F;X)=O(\sqrt{d/n})$ (for any sequence $X$) -- and hence the bound carries over to $R\_n(F;D)$ for all distributions $D$.

It's also known that the Rademacher complexity upper bounds the generalization error for agnostic PAC (plus a confidence term decaying as $\sqrt{\log(1/\delta)/n}$). On the other hand there exist adversarial distributions that force any learner to have a generalization error of $\Omega(\sqrt{d/n})$;
see, e.g., my course notes
<https://www.cs.bgu.ac.il/~asml162/Class_Material>
.

From these considerations alone, we can conclude that for any function class with VC-dimension $d$, there is a distribution for which $R\_n(F;D)=\Omega(\sqrt{d/n})$.

Edit: I also like to give the following exercise. Let $F$ be the set of all $\{\pm1\}$-valued functions on the integers. Prove that there exists a sequence of distributions $D\_n$ such that $\lim\_{n\to\infty}R\_n(F;D\_n)=1$.

> **Comments:**
> **username_0**: Thanks for the write-up. It seems there is a "wiki-files" page where all your lecture note pdf files exist and to some of which the above links to. Could you maybe link to that repository of the pdf files? Its a bit messy to render this HTML file.  
> **username_3**: I'm afraid the pdf files are internal to the wiki system, so I can't link to it externally. But the links should all point to working PDF files -- the HTML just gives a very rough outline. Also, if you agree with the answer, feel free to "accept" it.  

---

