One-Sided and Two-Sided Symmetrization

Directional and Absolute Uniform Deviations

Uniform deviations compare empirical averages with population averages simultaneously over a function class. The direction of that comparison matters. A bound on the largest positive deviation $P f-P_n f$ is not automatically a bound on the largest absolute deviation: a function can have a large negative deviation even when its positive deviation is small. Symmetrization makes this distinction precise and shows where the constants in the two bounds come from.

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations with distribution $P$. For a measurable, $P$-integrable function $f$, write $P f=E[f(Z_1)]$ and $P_n f=n^{-1}\sum_{i=1}^n f(Z_i)$. We will work with a nonempty countable class $\mathcal F$ of measurable functions satisfying $|f(z)|\leq B$ for every $f\in\mathcal F$ and $z$, for some finite $B$. Countability ensures the suprema below are measurable; boundedness ensures the expectations exist. More general classes require suitable measurability and integrability conditions.

Definition: The one-sided uniform deviation is $\sup_{f\in\mathcal F}(P f-P_n f)$. The two-sided uniform deviation is $\sup_{f\in\mathcal F}|P f-P_n f|$. Define the negative-closed class $\mathcal F^{\pm}=\mathcal F\cup\{-f:f\in\mathcal F\}$.

For a fixed observed sample $Z_1,\ldots,Z_n$, let $\sigma_1,\ldots,\sigma_n$ be independent Rademacher signs, independent of the sample: each sign equals $1$ or $-1$ with probability $1/2$. The empirical Rademacher complexity is

\widehat{\mathfrak R}_n(\mathcal F) = E_{\sigma}\!\left[ \sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n \sigma_i f(Z_i) \,\middle|\, Z_1,\ldots,Z_n \right].

Its expectation over the sample is $\mathfrak R_n(\mathcal F)=E_Z[\widehat{\mathfrak R}_n(\mathcal F)]$. If $0\in\mathcal F$, both complexities are nonnegative. This condition will be useful when comparing the complexity of $\mathcal F^{\pm}$ with that of $\mathcal F$.

The One-Sided Bound

A ghost sample is an independent sample $Z_1',\ldots,Z_n'$ from the same distribution $P$, with empirical measure $P_n'$. The expected one-sided symmetrization bound replaces the unknown population average by this independent empirical average, then uses random signs to compare the two samples.

Theorem: Under the boundedness and measurability conditions above, $$ E\sup_{f\in\mathcal F}(P f-P_n f) \leq 2\mathfrak R_n(\mathcal F). $$ No assumption that $0\in\mathcal F$ is needed for this inequality.

Here is the full derivation. First, condition on $Z_1,\ldots,Z_n$. For each fixed $f$, $P f=E[P_n'f\mid Z_1,\ldots,Z_n]$. The supremum of expectations is at most the expectation of the supremum, so

E\sup_{f\in\mathcal F}(P f-P_n f) \leq E\sup_{f\in\mathcal F}(P_n'f-P_n f).

Now independently swap or do not swap each pair $(Z_i,Z_i')$, with the choice recorded by $\sigma_i$. The joint distribution of the paired observations is unchanged by these swaps. Consequently, the last expectation equals

E\sup_{f\in\mathcal F} \frac{1}{n}\sum_{i=1}^n \sigma_i\bigl(f(Z_i')-f(Z_i)\bigr).

For every realization of the samples and signs, the supremum of a sum is at most the sum of the suprema. Therefore this is at most

E\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n\sigma_i f(Z_i') + E\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n(-\sigma_i) f(Z_i).

Each term has expectation $\mathfrak R_n(\mathcal F)$: the ghost sample has the same distribution as the original sample, and $(-\sigma_1,\ldots,-\sigma_n)$ has the same distribution as $(\sigma_1,\ldots,\sigma_n)$. Adding the two terms proves the inequality. $\square$

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

Let $Z$ be Bernoulli with $P(Z=1)=1/2$, take $n=1$, and let $\mathcal F=\{0,f\}$, where $f(z)=z$. Then $P f=1/2$. The one-sided deviation is $\max(0,1/2-Z)$: it is $1/2$ when $Z=0$ and $0$ when $Z=1$. Hence

Expected deviation: $E\sup_{g\in\mathcal F}(P g-P_1g)=(1/2)(1/2)+(1/2)(0)=1/4$.

Expected Rademacher complexity: if $Z=0$, then $\sup_{g\in\mathcal F}\sigma g(Z)=0$; if $Z=1$, then $E_\sigma\max(0,\sigma)=1/2$. Averaging over $Z$ gives $\mathfrak R_1(\mathcal F)=(1/2)(0)+(1/2)(1/2)=1/4$.

The theorem gives $1/4\leq 2(1/4)=1/2$, which holds. The example also shows that the inequality need not be an equality.

Two-Sided Deviations and Negative Functions

Taking absolute values is equivalent to allowing either sign of each function's deviation. In fact,

\sup_{f\in\mathcal F}|P f-P_n f| = \sup_{g\in\mathcal F^{\pm}}(P g-P_n g).

For a given $f$, the two functions $f$ and $-f$ give deviations $P f-P_n f$ and $-(P f-P_n f)$. Their larger value is the absolute deviation. Applying the one-sided theorem to the negative-closed class therefore yields the two-sided bound.

Theorem: Under the same assumptions, $$ E\sup_{f\in\mathcal F}|P f-P_n f| \leq 2\mathfrak R_n(\mathcal F^{\pm}). $$ If $0\in\mathcal F$, then also $$ E\sup_{f\in\mathcal F}|P f-P_n f| \leq 4\mathfrak R_n(\mathcal F). $$

To see the role of the enlarged class, note that

\widehat{\mathfrak R}_n(\mathcal F^{\pm}) = E_\sigma\!\left[ \sup_{f\in\mathcal F} \left|\frac{1}{n}\sum_{i=1}^n\sigma_i f(Z_i)\right| \,\middle|\,Z_1,\ldots,Z_n \right].

Indeed, maximizing the signed sum over $f$ and $-f$ is the same as maximizing its absolute value over $f$. This proves the first bound by applying the one-sided theorem to $\mathcal F^{\pm}$. For the second bound, use $0\in\mathcal F$. Then, for every sample and signs, the two suprema $\sup_{f\in\mathcal F} n^{-1}\sum_i\sigma_i f(Z_i)$ and $\sup_{f\in\mathcal F} -n^{-1}\sum_i\sigma_i f(Z_i)$ are nonnegative. The maximum of two nonnegative numbers is at most their sum. Taking expectations, and using the symmetry of the signs for the second term, gives $\mathfrak R_n(\mathcal F^{\pm})\leq 2\mathfrak R_n(\mathcal F)$. Substitution proves the factor-four bound. $\square$

Worked Example: A Symmetric Function Class

Let $Z$ be equally likely to be $-1$ or $1$, let $n=1$, and set $g(z)=z$. Take $\mathcal F=\{0,g,-g\}$. Since $P g=0$, the two nonzero functions have deviations $-Z$ and $Z$. Thus the one-sided supremum and the two-sided supremum are both $1$ for every observation.

For any observed $Z$ and sign $\sigma$, the Rademacher supremum is $\max(0,\sigma Z,-\sigma Z)=1$. Therefore $\mathfrak R_1(\mathcal F)=1$. The class already contains its negatives, so $\mathcal F^{\pm}=\mathcal F$, and $\mathfrak R_1(\mathcal F^{\pm})=1$ as well. The one-sided bound is $1\leq2$, and the two-sided bound is also $1\leq2$. Because this class is symmetric, negative-closure introduces no additional complexity.

Worked Example: Why the Negative-Closed Class Matters

Let $Z$ be any random variable, take $n=1$, and let $\mathcal F=\{f\}$ consist only of the constant function $f(z)=1$. Then $P f=P_1 f=1$, so the absolute deviation is exactly $0$. But the ordinary Rademacher complexity is $E_\sigma[\sigma]=0$. It cannot, by itself, express the positive size of the signed sum after taking an absolute value.

The negative-closed class is $\mathcal F^{\pm}=\{f,-f\}$. For either sign $\sigma$, $\sup_{g\in\mathcal F^{\pm}}\sigma g(Z)=\max(\sigma,-\sigma)=1$. Hence $\mathfrak R_1(\mathcal F^{\pm})=1$, and the two-sided bound reads $0\leq2$. It is valid, though loose. This example shows why a two-sided statement needs a complexity that accounts for both signs; the one-sided complexity of an arbitrary class may miss that information entirely.

Comparing the Bounds

The constants summarize two distinct choices. For a directional supremum, the one-sided bound is $2\mathfrak R_n(\mathcal F)$. For absolute deviations, the direct bound is $2\mathfrak R_n(\mathcal F^{\pm})$. If the class contains zero, the latter is at most $4\mathfrak R_n(\mathcal F)$. When $\mathcal F$ is already closed under negation, the direct two-sided bound is again $2\mathfrak R_n(\mathcal F)$. Thus the factor four is a general comparison with the ordinary complexity, not a universal exact constant for every class.

Deviation being controlled	Complexity in the bound	Expected bound
One-sided: $\sup_f(P f-P_n f)$	$\mathfrak R_n(\mathcal F)$	$2\mathfrak R_n(\mathcal F)$
Two-sided: $\sup_f\|P f-P_n f\|$	$\mathfrak R_n(\mathcal F^{\pm})$	$2\mathfrak R_n(\mathcal F^{\pm})$
Two-sided, with $0\in\mathcal F$	$\mathfrak R_n(\mathcal F)$	$4\mathfrak R_n(\mathcal F)$

Common Pitfall and Practical Use

A common mistake is to replace $\sup_f|P f-P_n f|$ by $\sup_f(P f-P_n f)$ without changing the bound. The latter only controls positive deviations. A class can have no large positive deviation while still containing a function with a large negative deviation. The correction is to use $\mathcal F^{\pm}$, or to establish separately that the class is symmetric so that the absolute supremum is represented already.

The one-sided result is useful when the direction of interest is fixed, as in controlling $P f-P_n f$ for every function in a class. Absolute uniform convergence requires the two-sided form. Before applying either inequality, check the sign convention in the deviation, whether zero belongs to the class, and whether the complexity is computed for $\mathcal F$ or for its negative-closed enlargement. These checks prevent a missing factor or an unjustified change from directional to absolute control.

Check Your Understanding

For each question, identify which class and which symmetrization bound are appropriate.

State the one-sided expected symmetrization inequality and identify the source of its factor of two.
Why does the two-sided bound involve $\mathcal F^{\pm}$? Express its Rademacher complexity using an absolute value inside the supremum.
Under what condition can $2\mathfrak R_n(\mathcal F^{\pm})$ be bounded by $4\mathfrak R_n(\mathcal F)$?
If $\mathcal F$ is already closed under negation, what is the two-sided bound in terms of $\mathfrak R_n(\mathcal F)$?
For a class containing only the constant function $f=1$ and $n=1$, calculate $\mathfrak R_1(\mathcal F)$ and $\mathfrak R_1(\mathcal F^{\pm})$. Why do these values illustrate the need for negative functions in a two-sided bound?

Deviation being controlled	Complexity in the bound	Expected bound
One-sided: \(\sup_f(P f-P_n f)\)	\(\mathfrak R_n(\mathcal F)\)	\(2\mathfrak R_n(\mathcal F)\)
Two-sided: \(\sup_f\|P f-P_n f\|\)	\(\mathfrak R_n(\mathcal F^{\pm})\)	\(2\mathfrak R_n(\mathcal F^{\pm})\)
Two-sided, with \(0\in\mathcal F\)	\(\mathfrak R_n(\mathcal F)\)	\(4\mathfrak R_n(\mathcal F)\)