Risk, empirical risk, and excess risk

Let Z=(X,Y) have distribution P, and let a measurable loss evaluate a predictor h on an example z. The population risk is its expectation on a fresh Z. Given n independent identically distributed training examples, empirical risk averages the losses on those particular observations. For a predictor fixed before seeing the sample, empirical risk is an unbiased estimate of risk when the expectation exists. A predictor selected using the sample is random and may exploit favorable sample fluctuations, so that unbiasedness does not automatically survive selection.

To keep the probability statements below ordinary and measurable, assume finite or countable classes with measurable predictors and losses, or explicitly assume any uncountable supremum and learning rule used is measurable. The elementary uniform bounds will additionally impose bounded losses when needed. Merely writing an integral does not ensure finite risk for an unbounded loss, and a zero training error does not identify the population distribution. Evaluation on independent fresh data changes which random variables are being averaged, rather than converting the original training average into an unbiased certificate.

The best risk within a class is the infimum over that class; it need not be attained unless additional conditions provide a minimizer. The Bayes risk takes the infimum over all admissible measurable predictors. Class excess risk measures learning relative to the chosen class, while Bayes excess also includes the class’s approximation error. A constant classifier can be learned perfectly within the two constant rules and still be far worse than a rule that uses X. No amount of optimization within the constant class removes that representational limitation.

For binary zero-one loss, the Bayes rule predicts the more likely label at each input, with a fixed convention for ties. Its conditional error is the smaller of the two conditional label probabilities. This reasoning does not assume labels are deterministic. The difference between best class risk and Bayes risk is nonnegative and distribution dependent. A theorem that only compares to the class should not be advertised as recovery of the Bayes rule unless the approximation term is separately controlled, for example by a sequence of increasingly rich classes.

Suppose a realized sample satisfies a uniform deviation bound Delta across the class. Suppose the algorithm returns a predictor whose empirical risk is at most the class infimum plus an optimization tolerance eta. Add and subtract the empirical risks of the returned predictor and a comparator. Each population-to-sample difference costs at most Delta, while approximate empirical minimization costs eta. Taking comparators approaching the population infimum gives class excess at most two Delta plus eta, without assuming a population minimizer exists.

This comparison is deterministic once the sample event holds. A later concentration theorem supplies a probability for that event. The separation is useful: improving an optimizer reduces eta, restricting a class may reduce the fluctuation Delta, and enriching the class may reduce approximation error. These effects need not move in the same direction. Reporting only the smallest training loss suppresses the quantities needed to decide whether a better fit is likely to improve fresh-sample performance.