Comparing Oracle Bounds In A Two-Model Example

Two Models, Two Sources of Error

Choosing between models involves two distinct quantities. A model’s approximation risk describes how well that model can represent the prediction problem. Its estimation uncertainty describes how far empirical risk may be from population risk when choosing a predictor using data. A more flexible model may have lower approximation risk but require a larger allowance for estimation uncertainty.

The comparison here is between selecting the model with the smallest empirical risk and adding a model-specific complexity penalty before selection. The main point is not that penalization always selects the model with lower actual risk. Rather, under a simultaneous deviation guarantee, the penalty gives an oracle bound that accounts for the uncertainty of each model separately.

The approximation risks \(r_1,r_2\) are not necessarily equal, and the classes need not be nested. For each class, suppose a radius \(\varepsilon_j\) satisfies the simultaneous event

The bounds below hold on \(\mathcal{E}\). This conditional form is useful: a concentration argument can establish that the event has high probability, while the selection argument explains what follows whenever it holds.

Unpenalized Selection and Its Oracle Bound

Unpenalized selection chooses \(\hat j_0\in\{1,2\}\) to minimize \(\hat r_j\), then uses \(\hat f_{\hat j_0}\). The selected fit can have the largest deviation radius, even when the other model has a smaller empirical minimum. Consequently, its guarantee involves both the comparator’s radius and the largest radius.

Proof. Fix either comparator model \(k\). Since \(\hat j_0\) minimizes empirical risk, \(\hat r_{\hat j_0}\leq\hat r_k\). The deviation bound for the selected class gives \(R(\hat f_{\hat j_0})\leq\hat r_{\hat j_0}+\varepsilon_{\hat j_0}\). Also, \(\hat r_k\leq r_k+\varepsilon_k\): compare the empirical minimum with a population risk minimizer in \(\mathcal{F}_k\), and apply the deviation bound to that predictor. Therefore

This holds for each \(k\), so taking the smaller of the two right-hand sides proves the result. \(\square\)

Penalized Selection and Its Oracle Bound

Define the penalized selector by \(\hat j_p\in\arg\min_{j\in\{1,2\}}\{\hat r_j+\varepsilon_j\}\), again with a fixed tie-breaking rule. The penalty is calibrated to the model’s deviation radius. It need not be the only possible penalty; this choice makes the comparison and its guarantee transparent.

Proof. Fix a comparator \(k\). The deviation bound for the selected fit gives \(R(\hat f_{\hat j_p})\leq\hat r_{\hat j_p}+\varepsilon_{\hat j_p}\). By the definition of the penalized selector, \(\hat r_{\hat j_p}+\varepsilon_{\hat j_p}\leq\hat r_k+\varepsilon_k\). Finally, the empirical minimum in model \(k\) satisfies \(\hat r_k\leq r_k+\varepsilon_k\), by comparing with a population minimizer and using \(\mathcal{E}\). Combining these inequalities,

Since the argument holds for either comparator, minimize the last expression over \(k\). \(\square\)

The difference between the two guarantees is important. The unpenalized bound uses \(\varepsilon_{\max}\) for whichever model wins empirical selection. The penalized bound instead pairs each model’s approximation risk with its own radius. If one model has both a smaller approximation risk and a substantially smaller radius, that pairing can be informative even when the other model is much more complex.

Calibrating the Radii for Finite Classes

For finite classes and bounded losses, Hoeffding’s inequality supplies one simple calibration. If \(N_j=|\mathcal{F}_j|\), then for any fixed \(f\in\mathcal{F}_j\) and \(t>0\), \(P(|R(f)-\hat R(f)|>t)\leq 2\exp(-2nt^2)\). Taking a union bound over the \(N_j\) predictors gives \(P(\sup_{f\in\mathcal{F}_j}|R(f)-\hat R(f)|>t)\leq 2N_j\exp(-2nt^2)\). Thus, for a chosen \(\delta_j\in(0,1)\), one may use \(\varepsilon_j=\min\{1,\sqrt{\log(2N_j/\delta_j)/(2n)}\}\). The cap at one is valid because both risks lie in \([0,1]\). Applying another union bound over the two models gives \(P(\mathcal{E})\geq1-\delta_1-\delta_2\).

This derivation distinguishes a calibrated penalty from an arbitrary surcharge: the radius is chosen to control a stated deviation event. The resulting guarantee is only as useful as that event and its radii. A very conservative concentration bound can produce valid but loose oracle bounds.

When the Comparison Is Useful—and a Common Pitfall

A complexity penalty matters most when model uncertainty differs appreciably. For the two-model rule, model 2 is selected precisely when \(\hat r_1-\hat r_2>\varepsilon_2-\varepsilon_1\), apart from ties. Thus, a larger penalty for model 2 requires a correspondingly larger empirical advantage before it is selected. This threshold makes the role of the penalty explicit; the oracle inequality then states the risk consequence on the simultaneous event.

Common mistake: treating the penalty as proof that the selected model has lower risk. The penalized criterion is not the population risk. It is an empirical risk adjusted by a bound on uncertainty. Penalization can select a model with larger approximation risk, as the first worked example illustrates. The conclusion justified by the theorem is instead a bound on the risk of the selected fit relative to each model’s approximation risk and radius. Nor does a smaller oracle bound assert that the selected fit attains that bound exactly.

In practice, these comparisons help clarify what a theoretical penalty is buying. The approximation term rewards models capable of representing the signal; the radius charges for the uncertainty incurred in searching their predictor classes. A useful penalty has to match a valid deviation guarantee for the selection procedure, rather than being chosen solely because a model is labelled “complex.”