Truncation For Finite Aggregation With Unbounded Losses

Why Truncate an Unbounded Loss?

Finite-class selection is especially direct when every candidate's loss is bounded: concentration inequalities then control how far empirical risk can be from population risk. But losses such as squared error can be unbounded, and finite expected risk by itself does not give the same concentration guarantee. Truncation addresses this gap. It caps each observed loss so a bounded-loss inequality applies, while an explicit tail term records what capping removed.

The resulting guarantee has two competing terms. A higher cap reduces the truncation bias but makes the bounded observations less concentrated; a lower cap improves the concentration term but discards more of the loss tail. A useful threshold must balance both.

Truncated Risk and Its Bias

Let \(Z_1,\ldots,Z_n\) be independent and identically distributed observations from a distribution \(P\). A finite dictionary contains \(M\) measurable candidate loss functions \(\ell_1,\ldots,\ell_M\), with \(\ell_j(Z)\geq 0\). Assume each has finite risk \(R_j=E[\ell_j(Z)]<\infty\). For a fixed threshold \(\tau>0\), define the capped loss, its population risk, and its empirical risk as follows.

This bias is not the probability of exceeding the threshold: it measures the expected amount by which losses exceed it. For nonnegative losses, Tonelli's theorem gives the useful tail identity

Indeed, pointwise \((x-\tau)_+=\int_\tau^\infty \mathbf{1}\{x>t\}\,dt\). The integrand is nonnegative, so Tonelli permits exchanging expectation and integration without requiring a separate integrability condition; the assumed finite risk ensures the resulting bias is finite.

A Finite-Dictionary Oracle Bound

Choose the candidate with the smallest empirical truncated risk, using a fixed rule to break ties: \(\hat j\in\arg\min_{1\leq j\leq M}\widehat R_{j,\tau}\). The next result compares its original, untruncated risk with the best original risk in the dictionary. Its assumption on bias is explicit: there must be a known bound \(B(\tau)\) such that \(b_j(\tau)\leq B(\tau)\) for every candidate.

Proof. For each fixed candidate \(j\), the \(n\) truncated losses are independent and lie in \([0,\tau]\). Hoeffding's inequality for independent bounded variables states that if \(W_i\in[0,\tau]\), then \(P(|n^{-1}\sum_i W_i-E[W_1]|>\epsilon)\leq 2\exp(-2n\epsilon^2/\tau^2)\). Apply this to each candidate and use the union bound. With \(\epsilon=\tau\sqrt{\log(2M/\delta)/(2n)}\), the probability that any candidate violates the deviation bound is at most

On the complementary event, every candidate simultaneously satisfies \(|\widehat R_{j,\tau}-R_{j,\tau}|\leq\epsilon\). For any fixed \(j\), use this event, the defining empirical minimization, and the uniform bias bound:

The inequality holds for every \(j\), so taking the minimum over the finite dictionary and substituting the value of \(2\epsilon\) proves the result. \(\square\)

The concentration penalty grows linearly with \(\tau\) and decreases at the usual square-root rate in \(n\). The factor \(\log(2M/\delta)\) reflects both the number of candidates and the desired confidence. The bias term, in contrast, depends on the loss tails and need not be inferred from the bounded-loss concentration step.

Tail Bounds Make the Trade-Off Quantitative

The tail identity converts assumptions about large losses into bounds on truncation bias. For example, if for all \(t\geq\tau\) a candidate satisfies \(P\{\ell_j(Z)>t\}\leq Ct^{-q}\), where \(C>0\) and \(q>1\), then

If this holds uniformly over the dictionary, the oracle bound's excess term is at most \(C\tau^{1-q}/(q-1)+A\tau\), where \(A=\sqrt{2\log(2M/\delta)/n}\). Minimizing this expression over positive \(\tau\) yields the following threshold and bound.

To verify this, differentiate the bias-plus-penalty function. Its derivative is \(-C\tau^{-q}+A\), which vanishes at \(\tau_*=(C/A)^{1/q}\). The derivative is negative below this value and positive above it, so this is the minimum. Substitution gives a bias term \(C^{1/q}A^{(q-1)/q}/(q-1)\) and a penalty \(C^{1/q}A^{(q-1)/q}\); adding them gives the displayed expression. Thus this tail envelope leads to a rate proportional to \((\log(2M/\delta)/n)^{(q-1)/(2q)}\), rather than automatically giving the bounded-loss square-root rate.

What the Bound Does—and Does Not—Say

For a finite dictionary with integrable losses, each \(b_j(\tau)\) tends to zero as \(\tau\) increases: \((\ell_j-\tau)_+\) tends pointwise to zero and is bounded above by the integrable \(\ell_j\), so dominated convergence applies. Since there are finitely many candidates, the maximum of their biases also tends to zero. This fact alone does not give a convenient rate: the theorem needs a numerical upper bound \(B(\tau)\) to quantify the trade-off for a particular sample size.

A common mistake is to argue that truncation is harmless because the original risks are finite. Finite mean guarantees that the bias vanishes eventually, but it does not specify how quickly; two finite-mean losses can have very different tails. A second mistake is to use the concentration penalty while dropping the bias. The bounded empirical risks estimate \(R_{j,\tau}\), not \(R_j\). The proof's final comparison needs the bias bound for the selected candidate as well as for the comparator, which is why the theorem assumes a uniform bound across the dictionary.

There is also a tuning issue: the proof takes \(\tau\) as fixed before observing the data. Choosing it after inspecting the same empirical losses is not covered by this probability statement as written. A data-dependent choice needs an additional argument controlling the choices considered. The central practical lesson is to state the tail assumption, obtain \(B(\tau)\), and balance it against the concentration term rather than selecting a threshold by convenience alone.