entropy number

Definition

Let $(\Theta ,\rho )$ be a metric space. The entropy number of $\Theta$ with respect to $\rho$ is

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

where the infimum is taken over all subset ${\Theta }_n$ of $\Theta$ subject to a cardinality constraint $N_n$ (usually $N_n=2^{2^n}$ in the case of Dudley chaining).

Entropy numbers show up when proving maximal inequalities via chaining-type arguments. Dudley’s entropy bound can be expressed in terms of entropy numbers.

They are related to covering numbers (covering and packing) via the formula

$$e_n(\Theta )=\inf \{ϵ>0:N(\Theta ,\rho ,ϵ)\le N_n\}.$$

That is, they are the minimum width $ϵ$ required to cover $\Theta$ in balls of width $ϵ$. Entropy numbers are equivalent to the metric entropy of $\Theta$ in the sense that

$$\sum _{n\ge 0}{2}^{n/2}{e}_n(\Theta )\asymp {\int }_0^{\infty }\sqrt{\log N(\Theta ;\rho ,ϵ)}\text{d}ϵ,$$

which is what yields the equivalence between the two forms of Dudley’s entropy bound.