Uniform Concentration Over a Finite Function Class

From Pointwise Accuracy to Uniform Accuracy

Suppose a statistician considers several possible functions of the same observations. A concentration inequality for one fixed function controls its empirical average, but it does not by itself guarantee that all the functions are accurate at once. The distinction matters whenever a function is selected after examining the data: a pointwise guarantee for a function chosen in advance need not apply to the selected one.

For a finite class, a direct route to simultaneous control is to apply a pointwise Hoeffding bound to each function and then use the union bound. The resulting guarantee reveals how the size of the class affects the deviation threshold. No independence between the different functions’ empirical averages is needed; they may all be computed from the same sample.

Empirical Averages and Uniform Deviation

The class \(\mathcal{F}\) is fixed independently of the observations. Assume each \(f\in\mathcal{F}\) is bounded, with deterministic bounds \(a_f\leq f(z)\leq b_f\) almost surely under \(P\), and write \(c_f=b_f-a_f\) for its range width. The bounds may differ from one function to another.

For one fixed function, Hoeffding’s inequality gives an exponential tail bound for its empirical average. The uniform result below combines those pointwise guarantees. Its cost depends on the number of functions because a larger class creates more opportunities for at least one deviation to be large.

The Finite-Class Hoeffding Bound

The factor \(2\) accounts for deviations in either direction, and \(M\) counts the functions when a common range width is used. The displayed upper bound is valid even if its numerical value exceeds one; in that case it can be replaced by the trivial probability bound \(1\).

Proof. For each \(f\in\mathcal{F}\) with \(c_f>0\), Hoeffding’s inequality for independent bounded variables gives

If \(c_f=0\), then \(f(Z_i)=a_f\) almost surely for every \(i\), so \(P_n f=Pf=a_f\) almost surely. Now the event that the maximum deviation is at least \(\varepsilon\) is the union of the events \(\{|P_n f-Pf|\geq\varepsilon\}\) over \(f\in\mathcal{F}\). By the union bound, its probability is at most the sum of their probabilities. Substituting the pointwise bounds gives the claimed inequality. If all widths equal \(c\), the sum has \(M\) terms, each bounded by \(2\exp(-2n\varepsilon^2/c^2)\), which gives the common-width result. \(\square\)

Choosing a Threshold for a Desired Guarantee

The common-width inequality can be rearranged to give a deviation threshold for a specified failure probability. If all functions take values in an interval of width \(c>0\), then for any \(0<\delta<1\),

Indeed, substituting \(\varepsilon=c\sqrt{\log(2M/\delta)/(2n)}\) into the bound makes its right-hand side \(2M\exp[-\log(2M/\delta)]=\delta\). The threshold grows with the logarithm of the class size, rather than linearly with that size. Increasing the sample size reduces the threshold at the rate \(n^{-1/2}\).

Different Range Widths and Interpretation

When the functions have substantially different ranges, retaining the individual widths can sharpen the result. A function with a narrow range has a stronger pointwise Hoeffding bound at the same \(\varepsilon\), and the theorem sums these separate bounds rather than replacing all widths by the largest one. This refinement is useful only when the actual deterministic range widths are known.

Why the Union Bound Works—and Its Limits

The empirical averages for different functions are generally dependent because they are calculated from the same observations. That dependence does not obstruct this argument: the union bound applies to any finite collection of events, whether independent or not. What matters for the pointwise Hoeffding step is that, for each fixed function, the observations \(f(Z_1),\ldots,f(Z_n)\) are independent and bounded.

The theorem controls a maximum over a class fixed in advance. If the class itself is selected using the observed data, it is not automatically a fixed finite class to which this result applies. One safe use of the theorem is to choose a function from a fixed finite class after seeing the data: on the event that every function in the class is within \(\varepsilon\) of its expectation, the selected function is too. The class-size factor pays for this simultaneous guarantee.

Common Mistake

A frequent error is to quote the pointwise Hoeffding bound for one function and then claim the same failure probability for the maximum over \(M\) functions. The event that some function has a large deviation contains each individual deviation event, so its probability generally needs to account for all \(M\) possibilities. Applying the union bound introduces the factor \(M\) (and the factor \(2\) for two-sided deviations). Omitting these factors does not establish a simultaneous guarantee.