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

A function $\phi: \mathbb{R} \to \mathbb{R}$ is $L$-Lipschitz 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

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 proceeds by conditioning on $\sigma_1, \ldots, \sigma_{n-1}$ and analyzing the effect of $\sigma_n$. For fixed values of all other Rademacher variables, the supremum is of the form $\sup_f [A(f) + \sigma_n \phi(f(z_n))/n]$ where $A(f)$ collects all other terms.

Since $\phi$ is $L$-Lipschitz with $\phi(0) = 0$, we have $|\phi(t)| \leq L|t|$ for all $t$. This means the contribution of $\sigma_n \phi(f(z_n))$ to the supremum is bounded by $L$ times the contribution of $\sigma_n f(z_n)$. Applying this argument inductively for each coordinate gives the result.

The formal tool is the comparison inequality for Rademacher processes (Ledoux-Talagrand): if $\phi_i$ are $L$-Lipschitz with $\phi_i(0) = 0$, then $\mathbb{E}[\sup_t \sum_i \sigma_i \phi_i(t_i)] \leq L \cdot \mathbb{E}[\sup_t \sum_i \sigma_i t_i]$.

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.

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.

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

The squared loss viewed as a function of $h(x)$ is $\phi_y(t) = (t - y)^2$. Center: $\tilde{\phi}_y(t) = (t-y)^2 - y^2 = t^2 - 2yt$.

Then $\tilde{\phi}_y(0) = 0$ and $\tilde{\phi}_y'(t) = 2t - 2y$. If $|t| \leq B$ and $|y| \leq B$, then $|\tilde{\phi}_y'(t)| \leq 4B$.

By contraction: $\hat{\mathfrak{R}}_S(\ell \circ \mathcal{H}) \leq 4B \cdot \hat{\mathfrak{R}}_S(\mathcal{H})$.

The Lipschitz constant grows with $B$ --- this is expected because the squared loss is more sensitive to large predictions.

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

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), Chapter 4
• Bartlett & Mendelson, "Rademacher and Gaussian Complexities" (JMLR 2002)

Current:

• Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014), Chapter 26.2

• Wainwright, High-Dimensional Statistics (2019), Chapter 4.2

• Vershynin, High-Dimensional Probability (2018), Chapters 2-5

• Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Chapters 2-6

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