• 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$ Jul 26, 2017 at 21:33
  • $\begingroup$ In that book I don't see any discussion about lowerbounds for Rademacher complexity. Am I missing something? $\endgroup$ Aug 1, 2017 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$
    – ABIM
    Feb 19, 2020 at 16:05

1 Answer 1


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$ Aug 1, 2017 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, 2017 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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