Gaussian complexity

Given some parameter space $\Theta \subset {\mathbb{R}}^d$, consider $\{G_{\theta }:\theta \in \Theta \}$, where

$$G_{\theta }=⟨w,\theta ⟩,w_i\sim N(0,1).$$

This is called a canonical Gaussian process. The expected value of the supremum of this process (see maximal inequalities),

$$\mathcal{G}(\Theta )=\mathbb{E}\underset{\theta \in \Theta }{\sup }{G}_{\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 Rademacher complexity.

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