# Understanding Rademacher Complexity Deeply

empirical Rademacher complexity is defined as, $$\hat{R}_{m}(\mathcal{F}, S)=\frac{1}{m} \mathbb{E}_{\boldsymbol{\sigma}}\left[\sup _{f \in \mathcal{F}} \sum_{i=1}^{m} \sigma_{i} f\left(z_{i}\right)\right] .$$ Remark. We can motivate the Rademacher complexity from the binary classification. Let $$f$$ be a classification function which maps data $$z_{i}$$ to its label $$\sigma_{i} \in\{-1,1\}$$. It is straightforward to show that $$\sup _{f \in \mathcal{F}} \sum_{i}^{m} \sigma_{i} f\left(z_{i}\right)$$ is equivalent to minimizing the classification error. Taking the expectation over all $$\sigma_{i}$$ amounts to considering all possible labeling (partitioning) of the samples. If $$\mathcal{F}$$ consists of a single function $$f$$, then $$\hat{R}_{m}(\mathcal{F}, S)=0$$. If $$\mathcal{F}$$ shatters $$\left\{z_{1}, \cdots, z_{m}\right\}$$, then $$\hat{R}_{m}(\mathcal{F}, S)=1$$. Therefore, the Rademacher complexity intuitively indicates how expressive the function class is.

I am trying to understand this theorem very deeply. Unfortunately, I cannot be able to understand much from this note. Can anybody help me understand very deeply and intuitively so that I can make understand other people very easily?