Why a Fixed-Predictor Bound Is Not Enough
A risk guarantee for one predictor controls its empirical risk relative to its population risk. But learning procedures usually compare several predictors and may select one after seeing the sample. A bound that holds separately for each predictor does not, by itself, say that all the bounds hold at once. The finite-grid argument addresses this gap: it combines individual concentration bounds to control the largest deviation over a prespecified finite collection.
This distinction matters because selection can favor a predictor whose empirical risk happens to be unusually low. A simultaneous guarantee accounts for that search over the collection. Its cost is visible in the bound through the number of predictors.
Setup and Simultaneous Guarantee
\(R(h)=E[\mathcal{L}(h,Z)]\), \(\qquad \widehat R_n(h)=\frac{1}{n}\sum_{i=1}^n\mathcal{L}(h,Z_i).\)
For each fixed \(h\), the losses \(\mathcal{L}(h,Z_i)\) are independent, identically distributed, and bounded in \([0,1]\). Hoeffding’s inequality therefore gives \(P(|\widehat R_n(h)-R(h)|>\epsilon)\leq 2\exp(-2n\epsilon^2)\). The finite-grid result follows by bounding the probability that this deviation occurs for at least one predictor.
\(P\!\left(\max_{h\in\mathcal{H}}|\widehat R_n(h)-R(h)|>\epsilon\right)\leq 2M\exp(-2n\epsilon^2).\)
Consequently, for any \(0<\delta<1\), with probability at least \(1-\delta\),
\(\max_{h\in\mathcal{H}}|\widehat R_n(h)-R(h)|\leq \sqrt{\frac{\log(2M/\delta)}{2n}}.\)
The logarithm is natural. For a loss bounded in an interval \([a,b]\) of width \(b-a\), replace \(\epsilon\) in the exponential by \(\epsilon/(b-a)\). The resulting confidence threshold is \((b-a)\sqrt{\log(2M/\delta)/(2n)}\).
Proof of the Finite-Grid Bound
For each \(h\in\mathcal{H}\), define the deviation event \(A_h=\{|\widehat R_n(h)-R(h)|>\epsilon\}\). The event that at least one predictor has a deviation larger than \(\epsilon\) is the union of these events. The union bound applies whether or not the events are independent.
For each fixed \(h\), boundedness and independence of the observations give \(P(A_h)\leq 2\exp(-2n\epsilon^2)\) by Hoeffding’s inequality.
Since \(\mathcal{H}\) has \(M\) elements, the union bound yields \(P(\bigcup_{h\in\mathcal{H}}A_h)\leq\sum_{h\in\mathcal{H}}P(A_h)\leq 2M\exp(-2n\epsilon^2)\). The event on the left is exactly that the maximum deviation exceeds \(\epsilon\).
Set \(2M\exp(-2n\epsilon^2)=\delta\). Taking logarithms and rearranging gives \(\epsilon=\sqrt{\log(2M/\delta)/(2n)}\). Thus the probability of exceeding this threshold is at most \(\delta\), proving the stated confidence guarantee. \(\square\)
The proof does not assume that the empirical risks for different predictors are independent. They are often dependent because every predictor is evaluated on the same observations. The union bound needs only the individual event probabilities and the fact that there are finitely many events.
Worked Risk and Sample-Size Calculations
Worked Example: Three Predictors and a 95% Guarantee
Suppose a prespecified collection contains \(M=3\) predictors, the sample size is \(n=1000\), and the desired confidence level is \(1-\delta=0.95\). The simultaneous deviation threshold is
Here \(2M/\delta=2(3)/0.05=120\). Thus, with probability at least \(0.95\), all three predictors have empirical risk within about \(0.0489\) of their population risks. If one of these three predictors is selected using the sample, the same event still controls its deviation, because the event controls every member of the collection simultaneously.
If the selected predictor is an empirical risk minimizer, the corresponding excess-risk bound below is \(2\epsilon\). Using the unrounded threshold,
The doubling is important: the empirical minimizer can have both a downward deviation in its own risk estimate and an upward deviation for the best predictor in the collection.
Worked Example: Required Sample Size
How many observations suffice to make every empirical risk in a prespecified set of \(M=20\) predictors accurate to within \(\epsilon=0.05\), with probability at least \(0.99\)? Here \(\delta=0.01\). Starting from the theorem’s tail bound, require
Taking logarithms and solving for \(n\) gives
The sample size must be an integer, so \(n=1659\) suffices. Rounding down to 1658 would not meet the displayed requirement. The calculation controls all 20 deviations together; it is not a separate 99% guarantee that must somehow be informally extended to the other predictors.
Worked Example: The Cost of a Larger Collection
Compare collections of \(M=10\) and \(M=1000\) predictors, using the same sample size \(n=5000\) and confidence level \(1-\delta=0.95\). For \(M=10\), the simultaneous threshold is
For \(M=1000\), it becomes
The larger grid increases the threshold because the bound must cover more possible deviations. The increase is logarithmic in \(M\), not proportional to \(M\), but it is still relevant when interpreting a guarantee. These are upper bounds from Hoeffding’s inequality and the union bound, not claims that the actual deviations equal the thresholds.
Consequence for Empirical Risk Minimization
A useful application is to a predictor chosen to minimize empirical risk over the finite grid. Define \(\widehat h\in\mathcal{H}\) to satisfy \(\widehat R_n(\widehat h)=\min_{h\in\mathcal{H}}\widehat R_n(h)\), with any rule for breaking ties. Since \(\mathcal{H}\) is finite, a population-risk minimizer \(h^*\in\arg\min_{h\in\mathcal{H}}R(h)\) also exists.
\(R(\widehat h)-R(h^*)\leq 2\sqrt{\frac{\log(2M/\delta)}{2n}}.\)
To prove this, let \(D=\max_{h\in\mathcal{H}}|\widehat R_n(h)-R(h)|\). On the event \(D\leq\epsilon\), insert empirical risks between the two population risks. The middle inequality follows from the definition of \(\widehat h\):
The finite-grid theorem says that \(D\leq\sqrt{\log(2M/\delta)/(2n)}\) with probability at least \(1-\delta\). Substituting this threshold proves the corollary. \(\square\)
This is an excess-risk guarantee relative to the best predictor in \(\mathcal{H}\), not necessarily relative to the best possible predictor outside the grid. The bound separates two issues: how well the empirical minimizer performs compared with the grid’s best member, and whether the grid itself contains a predictor suitable for the application.
What the Guarantee Does and Does Not Cover
The collection must be specified independently of the sample for the stated argument to apply directly. Once a fixed finite collection is chosen, a data-dependent choice among its members is allowed: simultaneous control is precisely what makes that selection safe under this bound. In contrast, if the collection is built or expanded after inspecting the same observations, the fixed-collection union calculation does not automatically cover the resulting search. One cannot simply count the final candidates while ignoring how they were generated.
A common mistake is to reason, “Each predictor has a high-probability bound, so the predictor selected by empirical risk minimization has that bound too.” The gap is that the selected predictor is random and may be the one with the most favorable empirical fluctuation. The correction is to bound the probability of any failure across the whole prespecified collection, then use that single simultaneous event for the selected predictor. The factor \(M\) in the union bound pays for this protection.
Another mistake is to assume independence across predictors is needed for the union bound. It is not: the proof only uses \(P(\bigcup_h A_h)\leq\sum_h P(A_h)\). Independence of the observations is needed for each fixed predictor’s Hoeffding bound, but the events \(A_h\) may be strongly dependent.
Check Your Understanding
Use the assumptions and results above to answer these questions.
- Why does a union bound remain valid even when all predictors are evaluated on the same observations?
- For a finite collection with \(M=5\), what expression gives the deviation threshold at confidence level \(1-\delta\) and sample size \(n\)?
- What condition on the predictor collection is needed for the stated finite-grid guarantee to apply directly?
- Why does the empirical risk minimization corollary contain \(2\epsilon\), rather than \(\epsilon\)?
- Does the corollary compare the selected predictor with the best predictor over all possible predictors, or only with the best member of \(\mathcal{H}\)?