Rademacher complexity

Given some parameter space $\Theta \subset {\mathbb{R}}^d$, consider $\{R_{\theta }:\theta \in \Theta \}$, where $R_{\theta }=⟨\xi ,\theta ⟩$ and ${\xi }_i$ is a Rademacher random variable (i.e., $\pm 1$ with equal probability). This process is called a Rademacher process. The expected value of the supremum of this process (see maximal inequalities),

$$\mathcal{R}(\Theta )=\mathbb{E}\underset{\theta \in \Theta }{\sup }{R}_{\theta },$$

is the Gaussian complexity of $\Theta$. Like metric entropy, it’s a measure of the size of $\Theta$. If we replace $w_i$ with Rademacher random variables, then we obtain the Gaussian complexity.

The relationship to the Gaussian complexity is $\mathcal{R}(\Theta )\le \sqrt{\frac{\pi }{2}}\mathcal{G}(\Theta )$.