Contraction Inequality

Why This Matters

In learning theory, the generalization bound involves the Rademacher complexity of the loss class $\ell \circ \mathcal{H}$, not the hypothesis class $\mathcal{H}$ itself. But computing Rademacher complexity of the composed class directly is often hard. The contraction inequality solves this problem: if the loss function $\ell$ is $L$-Lipschitz, then $\mathfrak{R}_n(\ell \circ \mathcal{H}) \leq L \cdot \mathfrak{R}_n(\mathcal{H})$.

This is the bridge between the quantity you need (loss class complexity) and the quantity you can compute (hypothesis class complexity). Without it, every new loss function would require a separate Rademacher analysis from scratch.

Mental Model

Imagine the outputs of your hypothesis class as a cloud of points in $\mathbb{R}^n$ (one coordinate per data point). The Rademacher complexity measures how "spread out" this cloud is in terms of correlating with random signs. Now apply a Lipschitz function $\phi$ to each coordinate independently. The Lipschitz condition means $\phi$ cannot stretch distances. It can only shrink them, or preserve them at most. The cloud after applying $\phi$ is no more spread out than the original cloud, so the Rademacher complexity can only decrease.

The condition $\phi(0) = 0$ ensures that the contraction is anchored: $\phi$ does not shift the cloud, only reshapes it.

Formal Setup

Let $\mathcal{F}$ be a class of real-valued functions $f: \mathcal{Z} \to \mathbb{R}$. Let $S = (z_1, \ldots, z_n)$ be a sample and $\sigma_1, \ldots, \sigma_n$ i.i.d. Rademacher random variables. Let $\phi: \mathbb{R} \to \mathbb{R}$ be a function applied pointwise.

Definition

Lipschitz Function$\varphi$

A function $\phi: \mathbb{R} \to \mathbb{R}$ is $L$-Lipschitz if and only if for all $a, b \in \mathbb{R}$:

$|\phi(a) - \phi(b)| \leq L|a - b|$

The smallest such $L$ is the Lipschitz constant of $\phi$. If $\phi$ is differentiable, then $L = \sup_t |\phi'(t)|$.

Definition

Composed Function Class$\varphi \circ \mathcal{F}$

Given a function $\phi: \mathbb{R} \to \mathbb{R}$ and a class $\mathcal{F}$, the composed class is:

$\phi \circ \mathcal{F} = \{\phi \circ f : f \in \mathcal{F}\}$

where $(\phi \circ f)(z) = \phi(f(z))$. In learning theory, $\phi$ is typically the loss function viewed as a function of the hypothesis output, and $\mathcal{F} = \mathcal{H}$ is the hypothesis class.

Main Theorems

Theorem

Contraction Inequality (Ledoux-Talagrand)

Statement

Let $\phi: \mathbb{R} \to \mathbb{R}$ be $L$-Lipschitz with $\phi(0) = 0$. For any class $\mathcal{F}$ of real-valued functions and any sample $S = (z_1, \ldots, z_n)$:

$\hat{\mathfrak{R}}_S(\phi \circ \mathcal{F}) \leq L \cdot \hat{\mathfrak{R}}_S(\mathcal{F})$

where $\hat{\mathfrak{R}}_S$ denotes the empirical Rademacher complexity. Taking expectations over $S$:

$\mathfrak{R}_n(\phi \circ \mathcal{F}) \leq L \cdot \mathfrak{R}_n(\mathcal{F})$

Intuition

Applying $\phi$ pointwise to the values $f(z_1), \ldots, f(z_n)$ cannot increase how well the class correlates with random signs. The Lipschitz condition bounds how much $\phi$ can separate two function values, and $\phi(0) = 0$ ensures $\phi$ does not add a constant offset. The result is that post-composition with $\phi$ can only reduce the "effective spread" of the function class as seen by Rademacher variables.

Proof Sketch

We need to show:

$\mathbb{E}_\sigma\!\left[\sup_{f \in \mathcal{F}} \frac{1}{n}\sum_{i=1}^n \sigma_i \phi(f(z_i))\right] \leq L \cdot \mathbb{E}_\sigma\!\left[\sup_{f \in \mathcal{F}} \frac{1}{n}\sum_{i=1}^n \sigma_i f(z_i)\right]$

The proof is by induction: peel off one Rademacher variable at a time. Condition on $\sigma_1, \ldots, \sigma_{n-1}$ and let $A(f)$ collect those fixed terms. The inner conditional expectation in $\sigma_n$ is:

$\frac{1}{2}\sup_{f \in \mathcal{F}}\bigl[A(f) + \phi(f(z_n))\bigr] + \frac{1}{2}\sup_{g \in \mathcal{F}}\bigl[A(g) - \phi(g(z_n))\bigr]$

This is the two-point step. The goal is to bound this by the same expression with $L \cdot f(z_n)$ in place of $\phi(f(z_n))$. The key lemma is: for any two values $u = f(z_n)$ and $v = g(z_n)$ and any $L$-Lipschitz $\phi$,

$\phi(u) - \phi(v) \leq L|u - v| = L \cdot s(u - v), \quad s \in \{+1, -1\}$

chosen to match the sign of $u - v$. Splitting the two suprema by the relative ordering of $f(z_n)$ and $g(z_n)$ and applying this pointwise replaces $\phi(u) - \phi(v)$ with $L(u - v)$ inside the sum of suprema, which is exactly the target inequality after using the symmetry $\{+1, -1\}$ of the Rademacher distribution. The condition $\phi(0) = 0$ is used to anchor the comparison when only one of $u, v$ appears (see Ledoux and Talagrand 1991, Theorem 4.12 for the full argument).

Iterating the two-point step across all $n$ coordinates gives the stated inequality. The same argument yields the vector (coordinate-wise) contraction in which each $\sigma_i$ may see a different $L$-Lipschitz $\phi_i$ with $\phi_i(0) = 0$.

The naive argument using $|\phi(t)| \leq L|t|$ does not prove contraction, since that only controls $\phi$ at zero, not pairwise differences $\phi(u) - \phi(v)$. The two-point argument is essential.

Why It Matters

This is the key modularity result in Rademacher complexity theory. It means you can analyze the Rademacher complexity of common hypothesis classes (linear functions, kernel classes, neural networks) once, and then compose with any Lipschitz loss to get a generalization bound.

For example, if you know $\mathfrak{R}_n(\mathcal{H}) \leq BR/\sqrt{n}$ for norm-bounded linear classifiers, and the loss is 1-Lipschitz (like the ramp loss), then immediately $\mathfrak{R}_n(\ell \circ \mathcal{H}) \leq BR/\sqrt{n}$.

Without contraction, you would need to compute the Rademacher complexity of each loss-hypothesis combination separately.

Failure Mode

The condition $\phi(0) = 0$ is essential. If $\phi(0) = c \neq 0$, the result fails because $\phi$ shifts all function values by a constant, which can increase the ability to correlate with noise. In practice, you can often center the loss: define $\tilde{\phi}(t) = \phi(t) - \phi(0)$, apply contraction to $\tilde{\phi}$, and add back the constant (which does not affect the supremum over $\mathcal{F}$ since it is independent of $f$).

Also, the Lipschitz constant is a global worst case. If $\phi$ is much smoother in the range actually taken by functions in $\mathcal{F}$, the bound can be loose.

report a correction →

Proposition

Vector-Valued Contraction

Statement

Let $\phi_1, \ldots, \phi_n: \mathbb{R} \to \mathbb{R}$ each be $L$-Lipschitz with $\phi_i(0) = 0$ (the $\phi_i$ may differ). Then:

$\mathbb{E}_\sigma\!\left[\sup_{f \in \mathcal{F}} \sum_{i=1}^n \sigma_i \phi_i(f(z_i))\right] \leq L \cdot \mathbb{E}_\sigma\!\left[\sup_{f \in \mathcal{F}} \sum_{i=1}^n \sigma_i f(z_i)\right]$

Intuition

The contraction works even when different coordinates undergo different Lipschitz maps, as long as they all share the same Lipschitz constant $L$. This is useful because in supervised learning, the loss at data point $i$ is $\ell(h(x_i), y_i)$, viewed as a function of $h(x_i)$ alone. Since $y_i$ differs across data points, the effective $\phi_i(t) = \ell(t, y_i)$ differs per coordinate, but the Lipschitz constant is the same.

Proof Sketch

The proof is the same as for the scalar case. The comparison inequality for Rademacher processes handles the coordinate-wise case directly. Each $\phi_i$ is individually $L$-Lipschitz, and the key property, that contracting each coordinate individually cannot increase the expected supremum of $\sum_i \sigma_i \phi_i(t_i)$, follows from the independence of the Rademacher variables and the inductive peeling argument.

Why It Matters

This vector-valued version is what you actually use in practice. When computing $\mathfrak{R}_n(\ell \circ \mathcal{H})$, the loss at each data point depends on the label $y_i$, giving a different function $\phi_i$ per data point. The vector-valued contraction handles this seamlessly.

Failure Mode

If the Lipschitz constants differ across coordinates ($\phi_i$ is $L_i$-Lipschitz), the bound uses $\max_i L_i$. This can be loose if a few coordinates have much larger Lipschitz constants than the rest.

report a correction →

Proof Ideas and Templates Used

The contraction inequality uses one main technique:

1. Rademacher comparison inequality: the core tool from the theory of Gaussian and Rademacher processes. It says that if you apply Lipschitz maps coordinate-wise to the index set of a Rademacher process, the expected supremum can only decrease. The proof works by induction on the number of coordinates, conditioning on all but one Rademacher variable at each step.

This is conceptually different from the symmetrization technique (which connects generalization gaps to Rademacher complexity). Contraction is about composing function classes, not about connecting population and empirical quantities.

Canonical Examples

Example

Contraction for the hinge loss

The hinge loss is $\ell(t, y) = \max(0, 1 - yt)$ for $y \in \{-1, +1\}$. As a function of $t$ for fixed $y$, $\phi_y(t) = \max(0, 1 - yt)$.

This is 1-Lipschitz: $|\phi_y(a) - \phi_y(b)| \leq |a - b|$. But $\phi_y(0) = 1 \neq 0$. So center it: $\tilde{\phi}_y(t) = \phi_y(t) - 1$. Then $\tilde{\phi}_y(0) = 0$ and $\tilde{\phi}_y$ is still 1-Lipschitz.

By contraction: $\hat{\mathfrak{R}}_S(\tilde{\phi}_y \circ \mathcal{H}) \leq 1 \cdot \hat{\mathfrak{R}}_S(\mathcal{H})$. Since the constant shift by 1 does not affect the supremum over $\mathcal{H}$ (it cancels):

$\hat{\mathfrak{R}}_S(\ell \circ \mathcal{H}) \leq \hat{\mathfrak{R}}_S(\mathcal{H})$

For linear classifiers with $\|w\| \leq B$ and $\|x_i\| \leq R$: $\hat{\mathfrak{R}}_S(\ell \circ \mathcal{H}) \leq BR/\sqrt{n}$.

Example

Contraction for the squared loss (bounded case)

The squared loss $\phi_y(t) = (t - y)^2$ is only locally Lipschitz. To apply contraction, assume $|f(x)| \leq M$ for all $f \in \mathcal{F}$ and $|y| \leq Y_{\max}$. Then $\phi_y$ restricted to $[-M, M]$ is Lipschitz with constant

$L = \sup_{|t| \leq M} |\phi_y'(t)| = \sup_{|t| \leq M} |2(t - y)| \leq 2(M + Y_{\max}).$

Next handle $\phi_y(0) = y^2 \neq 0$ by constant-shift invariance. For any constant $c$ (here $c = y^2$, which depends on $i$ but not on $f$),

$\mathbb{E}_\sigma \sup_f \sum_i \sigma_i (g_i(f) + c_i) = \mathbb{E}_\sigma \sup_f \sum_i \sigma_i g_i(f) + \mathbb{E}_\sigma \sum_i \sigma_i c_i = \mathbb{E}_\sigma \sup_f \sum_i \sigma_i g_i(f),$

since $\mathbb{E}\sigma_i = 0$ and the $c_i$ do not depend on $f$. So subtracting the constants $y_i^2$ from $\phi_{y_i}(f(x_i))$ leaves the Rademacher average unchanged. Define $\tilde{\phi}_y(t) = (t - y)^2 - y^2 = t^2 - 2yt$; then $\tilde{\phi}_y(0) = 0$ and the Lipschitz constant on $[-M, M]$ is still bounded by $2(M + Y_{\max})$.

Applying the vector contraction gives

$\hat{\mathfrak{R}}_S(\ell \circ \mathcal{F}) \leq 2(M + Y_{\max}) \cdot \hat{\mathfrak{R}}_S(\mathcal{F}).$

The Lipschitz constant grows with the output range. This is expected: the squared loss is more sensitive to large predictions. Without the bounded-range assumption, contraction cannot be applied directly to the squared loss at all.

Common Confusions

Watch Out

The phi(0) = 0 condition is not optional

Students often forget this condition and apply contraction directly to losses like $\ell(t) = (t - y)^2$, which has $\ell(0) = y^2 \neq 0$. The fix is always to center: $\tilde{\ell}(t) = \ell(t) - \ell(0)$. This works because shifting all function values by a constant does not change the Rademacher complexity (the $\sigma_i$ have mean zero, so $\sum_i \sigma_i \cdot c = c \sum_i \sigma_i$ has zero mean and does not affect the supremum in expectation).

Watch Out

Contraction gives an upper bound, not equality

$\hat{\mathfrak{R}}_S(\phi \circ \mathcal{F}) \leq L \cdot \hat{\mathfrak{R}}_S(\mathcal{F})$, and the inequality can be strict. A loss function might dramatically reduce the effective complexity (e.g., a loss that is constant on most of the range). Contraction does not tell you the Rademacher complexity of the composed class. It only gives you an upper bound. For tighter results, you may need direct computation.

Watch Out

Which constant applies: L, 2L, or sqrt(2) L?

The contraction inequality has several forms with different constants, and the conditions matter.

• Factor $L$, centered case (Ledoux-Talagrand 1991, Theorem 4.12): if $\phi$ is $L$-Lipschitz with $\phi(0) = 0$ and the supremum is over the signed form $\sum_i \sigma_i \phi(f(z_i))$, then $\mathbb{E}\sup_f \sum_i \sigma_i \phi(f(z_i)) \leq L \cdot \mathbb{E}\sup_f \sum_i \sigma_i f(z_i)$.

• Factor $2L$, absolute-value supremum without $\phi(0) = 0$ (Boucheron-Lugosi-Massart 2013, Theorem 11.6): dropping the centering assumption and taking $\sup_f |\cdot|$ costs an extra factor of 2.

• Factor $\sqrt{2} L$, vector case (Maurer 2016): when $\mathcal{F}$ is a class of $\mathbb{R}^k$-valued functions and $\phi: \mathbb{R}^k \to \mathbb{R}$ is $L$-Lipschitz in Euclidean norm, the vector contraction inequality carries a constant $\sqrt{2}$ in place of $1$.

Always state explicitly which version you are using, and check whether your $\phi$ is centered.

Watch Out

Contraction is about pointwise composition, not class composition

The contraction inequality applies $\phi$ to the output of each function $f$ in the class. It does not compose two function classes (e.g., $\mathcal{F}_1 \circ \mathcal{F}_2$). Composing two function classes can increase Rademacher complexity and requires different tools (e.g., covering number arguments for deep networks).

Summary

• Contraction: $\hat{\mathfrak{R}}_S(\phi \circ \mathcal{F}) \leq L \cdot \hat{\mathfrak{R}}_S(\mathcal{F})$ for $L$-Lipschitz $\phi$ with $\phi(0) = 0$
• This lets you bound loss class complexity from hypothesis class complexity
• Center the loss ($\tilde{\phi} = \phi - \phi(0)$) if $\phi(0) \neq 0$
• The vector-valued version allows different $\phi_i$ per coordinate (same $L$)
• Hinge loss: $L = 1$, so loss class Rademacher equals hypothesis class Rademacher
• Squared loss with $|t|, |y| \leq B$: $L = 4B$
• Contraction is why Rademacher bounds are modular: compute $\mathfrak{R}_n(\mathcal{H})$ once, compose with any Lipschitz loss

Exercises

ExerciseCore

Problem

The ramp loss is $\ell_\gamma(t) = \min(1, \max(0, 1 - t/\gamma))$ for margin parameter $\gamma > 0$. Show that the ramp loss is $(1/\gamma)$-Lipschitz and apply the contraction inequality to bound $\hat{\mathfrak{R}}_S(\ell_\gamma \circ \mathcal{H})$ in terms of $\hat{\mathfrak{R}}_S(\mathcal{H})$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Consider the logistic loss $\ell(t, y) = \log(1 + e^{-yt})$ for $y \in \{-1, +1\}$. Compute the Lipschitz constant of $\phi_y(t) = \log(1 + e^{-yt})$ as a function of $t$, and use the contraction inequality to bound the Rademacher complexity of the logistic loss class in terms of $\hat{\mathfrak{R}}_S(\mathcal{H})$.

Hint

Reveal Solution

ExerciseResearch

Problem

The contraction inequality gives a global Lipschitz constant $L$. In practice, if $f \in \mathcal{F}$ takes values in $[a, b]$, only the Lipschitz constant of $\phi$ restricted to $[a, b]$ matters. State and prove this "local contraction" refinement. How does this improve the bound for the squared loss when the hypothesis class has bounded output?

Hint

Reveal Solution

References

Canonical:

• Ledoux & Talagrand, Probability in Banach Spaces (1991), Theorem 4.12. The canonical statement and proof of the scalar contraction principle via the two-point comparison argument.
• Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Theorem 11.6. Textbook form of the contraction corollary, with the factor-2 variant discussed.
• Bartlett & Mendelson, "Rademacher and Gaussian Complexities" (JMLR 2002). Introduces the modern data-dependent Rademacher framework in which contraction is used.

Vector-valued and applications:

• Maurer, "A Vector-Contraction Inequality for Rademacher Complexities" (ALT 2016). Extends contraction to $\mathbb{R}^k$-valued function classes with the $\sqrt{2}$ constant.
• Golowich, Rakhlin, Shamir, "Size-Independent Sample Complexity of Neural Networks" (COLT 2018). Uses contraction (and peeling) to bound Rademacher complexity of deep networks.
• Bartlett, Foster, Telgarsky, "Spectrally-normalized margin bounds for neural networks" (NeurIPS 2017). Applies contraction to margin-based surrogate losses for deep networks.

Textbook treatments:

• Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014), Lemma 26.9. Contraction lemma in standard learning-theory form.
• Wainwright, High-Dimensional Statistics (2019), Chapter 4.2. Rademacher and Gaussian complexities, contraction discussion.
• Vershynin, High-Dimensional Probability (2018), Chapter 8. Concentration of measure in Banach-space form, related to the contraction argument.

Next Topics

From contraction, the natural next steps are:

• Algorithmic stability: moving beyond complexity-based bounds to algorithm-dependent generalization
• Covering numbers and epsilon-nets: alternative complexity measures that interact with contraction via chaining arguments