Dudley chaining

We are in the setting that was described in chaining. We are trying to obtain a maximal inequality for the sub-Gaussian process $(X_{\theta })$, $\theta \in \Theta$. Chaining gave a bound of the form

$$\mathbb{E}\underset{\theta }{\sup }{X}_{\theta }\le \underset{\theta \in \Theta }{\sup }\sum _{0\le n\le N}{2}^{n/2}\rho (\theta ,{\Theta }_n),$$

where ${\Theta }_0\subset {\Theta }_1\subset \cdots \subset {\Theta }_N=\Theta$ is a chain of sets approximating $\Theta$, where $|{\Theta }_n|\le 2^{2^n}$. The idea behind Dudley chaining is to move the supremum inside the sum. That is, we upper bound the right hand side as

$$\underset{\theta \in \Theta }{\sup }\sum _{0\le n\le N}{2}^{n/2}\rho (\theta ,{\Theta }_n)\le \sum _{0\le n\le N}{2}^{n/2}\underset{\theta \in \Theta }{\sup }\rho (\theta ,{\Theta }_n).$$

We can then take the infimum over all sets ${\Theta }_n$ of size $2^{2^n}$, which leads to Dudley’s entropy bound stated in terms of entropy numbers, which are

$$e_n(\Theta )=\underset{{\Theta }_n}{\inf }\underset{\theta }{\sup }\rho (\theta ,{\Theta }_n).$$

This method is provably loose for bounds on the Gaussian complexity. Generic chaining is tighter but can be harder to compute at times. The idea behind generic chaining is to not move the supremum inside the sum.