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

CC BY-SA 4.0
2020-11-19T10:10:07.843Z
What do you mean by "symmetric random noise"?
Abhishek Singh
CC BY-SA 4.0
2020-11-19T12:13:55.553Z
The Rademacher variables are symmetric random noise: are independent and take on +/-1 with equal probability.
Aryeh
CC BY-SA 4.0
2021-01-04T16:21:09.780Z
@Aryeh How is capacity of a function class defined?
Turbo
CC BY-SA 4.0
2021-01-04T22:19:07.367Z
@1.. "capacity" is not a formally defined term and notice that I put it in quotes. Roughly speaking, it measures the ability of a function class to fit random noise. VC-dim is a worst-case measure of this, while Rademacher is more of an avergae-case measure.
Aryeh
CC BY-SA 4.0
2020-11-18T13:56:24.630Z
2020-11-18T14:04:37.517Z
2020-11-18T14:04:37.517Z
Aryeh
<p>As stated, what exactly is the intuition behind Rademacher Complexity which is defined:</p>
<blockquote>
<p>Rademacher complexity captures the richness of a family of functions by measuring the degree to which a hypothesis set can fit random noise.</p>
</blockquote>

<machine-learning>
What's the intuition behind Rademacher complexity?
Abhishek Singh
# What's the intuition behind Rademacher complexity?

(Asked by: username_0 on 2020-11-18)

As stated, what exactly is the intuition behind Rademacher Complexity which is defined:

> Rademacher complexity captures the richness of a family of functions by measuring the degree to which a hypothesis set can fit random noise.

**Tags:** machine-learning


---

## 1 answers

### Answer by username_1 on 2020-11-18. Score: 7 | Accepted answer

The standard "intuition" 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 "capacity" 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 "Massart's finite class lemma", which gives a bound for $|F|<\infty$ and is actually at the heart of more sophisticated (covering-number based) bounds.

> **Comments:**
> **username_0**: What do you mean by "symmetric random noise"?  
> **username_1**: The Rademacher variables are symmetric random noise: are independent and take on +/-1 with equal probability.  
> **username_2**: @username_1 How is capacity of a function class defined?  
> **username_1**: @1.. "capacity" is not a formally defined term and notice that I put it in quotes. Roughly speaking, it measures the ability of a function class to fit random noise. VC-dim is a worst-case measure of this, while Rademacher is more of an avergae-case measure.  

---

