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?



You must log in to answer this question.

Browse other questions tagged .