Contraction for Localized Lipschitz Losses

Why Contraction Must Respect the Localization

A localized complexity bound studies only predictors close to a reference predictor, rather than the entire candidate class. When the objective is a loss, contraction lets us transfer a complexity bound for those predictors to the corresponding loss differences. The transfer preserves the localization, but its size is multiplied by the loss’s Lipschitz constant. A crucial detail is that Lipschitz continuity must hold between every pair of predictions represented in the localized class, not just between each prediction and the reference.

We formulate the result for a fixed observed sample. This makes the localization and the required condition explicit, and it also makes clear that the argument can be applied conditionally on a random sample.

Definition: Let $S=(X_1,Y_1),\ldots,(X_n,Y_n)$ be a sample, let $\mathcal F$ be a predictor class, and fix a reference predictor $f_0\in\mathcal F$. For a radius $r\geq 0$, define the empirically localized class $$ \mathcal F_r(S)=\left\{f\in\mathcal F:\frac{1}{n}\sum_{i=1}^n\bigl(f(X_i)-f_0(X_i)\bigr)^2\leq r^2\right\}. $$ Its prediction-difference class on $S$ is $G_r(S)=\{(f(X_i)-f_0(X_i))_{i=1}^n:f\in\mathcal F_r(S)\}$. Its centered loss class is $A_r(S)=\{(\ell(f(X_i),Y_i)-\ell(f_0(X_i),Y_i))_{i=1}^n:f\in\mathcal F_r(S)\}$.

Both classes contain the zero vector because $f_0\in\mathcal F_r(S)$. For any finite set $A\subseteq\mathbb R^n$, define its empirical Rademacher complexity by

\widehat{\mathfrak R}_S(A)=E_\sigma\left[\sup_{a\in A}\frac{1}{n}\sum_{i=1}^n\sigma_i a_i\right],

where $\sigma_1,\ldots,\sigma_n$ are independent random variables taking values $1$ and $-1$ with probability $1/2$ each. Since $0\in A$, the supremum inside the expectation is nonnegative.

The Pairwise Lipschitz Condition

For each observation $i$, the centered loss as a function of a prediction difference is

\phi_i(u)=\ell(f_0(X_i)+u,Y_i)-\ell(f_0(X_i),Y_i).

The relevant inputs to $\phi_i$ are the coordinate values $D_i=\{f(X_i)-f_0(X_i):f\in\mathcal F_r(S)\}$. The condition needed below is that for every $i$ and every pair $u,v\in D_i$,

|\phi_i(u)-\phi_i(v)|\leq L|u-v|.

In particular, $0\in D_i$ and $\phi_i(0)=0$. The pairwise condition is stronger than checking only $|\phi_i(u)|\leq L|u|$: the latter compares each candidate to the reference but says nothing sufficient about the distance between two nonreference candidates.

Theorem (localized contraction): Suppose $\mathcal F_r(S)$ is finite and, for every sample point $i$, the map $\phi_i$ is $L$-Lipschitz on all of $D_i$. Then $$ \widehat{\mathfrak R}_S(A_r(S))\leq L\,\widehat{\mathfrak R}_S(G_r(S)). $$ For countable classes, the same conclusion holds when the suprema are measurable, by applying the finite result to increasing finite subclasses containing $f_0$ and taking limits. A separable class can be treated through a countable subclass that gives the same suprema.

Proof of the Contraction Inequality

We first prove the finite-set inequality used in the theorem. Let $T\subseteq\mathbb R^n$ be finite and contain the zero vector. Suppose each $\phi_i$ vanishes at zero and is $L$-Lipschitz on the coordinate values $\{t_i:t\in T\}$. We claim

E_\sigma\sup_{t\in T}\sum_{i=1}^n\sigma_i\phi_i(t_i) \leq L E_\sigma\sup_{t\in T}\sum_{i=1}^n\sigma_i t_i.

To prove it, replace the coordinates one at a time. Fix a coordinate $k$, fix all signs other than $\sigma_k$, and let $a_t$ denote the contribution of those other coordinates for index $t$. The average over $\sigma_k$ before replacing coordinate $k$ is

\frac12\left[\sup_{t\in T}\{a_t+\phi_k(t_k)\}+ \sup_{s\in T}\{a_s-\phi_k(s_k)\}\right].

Because $T$ is finite, choose maximizers $t$ and $s$ for the two suprema. The displayed quantity is then $\frac12[a_t+a_s+\phi_k(t_k)-\phi_k(s_k)]$. The Lipschitz condition gives $\phi_k(t_k)-\phi_k(s_k)\leq L|t_k-s_k|$. On the other hand, the average with $L t_k$ in place of $\phi_k(t_k)$ is at least

\frac12\max\{a_t+a_s+L(t_k-s_k),\ a_t+a_s+L(s_k-t_k)\} =\frac12[a_t+a_s+L|t_k-s_k|].

Thus replacing $\phi_k$ by the map $u\mapsto Lu$ cannot decrease the conditional expected supremum. Averaging over the other signs preserves the inequality. Repeating this argument for coordinates $1,\ldots,n$ proves the claim. Divide by $n$ and take $T=G_r(S)$. Since the loss vector corresponding to $t\in T$ has coordinates $\phi_i(t_i)$, the claim is exactly the localized contraction theorem. $\square$

The proof pinpoints why the condition must be pairwise: at each replacement it compares $\phi_k(t_k)$ with $\phi_k(s_k)$ for two potentially different maximizers. A bound involving only $\phi_k(u)-\phi_k(0)$ does not control that difference with the required constant.

Worked Consequences and Examples

Worked Example: Squared Loss on a Bounded Prediction Range

Take one observation with $Y_1=0$, reference prediction $f_0(X_1)=0$, and localized predictions $0,1,2$. The prediction differences are $T=\{0,1,2\}$, which lie in the radius-$2$ class because their squared differences are at most $4$. For squared loss $\ell(t,y)=(t-y)^2$, the centered loss values are $0,1,4$.

On the prediction range $[0,2]$, the loss is $4$-Lipschitz for this observation: for $u,v\in[0,2]$, $|u^2-v^2|=|u-v||u+v|\leq4|u-v|$. Thus the pairwise condition holds with $L=4$.

For the predictor class, when $\sigma_1=1$ the supremum of $\sigma_1 t$ over $T$ is $2$; when $\sigma_1=-1$ it is $0$. Its complexity is $(2+0)/2=1$. For the loss class, the corresponding suprema over $\{0,1,4\}$ are $4$ and $0$, so its complexity is $(4+0)/2=2$. The theorem gives $2\leq4\cdot1$, as required.

Worked Example: Logistic Loss on a Localized Class

Consider one observation with label $Y_1=1$, reference prediction $f_0(X_1)=0$, and candidate prediction differences $T=\{0,0.5,-1\}$. The empirical squared prediction distances are at most $1$, so these candidates belong to the radius-$1$ class. Use logistic loss $\ell(t,y)=\log(1+\exp(-yt))$.

For $y=1$, the derivative with respect to $t$ is $-1/(1+\exp(t))$, whose absolute value is at most $1$ for every real $t$. The mean value theorem therefore shows that logistic loss is $1$-Lipschitz between every pair of predictions, so $L=1$.

The predictor complexity is $(0.5+1)/2=0.75$: for sign $+1$, the supremum over $T$ is $0.5$, and for sign $-1$, it is $1$. The centered logistic loss values are $0$, $\log(1+\exp(-0.5))-\log 2\approx-0.2191$, and $\log(1+\exp(1))-\log 2\approx0.6201$. The two signed suprema are $0.6201$ and $0.2191$, respectively, giving loss complexity approximately $(0.6201+0.2191)/2=0.4196$. This is no greater than $1\cdot0.75$.

Worked Example: Why Reference-Only Lipschitz Bounds Fail

Let the prediction differences be $T=\{0,1,2\}$ and assign centered loss differences $\phi(0)=0,\phi(1)=1,\phi(2)=-2$. Relative to the reference value $0$, the bounds $|\phi(u)|\leq|u|$ hold for all three candidates. But the pair $1,2$ violates the required condition: $|\phi(1)-\phi(2)|=3$, while $|1-2|=1$.

The predictor complexity is $1$, since the signed suprema are $2$ for sign $+1$ and $0$ for sign $-1$. The signed loss suprema are $1$ and $2$, so the loss complexity is $1.5$. A claimed contraction bound with $L=1$ would assert $1.5\leq1$, which is false. The correction is not to change the radius: it is to require pairwise $L$-Lipschitz continuity on all candidate prediction values.

Using the Bound Correctly

For a fixed sample, the result transfers a bound on the localized prediction-difference complexity directly to the centered loss class. If $S$ is random, the same inequality holds for each realized sample satisfying the stated conditions; taking expectation over $S$ gives

E_S\!\left[\widehat{\mathfrak R}_S(A_r(S))\right] \leq L\,E_S\!\left[\widehat{\mathfrak R}_S(G_r(S))\right].

This does not by itself supply a rate for the right-hand side. That rate must come from a separate analysis of the localized predictor class. Nor does contraction assert that the loss differences have the same radius as the prediction differences: it bounds their complexity through the factor $L$. For example, the squared-loss Lipschitz constant depends on the prediction and response ranges, while logistic loss has constant $1$ on the real line for labels in $\{-1,1\}$.

A population-localized class can be handled in the same way. One may restrict predictors using a population distance such as $E[(f(X)-f_0(X))^2]\leq r^2$; conditional on the sample, apply the same contraction argument to the resulting predictions. The pairwise Lipschitz requirement remains samplewise and must hold for the candidate values at each observed point.

Key takeaway: Localization restricts which prediction vectors enter the complexity, and contraction transfers that restricted complexity to centered losses. The transfer is valid with factor $L$ only when the loss map is $L$-Lipschitz between every pair of candidate prediction values, including the reference.

Check Your Understanding

Use the definitions and pairwise condition above to answer the following.

Why does including $f_0$ in the localized class ensure that the prediction-difference and centered loss classes contain zero?
For squared loss with predictions in $[-B,B]$ and responses in $[-M,M]$, derive a valid Lipschitz constant on that range.
Which pair of prediction differences is compared in the coordinate-replacement step of the proof, and why is a reference-only bound insufficient?
If a loss has Lipschitz constant $L=3$ on a localized class and its prediction complexity is $0.04$, what upper bound does contraction give for the loss complexity?
Does the contraction theorem itself establish a rate as a function of the localization radius? Explain what additional quantity must be bounded.