covering numbers and metric entropy

A function class can be infinite, yet at a given resolution only finitely many genuinely different functions matter. Picture placing balls of radius epsilon so that every function in the class sits within epsilon of some ball's center; the covering number is the fewest centers you need, and its logarithm is the metric entropy. It is a resolution-dependent count of the class's effective size: coarse resolution, few representatives; fine resolution, many.

Given a metric, often the empirical distance on a sample, the covering number is the minimal cardinality of an epsilon-net and its logarithm is the metric entropy. These feed generalization in two ways. A simple discretization plus union bound gives a bound at a single scale; far sharper is Dudley's entropy integral, which sums the square root of the metric entropy over all scales to bound the Rademacher complexity, capturing the chaining intuition that fluctuations at many resolutions add up. Covering numbers also connect to VC dimension through Haussler's bound and to fat-shattering dimensions for real-valued classes.

Metric entropy is the common language linking statistics, approximation theory, and empirical process theory; its growth rate dictates minimax rates of estimation. A class whose log-covering number grows like epsilon to a negative power yields predictable convergence speeds, and that exponent often equals a smoothness-to-dimension ratio. The cost is technical: computing or bounding covering numbers for rich classes like deep networks is delicate and frequently known only up to constants or logarithms.