Penalties For Unbounded Losses

Why Unbounded Losses Change the Penalty

An empirical risk minimizer can be compared with a good predictor only to the extent that empirical risks estimate population risks reliably. For bounded losses, concentration inequalities give deviations that shrink at familiar rates. With unbounded losses, a rare, very large observation can dominate the empirical average, so a penalty derived as if losses were bounded may be invalid.

The remedy is not one universal penalty. Its form depends on what is known about the tails: an exponential-tail condition supports a variance-and-scale penalty; a finite moment condition supports truncation; and finite variance supports robust mean estimation. In each case the aim is the same: obtain simultaneous error bounds, then pay a penalty at least as large as the corresponding deviation radius.

For a countable class, assign weights \(\pi_f>0\) satisfying \(\sum_{f\in\mathcal F}\pi_f\leq1\). The quantity \(\log(1/\pi_f)\) charges more for predictors with smaller weights. The union-bound argument below uses these weights to control all predictors at once.

From Deviations to an Oracle Inequality

The basic conversion from estimation error to an oracle bound is useful for all three tail regimes. It does not require that the loss be bounded; it requires a valid simultaneous deviation bound for the chosen risk estimates.

Proof. On the simultaneous-deviation event, \(R(\hat f)\leq\tilde R(\hat f)+r_{\hat f}\). The approximate-minimization condition bounds this by \(\tilde R(f)+r_f+\eta\) for any comparator \(f\). The deviation event also gives \(\tilde R(f)\leq R(f)+r_f\). Combining the inequalities yields \(R(\hat f)\leq R(f)+2r_f+\eta\), simultaneously for all \(f\). □

Thus a penalty should be calibrated to a deviation radius, not chosen merely because it resembles a familiar bounded-loss formula. The theorem also shows why the factor of two appears: one radius controls the selected predictor’s risk, and another controls the comparator’s estimated risk.

Exponential Tails: A Variance-and-Scale Penalty

A useful exponential-tail assumption allows both variance and tail scale to affect the radius. For a fixed predictor, write \(Y=L_f(Z)-R(f)\). Suppose there are known values \(v_f\geq0\) and \(b_f>0\) such that, for either sign and every \(0<\lambda<1/b_f\),

This is a two-sided Bernstein-type moment-generating-function condition. The parameter \(v_f\) controls local variability; \(b_f\) controls how quickly the tail penalty grows as confidence increases.

Proof. For a one-sided deviation of the average by \(x>0\), independence and the assumed moment-generating-function bound give, for \(0<\lambda<1/b_f\),

Taking \(\lambda=x/(v_f+b_fx)\) when \(v_f>0\) gives an exponent of \(-nx^2/[2(v_f+b_fx)]\). The same argument applies to \(-Y_i\). For \(x=\sqrt{2v_ft/n}+2b_ft/n\), direct expansion gives \(nx^2\geq2t(v_f+b_fx)\). Each one-sided probability is therefore at most \(e^{-t}\), proving the two-sided bound. If \(v_f=0\), then \(Y=0\) almost surely and the deviation statement is immediate. Finally, set \(t=t_f\) and sum the failure probabilities: \(\sum_f2e^{-t_f}=\delta\sum_f\pi_f\leq\delta\). □

The corresponding oracle procedure minimizes \(\hat R(f)+r_f\), with \(r_f=\sqrt{2v_ft_f/n}+2b_ft_f/n\). The first term reflects sampling variability and the second the tail scale; omitting the second term can be unsafe when losses have exponential tails but are not uniformly bounded.

Finite Moments: Truncate Before Averaging

A finite \(q\)-th moment, for \(1<q\leq2\), does not generally give exponential concentration for the ordinary empirical mean. Truncating each loss controls the influence of extreme observations. The truncation introduces bias, which must be included in the penalty rather than ignored.

Proof. Since losses are nonnegative, the truncation bias is nonnegative and \(0\leq R(f)-E[U_f]\leq E[L_f\,\mathbf 1\{L_f>\tau_f\}]\leq E[L_f^q]/\tau_f^{q-1}\leq M_f^q/\tau_f^{q-1}\). Also, for \(0\leq L_f\leq\tau_f\), \(\min(L_f,\tau_f)^2\leq\tau_f^{2-q}L_f^q\); hence \(\operatorname{Var}(U_f)\leq E[U_f^2]\leq M_f^q\tau_f^{2-q}\). The centered variable \(U_f-E[U_f]\) is bounded in absolute value by \(\tau_f\). Bernstein’s inequality therefore bounds \(|\hat R_\tau(f)-E[U_f]|\), with probability at least \(1-2e^{-t}\), by \(\sqrt{2M_f^q\tau_f^{2-q}t/n}+2\tau_ft/n\). Adding the bias bound proves the claim. □

A convenient threshold balances the terms. Set \(s=t/n\) and \(\tau_f=M_fs^{-1/q}\). Substitution gives the simple radius \((3+\sqrt2)M_fs^{(q-1)/q}\). With weights \(\pi_f\), take \(t=t_f=\log(2/(\delta\pi_f))\); a union bound gives simultaneous validity with probability at least \(1-\delta\). Minimizing \(\hat R_\tau(f)+r_f\) then yields the oracle inequality above. This route is appropriate when a moment envelope is credible but an exponential-tail assumption is not.

Finite Variance: Robust Empirical Means

If only \(E[L_f(Z)^2]<\infty\) is assumed, a median-of-means estimate can give exponential confidence without assuming exponential tails. Divide the observations into \(K\) disjoint blocks of equal size \(m=\lfloor n/K\rfloor\), discard any leftover observations, compute the mean loss within each block, and take the lower median of those \(K\) means.

Proof. Each block mean has variance \(v_f/m\). Chebyshev’s inequality shows that its probability of differing from \(R(f)\) by more than \(2\sqrt{v_f/m}\) is at most \(1/4\). The block means are independent. Let an indicator equal one when a block mean is outside that radius. Each indicator has expectation at most \(1/4\). Hoeffding’s inequality bounds the probability that at least \(K/2\) blocks are bad by \(\exp[-2K(1/2-1/4)^2]=e^{-K/8}\). If fewer than half the blocks are bad, the lower median lies within the radius, proving the first claim. For \(K\leq n\), \(n/K\geq1\) and \(\lfloor n/K\rfloor\geq n/(2K)\); therefore \(2\sqrt{v_f/m}\leq\sqrt{8v_fK/n}\). □

For a countable class, choose \(K_f=\lceil8\log(1/(\delta\pi_f))\rceil\). Provided \(K_f\leq n\) for the predictors to which the bound is applied, the failure probability for predictor \(f\) is at most \(\delta\pi_f\). A union bound gives simultaneous validity, with penalty \(\sqrt{8v_fK_f/n}\). This construction estimates each risk robustly before minimizing the penalized criterion; it does not make the ordinary empirical mean itself robust.

Choosing a Route and Avoiding a Common Error

The assumptions determine which penalty is defensible. Exponential-tail control supports a variance-and-scale radius for the ordinary empirical risk. A finite \(q\)-th moment supports a truncated empirical risk with an explicit bias term. Finite variance supports median-of-means risk estimates. In all three cases, confidence and class complexity enter through \(t_f\) or \(K_f\), and the oracle comparison applies only after the corresponding simultaneous deviation statement has been established.

• Common mistake: applying a bounded-loss Hoeffding penalty to an unbounded loss because the observed sample happens to contain no extreme values. The sample does not establish a deterministic upper bound on losses that were not observed.
• Correction: state and justify an appropriate tail or moment condition, then use a penalty derived from it. Under a moment condition, account for truncation bias; under a robust-mean approach, penalize the robust estimate’s deviation radius rather than treating the raw empirical mean as robust.
• Another caution: a variance term alone need not be enough for exponential-tail losses. The tail-scale term grows linearly in \(t_f/n\) and may matter for stringent confidence or small class weights.