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

  • $\begingroup$ 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. $\endgroup$ – Mike Izbicki Jul 26 '17 at 21:33
  • $\begingroup$ In that book I don't see any discussion about lowerbounds for Rademacher complexity. Am I missing something? $\endgroup$ – gradstudent Aug 1 '17 at 16:03
  • $\begingroup$ @gradstudent Did you ever find anything about lowerbounds for the Rademacher complexity? Besides this fact: math.stackexchange.com/questions/2230255/… $\endgroup$ – AIM_BLB Feb 19 '20 at 16:05

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

  • $\begingroup$ 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. $\endgroup$ – gradstudent Aug 1 '17 at 16:00
  • $\begingroup$ 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. $\endgroup$ – Aryeh Aug 1 '17 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.