Contraction for Loss-Composed Function Classes

Why Contract the Loss Class?

Learning procedures are often evaluated through their losses rather than through their predictions themselves. A predictor \(f\) maps an input \(x\) to a prediction \(f(x)\), while a loss function \(\ell(y,t)\) measures the discrepancy between response \(y\) and prediction \(t\). The resulting class of functions on input-response pairs is \(\{(x,y)\mapsto \ell(y,f(x)):f\in\mathcal F\}\).

If the loss changes at most proportionally to changes in its prediction argument, the Rademacher contraction inequality controls the complexity of this loss class using the complexity of the original predictor class. The key qualification is that the responses are held fixed while applying the inequality: each observed response determines a coordinate-specific transformation of the prediction.

Definition: For a fixed sample \(S=((x_1,y_1),\ldots,(x_n,y_n))\), the loss-composed class evaluated on \(S\) is the set of vectors \[ \{(\ell(y_1,f(x_1)),\ldots,\ell(y_n,f(x_n))):f\in\mathcal F\}. \] Its empirical Rademacher complexity is \[ \widehat{\mathfrak R}_S(\ell\circ\mathcal F) = E_\sigma\left[\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n \sigma_i\ell(y_i,f(x_i))\right], \] where \(\sigma_1,\ldots,\sigma_n\) are independent Rademacher signs, each equal to \(1\) or \(-1\) with probability \(1/2\). We use the same convention for predictors: \[ \widehat{\mathfrak R}_{x_{1:n}}(\mathcal F) = E_\sigma\left[\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n \sigma_i f(x_i)\right]. \]

These definitions use a supremum without an absolute value. For clarity about measurability, the results below hold directly for finite \(\mathcal F\); they also hold for classes for which the displayed suprema are measurable and integrable and the contraction inequality applies. The observed \(x_i,y_i\) are fixed throughout the empirical bound.

The Loss-Contraction Bound

Suppose that, at each observed response \(y_i\), the loss is \(L\)-Lipschitz in its prediction argument: \[ |\ell(y_i,t)-\ell(y_i,t')|\leq L|t-t'| \quad\text{for every }t,t'\in\mathbb R,\ i=1,\ldots,n. \] The responses may differ across observations; all that is required is a common Lipschitz constant for the observed coordinates. A uniform condition over all possible responses is sufficient, but stronger than necessary for this fixed-sample inequality.

Theorem: Under the stated Lipschitz and measurability conditions, \[ \widehat{\mathfrak R}_S(\ell\circ\mathcal F) \leq L\,\widehat{\mathfrak R}_{x_{1:n}}(\mathcal F). \] The loss may be nonzero at prediction \(0\). The responses \(y_1,\ldots,y_n\) are fixed in this statement.

To see why a nonzero value at prediction zero causes no extra term, define the coordinate transformations \[ \phi_i(t)=\ell(y_i,t)-\ell(y_i,0). \] Each \(\phi_i\) is \(L\)-Lipschitz and satisfies \(\phi_i(0)=0\). For every fixed sign vector, subtracting \(\ell(y_i,0)\) from each coordinate changes the supremum by the same quantity \(\frac1n\sum_i\sigma_i\ell(y_i,0)\), independent of \(f\). Its expectation over the signs is zero. Thus the Rademacher complexity is unchanged by this centering.

Fix the data.
For each coordinate, use the transformation \(t\mapsto \ell(y_i,t)\). The observed response is fixed, so this is a function of the prediction alone.

Center the transformations.
Replace each transformation by \(\phi_i(t)=\ell(y_i,t)-\ell(y_i,0)\). This makes \(\phi_i(0)=0\), without changing the expected supremum over signs.

Apply contraction.
The Rademacher contraction inequality bounds the expected supremum after these coordinatewise \(L\)-Lipschitz transformations by \(L\) times the predictor-class expected supremum.

Here is the full derivation, including the centering step. Write \(c_i=\ell(y_i,0)\). Since \(\sum_i\sigma_i c_i\) does not depend on \(f\), it can be taken outside the supremum. Also, \(E_\sigma[\sum_i\sigma_i c_i]=\sum_i c_i E[\sigma_i]=0\). Consequently,

\begin{aligned} \widehat{\mathfrak R}_S(\ell\circ\mathcal F) &= E_\sigma\left[\sup_{f\in\mathcal F} \frac1n\sum_{i=1}^n\sigma_i\bigl(\phi_i(f(x_i))+c_i\bigr)\right]\\ &= E_\sigma\left[\sup_{f\in\mathcal F} \frac1n\sum_{i=1}^n\sigma_i\phi_i(f(x_i))\right] +\frac1n\sum_{i=1}^n c_i E[\sigma_i]\\ &= E_\sigma\left[\sup_{f\in\mathcal F} \frac1n\sum_{i=1}^n\sigma_i\phi_i(f(x_i))\right]\\ &\leq L E_\sigma\left[\sup_{f\in\mathcal F} \frac1n\sum_{i=1}^n\sigma_i f(x_i)\right]\\ &=L\,\widehat{\mathfrak R}_{x_{1:n}}(\mathcal F). \end{aligned}

The inequality is precisely the Rademacher contraction inequality applied to the vectors \((f(x_1),\ldots,f(x_n))\) and the coordinate transformations \(\phi_1,\ldots,\phi_n\). This derivation explains why the response values must be fixed for the application: they specify which transformation acts in each coordinate.

Worked Examples

Worked Example: Squared Loss on a Bounded Prediction Range

Take two observed inputs \(x_1,x_2\), responses \(y_1=1,y_2=-1\), and the two constant predictors \(f_+(x)=1\) and \(f_-(x)=-1\). Use squared loss \(\ell(y,t)=(y-t)^2\). On the prediction range \([-2,2]\), with responses in \([-1,1]\), calculate a valid Lipschitz constant and compare the two empirical complexities.

For \(t,t'\in[-2,2]\) and \(y\in[-1,1]\), \[ |\ell(y,t)-\ell(y,t')| =|(t-y)^2-(t'-y)^2| =|t-t'||t+t'-2y| \leq 6|t-t'|. \] The last inequality follows from \(|t+t'-2y|\leq |t|+|t'|+2|y|\leq 2+2+2=6\). Thus \(L=6\) is valid on this range.

The predictor vectors on the two inputs are \((1,1)\) and \((-1,-1)\). For a sign pair, the supremum of the signed sums is \(|\sigma_1+\sigma_2|\). This is \(2\) for the two equal-sign pairs and \(0\) for the two opposite-sign pairs, so its expectation is \(1\). Dividing by \(n=2\) gives \[ \widehat{\mathfrak R}_{x_{1:2}}(\mathcal F)=\frac12. \]

The squared-loss vectors are \((0,4)\) for \(f_+\) and \((4,0)\) for \(f_-\). For sign pairs \(++,+-,-+,--\), respectively, the supremum of the signed sums is \(4,4,4,-4\). Its expectation is \((4+4+4-4)/4=2\). Therefore \(\widehat{\mathfrak R}_{S}(\ell\circ\mathcal F)=2/2=1\), and the bound gives \(1\leq 6(1/2)=3\), as required.

Worked Example: Logistic Loss for Two Constant Predictors

Let \(n=2\), \(y_1=1,y_2=-1\), and consider the constant score predictors \(f_+(x)=1\) and \(f_-(x)=-1\). For logistic loss \(\ell(y,t)=\log(1+\exp(-yt))\), verify the Lipschitz constant and calculate both complexities.

Differentiation with respect to \(t\) gives \[ \frac{\partial}{\partial t}\ell(y,t)=\frac{-y}{1+\exp(yt)}. \] For \(y\in\{-1,1\}\), the absolute value is at most \(1\), so the mean value theorem shows that the loss is \(1\)-Lipschitz in \(t\).

Put \(a=\log(1+\exp(-1))\). Since \(\log(1+\exp(1))=a+1\), the two loss vectors are \((a,a+1)\) and \((a+1,a)\). For sign pairs \(++\) and \(--\), the suprema of the signed sums are \(2a+1\) and \(-(2a+1)\), whose sum is zero. For \(+-\) and \(-+\), the supremum is \(1\) in each case. The expected supremum is therefore \((0+1+1)/4=1/2\), and the normalized loss complexity is \(1/4\).

The predictor vectors are \((1,1)\) and \((-1,-1)\), giving expected supremum \(E|\sigma_1+\sigma_2|=1\) and predictor complexity \(1/2\). Hence \(1/4\leq 1(1/2)\).

Worked Example: Hinge Loss on a Two-Point Sample

Take two distinct inputs \(x_1,x_2\), responses \(y_1=y_2=1\), and two predictors with vectors \((f_A(x_1),f_A(x_2))=(2,0)\) and \((f_B(x_1),f_B(x_2))=(0,1)\). For hinge loss \(\ell(y,t)=\max(0,1-yt)\), calculate the empirical complexities.

As a function of \(t\), hinge loss is the maximum of the two affine functions \(0\) and \(1-yt\). For \(y=1\), it is continuous, with slope \(-1\) when \(t<1\) and slope \(0\) when \(t>1\); thus it is \(1\)-Lipschitz. The loss vectors for \(f_A\) and \(f_B\) are \((0,1)\) and \((1,0)\).

For signs \(++,+-,-+,--\), the predictor-class suprema of signed sums are \(2,2,1,-1\). Their average is \(1\), so the predictor complexity is \(1/2\). The corresponding loss-class suprema are \(1,1,1,-1\). Their average is \(1/2\), so the loss complexity is \(1/4\). The contraction inequality reads \(1/4\leq 1(1/2)\).

From a Fixed Sample to Expected Complexity

The empirical result can also be averaged over random data. Let \(Z_i=(X_i,Y_i)\) be independent observations with a common distribution, and suppose the fixed-sample assumptions hold almost surely, with the same \(L\). Define expected complexities by averaging the empirical complexities over the sample.

Result: Under these conditions, \[ E\!\left[\widehat{\mathfrak R}_{Z_{1:n}}(\ell\circ\mathcal F)\right] \leq L E\!\left[\widehat{\mathfrak R}_{X_{1:n}}(\mathcal F)\right]. \]

Indeed, for almost every realized sample \(Z_{1:n}\), the fixed-sample theorem gives \[ \widehat{\mathfrak R}_{Z_{1:n}}(\ell\circ\mathcal F) \leq L\widehat{\mathfrak R}_{X_{1:n}}(\mathcal F). \] Both sides are measurable and integrable by assumption. Taking expectations preserves the inequality, and the constant \(L\) factors out: \[ E[\widehat{\mathfrak R}_{Z_{1:n}}(\ell\circ\mathcal F)] \leq L E[\widehat{\mathfrak R}_{X_{1:n}}(\mathcal F)]. \] This step does not apply contraction to an average over random responses inside a coordinate. It first conditions on—and fixes—the realized responses, then averages the valid samplewise inequality.

Common Pitfall and Practical Meaning

A frequent error is to use a Lipschitz constant that is valid only on a restricted prediction range without verifying that the predictors stay in that range. For example, squared loss has derivative \(2(t-y)\) with respect to \(t\). If predictions \(t\) are unrestricted, this derivative has no finite uniform bound, so squared loss is not globally Lipschitz in its prediction argument. A finite contraction bound for squared loss therefore needs an appropriate restriction on predictions and responses, or another argument.

The bound matters because it lets an analysis control a class of losses through the complexity of the predictors that generate them. The loss can vary with the observed response from coordinate to coordinate; the essential requirement is control of its sensitivity to prediction at those coordinates. The inequality does not say that the two complexities are equal, nor does it guarantee a useful bound when \(L\) is very large. It supplies a reduction, whose value depends on both the predictor class and the relevant loss range.

Key takeaway: With responses fixed, a loss that is \(L\)-Lipschitz in prediction yields \(\widehat{\mathfrak R}_S(\ell\circ\mathcal F)\leq L\widehat{\mathfrak R}_{x_{1:n}}(\mathcal F)\). Centering each coordinate loss at prediction zero makes the application valid even when the loss is nonzero there.

Check Your Understanding

Answer each question using the fixed-sample viewpoint.

Why may the observed response \(y_i\) be different at every coordinate in the contraction argument?
Explain why subtracting \(\ell(y_i,0)\) does not change the expected supremum over Rademacher signs.
For squared loss and \(|y|\leq A,\ |t|\leq B\), derive a Lipschitz constant in \(t\).
If a loss is \(L\)-Lipschitz only on \([-B,B]\), what property of the predictor class must be checked before applying contraction?
What additional step turns the fixed-sample bound into an expected-complexity bound?