What's the intuition behind Rademacher complexity?
The standard &quot;intuition&quot; is that the Rademacher complexity quantifies the ability of the function class $F$ to fit symmetric random noise: a low value (close to 0) means that this ability is limited (and hence the &quot;capacity&quot; of this class is bounded), while a high value (close to 1 for $\{-1,1\}$-valued classes) means that essentially any sequence of random signed bits has a perfect fit (and hence the capacity is unbounded).
To delve a bit deeper, it's always helpful to consider the extreme cases. Let $F$ be a collection of $\{-1,1\}$-valued functions on some large set $\Omega$, $|\Omega|=N\gg1$. What happens when $F$ consists of a single function $f$? What happens when $F=2^\Omega$ consists of all possible functions? You can also consider the cases where $|F|=2,3$ and look up &quot;Massart's finite class lemma&quot;, which gives a bound for $|F|&lt;\infty$ and is actually at the heart of more sophisticated (covering-number based) bounds.