Why Random Penalties Require Joint Control
A penalty can depend on the observed data: it might use a pilot estimate of variability, a data-dependent complexity estimate, or another random quantity. Such a penalty can be useful, but its randomness creates a specific proof obligation. It is not enough to show, separately for each fixed predictor, that its empirical risk is usually close to its risk. The predictor selected by penalized empirical risk minimization is itself data-dependent, so the deviation control must hold for the candidates jointly, on one event.
This tutorial gives a direct condition for that control and derives the resulting oracle inequality. The argument does not require the penalty to be independent of the empirical risks. It requires that, with high probability, the deviations and the realized penalties satisfy suitable inequalities simultaneously.
We consider an estimator \(\hat f\) that approximately minimizes the penalized empirical risk \(R_n(f)+\lambda\hat p(f)\), where \(\lambda\) is a fixed nonnegative coefficient. “Approximately” allows for numerical or optimization error; the theorem records that error explicitly.
A Simultaneous Oracle Inequality
The condition below separates the two directions of empirical-risk error. The first inequality protects the selected predictor when converting its empirical risk into risk. The second converts the comparator’s empirical risk into risk. The bounds can have different constants and a common additive remainder.
\(R(f)\leq R_n(f)+A\hat p(f)+r\) and \(R_n(f)\leq R(f)+B\hat p(f)+r,\)
where \(A,B,r\geq0\). If \(\lambda\geq A\) and \(\hat f\) satisfies
\(R_n(\hat f)+\lambda\hat p(\hat f)\leq R_n(f)+\lambda\hat p(f)+\varepsilon\)
for every \(f\in\mathcal F\), with \(\varepsilon\geq0\), then on \(\mathcal E\),
\(R(\hat f)\leq \inf_{f\in\mathcal F}\{R(f)+(\lambda+B)\hat p(f)\}+2r+\varepsilon.\)
Consequently, this oracle inequality holds with probability at least \(1-\delta\).
The penalty on the right is evaluated at each comparator using the same realized sample as the selected penalty. Thus the bound remains meaningful when penalties are random. It is an eventwise statement: once the simultaneous inequalities hold, the following derivation is deterministic.
On \(\mathcal E\), apply the first deviation inequality at the random predictor \(\hat f\). This is valid because the inequality holds for every \(f\) on the same event.
Compare \(\hat f\) with an arbitrary fixed candidate \(f\), retaining the optimization tolerance \(\varepsilon\).
Apply the second deviation inequality at \(f\), then use \(\lambda\geq A\) and \(\hat p(\hat f)\geq0\) to discard a nonpositive term.
For completeness, fix any \(f\in\mathcal F\). On \(\mathcal E\), the first deviation inequality, approximate-minimizer property, and second deviation inequality give, in that order,
The final inequality follows because \(\lambda-A\geq0\) and the selected penalty is nonnegative. Since this holds for every \(f\in\mathcal F\), taking the infimum over \(f\) proves the result. The proof ends with \(\square\).
Worked Examples
Worked Example: A Random Pilot Multiplier for a Finite Class
Let \(\mathcal F=\{f_1,f_2\}\). For each predictor, suppose the losses on \(n=100\) independent observations are independent and lie in \([0,1]\), with risk \(R(f_j)\). Hoeffding’s inequality gives \(P(|R_n(f_j)-R(f_j)|>t)\leq2e^{-2nt^2}\). Choose \(\delta=0.05\) and \(c=\sqrt{\log(2|\mathcal F|/\delta)/(2n)}=\sqrt{\log(80)/200}\approx0.1480\). A union bound yields \(P(\text{some }j\text{ has }|R_n(f_j)-R(f_j)|>c)\leq4e^{-200c^2}=0.05\).
Now let \(U_1,U_2\) be random pilot multipliers, each taking values \(1\) or \(1.5\), and define \(\hat p(f_j)=U_jc\). They may be generated from an independent pilot sample, but independence is not needed for the next step: pointwise, \(\hat p(f_j)\geq c\). Thus, on the event just established, both one-sided deviations are bounded by \(\hat p(f_j)\), simultaneously. The theorem applies with \(A=B=1\), \(r=0\), and any \(\lambda\geq1\).
For a possible realized training sample with \(R_n(f_1)=0.27\), \(R_n(f_2)=0.35\), \(U_1=1\), and \(U_2=1.5\), take \(\lambda=1\). The penalties are approximately \(0.1480\) and \(0.2220\); the criteria are \(0.4180\) and \(0.5720\), respectively, so \(f_1\) is selected. On the simultaneous event, the theorem guarantees \(R(f_1)\leq\inf_{j=1,2}\{R(f_j)+2\hat p(f_j)\}\). The random multipliers affect the comparator costs and the selection, while the event verifies that these costs dominate the deviations.
Worked Example: Checking the Criterion and Oracle Bound
Suppose two candidates have empirical risks \(R_n(f_A)=0.20\) and \(R_n(f_B)=0.40\), with realized penalties \(\hat p(f_A)=\hat p(f_B)=0.10\). Let \(\lambda=6\). Their penalized criteria are \(0.20+6(0.10)=0.80\) for \(f_A\) and \(0.40+6(0.10)=1.00\) for \(f_B\). Thus \(f_A\) is selected; the criteria do not tie.
For a concrete simultaneous event, suppose the true risks are \(R(f_A)=0.25\) and \(R(f_B)=0.50\), and on the event under consideration the absolute deviations are bounded by the corresponding penalties. Indeed, \(|0.20-0.25|=0.05\leq0.10\) and \(|0.40-0.50|=0.10\leq0.10\). The theorem has \(A=B=1\), \(r=0\), and \(\varepsilon=0\), with \(\lambda=6\geq1\). Its right-hand side is \(\min\{0.25+7(0.10),\,0.50+7(0.10)\}=\min\{0.95,1.20\}=0.95\). The selected risk is \(0.25\), which satisfies the bound. The arithmetic on the criteria identifies the selected candidate; the simultaneous deviation event, not the criterion calculation, is what justifies the risk guarantee.
Worked Example: Marginal Guarantees Can Fail After Selection
Let one observation \(J\) be uniform on \(\{1,\ldots,10\}\). Include a predictor \(f_0\) whose loss is always \(0.4\). For each \(j=1,\ldots,10\), define a predictor \(f_j\) whose loss is \(0\) when \(J=j\), and \(2/3\) otherwise. Then \(R(f_0)=0.4\), while \(R(f_j)=(1/10)0+(9/10)(2/3)=0.6\).
For any fixed \(j\), the empirical risk from this one observation differs from \(R(f_j)\) by \(0.6\) with probability \(0.1\), when \(J=j\), and by \(|2/3-0.6|=1/15\) otherwise. Therefore \(P(|R_n(f_j)-R(f_j)|\leq0.5)=0.9\) for each fixed bad predictor. Yet with zero penalties, empirical risk minimization always selects \(f_J\): its empirical risk is \(0\), below \(R_n(f_0)=0.4\), and every other bad predictor has empirical risk \(2/3\). The selected predictor consequently has risk \(0.6\), not the oracle risk \(0.4\).
The ten marginal statements do not imply a simultaneous 90% statement: exactly one bad predictor has deviation \(0.6\) for every realized value of \(J\). This example does not contradict the theorem, whose hypothesis is a joint event controlling all candidates. It shows why separate confidence statements cannot simply be applied to a data-selected candidate.
What Must Be Verified in Practice
The theorem’s most important condition is its event, not the label “random penalty.” A penalty computed from the same observations as \(R_n(f)\) is not automatically valid, and a pilot-based penalty is not automatically valid merely because the pilot is independent. One must still establish that the required inequalities hold jointly, with the stated probability. A standard route for a finite class is to prove a deviation bound for each candidate and use a union bound; for other settings, the joint control must be justified by an appropriate argument for that class and loss.
The coefficient condition \(\lambda\geq A\) has a specific role. The first deviation inequality charges the selected predictor \(A\hat p(\hat f)\). Penalized minimization subtracts \(\lambda\hat p(\hat f)\), so \(\lambda\) must be large enough to cancel that selected-model charge. The comparator still pays \((\lambda+B)\hat p(f)\) in this general bound. If approximate optimization is used, its tolerance \(\varepsilon\) adds directly to the risk guarantee.
A frequent mistake is to prove a high-probability inequality for each fixed \(f\), then substitute \(\hat f\) into it as though \(\hat f\) had been fixed in advance. That substitution is unjustified unless the event covers all candidates or a separate argument handles the selection. The correction is to establish a single event on which the inequalities hold for every candidate, and only then apply them to both \(\hat f\) and an arbitrary comparator.
Check Your Understanding
For each question, identify which hypothesis or step in the argument is involved.
- In the theorem, why must the event control deviations for every candidate rather than only for each fixed candidate separately?
- Which term in the proof explains the condition \(\lambda\geq A\)? What would be left if \(\lambda<A\)?
- If \(\hat f\) minimizes the penalized criterion only up to \(\varepsilon=0.03\), how does the oracle bound change?
- In the finite-class example, verify the union-bound probability using \(c=\sqrt{\log(80)/200}\).
- In the ten-predictor example, what is the marginal probability that a fixed \(f_j\) deviates from its risk by more than \(0.5\), and why does that not give simultaneous control?