Oracle Inequalities for Penalized Neural Risk Minimization

Why Penalize Neural Risk Minimization?

A neural-network class with more parameters or a larger norm allowance can often fit the observed sample at least as well as a smaller class. But the smallest empirical risk need not identify the best predictor for future data. An oracle inequality makes this tradeoff explicit: it bounds the risk of a selected predictor by the risk achievable in each candidate class, plus a complexity cost for estimating within that class.

Here the candidates may differ in depth, width, or norm restrictions. The point is not to prescribe how those candidates should be designed, but to show how a penalty can compare them in one risk guarantee. The guarantee rests on simultaneous control of empirical and population risks, and it can include a nonzero optimization error.

Setup and Definitions

Let \(Z_1,\ldots,Z_n\) be independent observations with common distribution \(P\). A predictor \(f\) incurs loss \(\ell_f(Z)\), assumed measurable and bounded between zero and one. Its population risk and empirical risk are

Consider a fixed, finite collection of candidate classes \(\mathcal{F}_1,\ldots,\mathcal{F}_K\). An index \(k\) can encode both an architecture and a norm restriction; for example, one class might contain networks of a specified depth and width whose layer norms do not exceed specified bounds. The classes need not be nested. Let \(a_k\) be a nonnegative number such that, with high probability, every predictor in class \(k\) has population risk close to empirical risk.

For a finite class with \(M_k\) predictors, one such choice follows from Hoeffding's inequality. More generally, a classwise uniform-deviation result can provide \(a_k\) for an infinite neural-network class, provided its assumptions apply to the loss class under consideration. In particular, a bound for the networks themselves is not automatically a bound for their losses.

A Simultaneous Bound for Finite Candidate Classes

Suppose each \(\mathcal{F}_k\) contains \(M_k<\infty\) predictors, and choose positive weights \(\pi_1,\ldots,\pi_K\) with \(\sum_{k=1}^K\pi_k=1\). Define

For a fixed predictor, its \(n\) losses are independent, lie in \([0,1]\), and have mean \(R(f)\). Hoeffding's inequality therefore gives \(P(|R_n(f)-R(f)|>t)\leq 2\exp(-2nt^2)\). At \(t=a_k\), this probability is at most \(\delta\pi_k/M_k\). Taking a union bound over the \(M_k\) predictors in class \(k\), then over the \(K\) classes, proves the following result.

Indeed, the probability that any one of the inequalities fails is at most \(\sum_{k=1}^K M_k\{\delta\pi_k/M_k\}=\delta\sum_{k=1}^K\pi_k=\delta\). This also explains the role of the weights: they allocate the total failure probability across classes. A class given a smaller weight pays a larger logarithmic penalty.

The Oracle Inequality

For each class, the quantity \(\inf_{f\in\mathcal{F}_k}R(f)\) is its best achievable population risk. The selected predictor is allowed to trade off empirical fit against the class-specific radius. Write \(\hat f\in\mathcal{F}_{\hat k}\) for a predictor whose penalized empirical risk is within \(\eta\geq0\) of the best value over all candidate classes:

Exact minimization has \(\eta=0\). An approximate training procedure can instead be covered when its returned predictor satisfies this inequality for a known tolerance \(\eta\).

Proof. On \(\mathcal{E}\), the selected predictor satisfies \(R(\hat f)\leq R_n(\hat f)+a_{\hat k}\). By its approximate-minimization property, for any fixed \(k\) and \(f\in\mathcal{F}_k\), \(R_n(\hat f)+a_{\hat k}\leq R_n(f)+a_k+\eta\). The same event gives \(R_n(f)\leq R(f)+a_k\). Combining these three inequalities yields \(R(\hat f)\leq R(f)+2a_k+\eta\). This holds for every \(k\) and every \(f\in\mathcal{F}_k\); taking the infimum over them proves the result. \(\square\)

The factor \(2a_k\) has a direct source: one radius controls the selected predictor's risk relative to its empirical risk, while another controls the comparator's empirical risk relative to its population risk. The penalty \(a_k\) in the selection criterion is enough to cancel the selected class's radius in this argument. If a different penalty is used, the same proof must be repeated with that penalty rather than assuming the displayed bound remains unchanged.

Using the Bound and Avoiding a Common Mistake

The oracle inequality matters because it adapts a single selected predictor to a collection of candidate neural classes. A larger class can have a lower approximation risk, while its larger \(a_k\) reflects the statistical cost of comparing predictors within it. Norm restrictions enter through the definition of the candidate classes and through whichever valid uniform-deviation bounds are available for them. No single complexity formula is required by the oracle argument; the essential requirement is that the bounds hold simultaneously.

Common mistake: choosing the smallest empirical risk and treating it as the oracle choice. The reasoning “the largest network fits best on the sample, so it must have the smallest population risk” ignores sampling variation and the cost of searching a richer class. The correction is to compare penalized empirical risks using valid classwise bounds. Equally important, a bound proved for one fixed class cannot simply be reused after choosing among many classes from the same data: the confidence allocation or another simultaneous argument must account for that selection.

For infinite neural classes, replacing \(M_k\) in the finite-class formula by a parameter count is not, by itself, a proof. One must use a valid uniform bound for the losses under the stated architecture, norm, distribution, and loss assumptions. Once such radii are established, the oracle proof applies without change. The resulting guarantee is therefore modular: statistical complexity determines the radii, and penalized risk minimization converts them into a comparison with the best candidate.