I am learning the Rademacher complexity and have a question on the definition of it. Let $$\mathcal{H}$$ be a hypothesis class and $$m$$ is the number of iid samples from a distribution $$\mathcal{D}$$, say, $$S=\{x_i\}_{i=1}^m$$. Then the Rademacher complexity is defined to be $$R_s(\mathcal{H}) := \mathbb{E}_{\sigma} \sup_{h \in \mathcal{H}} \frac{1}{m}\left|\sum_{i=1}^m \sigma_i \ell(h,x_i) \right|,$$ where $$\sigma_i$$'s are iid uniform on $$\{-1, 1\}$$. It seems that the more appropreate definition should be $$\tilde{R}_s(\mathcal{H}) := \mathbb{E}_{\sigma} \sup_{h \in \mathcal{H}}\left| \frac{1}{|S_+|}\sum_{i \in S_+} \ell(h,x_i) - \frac{1}{|S_-|}\sum_{i \in S_-} \ell(h,x_i)\right|,$$ where $$S_+ = \{i \in [m] | \sigma_i = 1\}$$ and $$S_+ = \{i \in [m] | \sigma_i = -1\}$$. This is because the cross-validation should take the normalization constants into account. But I am not sure why the definition does not reflect the normalization constants.
• We don't want to fit random noise . The idea is that if we look at two families of functions , the one that can fit better random noise is richer , "more complex" . Think about two extremities : first a hypothesis class with only one function and second the set of all functions defined on the domain with values in $\{,1\}. The first class has$R_{S} = 0\$ and the second 1 (assume a suitable loss function) , .The first is as simple as we can get and the second is the most complex possible . – Popescu Claudiu Mar 26 at 18:14