Covering numbers and chaining

For a fixed sample of n inputs, use the root mean square distance between prediction vectors. It is a pseudometric on functions: two different functions can have distance zero when they agree on the sample. An epsilon cover is a finite collection of representatives within epsilon of every prediction vector, and its covering number is the smallest such collection size. Here centers lie in the restricted function class and closed balls are allowed. Other conventions can change boundary counts or constants, so identify the one being used.

For constant functions with values theta between zero and one, the empirical root mean square distance is simply the absolute difference of their constants, independent of n. A radius-one-quarter cover needs only two centers, at one quarter and three quarters. One center cannot cover the entire interval because its ball has length at most one half. This small example separates the geometry of the class from the number of observed coordinates: duplicating the same constant value across more inputs does not create additional distinct parameter directions.

Choose covers at dyadically decreasing radii and associate every function with a representative at each scale. Its prediction vector can be written as a coarse representative plus successive differences, followed by a residual. Adjacent approximations are close, so their signed-sum fluctuations have smaller amplitude than the original functions even though finer covers contain more representatives. A finite-class maximal inequality applied separately to these increments yields a sum of radius-weighted square roots of log covering numbers.

Passing from that multiscale sum to an integral gives a Dudley bound. For function values in[−1,1], the displayed version bounds our conditional Rademacher average by a residual term four alpha plus twelve divided by the square root of n times an entropy integral from alpha to one. It applies under measurable or finite sample-restriction conditions. Taking alpha positive can avoid divergence at very fine scales; discarding the residual after truncation would omit the approximation error that makes the finite-resolution argument valid.

A single-scale argument often balances its cover radius against a square root of log cover size divided by n. Chaining uses all scales, which can remove an artificial logarithmic factor for classes with sufficiently mild entropy growth. Conversely, a diverging entropy integral does not prove that the class is unlearnable: truncation or a different complexity method may still yield control. The displayed constants are sufficient and can be conservative, particularly on tiny samples or very simple classes.

Covering numbers are also metric dependent. A population L2 cover and an empirical L2 cover answer different questions, and replacing the normalized distance by an unnormalized Euclidean norm changes all radii by a square-root sample-size factor. A numerical cover needs a proof that every function is represented; a scatterplot of selected parameters is not enough. The examples use constant functions precisely because the metric balls and the minimal cover count can be verified directly rather than inferred visually.