# Rademacher complexity and lowerbounds in learning theory

• 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?

• I'm not sure what you mean by 'non-trivial'. Chapter 26 of understanding machine learning (available free online here) has a reasonable introduction to rademacher complexity. – Mike Izbicki Jul 26 '17 at 21:33
• In that book I don't see any discussion about lowerbounds for Rademacher complexity. Am I missing something? – gradstudent Aug 1 '17 at 16:03
• @gradstudent Did you ever find anything about lowerbounds for the Rademacher complexity? Besides this fact: math.stackexchange.com/questions/2230255/… – AIM_BLB Feb 19 '20 at 16:05

## 1 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$.

• 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 Aug 1 '17 at 16:00
• 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 Aug 1 '17 at 16:40