Separating Optimization Error in Neural Risk Bounds

Why Separate the Sources of Error?

A trained neural predictor can have poor population performance for several different reasons. The chosen architecture may not represent a good predictor; the sample may make empirical performance differ from population performance; or the training algorithm may not find a predictor with nearly minimal empirical risk. A useful risk bound distinguishes these mechanisms rather than combining them into an unexplained remainder.

This separation is especially important when optimization is approximate. A method may return a predictor that is not an empirical risk minimizer, yet is close to one. The resulting population guarantee should account explicitly for that gap, alongside the generalization and approximation terms.

Risks and the Three Error Terms

Let \(Z_1,\ldots,Z_n\) be independent and identically distributed observations from a distribution \(P\). A predictor \(f\) incurs loss \(\ell_f(Z)\), where the loss is measurable and has finite expectation. Its population risk and empirical risk are

Let \(\mathcal F\) be a nonempty class of measurable predictors, such as neural networks with a specified architecture and parameter constraints. Define the best achievable population risk over all admissible predictors as \(\mathcal R^*=\inf_{f\in\mathcal G}\mathcal R(f)\), where \(\mathcal G\) is the larger benchmark class containing \(\mathcal F\). The class’s approximation error is the gap between its best population risk and this benchmark.

The approximation error is nonnegative because \(\mathcal F\subseteq\mathcal G\). The optimization error is also nonnegative by its definition. It measures how far the algorithm’s output is from the best empirical risk available within the chosen class, not how far that class is from the population benchmark. The deviation \(\Delta_n\) is uniform: it controls the population-to-empirical discrepancy for every member of \(\mathcal F\), including a predictor selected after seeing the sample.

The Basic Excess-Risk Bound

The central result is deterministic once a uniform deviation bound holds. No convexity, differentiability, or existence of an exact empirical minimizer is required. The output only needs to lie in the class and have a stated empirical suboptimality.

Proof. For any \(f\in\mathcal F\), the definition of \(\Delta_n\) implies \(\mathcal R(f)\leq\widehat{\mathcal R}_n(f)+\delta\). Apply this first to \(\widehat f\), then use its empirical suboptimality:

For each \(f\in\mathcal F\), the other direction of the same uniform bound gives \(\widehat{\mathcal R}_n(f)\leq\mathcal R(f)+\delta\). Taking infima preserves this inequality, so

Combining the last two displays yields \(\mathcal R(\widehat f)\leq\inf_{f\in\mathcal F}\mathcal R(f)+\epsilon+2\delta\). Subtract \(\mathcal R^*\) and use the definition of \(\mathcal A(\mathcal F)\). This proves the result. \(\square\)

The two deviation terms arise at two distinct comparisons: first, from the returned predictor’s empirical risk to its population risk; second, from the class’s best empirical risk to its best population risk. In applications, a sharper analysis may sometimes control these comparisons differently, but the displayed inequality requires only one uniform deviation bound.

Obtaining a Uniform Deviation Bound

The deterministic theorem separates the terms but does not itself guarantee that \(\Delta_n\) is small. That step requires assumptions on the loss and predictor class. For a finite class and bounded loss, the preceding calculation gives a simple high-probability result.

Proof. Fix \(f\in\mathcal F\). Its losses \(\ell_f(Z_i)\) are independent, identically distributed, and lie in \([0,1]\). Hoeffding’s inequality, applied to their sample mean, gives \(P(|\widehat{\mathcal R}_n(f)-\mathcal R(f)|>t)\leq2e^{-2nt^2}\). The event \(\{\Delta_n>t\}\) is the union, over all \(M\) predictors, of the events that the corresponding absolute deviation exceeds \(t\). The union bound therefore implies

Set \(t=\sqrt{\log(2M/\eta)/(2n)}\). Then \(e^{-2nt^2}=e^{-\log(2M/\eta)}=\eta/(2M)\), so \(P(\Delta_n>t)\leq\eta\). Equivalently, \(P(\Delta_n\leq t)\geq1-\eta\), as claimed. \(\square\)

Combining this theorem with the basic excess-risk bound gives, under its assumptions, a probability-\(1-\eta\) guarantee of \(\mathcal R(\widehat f)-\mathcal R^*\leq\mathcal A(\mathcal F)+2\sqrt{\log(2M/\eta)/(2n)}+\epsilon\). For large or infinite neural classes, a different valid uniform generalization bound may be used in place of this finite-class expression. The deterministic decomposition remains the same; only the way \(\delta\) is established changes.

Interpreting the Bound and Avoiding a Common Pitfall

The decomposition is useful because the three terms suggest different questions about a trained neural estimator. Is the architecture expressive enough for the target, making \(\mathcal A(\mathcal F)\) small? Does the available sample and class complexity support a sufficiently small uniform deviation? Did the training procedure reduce empirical risk close enough to the class infimum? A small value for one term cannot compensate for an uncontrolled value in another.

Common mistake: treating empirical optimization as a population guarantee. It is incorrect to argue that a small empirical risk, or successful convergence of an optimizer, by itself implies small population excess risk. The empirical risk is calculated on the observed sample, and its difference from population risk must still be controlled; moreover, a class may have a nonzero approximation gap. The correction is to establish a population-to-empirical deviation bound and account for the benchmark approximation error, while recording any empirical suboptimality separately.

The bound also clarifies why optimization error should not be silently folded into a generalization term. A generalization statement concerns the relationship between empirical and population risk. Optimization error concerns the empirical objective’s minimization within the selected class. Keeping their roles distinct makes the assumptions, calculations, and possible remedies easier to assess.