Symmetrization Inequality

Why This Matters

Symmetrization is not just a theorem. It is a proof template that appears in virtually every generalization bound in statistical learning theory. The VC dimension proof uses it. The Rademacher complexity generalization bound uses it. The proof that covering numbers control uniform convergence uses it. If you understand symmetrization deeply, you understand the engine that makes all these results work.

The core problem symmetrization solves: how do you bound the gap between a population quantity $\mathbb{E}[f]$ (which involves the unknown distribution $\mathcal{D}$) and its empirical estimate $\hat{E}_n[f]$ (which you can compute), uniformly over a function class $\mathcal{F}$? Symmetrization replaces the unknown population expectation with a second empirical estimate, then exploits the symmetry between the two samples to introduce Rademacher variables. converting an intractable problem about $\mathcal{D}$ into a tractable problem about random signs.

Mental Model

The symmetrization argument proceeds in three conceptual steps:

1. Ghost sample trick: replace the population expectation $\mathbb{E}[f]$ with the average over a second independent sample $S'$ (the "ghost sample"). This is valid in expectation by the law of large numbers.

2. Swap trick: since $S$ and $S'$ are identically distributed, swapping $z_i$ with $z'_i$ does not change the joint distribution. Introduce random signs $\sigma_i \in \{-1, +1\}$ to randomly decide which sample each point comes from.

3. Drop the ghost: after introducing Rademacher variables, the ghost sample $S'$ can be removed. The Rademacher averages depend only on $S$, not on $S'$.

The result: the gap $\sup_f (\mathbb{E}[f] - \hat{E}_n[f])$ is bounded by $2 \mathfrak{R}_n(\mathcal{F})$, the Rademacher complexity.

Formal Setup and Notation

Let $\mathcal{F}$ be a class of functions $f: \mathcal{Z} \to [0, 1]$. Let $S = (z_1, \ldots, z_n)$ be drawn i.i.d. from $\mathcal{D}$ and let $S' = (z'_1, \ldots, z'_n)$ be an independent copy. Let $\sigma_1, \ldots, \sigma_n$ be i.i.d. Rademacher variables.

Write $P f = \mathbb{E}_{z \sim \mathcal{D}}[f(z)]$ for the population expectation and $P_n f = \frac{1}{n}\sum_{i=1}^n f(z_i)$ for the empirical expectation on $S$.

Definition

Ghost Sample

The ghost sample $S'$ is an independent copy of the training sample $S$, drawn from the same distribution $\mathcal{D}$. It is "ghost" because it does not actually need to be observed. It is a theoretical device used in the proof. The ghost sample replaces the intractable population expectation $Pf = \mathbb{E}[f]$ with a second empirical average $P'_n f = \frac{1}{n}\sum_i f(z'_i)$ that can be compared symmetrically with $P_n f$.

Definition

Symmetrization Gap

The symmetrization gap is the quantity:

$\mathbb{E}_S\!\left[\sup_{f \in \mathcal{F}} (Pf - P_n f)\right]$

This is the expected maximum deviation of the empirical average from the population mean, taken over the worst-case function in $\mathcal{F}$. It is the fundamental quantity that controls uniform convergence.

Main Theorems

Theorem

Symmetrization Inequality

Statement

Let $\mathcal{F}$ be a class of functions $f: \mathcal{Z} \to [0, 1]$ and let $S = (z_1, \ldots, z_n)$ be drawn i.i.d. from $\mathcal{D}$. Then:

$\mathbb{E}_S\!\left[\sup_{f \in \mathcal{F}} (Pf - P_n f)\right] \leq 2\,\mathfrak{R}_n(\mathcal{F})$

where $\mathfrak{R}_n(\mathcal{F}) = \mathbb{E}_{S, \sigma}\!\left[\sup_{f \in \mathcal{F}} \frac{1}{n}\sum_{i=1}^n \sigma_i f(z_i)\right]$ is the Rademacher complexity.

Intuition

The population expectation $Pf$ is an average over infinitely many points. The empirical expectation $P_n f$ is an average over $n$ points. The gap between them measures how much the finite sample misrepresents the truth.

Symmetrization bounds this gap by measuring how well $\mathcal{F}$ can correlate with random noise (Rademacher complexity). The logic: if the class cannot even fit random labels well, it certainly cannot overfit to the specific noise in the training data.

The factor of 2 is structural, not a proof artifact. It arises from two steps: (1) replacing $Pf$ with $P'_n f$ introduces one factor (bounding the difference of two empirical averages), and (2) dropping the ghost sample to get pure Rademacher averages introduces at most another factor (by the triangle inequality and symmetry of $\sigma_i$).

Proof Sketch

The proof has three steps:

Step 1 (Introduce ghost sample). Since $P'_n f$ is an unbiased estimate of $Pf$, by Jensen's inequality:

$\mathbb{E}_S\!\left[\sup_f (Pf - P_n f)\right] = \mathbb{E}_S\!\left[\sup_f (\mathbb{E}_{S'}[P'_n f] - P_n f)\right] \leq \mathbb{E}_{S, S'}\!\left[\sup_f (P'_n f - P_n f)\right]$

The inequality follows because the supremum of an expectation is at most the expectation of the supremum (Jensen for concave functions, applied in reverse).

Step 2 (Introduce Rademacher variables). Write the difference:

$P'_n f - P_n f = \frac{1}{n}\sum_{i=1}^n (f(z'_i) - f(z_i))$

For each $i$, the pair $(z_i, z'_i)$ is exchangeable (same distribution). So replacing $f(z'_i) - f(z_i)$ with $\sigma_i(f(z'_i) - f(z_i))$ for random signs $\sigma_i$ does not change the distribution:

$\mathbb{E}_{S, S'}\!\left[\sup_f \frac{1}{n}\sum_i (f(z'_i) - f(z_i))\right] = \mathbb{E}_{S, S', \sigma}\!\left[\sup_f \frac{1}{n}\sum_i \sigma_i(f(z'_i) - f(z_i))\right]$

Step 3 (Triangle inequality and drop ghost). By the triangle inequality:

$\sup_f \frac{1}{n}\sum_i \sigma_i(f(z'_i) - f(z_i)) \leq \sup_f \frac{1}{n}\sum_i \sigma_i f(z'_i) + \sup_f \frac{1}{n}\sum_i (-\sigma_i) f(z_i)$

Since $-\sigma_i$ has the same distribution as $\sigma_i$ and $S'$ has the same distribution as $S$:

$\mathbb{E}\!\left[\sup_f \frac{1}{n}\sum_i \sigma_i f(z'_i)\right] = \mathbb{E}\!\left[\sup_f \frac{1}{n}\sum_i \sigma_i f(z_i)\right] = \mathfrak{R}_n(\mathcal{F})$

Combining: $\leq 2\,\mathfrak{R}_n(\mathcal{F})$.

Why It Matters

This theorem is the bridge between the generalization gap (which involves the unknown distribution $\mathcal{D}$) and Rademacher complexity (which can be estimated from data). Every Rademacher-based generalization bound starts here:

1. Apply symmetrization to bound the expected gap by $2\mathfrak{R}_n(\mathcal{F})$
2. Apply McDiarmid's inequality to convert the expected bound into a high-probability bound
3. Bound $\mathfrak{R}_n(\mathcal{F})$ using structural properties of $\mathcal{F}$ (e.g., linear classifiers, kernel classes, neural networks)

Without symmetrization, there would be no way to connect the empirical performance on training data to the unknown population performance.

Failure Mode

The bound requires $\mathcal{F}$ to map into a bounded range (here $[0,1]$). For unbounded function classes, the ghost sample trick still works but the Rademacher complexity may not be finite. Also, the factor of 2 can be loose: for one-sided deviations, localized Rademacher complexity techniques can sometimes achieve a tighter constant.

Proposition

Desymmetrization (Converse Direction)

Statement

Under the same conditions, the Rademacher complexity is also bounded from above by the symmetrization gap (up to constants). Specifically:

$\mathfrak{R}_n(\mathcal{F}) \leq \mathbb{E}_S\!\left[\sup_{f \in \mathcal{F}} (Pf - P_n f)\right] + \frac{1}{\sqrt{n}}$

For large $n$, symmetrization and Rademacher complexity are equivalent up to lower-order terms as measures of the uniform convergence rate.

Intuition

Symmetrization is not a lossy reduction. The Rademacher complexity is, up to lower-order terms, equivalent to the expected uniform deviation. This means Rademacher complexity exactly characterizes the rate of uniform convergence, not just an upper bound on it.

Proof Sketch

The key idea is a "reverse" symmetrization. Starting from the Rademacher average $\frac{1}{n}\sum_i \sigma_i f(z_i)$, condition on the signs and use the fact that $\sigma_i f(z_i)$ has the same distribution as $f(z_i)$ minus a correction term. The $1/\sqrt{n}$ term comes from the difference between using the full population expectation and a single-sample estimate.

Why It Matters

This converse shows that Rademacher complexity is the right complexity measure for uniform convergence. It is both necessary and sufficient (up to lower-order terms): the generalization gap scales as $\Theta(\mathfrak{R}_n(\mathcal{F}))$, not just $O(\mathfrak{R}_n(\mathcal{F}))$.

Failure Mode

The converse requires $n \geq 2$ and the lower-order $1/\sqrt{n}$ term is not negligible for very small $n$. For practical purposes, the upper bound (symmetrization) is much more commonly used than the lower bound (desymmetrization).

The Symmetrization Template in Detail

Symmetrization is a proof template, not just a theorem. Here is the abstract pattern, which you will see instantiated in multiple contexts:

Input: A quantity $\Phi(S) = \sup_f (\mathbb{E}_\mathcal{D}[g(f, Z)] - \frac{1}{n}\sum_i g(f, z_i))$ involving the unknown distribution $\mathcal{D}$.

Template:

1. Ghost sample: Replace $\mathbb{E}_\mathcal{D}[g(f, Z)]$ with the empirical average on an independent sample $S'$. This is valid in expectation.

2. Exchangeability: Since $(z_i, z'_i)$ are exchangeable, introduce Rademacher signs $\sigma_i$ to randomly swap them. The distribution is unchanged.

3. Decouple: Use the triangle inequality to split the Rademacher sum into two terms, each depending on only one sample.

4. Result: $\mathbb{E}[\Phi(S)] \leq 2 \cdot \text{(Rademacher-type complexity)}$.

Where the factor of 2 comes from: Step 3 applies the triangle inequality to $\sigma_i(g(f, z'_i) - g(f, z_i))$, splitting it into $\sigma_i g(f, z'_i) + (-\sigma_i) g(f, z_i)$. Each half contributes one copy of the Rademacher complexity. The factor of 2 is the price of decoupling the two samples.

Symmetrization in Other Proofs

The same template appears in:

VC dimension proof. The classical proof of the VC generalization bound uses symmetrization to reduce the problem to bounding the probability that a function class shatters a random sample. The ghost sample is used to create a "double sample" of size $2n$, and Rademacher variables are replaced by random permutations.

Covering number bounds. The chaining argument for covering numbers starts with symmetrization to introduce Rademacher variables, then bounds the Rademacher complexity using the covering structure of $\mathcal{F}$.

U-statistics. Symmetrization techniques for U-statistics use "decoupling" (a generalization of the ghost sample trick) to reduce the analysis of dependent sums to independent sums.

Canonical Examples

Example

Symmetrization for a finite class

Let $|\mathcal{F}| = N$ with $f: \mathcal{Z} \to [0, 1]$. Symmetrization gives:

$\mathbb{E}_S[\sup_f (Pf - P_n f)] \leq 2\mathfrak{R}_n(\mathcal{F}) \leq 2\sqrt{\frac{2\log N}{n}}$

The second inequality uses the sub-Gaussian maximal inequality for Rademacher averages. Combined with McDiarmid's inequality, this yields the classical uniform convergence bound for finite classes.

Example

Why you cannot avoid the ghost sample

A tempting shortcut: directly bound $\sup_f (Pf - P_n f)$ without introducing $S'$. But $Pf$ depends on the unknown $\mathcal{D}$, so there is no way to relate the supremum to a computable quantity without first replacing $Pf$ by something empirical. The ghost sample is the minimal device that achieves this. Any bound on the generalization gap must implicitly or explicitly invoke a symmetrization-like argument.

Example

Tightness of the factor of 2

Consider $\mathcal{F} = \{f, -f\}$ where $f(z) = z$ for $z \in \{0, 1\}$ with $\Pr[z = 1] = 1/2$. Then $Pf = 1/2$ and $P_n f = \bar{z}$. The expected gap is $\mathbb{E}[\sup(|Pf - P_nf|, |P(-f) - P_n(-f)|)] = \mathbb{E}[|1/2 - \bar{z}|]$.

The Rademacher complexity is $\mathbb{E}[\frac{1}{n}|\sum_i \sigma_i z_i|]$. For this simple class, the factor of 2 in symmetrization is tight up to lower-order terms: the expected gap is approximately $\mathfrak{R}_n(\mathcal{F})$, not $2\mathfrak{R}_n(\mathcal{F})$. So the factor of 2 is sometimes conservative, but it cannot be improved to 1 in general.

Common Confusions

Watch Out

The ghost sample is a proof device, not a data requirement

Symmetrization does not require you to collect a second sample. The ghost sample $S'$ is a theoretical object used only in the proof. The final bound depends only on the original sample $S$ (through $\hat{\mathfrak{R}}_S$) or on the distribution (through $\mathfrak{R}_n$). No additional data is needed to apply the result.

Watch Out

Exchangeability is the key property, not independence

The swap trick in Step 2 uses the fact that $(z_i, z'_i)$ are exchangeable. swapping them does not change the joint distribution. This is stronger than just saying $z_i$ and $z'_i$ are identically distributed; it requires that the joint distribution is symmetric. For i.i.d. samples, this is automatic. For dependent samples (e.g., from a Markov chain), the standard symmetrization argument breaks down.

Watch Out

Symmetrization bounds the expected gap, not the gap itself

The symmetrization inequality bounds $\mathbb{E}_S[\sup_f (Pf - P_n f)]$, the expected worst-case gap. To get a high-probability bound (which is what you need in practice), you must combine symmetrization with a concentration inequality. typically McDiarmid's inequality applied to the function $\phi(S) = \sup_f (Pf - P_n f)$, which satisfies bounded differences with parameter $1/n$.

Summary

• Symmetrization is a proof template, not just a theorem
• Three steps: ghost sample, Rademacher signs, decouple via triangle inequality
• Result: $\mathbb{E}[\sup_f (Pf - P_n f)] \leq 2\mathfrak{R}_n(\mathcal{F})$
• The factor of 2 comes from decoupling the ghost sample and original sample
• The ghost sample is a theoretical device; no extra data is needed
• Symmetrization converts a problem about the unknown $\mathcal{D}$ into a problem about Rademacher averages (which are computable)
• Same template used in: VC dimension proofs, covering number arguments, U-statistic analysis
• Combine with McDiarmid for high-probability bounds

Exercises

ExerciseCore

Problem

Walk through the symmetrization argument for a class $\mathcal{F}$ containing a single function $f$. Show that in this case, the symmetrization bound reduces to controlling $\mathbb{E}[|Pf - P_n f|]$ and that the factor of 2 is unnecessary (the bound is $\leq \mathfrak{R}_n(\{f\}) + \mathfrak{R}_n(\{f\}) = 2\mathfrak{R}_n(\{f\})$ but actually $\leq \mathfrak{R}_n(\{f, -f\})$).

Hint

Reveal Solution

ExerciseAdvanced

Problem

Show that the symmetrization argument fails for dependent samples. Construct a concrete example where $z_1, z_2$ are identically distributed but not exchangeable, and the symmetrization bound gives a wrong result.

Hint

Reveal Solution

ExerciseResearch

Problem

The factor of 2 in symmetrization can sometimes be improved using local Rademacher complexity. State the local Rademacher complexity bound (without proof): for a class $\mathcal{F}$ of functions in $[0, 1]$, the expected supremum of $Pf - P_n f$ is bounded by the fixed point of the equation $r = c \cdot \mathbb{E}[\sup_{f: Pf^2 \leq r} \frac{1}{n}\sum_i \sigma_i f(z_i)]$. Explain intuitively why this can be tighter than $2\mathfrak{R}_n(\mathcal{F})$.

Hint

Reveal Solution

References

Canonical:

• Bartlett & Mendelson, "Rademacher and Gaussian Complexities" (JMLR 2002)
• van der Vaart & Wellner, Weak Convergence and Empirical Processes (1996), Chapter 2.3
• Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014), Chapter 26

Current:

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

• Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Chapter 11

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

Next Topics

Building on symmetrization:

• Algorithmic stability: generalization bounds that bypass symmetrization entirely, using properties of the learning algorithm instead of the function class
• Epsilon-nets and covering numbers: combining symmetrization with geometric covering arguments for continuous function classes