A Basic Oracle Inequality From Simultaneous Deviations

From Simultaneous Deviations to an Oracle Comparison

Penalized risk minimization chooses a predictor using the data, so its risk cannot generally be controlled by analyzing it as though it had been fixed in advance. A deviation bound for one fixed predictor need not hold for whichever predictor happens to win the data-dependent selection. The useful input is a simultaneous deviation event: an event on which empirical and population risks are close for every predictor under consideration.

On that event, the basic inequality for penalized empirical risk minimization can be combined with the deviation bounds. The result compares the selected predictor with every comparator, not only with the risk-minimizing candidate. The comparison retains a penalty term for the selected predictor and allows larger deviations for comparators whose risks are harder to estimate.

Definition: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations with distribution $P$. For each predictor $f$ in a class $\mathcal F$, let $\ell_f(Z)$ be its loss, with population risk $R(f)=E[\ell_f(Z)]$ and empirical risk $R_n(f)=n^{-1}\sum_{i=1}^n \ell_f(Z_i)$. Given fixed nonnegative radii $q(f)$, a simultaneous deviation event is $$ \mathcal E=\left\{\, |R_n(f)-R(f)|\le q(f)\ \text{for every } f\in\mathcal F\,\right\}. $$

The radii may be equal for all predictors or vary across the class. Their main property here is not how they were obtained, but that the displayed inequalities hold at once. We first give a common finite-class construction, then prove the deterministic implication that produces the oracle inequality.

A Finite-Class Simultaneous Deviation Bound

Suppose $\mathcal F=\{f_1,\ldots,f_M\}$ is finite and every loss satisfies $0\le \ell_f(Z)\le 1$. For each fixed $f$, the losses $\ell_f(Z_i)$ are independent, identically distributed, and bounded in an interval of length one. Hoeffding’s inequality gives $$ P\left(|R_n(f)-R(f)|>t\right)\le 2\exp(-2nt^2). $$ The union bound then controls the chance that even one of the $M$ deviations exceeds $t$.

Result: Under the preceding assumptions, for any $0<\delta<1$, setting $$ q=\sqrt{\frac{\log(2M/\delta)}{2n}} $$ gives $$ P\left(\, |R_n(f)-R(f)|\le q\ \text{for every }f\in\mathcal F\,\right)\ge 1-\delta. $$

To verify the probability, apply the union bound to the $M$ events:

\begin{aligned} P\left(\exists f\in\mathcal F:\ |R_n(f)-R(f)|>q\right) &\le \sum_{f\in\mathcal F}2\exp(-2nq^2)\\ &=2M\exp\left(-2n\frac{\log(2M/\delta)}{2n}\right)\\ &=2M\exp\bigl(-\log(2M/\delta)\bigr)\\ &=\delta. \end{aligned}

Thus the event on which all $M$ deviations are at most $q$ has probability at least $1-\delta$. Independence between the losses of different predictors is not required: the union bound uses each predictor’s deviation probability separately.

Worked Example: Checking a Finite-Class Radius

There are $M=3$ candidate predictors, each with loss in $[0,1]$, and $n=100$ independent observations. Find the Hoeffding-union-bound radius for confidence level $1-\delta=0.90$, and check the guarantee using a rounded radius.

Here $\delta=0.10$, so $$ q=\sqrt{\frac{\log(2\cdot 3/0.10)}{2\cdot100}} =\sqrt{\frac{\log(60)}{200}} \approx 0.1430794. $$ A rounded radius must be at least this value. Take $q=0.1431$. The union-bound failure probability is at most $$ 6\exp\bigl(-200(0.1431)^2\bigr) =6\exp(-4.095522) \approx 0.09988<0.10. $$ Consequently, with probability at least $1-0.09988$, all three empirical risks differ from their population risks by at most $0.1431$. Rounding the radius down to $0.1428$ would not establish the claimed 0.90 confidence: the corresponding union-bound upper bound is greater than $0.10$.

The Basic Oracle Inequality

Let $p(f)$ be a nonnegative penalty, and let $\hat f$ minimize the penalized empirical risk $R_n(f)+p(f)$ over $\mathcal F$. The next result turns any simultaneous deviation event into a comparison with every $f\in\mathcal F$. For a finite class a minimizer exists; for a more general class, assume a minimizer exists.

Theorem: Suppose that on an event $\mathcal E$, $$ |R_n(f)-R(f)|\le q(f)\qquad\text{for every } f\in\mathcal F, $$ and that $q(f)\le \alpha p(f)$ for every $f$, where $0\le\alpha<1$. If $\hat f$ minimizes $R_n(f)+p(f)$, then on $\mathcal E$, for every comparator $f\in\mathcal F$, $$ R(\hat f)-R(f)+(1-\alpha)p(\hat f)\le (1+\alpha)p(f). $$

This is a deterministic implication on $\mathcal E$. It does not require the comparator to minimize population risk, and it does not require the event to have been obtained from a finite-class bound.

Proof. Penalized empirical minimization gives, for each $f\in\mathcal F$,

R_n(\hat f)+p(\hat f)\le R_n(f)+p(f).

On $\mathcal E$, the selected predictor’s true risk is no greater than its empirical risk plus its radius, and the comparator’s empirical risk is no greater than its true risk plus its radius. Applying both inequalities in the displayed basic inequality yields

\begin{aligned} R(\hat f) &\le R_n(\hat f)+q(\hat f)\\ &\le R_n(f)+p(f)-p(\hat f)+q(\hat f)\\ &\le R(f)+q(f)+p(f)-p(\hat f)+q(\hat f)\\ &\le R(f)+(1+\alpha)p(f)-(1-\alpha)p(\hat f). \end{aligned}

The last line uses $q(f)\le\alpha p(f)$ for the comparator and $q(\hat f)\le\alpha p(\hat f)$ for the selected predictor. Rearranging gives the asserted inequality. Since $f$ was arbitrary, it holds for every comparator on the same event. $\square$

A convenient calibration is $p(f)=2q(f)$, for which $\alpha=1/2$. The theorem then takes the form

R(\hat f)-R(f)+q(\hat f)\le 3q(f) \qquad\text{for every }f\in\mathcal F.

Equivalently, the selected predictor’s risk plus its radius is at most the comparator’s risk plus three times the comparator’s radius. The penalty in the selection criterion is twice the radius; the selected predictor retains half that penalty in this excess-risk formulation.

Worked Example: Three Predictors With a Common Radius

For the three-predictor setting above, suppose the simultaneous event holds with $q=0.1431$, and the observed empirical risks and population risks are as follows:

Predictor	Population risk $R(f)$	Empirical risk $R_n(f)$	Absolute deviation
A	0.20	0.22	0.02
B	0.24	0.13	0.11
C	0.32	0.34	0.02

Each deviation is at most $0.1431$, as required. Using $p(f)=2q=0.2862$ for each candidate makes the penalized criterion equal to empirical risk plus the same constant. Predictor B is selected because $0.13$ is the smallest empirical risk. Predictor A has the smallest population risk. Comparing the selected predictor with A, the theorem gives $$ R(B)-R(A)+q =0.24-0.20+0.1431 =0.1831 \le 3q=0.4293. $$ The inequality holds, although the bound is conservative. It does not claim that empirical selection must identify the predictor with the smallest true risk.

Unequal Radii and Comparator Choice

When deviation bounds vary by predictor, setting $p(f)=2q(f)$ still gives a direct comparison. A predictor with a larger radius pays a larger penalty in the selection criterion, while the oracle inequality permits a larger right-hand side when that predictor is used as comparator. This makes the comparison useful even when a single common deviation radius would be too crude.

Worked Example: A Selected Predictor With Higher Risk

Suppose two predictors have radii $q(A)=0.04$ and $q(B)=0.07$, and their population and empirical risks on a simultaneous deviation event are $$ R(A)=0.20,\quad R_n(A)=0.23,\qquad R(B)=0.23,\quad R_n(B)=0.16. $$ The deviations are $0.03$ and $0.07$, respectively, so each is within its stated radius.

With penalties $p=2q$, the penalized empirical criteria are $$ R_n(A)+p(A)=0.23+0.08=0.31,\qquad R_n(B)+p(B)=0.16+0.14=0.30. $$ Thus B is selected, even though A has lower population risk. Comparing B with A, the oracle inequality says $$ R(B)-R(A)+q(B) =0.23-0.20+0.07 =0.10 \le 3q(A)=0.12. $$ The selected predictor’s excess risk is $0.03$; adding its radius gives $0.10$, which is controlled by the comparator’s radius.

The phrase “every comparator” matters. Once the simultaneous event holds, the theorem’s algebra applies to each $f\in\mathcal F$, without choosing a comparator before observing the data. Therefore one may compare with a particularly favorable candidate, or take the infimum of the right-hand side over the class. For the calibration $p=2q$, this yields the consequence

R(\hat f)+q(\hat f) \le \inf_{f\in\mathcal F}\{R(f)+3q(f)\}.

The expression on the right is an oracle benchmark: it balances population risk against the size of the deviation radius. It is not necessarily the risk of the single best predictor, and the inequality does not require that the infimum be attained.

Worked Example: Comparing Risk and Deviation Cost

Consider three predictors on an event where their deviations are bounded by $q(A)=0.03$, $q(B)=0.055$, and $q(C)=0.10$: $$ \begin{array}{c|ccc} & A & B & C\\ R(f)&0.12&0.14&0.19\\ R_n(f)&0.15&0.09&0.14 \end{array} $$ The absolute deviations are $0.03$, $0.05$, and $0.05$, respectively, so all satisfy their bounds.

With $p=2q$, the penalized criteria are $0.15+0.06=0.21$ for A, $0.09+0.11=0.20$ for B, and $0.14+0.20=0.34$ for C. The selected predictor is B, whereas A minimizes population risk. Comparing B with A gives $$ R(B)-R(A)+q(B) =0.14-0.12+0.055 =0.075 \le 3q(A)=0.09. $$ In terms of the oracle benchmark, $R(A)+3q(A)=0.21$, $R(B)+3q(B)=0.305$, and $R(C)+3q(C)=0.49$. The theorem’s bound $R(B)+q(B)=0.195\le0.21$ is consistent with all three comparisons.

What the Inequality Does—and Does Not—Say

A simultaneous deviation event is what permits a data-dependent predictor to be handled by these pointwise algebraic steps: the deviation bound is already valid for $\hat f$, whatever the data selected. For finite classes, the union-bound construction pays for considering all $M$ candidates through the term $\log(2M/\delta)$ in the radius.

The result is a basic, generally conservative oracle inequality. It needs no curvature assumption and does not claim a faster rate than the deviation radii supply. Its guarantee is high probability when the simultaneous event has high probability; the deterministic comparison alone does not specify that probability. Stronger rates require additional structure, which is not assumed here.

A common mistake is to use a deviation statement proved only for each fixed predictor and then apply it to the selected $\hat f$, as if $\hat f$ had been fixed in advance. The selection depends on the same data used to calculate $R_n$, so the pointwise probability guarantee alone does not justify that step. The correction is to establish a deviation event that holds simultaneously over the candidate class, or otherwise to justify a bound specifically for the selected predictor. A second mistake is to omit the comparator’s deviation cost: the transfer from $R_n(f)$ to $R(f)$ contributes $q(f)$, just as the transfer for the selected predictor contributes $q(\hat f)$.

Key takeaway: If all empirical risks are simultaneously within $q(f)$ of their population risks and the penalty satisfies $q(f)\le\alpha p(f)$ for some $\alpha<1$, penalized empirical minimization guarantees $$ R(\hat f)-R(f)+(1-\alpha)p(\hat f)\le(1+\alpha)p(f) $$ for every comparator $f$ on that event.

Check Your Understanding

Use the event and inequalities in this tutorial to answer the following questions.

Why does a deviation bound for one fixed predictor not automatically apply to the predictor selected using the same sample?
For a class of $M$ predictors with losses in $[0,1]$, write the Hoeffding-union-bound radius that gives failure probability at most $\delta$.
If $p(f)=2q(f)$, what does the oracle inequality bound for the selected predictor when compared with $f$?
In the unequal-radius example, verify the deviation for predictor B and the penalized criterion for both A and B.
Does the oracle inequality assert that the selected predictor has the smallest population risk? Explain the role of the comparator’s radius.