Covering numbers measure metric size. In learning theory they quantify how many finite representatives are needed to approximate a loss class at a chosen accuracy.
Metric entropy
Entropy replaces an infinite class by finite nets at multiple scales.
Definition. For a metric space \((T,d)\), the covering number \(N(\varepsilon,T,d)\) is the smallest number of \(d\)-balls of radius \(\varepsilon\) needed to cover \(T\). The metric entropy is \(\log N(\varepsilon,T,d)\).
Example. The Euclidean ball \(B_2^p(R)\) satisfies \[ N(\varepsilon,B_2^p(R),\|\cdot\|_2)\le \left(1+\frac{2R}{\varepsilon}\right)^p. \] This is a volume comparison between a large ball and disjoint small balls centered at a maximal separated set.
Bracketing
For function classes, brackets often give stronger integral bounds than ordinary covers.
Definition. For functions on \((\mathcal Z,P)\), an \(L^r(P)\)-bracket \([l,u]\) is the set of \(g\) satisfying \(l\le g\le u\) and \(\|u-l\|_{L^r(P)}\le\varepsilon\). The bracketing number \(N_{[]}(\varepsilon,\mathcal G,L^r(P))\) is the minimum number of such brackets covering \(\mathcal G\).
Remark. Brackets control both approximation and order. This is why monotone and bounded-variation classes often have clean bracketing entropy bounds.
Dudley entropy integral
Chaining converts entropy at all scales into an expected supremum bound.
Theorem. For a sub-Gaussian process \((X_t:t\in T)\) with canonical metric \(d(s,t)^2=\mathbb E(X_s-X_t)^2\), \[ \mathbb E\sup_{t\in T}(X_t-X_{t_0}) \le C\int_0^{\operatorname{diam}(T)}\sqrt{\log N(\varepsilon,T,d)}\,\mathrm{d}\varepsilon. \]
Proof. Choose nested \(2^{-k}\)-nets and write each \(X_t-X_{t_0}\) as a telescoping sum of increments between successive net projections. At each scale, the maximum over finitely many sub-Gaussian increments is bounded by the scale times the square root of the log covering number. Summing over scales and passing to the integral gives Dudley's bound.
Entropy and uniform convergence
Entropy bounds become learning bounds after applying them to the loss class.
Proposition. If \(\mathcal G\) is uniformly bounded and \[ \int_0^1\sqrt{\log N(\varepsilon,\mathcal G,L^2(P_n))}\,\mathrm{d}\varepsilon \] is bounded in probability, then \(\mathcal G\) has controlled Rademacher complexity and hence uniform deviations of order \(n^{-1/2}\) up to the entropy integral.
Proof. Conditional on the data, the Rademacher process indexed by \(\mathcal G\) is sub-Gaussian under the empirical \(L^2(P_n)\) metric. Dudley's bound controls its expected supremum. Symmetrization then transfers this control to \(\sup_g|(P_n-P)g|\).
Packing numbers and maximal separated sets
Definition. The packing number \(M(\varepsilon,T,d)\) is the largest cardinality of an \(\varepsilon\)-separated subset of \(T\).
Proposition. For every metric space, \[ M(2\varepsilon,T,d)\le N(\varepsilon,T,d) \le M(\varepsilon,T,d). \]
Proof. An \(\varepsilon\)-ball contains at most one member of a \(2\varepsilon\)-separated set, proving the first inequality. A maximal \(\varepsilon\)-separated set must be an \(\varepsilon\)-net; otherwise one could add a point farther than \(\varepsilon\) from every selected point. Its cardinality therefore upper-bounds the minimum covering size.
Volumetric entropy in finite dimensions
Theorem. If \(B\) is the unit ball of any norm on \(\mathbb R^p\), then for \(0<\varepsilon\le1\), \[ N(\varepsilon,B,\|\cdot\|)\le(1+2/\varepsilon)^p. \]
Proof. Take a maximal \(\varepsilon\)-separated set \(x_1,\ldots,x_M\subset B\). The translates \(x_j+(\varepsilon/2)B\) are disjoint and lie in \((1+\varepsilon/2)B\). Lebesgue volume scales as the \(p\)th power, so \[ M(\varepsilon/2)^p\operatorname{vol}(B) \le(1+\varepsilon/2)^p\operatorname{vol}(B). \] Rearranging gives \(M\le(1+2/\varepsilon)^p\), and maximality makes the centers an \(\varepsilon\)-cover.
Chaining rather than a single net
A one-scale union bound approximates each \(t\in T\) by one net point and pays both an approximation error and a maximal deviation over the net. Chaining repeats this at geometrically decreasing scales, so fine-scale increments pay only their correspondingly small diameter.
Theorem. Let \[ X_g=\frac1n\sum_{i=1}^n\varepsilon_i g(Z_i), \qquad d_n(g,h)=\left\{\frac1n\sum_{i=1}^n(g(Z_i)-h(Z_i))^2\right\}^{1/2}. \] Conditional on \(Z_1,\ldots,Z_n\), for every \(\alpha>0\), \[ \widehat{\mathfrak R}_n(\mathcal G) \le4\alpha+ \frac{12}{\sqrt n} \int_\alpha^{\operatorname{diam}(\mathcal G,d_n)/2} \sqrt{\log N(\varepsilon,\mathcal G,d_n)}\,\mathrm{d}\varepsilon. \]
Proof outline. Choose minimal nets at scales \(2^{-k}\) down to \(\alpha\), and represent each \(g\) by the telescoping sum of its successive projections. Rademacher increments are sub-Gaussian with standard deviation \(d_n(g,h)/\sqrt n\). Massart's finite-class lemma controls the maximum at each scale by \(2^{-k}\sqrt{\log N(2^{-k})/n}\). Sum the scales, compare the Riemann sum with the integral, and bound the unresolved final increment by \(4\alpha\).
Polynomial and logarithmic entropy regimes
Proposition. Suppose \(\log N(\varepsilon,\mathcal G,L^2(P_n))\le C\varepsilon^{-q}\) for \(0<\varepsilon\le1\), and the envelope is bounded. Dudley's bound gives the following characteristic scales: \[ \widehat{\mathfrak R}_n(\mathcal G)\lesssim \begin{cases} n^{-1/2},&q<2,\\ n^{-1/2}\log n,&q=2,\\ n^{-1/q},&q>2, \end{cases} \] up to constants and possible logarithmic refinements.
Proof. Insert the entropy bound into the truncated integral: \[ \alpha+\frac{C'}{\sqrt n}\int_\alpha^1 \varepsilon^{-q/2}\,\mathrm{d}\varepsilon. \] The integral is finite at zero when \(q<2\); logarithmic at \(q=2\); and of order \(\alpha^{1-q/2}\) when \(q>2\). In the last case, balancing with \(\alpha\) gives \(\alpha\asymp n^{-1/q}\).
Entropy of smooth function classes
Theorem. Let \(\mathcal H^s(L)\) be a Hölder ball of smoothness \(s>0\) on \([0,1]^d\), uniformly bounded by \(L\). Then \[ \log N(\varepsilon,\mathcal H^s(L),\|\cdot\|_\infty) \asymp \varepsilon^{-d/s} \] as \(\varepsilon\downarrow0\), up to constants depending on \(d,s,L\).
Proof outline. For the upper bound, partition the domain into cubes of side length \(h\asymp\varepsilon^{1/s}\), approximate each function by local Taylor polynomials, and quantize the finitely many coefficients consistently with Hölder constraints. The number of cubes is \(h^{-d}\asymp\varepsilon^{-d/s}\), producing exponential covering size. For the lower bound, place disjoint smooth bumps of width \(h\) and amplitude \(h^s\), choose their signs independently, and use a Varshamov-Gilbert subset. Distinct sign patterns are separated in sup norm by a constant times \(\varepsilon\).
Bracketing laws of large numbers and central limits
Theorem. If an integrable envelope exists and \(N_{[]}(\varepsilon,\mathcal G,L^1(P))<\infty\) for every \(\varepsilon>0\), then \(\mathcal G\) is \(P\)-Glivenko-Cantelli. If a square-integrable envelope exists and \[ \int_0^1\sqrt{\log N_{[]}(\varepsilon\|F\|_{P,2}, \mathcal G,L^2(P))}\,\mathrm{d}\varepsilon<\infty, \] then, under standard measurability conditions, \(\mathcal G\) is \(P\)-Donsker.
Proof outline. A finite \(L^1\)-bracketing cover reduces the uniform law to finitely many endpoint laws plus bracket widths. For the central limit theorem, bracketing entropy controls asymptotic equicontinuity of the empirical process through a maximal inequality; finite-dimensional convergence follows from the multivariate central limit theorem. Tightness and finite-dimensional convergence yield weak convergence in \(\ell^\infty(\mathcal G)\).
Sudakov lower bound
Theorem. For a centered Gaussian process \((X_t)_{t\in T}\) with canonical metric \(d\), \[ \mathbb E\sup_{t\in T}X_t \ge c\,\varepsilon\sqrt{\log M(\varepsilon,T,d)} \quad\text{for every }\varepsilon>0. \]
Proof outline. Restrict the process to a maximal \(\varepsilon\)-packing. Gaussian comparison reduces to the maximum of nearly independent normal variables whose pairwise increment variances are at least \(\varepsilon^2\). The expected maximum of \(M\) such variables is of order \(\varepsilon\sqrt{\log M}\). Thus large entropy is not merely an artifact of Dudley's upper bound; it forces a large stochastic supremum.
For full empirical-process versions of these results, including outer probability and asymptotic equicontinuity, see covering and bracketing numbers and the following entropy chapters.