Rademacher Complexity

Given a set system \((X,\mathcal{H})\) i.e. a set \(X\) and a class \(\mathcal{H}\) of subsets of \(X\) and \(S=\{x_1,\cdots,x_n\} \subset X\), the (empirical) Rademacher complexity of \(\mathcal{H}\) is defined as \[ R_S(\mathcal{H}) = \frac{1}{n}\mathbb{E}_{\sigma_1,\cdots,\sigma_n}[\max_{h\in \mathcal{H}}\sum_{i=1}^n\sigma_i h(x_i)]\] Where \(\sigma_i\) are Rademacher random variables i.e. take values in 1,-1 with equal probability.