Worked Example: Absolute Loss on a Bounded Range

Why Center Absolute Loss?

Absolute loss is a natural way to measure prediction error: a prediction \(g(X)\) is penalized by its distance from the response \(Y\). To control how far empirical risks can be from their population risks, we want to connect the loss class to the prediction class. The useful feature here is that, for each fixed response, absolute loss changes by at most the change in the prediction. The response may even be unbounded, provided it is integrable.

The loss itself includes a response-only term that can make it unbounded. Subtracting that term does not alter any risk deviation, and leaves a centered loss bounded by the size of the prediction. This makes the route from symmetrization to contraction particularly transparent.

Setup and definition: Let \(Z=(X,Y)\) have a distribution \(P\), and let \(Z_1,\ldots,Z_n\) be independent observations with this distribution. Assume \(E|Y|<\infty\). Let \(\mathcal G\) be a nonempty, measurable class of predictors satisfying \(|g(x)|\le B\) for every \(g\in\mathcal G\) and \(x\). Define the absolute-loss risk \(R(g)=E|g(X)-Y|\) and empirical risk \(R_n(g)=n^{-1}\sum_{i=1}^n|g(X_i)-Y_i|\). The uniform deviation is \(\sup_{g\in\mathcal G}|R(g)-R_n(g)|\). We assume the relevant suprema are measurable; this holds, for example, for a countable class or an appropriately separable class.

The risks are finite because \(|g(X)-Y|\le B+|Y|\). Introduce the centered loss \(h_g(x,y)=|g(x)-y|-|y|\). The reverse triangle inequality gives \[ \bigl||g(x)-y|-|y|\bigr|\le |g(x)|\le B. \] Thus each \(h_g\) is bounded, even if \(Y\) is not. Moreover, the subtracted term cancels between population and empirical averages: \[ R(g)-R_n(g)=P h_g-P_n h_g, \] where \(P h=E[h(X,Y)]\) and \(P_n h=n^{-1}\sum_{i=1}^n h(X_i,Y_i)\). The uniform deviation for absolute loss is exactly the uniform deviation for this centered class.

The Bound and Its Ingredients

For fixed observations \(X_1,\ldots,X_n\), define the absolute empirical Rademacher complexity of a prediction class \(\mathcal A\) by \(\widehat{\mathfrak R}^{\,\mathrm{abs}}_n(\mathcal A)=E_\sigma[\sup_{a\in\mathcal A}|n^{-1}\sum_{i=1}^n\sigma_i a(X_i)|]\), where the \(\sigma_i\) are independent signs, each equal to \(1\) or \(-1\) with probability \(1/2\). Write \(\mathcal G_0=\mathcal G\cup\{0\}\), with \(0\) the identically zero predictor. Including zero makes the centering condition for contraction explicit.

Theorem: Under the setup above, \[ E\left[\sup_{g\in\mathcal G}|R(g)-R_n(g)|\right] \le 4E\left[\widehat{\mathfrak R}^{\,\mathrm{abs}}_n(\mathcal G_0)\right]. \] The outer expectation is over the observations. No boundedness assumption on \(Y\) is needed beyond \(E|Y|<\infty\).

The two ingredients are two-sided symmetrization and the contraction inequality. In the form used here, symmetrization bounds the expected supremum of absolute deviations of a bounded measurable class by twice its expected absolute empirical Rademacher complexity. The absolute-value version of the contraction inequality says that, when \(0\in T\) and each coordinate map \(\phi_i\) is 1-Lipschitz with \(\phi_i(0)=0\), \[ E_\sigma\sup_{t\in T}\left|\sum_{i=1}^n\sigma_i\phi_i(t_i)\right| \le 2E_\sigma\sup_{t\in T}\left|\sum_{i=1}^n\sigma_i t_i\right|. \] The factor \(2\) is for this absolute-supremum version of contraction. These are the symmetrization and contraction bounds developed in the earlier material on those subjects.

Derived fact: For every fixed data point \((x,y)\), the map \(\phi_y(t)=|t-y|-|y|\) satisfies \(\phi_y(0)=0\) and \[ |\phi_y(s)-\phi_y(t)|=\bigl||s-y|-|t-y|\bigr|\le |s-t|. \] Also, \(|\phi_y(t)|\le |t|\). These follow respectively from the reverse triangle inequality and the triangle inequality.

Here is the symmetrization step in detail. Let \(\mathcal H=\{h_g:g\in\mathcal G\}\), and let \(Z'_1,\ldots,Z'_n\) be an independent sample from \(P\). Conditional on \(Z_1,\ldots,Z_n\), \(P h\) is the expectation of \(P'_n h\). Jensen's inequality for the supremum of absolute values therefore gives \[ E\sup_{h\in\mathcal H}|P h-P_n h| \le E\sup_{h\in\mathcal H}|P'_n h-P_n h|. \] For each \(i\), independently swapping \(Z_i\) and \(Z'_i\) does not change their joint distribution. Representing these swaps by Rademacher signs and then applying the triangle inequality yields \[ \begin{aligned} E\sup_{h\in\mathcal H}|P'_n h-P_n h| &=E\sup_{h\in\mathcal H}\left|\frac1n\sum_{i=1}^n\sigma_i\{h(Z'_i)-h(Z_i)\}\right|\\ &\le 2E\sup_{h\in\mathcal H}\left|\frac1n\sum_{i=1}^n\sigma_i h(Z_i)\right|. \end{aligned} \] The last inequality holds because the primed and unprimed samples have the same distribution. This proves the required two-sided symmetrization bound for \(\mathcal H\).

To finish, condition on \(Z_1,\ldots,Z_n\), and take \(T=\{(g(X_1),\ldots,g(X_n)):g\in\mathcal G_0\}\). It contains the zero vector. The coordinate maps \(\phi_{Y_i}\) just verified are 1-Lipschitz and vanish at zero. Contraction gives \[ E_\sigma\sup_{g\in\mathcal G_0}\left|\frac1n\sum_{i=1}^n\sigma_i h_g(Z_i)\right| \le 2E_\sigma\sup_{g\in\mathcal G_0}\left|\frac1n\sum_{i=1}^n\sigma_i g(X_i)\right|. \] Since \(h_0=0\), adjoining the zero predictor does not change the left-hand supremum. Combining this inequality with symmetrization proves the theorem. \(\square\)

Worked Calculations

Worked Example: Constant Predictors on Four Observations

Suppose the predictors are constant functions \(g_c(x)=c\), with \(c\in[-a,a]\), where \(0<a\le B\). For any four observed inputs and any choice of signs, \[ \sup_{c\in[-a,a]}\left|\frac14\sum_{i=1}^4\sigma_i c\right| =\frac a4\left|\sum_{i=1}^4\sigma_i\right|. \] If \(k\) of the four signs are positive, their sum is \(2k-4\), and \(k\) has probabilities \(1,4,6,4,1\) divided by \(16\) for \(k=0,1,2,3,4\). Thus \[ E\left|\sum_{i=1}^4\sigma_i\right| =\frac{4+8+0+8+4}{16} =\frac32. \] The empirical absolute complexity is therefore \(3a/8\). The theorem gives an expected uniform-deviation bound of \(4(3a/8)=3a/2\). This bound may exceed the possible deviation in a particular application; its purpose is to provide a valid, complexity-based upper bound, not necessarily a sharp one.

Worked Example: A Three-Point Prediction Vector

On three fixed inputs, suppose the class contains the zero predictor and one other predictor with values \((a,a,-a)\), where \(0<a\le B\). For any sign vector, taking the supremum of the absolute signed sum over these two predictors gives \(|a(\sigma_1+\sigma_2-\sigma_3)|\). The quantity inside the absolute value is an odd integer multiple of \(a\), so its absolute value is \(a\) or \(3a\). It equals \(3a\) when all three signs align with the corresponding vector \((1,1,-1)\), or all three oppose it. Those two sign patterns have total probability \(2/8\); the other six patterns give \(a\). Hence \[ E_\sigma|a(\sigma_1+\sigma_2-\sigma_3)| =\frac{2(3a)+6a}{8} =\frac{12a}{8} =\frac{3a}{2}. \] After dividing by \(n=3\), the empirical absolute complexity is \(a/2\). The uniform-deviation theorem consequently gives the bound \(4(a/2)=2a\) for the expected deviation of this class's absolute-loss risks.

Worked Example: Unbounded Responses With a Finite Risk Bound

Let \(X\) be constant and let \(Y\) have the exponential distribution with mean \(1\), so \(Y\ge0\) and \(E|Y|=1\). Consider the single predictor \(g(x)=a\), where \(0\le a\le B\). For every response, \[ |g(X)-Y|-|Y|=|a-Y|-Y. \] If \(Y\ge a\), this is \((Y-a)-Y=-a\); if \(0\le Y<a\), it is \((a-Y)-Y=a-2Y\). In either case its absolute value is at most \(a\). The response itself is unbounded, but the centered loss is bounded and the risk is finite, since \(E|a-Y|\le a+1\).

Because the predictor class has one member, its expected absolute Rademacher complexity on \(n\) observations is \(aE|\sum_{i=1}^n\sigma_i|/n\). The theorem bounds the expected absolute risk deviation by \(4aE|\sum_i\sigma_i|/n\). For \(n=1\), this is \(4a\), since \(|\sigma_1|=1\). The bound is valid without imposing a bounded-response assumption; integrability ensures the original absolute-loss risk is defined.

Interpreting the Bound

The theorem says that the uniform deviation is controlled by how well the prediction class can align with random signs on the observed inputs. It does not require a separate complexity calculation for every absolute-loss function. The Lipschitz property transfers control from predictions to centered losses, while symmetrization relates population-versus-sample deviations to random signed sums.

The response distribution still matters to the actual risks, but the complexity bound depends on the predictor values on the sampled inputs. In particular, bounded prediction outputs make the centered loss bounded even when the response is unbounded. This is why the integrability condition \(E|Y|<\infty\), rather than a bounded-response condition, is sufficient here.

Common Mistake

Keeping the response-only offset inside an absolute signed supremum. It is generally incorrect to say that adding \(|Y_i|\) to every loss leaves \(E_\sigma\sup_g|\sum_i\sigma_i|g(X_i)-Y_i||\) unchanged. Inside an absolute supremum, the signed offset \(\sum_i\sigma_i|Y_i|\) does not simply disappear.
Correction. First center the loss at the zero prediction: use \(h_g(x,y)=|g(x)-y|-|y|\). This subtraction leaves every population-minus-empirical risk deviation unchanged, and the coordinate maps now vanish at zero, as contraction requires. Then apply symmetrization and contraction to the centered class.
Dropping the zero predictor without checking the theorem's hypotheses. The contraction form used here requires the index set to contain zero. Use \(\mathcal G\cup\{0\}\) in the complexity unless zero is already in the prediction class.

Key takeaway: For bounded-output predictors and integrable responses, center absolute loss by subtracting \(|Y|\). The centered loss is bounded and 1-Lipschitz in the prediction, giving an expected uniform-deviation bound of four times the expected absolute Rademacher complexity of the prediction class with zero adjoined.

Check Your Understanding

Use the centering and complexity argument to answer the following.

Why does subtracting \(|Y|\) from each absolute loss leave \(R(g)-R_n(g)\) unchanged?
Show that \(\bigl||g(X)-Y|-|Y|\bigr|\le B\) when \(|g(X)|\le B\).
Which two properties of \(t\mapsto |t-y|-|y|\) allow the contraction inequality to be applied?
Why does the theorem require \(E|Y|<\infty\) even though its complexity bound does not involve a bound on \(Y\)?
For the predictor vector \((a,a,-a)\) and its zero predictor, what is the empirical absolute Rademacher complexity on three fixed inputs?