# 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

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