Rademacher Complexity Bounds for Uniform Deviations

From Uniform Deviations to Rademacher Complexity

A uniform deviation asks how far empirical averages can depart from their population averages when we look across an entire function class. Symmetrization turns this question into one about signed sums evaluated on the observed sample. The signs measure how richly the class can adapt to a particular sample, which is why the resulting quantity is useful for assessing the size of uniform fluctuations.

The factor of two in the expected symmetrization bound comes from comparing the sample with an independent copy. It is important, however, to match the form of the deviation to the class used in the complexity: a one-sided supremum and a supremum of absolute deviations need not be controlled by the same expression unless the class includes both signs of each function.

Definition: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations with common distribution $P$. For a measurable function $f$, write $Pf=E[f(Z)]$ and $P_n f=n^{-1}\sum_{i=1}^n f(Z_i)$. Let $\mathcal F$ be a nonempty countable class of measurable functions with $|f(z)|\le B$ for every $f\in\mathcal F$ and $z$. If $\varepsilon_1,\ldots,\varepsilon_n$ are independent Rademacher signs, independent of the observations, so $P(\varepsilon_i=1)=P(\varepsilon_i=-1)=1/2$, the expected Rademacher complexity is $$ \mathfrak R_n(\mathcal F) = E_{Z,\varepsilon}\left[ \sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n\varepsilon_i f(Z_i) \right]. $$

The normalization $1/n$ is part of this definition. The countability and boundedness assumptions ensure that the suprema are measurable and integrable, so the expectations and inequalities below are well-defined. The results also hold under suitable measurable-separability and integrability conditions, but the countable bounded setting is sufficient to show the main argument without additional technical machinery.

For a given sample, the signed supremum is the largest average signed sum the class can produce. It is not generally the same as the supremum of the absolute signed sums. In particular, changing $\mathcal F$ to include $-f$ for every $f$ changes the supremum into an absolute-value supremum.

The Expected Symmetrization Bound

Theorem (expected symmetrization inequality): Under the assumptions above, $$ E\left[\sup_{f\in\mathcal F}(Pf-P_n f)\right] \le 2\mathfrak R_n(\mathcal F). $$

This is a one-sided bound: it controls the largest population-minus-empirical deviation. The proof uses a second, independent sample, then randomizes which observation in each pair is assigned a positive sign. Finally, it separates the two resulting signed sums.

Introduce a ghost sample.
Let $Z'_1,\ldots,Z'_n$ be an independent sample from $P$, and write $P'_n f=n^{-1}\sum_{i=1}^n f(Z'_i)$.

Use conditional expectation.
For a fixed observed sample, $Pf=E[P'_n f\mid Z_1,\ldots,Z_n]$. Taking a supremum after this expectation gives an upper bound by the conditional expectation of the supremum.

Swap each pair at random.
The joint distribution of $(Z_i,Z'_i)$ is unchanged by swapping its entries. Independent Rademacher signs encode these swaps in the difference $P'_n f-P_n f$.

Separate the two samples.
The supremum of a sum is at most the sum of the two suprema. Each resulting expected supremum equals $\mathfrak R_n(\mathcal F)$.

Here is the complete argument. Conditional on $Z_1,\ldots,Z_n$, each $P'_n f$ has expectation $Pf$. Since the class is countable, the supremum is measurable, and $$ \sup_{f\in\mathcal F}(Pf-P_n f) = \sup_{f\in\mathcal F}E[P'_n f-P_n f\mid Z_1,\ldots,Z_n] \le E\left[\sup_{f\in\mathcal F}(P'_n f-P_n f)\mid Z_1,\ldots,Z_n\right]. $$ Taking expectations yields $$ E\left[\sup_{f\in\mathcal F}(Pf-P_n f)\right] \le E\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n(f(Z'_i)-f(Z_i))\right]. $$ For each $i$, exchanging $Z_i$ and $Z'_i$ changes the sign of $f(Z'_i)-f(Z_i)$. Because the pairs are independent and each pair has a distribution invariant under exchange, the last expectation is unchanged if each difference is multiplied by an independent sign $\varepsilon_i$. Therefore it equals $$ E\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n \varepsilon_i(f(Z'_i)-f(Z_i))\right]. $$ For any two indexed collections of real numbers $a_f,b_f$, $\sup_f(a_f+b_f)\le \sup_f a_f+\sup_f b_f$. Applying this inequality gives an upper bound of $$ E\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n\varepsilon_i f(Z'_i)\right] + E\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n(-\varepsilon_i) f(Z_i)\right]. $$ The first expectation is $\mathfrak R_n(\mathcal F)$, since the ghost sample has the same distribution as the original sample. The second is also $\mathfrak R_n(\mathcal F)$, since $(-\varepsilon_1,\ldots,-\varepsilon_n)$ has the same distribution as $(\varepsilon_1,\ldots,\varepsilon_n)$. Adding them proves the theorem. $\square$

Absolute Deviations and Symmetric Classes

The theorem bounds $Pf-P_n f$, not directly $|P_n f-Pf|$. To handle absolute deviations, define the enlarged class $\mathcal F^\pm=\mathcal F\cup\{-f:f\in\mathcal F\}$. It contains both directions of every deviation.

Corollary: Under the theorem’s assumptions, $$ E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le 2\mathfrak R_n(\mathcal F^\pm). $$ If $\mathcal F$ is already symmetric, meaning $f\in\mathcal F$ implies $-f\in\mathcal F$, then $\mathcal F^\pm=\mathcal F$, and the right-hand side is $2\mathfrak R_n(\mathcal F)$.

To verify the corollary, for each $f\in\mathcal F$, the two functions $f$ and $-f$ give the deviations $P_n f-Pf$ and $-(P_n f-Pf)$. Consequently, $$ \sup_{g\in\mathcal F^\pm}(Pg-P_n g) = \sup_{f\in\mathcal F}|P_n f-Pf|. $$ Apply the theorem to $\mathcal F^\pm$ to obtain the stated inequality. If $\mathcal F$ is symmetric, adding its negatives adds no functions, so its complexity can be used directly. $\square$

There is also a useful interpretation of the complexity in this symmetric case. For each fixed sample and signs, the supremum over $f$ and $-f$ is the absolute value of the signed sum. Thus symmetry makes the signed complexity an expected supremum of absolute signed averages without changing the definition.

Worked Examples

Worked Example: A Bernoulli Indicator and a One-Sided Bound

Let $Z$ be Bernoulli with $P(Z=1)=p$, where $0\le p\le1$, and take $\mathcal F=\{0,f\}$ with $f(z)=z$. Use a sample of size $n=1$. Calculate the expected Rademacher complexity and the expected one-sided deviation.

For a single observation and sign, the supremum in the complexity is $\max(0,\varepsilon Z)$. It equals 1 exactly when $Z=1$ and $\varepsilon=1$, an event of probability $p/2$, and is 0 otherwise. Hence $$ \mathfrak R_1(\mathcal F)=\frac p2. $$

Here $Pf=p$ and $P_1f=Z$. Since the zero function is in the class, the one-sided supremum is $\max(0,p-Z)$. It equals $p$ when $Z=0$, and 0 when $Z=1$. Therefore $$ E\left[\sup_{g\in\mathcal F}(Pg-P_1g)\right] =(1-p)p+ p\cdot 0 =p(1-p) \le p =2\mathfrak R_1(\mathcal F). $$ This verifies the theorem’s bound for every $p\in[0,1]$.

Worked Example: Absolute Deviation Requires Both Signs

Continue with $Z\sim\operatorname{Bernoulli}(p)$, but use $\mathcal F^\pm=\{0,f,-f\}$, with $f(z)=z$, and $n=1$. Find the absolute-deviation bound explicitly.

For the complexity, the signed supremum is $\max(0,\varepsilon Z,-\varepsilon Z)$. If $Z=1$, this equals 1 for either value of $\varepsilon$; if $Z=0$, it equals 0. Thus $$ \mathfrak R_1(\mathcal F^\pm)=p. $$ The absolute deviation is $|Z-p|$. When $Z=0$ it is $p$; when $Z=1$ it is $1-p$. Its expectation is $$ E[|Z-p|]=(1-p)p+p(1-p)=2p(1-p)\le 2p =2\mathfrak R_1(\mathcal F^\pm). $$ The absolute-value version uses the enlarged class, not the one-sided class $\{0,f\}$.

Worked Example: Checking the Signs in a Two-Observation Calculation

Let the observation be deterministic, and let $f$ equal 1 at that observation. For $n=2$, take $\mathcal F^\pm=\{0,f,-f\}$. Calculate the complexity and compare it with the uniform absolute deviation.

The signed average of $f$ is $(\varepsilon_1+\varepsilon_2)/2$, while that of $-f$ is its negative. Including the zero function, the supremum is therefore $$ \max\left(0,\frac{\varepsilon_1+\varepsilon_2}{2}, -\frac{\varepsilon_1+\varepsilon_2}{2}\right) = \frac{|\varepsilon_1+\varepsilon_2|}{2}. $$ For sign pairs $(1,1),(1,-1),(-1,1),(-1,-1)$, these values are respectively $1,0,0,1$. Averaging all four gives $$ \mathfrak R_2(\mathcal F^\pm)=\frac{1+0+0+1}{4}=\frac12. $$ The empirical average of $f$ and its population average are both 1, so every deviation is zero. The bound reads $$ E\left[\sup_{g\in\mathcal F^\pm}|P_2g-Pg|\right] =0 \le 2\mathfrak R_2(\mathcal F^\pm)=1. $$ In particular, when both signs are negative, the contribution from $-f$ makes the supremum equal to 1; omitting that function would give an incorrect complexity.

Why the Bound Matters—and a Common Pitfall

Expected Rademacher complexity gives a data-adaptive measure of how large signed fluctuations can be across a class. The symmetrization inequality connects that measure to the expected uniform empirical deviation without requiring a separate deviation calculation for every function. The factor of two comes from the two samples in the proof; it is not a claim that the complexity itself is a uniform-deviation quantity.

Common mistake: writing $E[\sup_f|P_n f-Pf|]\le 2\mathfrak R_n(\mathcal F)$ for an arbitrary class, using the signed supremum in the definition of $\mathfrak R_n$. This reasoning silently treats the supremum of signed sums as though it also included their negatives. The correction is to apply the theorem to $\mathcal F^\pm$, which yields $2\mathfrak R_n(\mathcal F^\pm)$, or to verify that the original class is symmetric. The distinction is substantive: the two-sided supremum can be larger than the one-sided one.

Before using a complexity bound, check three items: whether the deviation is one-sided or absolute, whether the class contains the needed sign reversals, and whether the complexity uses the same normalization $1/n$ as the empirical averages. These checks prevent a correct symmetrization argument from being applied to the wrong quantity.

Check Your Understanding

Try to answer each question by identifying the class and the direction of deviation involved.

State the expected symmetrization inequality for a one-sided uniform deviation.
What assumptions in this tutorial ensure that the relevant suprema are measurable and integrable?
Why does the proof introduce an independent sample, and where does the factor of two enter?
How should the class be changed to obtain a bound for $E[\sup_{f\in\mathcal F}|P_n f-Pf|]$?
For a symmetric class, explain why the signed supremum is also a supremum of absolute signed averages.
In the two-observation example with $\mathcal F^\pm=\{0,f,-f\}$, why is the complexity $1/2$, rather than $1/4$?