Peeling Localized Excess-Risk Classes

Why Peel a Class by Risk?

A deviation bound for functions with small risk is often sharper than a bound that treats every function in a class as equally complex. Localization makes this possible: one first controls functions whose risk is at most a specified radius. The difficulty is that a class of interest usually contains functions at many different risk levels. A single localized bound need not control all of them at once.

Peeling resolves this by splitting the class into geometrically increasing risk ranges, or dyadic shells. Each shell is contained in a localized class, so a deviation bound at the shell’s upper radius applies to every function in that shell. Allocating the total failure probability across the shells then gives a simultaneous guarantee over the full class.

Definitions and the Peeling Bound

Let \(Z_1,\ldots,Z_n\) be independent observations with common distribution \(P\), and let \(P_n g=n^{-1}\sum_{i=1}^n g(Z_i)\) be the empirical average of a measurable function \(g\). Write \(Pg=E[g(Z)]\). Consider a class \(\mathcal G\) of measurable functions whose risks satisfy \(0\le Pg\le R\). In excess-risk applications, \(Pg\) is the risk in excess of a reference risk and is nonnegative; the functions themselves need not be pointwise nonnegative.

Choose a finite integer \(J\) with \(R\le r_J\). These shells cover the class, including functions of zero risk. Assume the suprema below are measurable; alternatively, the probability statements can be interpreted using outer probability when the usual measurability conditions for empirical-process suprema are not available.

Suppose that for each \(j=0,\ldots,J\) and each \(t>0\), a localized deviation bound is available:

Here \(b(r,t)\) is a nonnegative bound, and the statement is an assumption about the localized classes. The peeling argument does not require a particular formula for \(b\).

Proof. For each \(j\), apply the assumed localized bound with \(t=t_j\). The probability that the bound fails at radius \(r_j\) is at most \(e^{-t_j}=\delta_j\). By the union bound, the probability of any failure among the \(J+1\) radii is at most

Therefore, with probability at least \(1-\delta\), every localized bound holds simultaneously. On this event, take any \(g\in\mathcal G\). If \(Pg\le r_0\), then \(g\in\mathcal G(r_0)\). Otherwise, there is a shell index \(j\ge1\) with \(r_{j-1}<Pg\le r_j\), so \(g\in\mathcal G(r_j)\). In either case, the deviation bound at the corresponding radius applies to \(g\). Taking the supremum gives the final inequality. \(\square\)

What the Shell Bound Does—and Does Not—Say

The allocation \(\delta_j=\delta 2^{-(j+1)}\) spends more of the failure-probability budget on the first shells and less on distant ones, while ensuring that the total expenditure is at most \(\delta\). The price of looking across shells appears in the confidence parameter \(t_j\): it increases by \(\log 2\) each time the radius doubles. A different summable allocation is possible, but its corresponding confidence parameters must also be included in the localized bounds.

The theorem gives an absolute deviation bound on each shell. It also gives relative control on shells bounded away from zero, provided the shell’s deviation is small enough. For example, if for some \(0<\eta<1\) we have \(b(r_j,t_j)\le\eta r_{j-1}\) for every \(j\ge1\), then on the same simultaneous event, every function in those shells satisfies

This condition cannot be applied to the first shell by the same reasoning: its members can have risk arbitrarily close to zero, so there is no positive lower bound \(r_{-1}\) to compare with the absolute deviation. Near zero risk, the useful conclusion is typically an absolute bound, not a relative one.

Obtaining Shellwise Bounds for a Finite Class

A common way to supply the localized bounds is to combine Bernstein’s inequality with a union bound over functions. Suppose \(\mathcal G\) is finite, \(|g(Z)|\le B\) almost surely for every \(g\in\mathcal G\), and \(\operatorname{Var}(g(Z))\le vPg\) for some \(v\ge0\). For each fixed \(g\), Bernstein’s inequality for independent observations gives

The boundedness assumption is stated for \(g\); consequently \(|g(Z)-Pg|\le2B\), as required by this version of Bernstein’s inequality. If \(Pg\le r\), the variance condition implies \(\operatorname{Var}(g(Z))\le vr\). If there are \(N(r)\) functions in \(\mathcal G(r)\), a union bound therefore gives, for every \(t>0\),

In particular, set \(t=\log(2N(r)/\varepsilon)\), for \(0<\varepsilon<1\). Then the right side is \(\varepsilon\), giving an explicit localized bound. Combining these bounds at the dyadic radii with the peeling theorem yields a full-class guarantee. The calculation illustrates how the sample-size term and the number of functions in each localized class both enter the shellwise control.

Common Pitfall: Treating One Local Bound as a Uniform Bound

A tempting but incorrect argument is: “The localized deviation bound holds with probability at least \(1-\delta\) at every radius, so it holds at all radii with probability at least \(1-\delta\).” Individual probability guarantees do not imply a simultaneous guarantee. If there are \(J+1\) radii and each bound fails with probability at most \(\delta\), the union bound only gives a failure probability at most \((J+1)\delta\), which may be much larger than \(\delta\).

The correction is to assign each shell its own failure probability \(\delta_j\) with \(\sum_j\delta_j\le\delta\), and to use the confidence parameter required by that smaller probability in that shell’s localized bound. Another mistake is to extend a relative deviation conclusion down to zero risk. Since \(Pg\) can be arbitrarily small in the first shell, an absolute error bound there does not automatically imply \(|P_n g-Pg|\le\eta Pg\). Keep the absolute and relative conclusions distinct.