Excess-Risk Bounds for Neural Empirical Risk Minimizers

From Empirical Fit to Population Risk

A neural network can achieve a small loss on its training sample without having small expected loss on new observations. The key question is not whether empirical risk minimization (ERM) selects the lowest training risk in the chosen class; it is how far the empirical risks of that class can be from their population risks. A uniform deviation bound answers this question by controlling the discrepancy for every network in the class at once. Once that discrepancy is controlled, a short comparison shows what ERM guarantees.

Let \((X_i,Y_i)_{i=1}^n\) be independent and identically distributed observations with the same distribution as \((X,Y)\). Let \(\mathcal F\) be a fixed class of neural-network predictors, and let \(\ell(f(X),Y)\) be a measurable loss taking values in \([0,1]\). The bounded-loss assumption is used for the concentration result below; it is not automatic for every regression loss.

For a potentially infinite class, assume the supremum defining \(\Delta_n\) is measurable and the selected minimizer is measurable. Alternatively, the statements below can be read on events where these quantities are well-defined. The central result is deterministic: whenever the uniform deviation is small, empirical minimization is close to optimal in population risk.

The Basic Excess-Risk Inequality

Proof. Write \(R_{\mathcal F}=\inf_{f\in\mathcal F}R(f)\). For any \(g\in\mathcal F\), the uniform deviation condition gives \(R(\hat f)\leq R_n(\hat f)+\varepsilon\) and \(R_n(g)\leq R(g)+\varepsilon\). The approximate minimization property then yields $$ R(\hat f) \leq R_n(\hat f)+\varepsilon \leq R_n(g)+\eta+\varepsilon \leq R(g)+\eta+2\varepsilon. $$ This inequality holds for every \(g\in\mathcal F\). Taking the infimum over \(g\) proves \(R(\hat f)\leq R_{\mathcal F}+\eta+2\varepsilon\), as required. \(\square\)

The two deviation terms arise from two separate comparisons: one compares the selected network’s population risk with its empirical risk, and the other compares a population competitor with its empirical risk. The middle comparison is exactly where ERM is used. Thus the factor of two does not assert that the training risk itself is twice as large; it reflects the two sides of the empirical comparison.

A High-Probability Bound for a Finite Class

The preceding theorem reduces the learning question to controlling \(\Delta_n\). A simple explicit control is available when the predictor class has finitely many distinct predictors. For each fixed \(f\), the sample losses are independent, identically distributed, and lie in \([0,1]\). Hoeffding’s inequality states that for independent random variables in an interval of length one, the probability that their sample mean differs from its expectation by more than \(t>0\) is at most \(2\exp(-2nt^2)\).

Derivation. For each fixed \(f\), apply Hoeffding’s inequality to the \(n\) losses \(\ell(f(X_i),Y_i)\). This gives $$ P\bigl(|R_n(f)-R(f)|>t\bigr)\leq 2\exp(-2nt^2). $$ If \(\Delta_n>t\), at least one of the \(M\) predictors has deviation greater than \(t\). The union bound therefore gives $$ P(\Delta_n>t)\leq 2M\exp(-2nt^2). $$ Choose \(t=\sqrt{\log(2M/\delta)/(2n)}\). Then \(2M\exp(-2nt^2)=\delta\), so the asserted probability bound for \(\Delta_n\) follows. Applying the basic excess-risk inequality on that event proves the second claim. \(\square\)

This finite-class result is not, by itself, a bound for every neural-network class: a class with continuously varying parameters can contain infinitely many distinct predictors. The ERM inequality still applies to such classes whenever a suitable uniform deviation bound is available. The particular complexity measure or argument needed to obtain that bound is a separate question.

Realizability and Misspecification

A bound relative to the best network in \(\mathcal F\) does not by itself say how good that network is for the prediction problem. To make this distinction precise, let \(\mathcal G\) be the larger set of admissible measurable predictors for the problem, and define the unrestricted optimal risk \(R_*=\inf_{g\in\mathcal G}R(g)\). Since \(\mathcal F\subseteq\mathcal G\), the approximation error $$ A_{\mathcal F}=\inf_{f\in\mathcal F}R(f)-R_* $$ is nonnegative. Adding and subtracting \(\inf_{f\in\mathcal F}R(f)\) gives the decomposition $$ R(\hat f)-R_* = \left(R(\hat f)-\inf_{f\in\mathcal F}R(f)\right)+A_{\mathcal F}. $$ Therefore, on the event \(\Delta_n\leq\varepsilon\), $$ R(\hat f)-R_*\leq A_{\mathcal F}+2\varepsilon+\eta. $$ The first term is a limitation of the chosen class; the other terms arise from empirical selection and, if applicable, inexact minimization.

These terms describe the approximation part of the problem, not the sample’s uniform deviation. Under either form of well-specification, \(A_{\mathcal F}=0\), so a deviation bound controls risk relative to the unrestricted optimum. Under misspecification, increasing the sample size can reduce the deviation term but cannot remove a positive approximation error for a fixed class.

What the Bound Does—and Does Not—Guarantee

The excess-risk inequality is useful because it isolates the job of a generalization argument: establish that empirical and population risks are uniformly close over the candidate class. But the inequality does not establish that closeness on its own, and a small training risk is not evidence of small population risk unless some control of the discrepancy is justified. In addition, the finite-class concentration result depends on bounded loss and a finite number of predictors; changing either assumption requires a corresponding concentration argument.

A common mistake is to reason that because \(\hat f\) minimizes empirical risk, it must minimize population risk. That replaces \(R_n\) by \(R\) without justification. The correct comparison inserts the uniform deviation on both sides of the ERM comparison, producing the \(2\Delta_n\) term. A second mistake is to call any small excess risk evidence that the network class is adequate. The bound relative to the class optimum can be small even when \(A_{\mathcal F}\) is large; assessing risk relative to the unrestricted optimum requires accounting for approximation error too.