Fixed-Predictor Risk Guarantees Under Bounded Loss

From Observed Losses to Population Risk

A predictor’s performance on a sample is not its performance on the population that generated the sample. The empirical risk is calculated from observed cases and is therefore random before the sample is drawn. The population risk is the predictor’s expected loss under the population distribution. A concentration guarantee quantifies how far these two quantities can differ for one predictor fixed in advance.

This distinction is useful whenever a predictor is evaluated on an independent sample and its loss is bounded. It lets us state, for example, how many observations are needed to make the empirical risk a reliable approximation to population risk. The guarantee concerns repeated samples from the population; it does not make the population risk itself random.

The predictor \(h\) is held fixed in this definition: it is not chosen after inspecting the sample used to calculate \(\widehat R_n(h)\). The observed losses \(W_i=\ell(h(X_i),Y_i)\) are independent, identically distributed random variables in \([0,1]\). Each has expectation \(R(h)\), so \(E[\widehat R_n(h)]=R(h)\). That equality is an expectation statement; a concentration inequality adds a probability bound on the size of the discrepancy.

Hoeffding’s Risk Guarantee

Hoeffding’s inequality for independent bounded averages gives, for independent random variables \(W_i\in[a_i,b_i]\), an exponential bound on the deviation of their average from its expectation. Here each \(W_i\) lies in \([0,1]\), and all have mean \(R(h)\). Applying the inequality to these losses gives the fixed-predictor risk guarantee below.

To see the application, set \(W_i=\ell(h(X_i),Y_i)\). Then \(E[W_i]=R(h)\) and \(\widehat R_n(h)=n^{-1}\sum_i W_i\). The one-sided inequalities are Hoeffding’s inequality applied to the upper and lower deviations of this average. The two-sided statement follows because the event that the absolute deviation is at least \(\varepsilon\) is contained in the union of the upper- and lower-deviation events. Adding their probability bounds gives \(e^{-2n\varepsilon^2}+e^{-2n\varepsilon^2}=2e^{-2n\varepsilon^2}\).

Inverting the Bound for a Confidence Statement

In applications, a tolerance \(\varepsilon\) is often chosen from a desired failure probability \(\delta\), where \(0<\delta<1\). Solving the one-sided inequality for \(\varepsilon\) gives an upper confidence bound on population risk. Solving the two-sided inequality gives an interval around empirical risk.

For the one-sided statement, choose \(\varepsilon=\sqrt{\log(1/\delta)/(2n)}\). Then \(e^{-2n\varepsilon^2}=\delta\), so the probability that \(R(h)-\widehat R_n(h)\geq\varepsilon\) is at most \(\delta\). Outside that event, \(R(h)<\widehat R_n(h)+\varepsilon\), which implies the displayed weak inequality. For the two-sided statement, choose \(\varepsilon=\sqrt{\log(2/\delta)/(2n)}\). The two-sided tail bound becomes \(2e^{-2n\varepsilon^2}=\delta\); outside the deviation event, the absolute difference is at most \(\varepsilon\). These probabilities are over the random sample.

Since a loss in \([0,1]\) also implies \(0\leq R(h)\leq1\), an upper bound greater than 1 can be replaced by 1, and an interval can be intersected with \([0,1]\). This clipping preserves coverage and may make the reported range more informative.

Worked Risk Calculations

What the Guarantee Does and Does Not Say

The radius \(\sqrt{\log(1/\delta)/(2n)}\) decreases as the sample size increases and increases as the requested failure probability decreases. It does not depend on the form of the loss distribution beyond its range. That distribution-free property is useful when little is known about the losses, but it can also make the bound conservative.

The scope of the statement is just as important as its formula. It guarantees concentration for one predictor fixed independently of the observations used to evaluate it. If a predictor is chosen after looking at those same observations, the selected predictor may have unusually small empirical risk precisely because it fits random features of the sample. The fixed-predictor guarantee alone does not establish the same coverage for such a data-selected predictor.

A second point of interpretation is that the confidence statement is not a probability distribution for \(R(h)\). For a fixed population and fixed predictor, \(R(h)\) is a fixed number. The random object is the sample, and the statement says that the stated inequality holds for at least a specified fraction of repeated samples.