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?
Rademacher complexity and lowerbounds in learning theory
cc.complexity theory;lg.learning;pac learning
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 noteshttps://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$.