Proof of the Rademacher Contraction Inequality

Why a Coordinatewise Proof Works

Rademacher complexity measures how well a class of functions can align with independent random signs. In many arguments, the function values are first passed through a Lipschitz transformation, such as an absolute value or a clipped response. The contraction inequality says that this operation cannot increase the expected supremum by more than the Lipschitz factor. Its proof is useful in its own right: it reduces a many-coordinate comparison to a simple comparison between the two possible values of one sign.

We prove the finite-class, one-sided version. “One-sided” means that the supremum is taken over signed sums, without an absolute value around each sum. This distinction matters: the theorem below is not itself a claim about every absolute-supremum formulation.

Definition: A Rademacher sign is a random variable $\sigma$ with $P(\sigma=1)=P(\sigma=-1)=1/2$. A Rademacher vector $(\sigma_1,\ldots,\sigma_n)$ consists of independent Rademacher signs. For a finite class $\mathcal F$ of real-valued functions and fixed points $x_1,\ldots,x_n$, its empirical Rademacher complexity is $$ \widehat{\mathfrak R}_n(\mathcal F;x_{1:n}) = E_\sigma\left[\sup_{f\in\mathcal F} \frac{1}{n}\sum_{i=1}^n \sigma_i f(x_i)\right]. $$

Because the class is finite, each supremum here is a maximum, and the expectations over signs are finite sums. Write $a_f=(f(x_1),\ldots,f(x_n))$ for the vector associated with $f$. The proof compares the maximum over these vectors before and after transforming one coordinate, while holding the other signs fixed.

The One-Coordinate Comparison

The key step does not require the transformed coordinate to be small in absolute value. It uses the Lipschitz condition to control the difference between its values at any two class elements. We first establish that step for an arbitrary finite index set.

Lemma (one-coordinate comparison): Let $A$ be a finite set, let $g:A\to\mathbb R$, and let $u:A\to\mathbb R$. Suppose $\psi:\mathbb R\to\mathbb R$ is $L$-Lipschitz for some $L\geq 0$; that is, $|\psi(s)-\psi(t)|\leq L|s-t|$ for all real $s,t$. Then $$ E_\sigma\left[\max_{a\in A}\{g(a)+\sigma\psi(u(a))\}\right] \leq E_\sigma\left[\max_{a\in A}\{g(a)+\sigma L u(a)\}\right], $$ where $\sigma$ is one Rademacher sign.

To prove the lemma, average over the two possible signs. The left side is

\begin{aligned} \frac12\max_{a\in A}\{g(a)+\psi(u(a))\} +\frac12\max_{b\in A}\{g(b)-\psi(u(b))\}\\ =\frac12\max_{a,b\in A} \{g(a)+g(b)+\psi(u(a))-\psi(u(b))\}. \end{aligned}

For every ordered pair $a,b$, the Lipschitz condition gives $\psi(u(a))-\psi(u(b))\leq L|u(a)-u(b)|$. Therefore the last display is at most

\frac12\max_{a,b\in A} \{g(a)+g(b)+L|u(a)-u(b)|\}.

This maximum equals the same expression with $L(u(a)-u(b))$ in place of $L|u(a)-u(b)|$. Indeed, if $u(a)-u(b)<0$, exchange the ordered pair: $g(a)+g(b)$ is unchanged, and the new difference is positive. Thus the maximum is

\frac12\max_{a,b\in A} \{g(a)+g(b)+L(u(a)-u(b))\} = E_\sigma\left[\max_{a\in A}\{g(a)+\sigma L u(a)\}\right].

The last equality follows by expanding the two maxima for $\sigma=1$ and $\sigma=-1$, just as in the first display. This proves the lemma. $\square$

Worked Example: Absolute Values Can Strictly Reduce the Supremum

Take $A=\{(0,0),(1,1),(-1,-1)\}$, and transform each coordinate with $\psi(t)=|t|$, which is 1-Lipschitz. Let $z=\sigma_1+\sigma_2$. Before transformation the supremum is $\max(0,z,-z)=|z|$. The four equally likely sign pairs give $z=2,0,0,-2$, so the expected supremum is $(2+0+0+2)/4=1$.

After transformation, the three vectors become $(0,0),(1,1),(1,1)$. The supremum is now $\max(0,z)$. Its values for the same four sign pairs are $2,0,0,0$, giving expectation $2/4=1/2$. Thus the transformed expected supremum is no larger than the original one, and in this example it is strictly smaller.

Iterating the Comparison Across Coordinates

For a finite class, applying the one-coordinate lemma repeatedly proves the desired result. At each step, condition on all signs except the coordinate being replaced. All the terms from the other coordinates then form the fixed function $g$ in the lemma. The resulting comparison can be averaged over the signs on which we conditioned.

Theorem (finite-class Rademacher contraction inequality): Let $A$ be a finite subset of $\mathbb R^n$. For each $i=1,\ldots,n$, let $\psi_i:\mathbb R\to\mathbb R$ be $L$-Lipschitz, with the same $L\geq 0$. If $\sigma_1,\ldots,\sigma_n$ are independent Rademacher signs, then $$ E_\sigma\left[\max_{a\in A}\sum_{i=1}^n\sigma_i\psi_i(a_i)\right] \leq L E_\sigma\left[\max_{a\in A}\sum_{i=1}^n\sigma_i a_i\right]. $$ The inequality also holds when each coordinate has its own Lipschitz constant $L_i$, with the transformed coordinate on the right replaced by $L_i a_i$: $$ E_\sigma\left[\max_{a\in A}\sum_{i=1}^n\sigma_i\psi_i(a_i)\right] \leq E_\sigma\left[\max_{a\in A}\sum_{i=1}^n\sigma_i L_i a_i\right]. $$

Proof. First consider the version with separate constants. Start with the expected maximum $E_\sigma\max_{a\in A}\sum_{i=1}^n\sigma_i\psi_i(a_i)$. Replace the transformed coordinates one at a time, in the order $1,\ldots,n$. At the step for coordinate $i$, condition on all signs other than $\sigma_i$. For each fixed choice of those other signs, their terms define a function $g(a)$ that does not depend on $\sigma_i$. Apply the one-coordinate lemma with $u(a)=a_i$ and $\psi=\psi_i$. It bounds the conditional expected maximum with $\sigma_i\psi_i(a_i)$ by the one with $\sigma_i L_i a_i$. Averaging over the other signs preserves the inequality.

After all $n$ replacements, this gives the claimed bound with separate constants. If all $L_i=L$, factor $L$ out of the signed sum inside the maximum. For $L\geq0$, multiplication by $L$ commutes with taking a maximum, yielding the common-constant inequality. All maxima and expectations used in this argument are finite, so the conditioning and averaging require no additional measurability or limit-interchange assumptions. $\square$

For a finite function class, take $A=\{(f(x_1),\ldots,f(x_n)):f\in\mathcal F\}$. Dividing the theorem by $n$ gives the empirical-complexity form. In particular, if $L>0$,

\widehat{\mathfrak R}_n \bigl(\{\,x\mapsto\psi(f(x)): f\in\mathcal F\,\};x_{1:n}\bigr) \leq L\,\widehat{\mathfrak R}_n(\mathcal F;x_{1:n}),

where the same $L$-Lipschitz function $\psi$ is applied at every observation. More generally, the coordinate version permits a different transform at each $x_i$.

Worked Example: A Scaled Linear Transform

Let $A=\{(0,0),(2,1)\}$, and use $\psi_i(t)=t/2$, so $L=1/2$. For the untransformed vectors, the signed sum for $(2,1)$ is $2\sigma_1+\sigma_2$. Across sign pairs $++,+-,-+,--$, its values are $3,1,-1,-3$. Taking the maximum with the zero vector gives $3,1,0,0$, whose average is $4/4=1$.

The transformed nonzero vector is $(1,1/2)$. Its signed sums are $3/2,1/2,-1/2,-3/2$; taking the maximum with zero gives $3/2,1/2,0,0$, with average $2/4=1/2$. The theorem's upper bound is $L$ times the original expectation, namely $(1/2)(1)=1/2$, so equality holds.

Why the Transform Need Not Vanish at Zero

Some presentations impose $\psi_i(0)=0$, particularly when stating related inequalities. That assumption is not needed for the finite-class one-sided theorem proved here. The proof uses only differences $\psi_i(s)-\psi_i(t)$, which the Lipschitz condition controls; adding a constant to a coordinate transform does not change those differences.

There is also a direct way to see the role of a constant shift. If $\psi_i(t)=\widetilde\psi_i(t)+c_i$, then the signed sum for any $a$ acquires the same term $\sum_i\sigma_i c_i$, independent of $a$. This term passes through the maximum, and its expectation is zero because each sign has mean zero.

Worked Example: Coordinate Transforms With Nonzero Offsets

Let $A=\{(0,0),(1,0),(0,1)\}$, with $\psi_1(t)=t+7$ and $\psi_2(t)=t-4$. Both transforms are 1-Lipschitz, despite not vanishing at zero. For fixed signs, the transformed score at $a$ is $\sigma_1(a_1+7)+\sigma_2(a_2-4)$. Separate this into the common term $7\sigma_1-4\sigma_2$ and the original score $\sigma_1a_1+\sigma_2a_2$. Thus the transformed maximum is $7\sigma_1-4\sigma_2+\max(0,\sigma_1,\sigma_2)$.

The common term has expectation $7E[\sigma_1]-4E[\sigma_2]=0$. The remaining maximum equals 1 for sign pairs $++,+-,-+$, and 0 for $--$, so its expectation is $3/4$. The original expected supremum is also $3/4$. This verifies the inequality exactly, with nonzero offsets present.

Common Mistake: Comparing Each Transformed Value to Its Input

A tempting but incorrect proof tries to show $|\psi_i(a_i)|\leq L|a_i|$ and then compares each term in the signed sums. Lipschitz continuity does not imply that inequality unless an extra condition, such as $\psi_i(0)=0$, is imposed. For example, $\psi(t)=t+7$ is 1-Lipschitz, but $|\psi(0)|=7$ is not at most $1\cdot|0|=0$.

The correction is to compare two candidate class elements at once. In the one-coordinate proof, the relevant quantity is $\psi_i(a_i)-\psi_i(b_i)$, not the absolute size of either transformed value. The Lipschitz condition controls that difference, and exchanging the ordered pair handles either sign of $a_i-b_i$. This pairwise comparison is exactly what allows the proof to condition on one Rademacher sign and then iterate.

The theorem also should not be extended silently to an absolute supremum. Replacing $\max_a\sum_i\sigma_i\psi_i(a_i)$ by $\max_a|\sum_i\sigma_i\psi_i(a_i)|$ changes the statement and requires checking the corresponding version and its hypotheses. Keeping the one-sided statement explicit avoids importing a constant or a symmetry assumption that has not been established here.

Key takeaway: For a finite class, contraction follows by conditioning on one sign, expressing the two-sign average as a maximum over pairs, applying the Lipschitz bound to pairwise differences, and repeating for every coordinate. The proof permits arbitrary transform offsets because it controls differences rather than values from zero.

Check Your Understanding

Use the one-coordinate comparison and the finite-class theorem to answer these questions.

In the one-coordinate lemma, why is it valid to exchange $a$ and $b$ when $u(a)-u(b)$ is negative?
Which parts of the theorem's proof use finiteness of $A$?
Suppose each coordinate transform is $L_i$-Lipschitz rather than sharing a common constant. What expression appears on the right side of the contraction bound?
Explain why adding a constant to a coordinate transform does not affect the expected one-sided supremum.
Why does the theorem as stated not automatically establish the same bound for an absolute supremum?