Conditional and Expected Rademacher Complexity

Why Distinguish the Two Complexities?

Rademacher complexity measures how well a function class can align with random signs on a sample. But there are two different questions one might ask. After observing the inputs, how much sign-based flexibility does this particular sample permit? Before observing them, what is the average of that quantity over repeated samples? These questions lead to a conditional, sample-dependent complexity and an expected, distribution-dependent complexity.

The distinction matters in generalization analysis. A bound involving the conditional quantity can reflect the inputs actually observed. Its expectation instead summarizes behavior across samples drawn from a specified distribution. The expected value is useful for average-case statements, but it does not tell us the conditional value for a particular data set.

Definition: Conditional and Expected Complexity

Let $X_1,\ldots,X_n$ be independent and identically distributed inputs with distribution $P$, and write $S=(X_1,\ldots,X_n)$. Let $\mathcal F$ be a nonempty countable class of measurable real-valued functions on the input space, with $|f(x)|\le B$ for every $f\in\mathcal F$ and every $x$, where $B<\infty$. Countability ensures that the suprema below are measurable; boundedness ensures that all expectations exist. Let $\sigma_1,\ldots,\sigma_n$ be independent Rademacher signs, independent of the inputs: each sign is $+1$ or $-1$, each with probability $1/2$.

Definition: The conditional empirical Rademacher complexity of $\mathcal F$ on the observed sample $S$ is $$ \widehat{\mathfrak R}_S(\mathcal F) = E_\sigma\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n \sigma_i f(X_i)\,\middle|\,S\right]. $$ Since the signs are independent of $S$, this conditional expectation averages over the signs while holding the observed inputs fixed. The expected, or population-level, Rademacher complexity at sample size $n$ is $$ \mathfrak R_n(\mathcal F;P) = E_S\!\left[\widehat{\mathfrak R}_S(\mathcal F)\right]. $$

The supremum is taken over the same function class in both definitions. What changes is which randomness is being averaged over. In $\widehat{\mathfrak R}_S(\mathcal F)$, the inputs are fixed and only the signs are averaged. In $\mathfrak R_n(\mathcal F;P)$, the input sample is averaged as well, so the result depends on $P$ and $n$, but is no longer a function of the realized sample.

These definitions use the non-absolute convention: the supremum is of the signed average, not of its absolute value. Other conventions are possible, but switching between them changes the quantity and its calculations.

What Averaging the Conditional Complexity Gives

Theorem: Under the boundedness and measurability assumptions above, $$ \mathfrak R_n(\mathcal F;P) = E_{S,\sigma}\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n \sigma_i f(X_i)\right]. $$ Thus the expected complexity is the joint expectation over the input sample and the independent signs of the same supremum used in the conditional definition.

Proof. For each fixed input sample $S$, the conditional complexity is the expectation of the displayed supremum over the signs. The supremum is measurable because $\mathcal F$ is countable. Also, for every realization of $S$ and the signs, $$ \left|\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n \sigma_i f(X_i)\right|\le B. $$ The random variable is therefore integrable. The law of total expectation, or equivalently Fubini's theorem for this bounded measurable function under the product distribution of $S$ and $\sigma$, gives $$ E_S\!\left[E_\sigma\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n \sigma_i f(X_i)\,\middle|\,S\right]\right] = E_{S,\sigma}\left[\sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n \sigma_i f(X_i)\right]. $$ The left-hand side is the definition of $\mathfrak R_n(\mathcal F;P)$, proving the identity. $\square$

Worked Example: A Class That Detects One Input Region

Let the input space be $\{a,b\}$, with $P(X=a)=p$ and $P(X=b)=1-p$. Take $n=1$, let $g(x)=\mathbf 1\{x=a\}$, and let $\mathcal F=\{g,-g\}$. Compute the conditional complexity and its expectation.

For a fixed observed input $X_1$, the two candidate signed values are $\sigma_1 g(X_1)$ and $-\sigma_1 g(X_1)$. Their supremum is $|g(X_1)|$, whatever the sign. Consequently, $$ \widehat{\mathfrak R}_{(X_1)}(\mathcal F)=|g(X_1)|=\mathbf 1\{X_1=a\}. $$ If the observed input is $a$, the conditional complexity is $1$; if it is $b$, it is $0$. Averaging over the input gives $$ \mathfrak R_1(\mathcal F;P)=E[\mathbf 1\{X_1=a\}]=p. $$ The population-level value $p$ is the average of sample-specific values $1$ and $0$, not necessarily the value for any particular observed input.

Worked Example: A Singleton Class Has Zero Complexity

Let the input space be arbitrary, take $n=1$, and let $\mathcal F=\{f\}$ contain just the constant function $f(x)=1$. For any observed input, the supremum over a singleton contains only $\sigma_1$, so $$ \widehat{\mathfrak R}_S(\mathcal F)=E_{\sigma_1}[\sigma_1] =\frac12(1)+\frac12(-1)=0. $$ The value does not depend on $S$, and hence $\mathfrak R_1(\mathcal F;P)=0$ for every $P$. This does not mean that the function's values are small: they are all $1$. It means that the non-absolute signed average for this singleton has mean zero. Replacing the supremum by a supremum of absolute values would give a different quantity.

A Bound and a Nonnegativity Property

Result: With a nonempty class of functions bounded in absolute value by $B$, both the conditional and expected complexities satisfy $$ 0\le \widehat{\mathfrak R}_S(\mathcal F)\le B, \qquad 0\le \mathfrak R_n(\mathcal F;P)\le B. $$

Proof. For any fixed input sample and any sign vector, each function satisfies $$ -B \le \frac{1}{n}\sum_{i=1}^n \sigma_i f(X_i) \le B. $$ Taking the supremum preserves the upper bound $B$, so averaging over signs gives $\widehat{\mathfrak R}_S(\mathcal F)\le B$.

For the lower bound, fix any $f_0\in\mathcal F$. For every sign vector, the supremum over $\mathcal F$ is at least the signed average for $f_0$. Thus $$ \widehat{\mathfrak R}_S(\mathcal F) \ge E_\sigma\left[\frac{1}{n}\sum_{i=1}^n \sigma_i f_0(X_i)\,\middle|\,S\right] = \frac{1}{n}\sum_{i=1}^n f_0(X_i)E[\sigma_i] =0. $$ Here $E[\sigma_i]=0$ for each $i$. Averaging both bounds over $S$ gives the claimed bounds on $\mathfrak R_n(\mathcal F;P)$. $\square$

Nonnegativity does not require that the zero function belong to $\mathcal F$. It follows because the supremum is at least as large as the signed average for any one fixed member, whose expectation over the mean-zero signs is zero. The singleton example shows that the lower bound can be attained.

Worked Example: Conditional Values and Their Population Average

Continue with the input space $\{a,b\}$ and $P(X=a)=p$, but now take $n=2$, $g(x)=\mathbf 1\{x=a\}$, and $\mathcal F=\{g,-g\}$. Let $K$ be the number of observed inputs equal to $a$. For a fixed sample, the supremum over the two functions is $$ \sup_{f\in\mathcal F}\frac12\sum_{i=1}^2\sigma_i f(X_i) = \frac12\left|\sum_{i=1}^2\sigma_i g(X_i)\right|. $$ If $K=0$, the sum is always zero, so $\widehat{\mathfrak R}_S(\mathcal F)=0$. If $K=1$, its absolute value is always $1$, giving conditional complexity $1/2$. If $K=2$, the sum is $\sigma_1+\sigma_2$. Its absolute value is $2$ for two of the four equally likely sign pairs and $0$ for the other two; its expectation is $1$, again giving conditional complexity $1/2$.

Since $K$ has a binomial distribution with two trials and success probability $p$, the expected complexity is $$ \mathfrak R_2(\mathcal F;P) = P(K=1)\frac12+P(K=2)\frac12 = 2p(1-p)\frac12+p^2\frac12 = p-\frac{p^2}{2}. $$ For example, if $p=1/2$, the conditional complexity is $0$ when both inputs are $b$, and $1/2$ for the other three possible input patterns. Its population average is $1/4+1/8=3/8$, which also agrees with $p-p^2/2=1/2-1/8=3/8$.

How to Use the Two Quantities

The conditional complexity is a function of the observed inputs. It can distinguish samples on which a class has different opportunities to align with the signs. For the two-point example, samples containing no $a$'s have conditional complexity zero, while samples containing at least one $a$ have complexity $1/2$. The expected complexity averages over this variation according to $P$.

Use the conditional quantity when the statement or calculation concerns a particular observed design or input sample. Use the expected quantity when averaging over repeated draws from a specified input distribution. Neither quantity should be substituted for the other without justification: an average over samples does not identify the value for the sample in hand. Their shared role is to summarize how rich a function class appears under random signs; their different roles come from which randomness remains unaveraged.

Common Mistake

A common error is to call $\widehat{\mathfrak R}_S(\mathcal F)$ the expectation over both the data and the signs, then treat it as a fixed population number. That removes the conditioning on $S$, and is instead the expected complexity $\mathfrak R_n(\mathcal F;P)$. The correction is to state explicitly which inputs are fixed: conditional empirical complexity averages only over signs at the observed sample, while expected complexity also averages over the random sample.

Key takeaway: Conditional empirical Rademacher complexity is sample-dependent; expected Rademacher complexity is its average under the input-sampling distribution. The latter equals the joint expectation over inputs and signs, but does not determine the former for a particular sample.

Check Your Understanding

Use the non-absolute convention in the definitions above.

Which randomness is averaged over in conditional empirical Rademacher complexity, and which additional randomness is averaged over in expected complexity?
For $n=1$ and $\mathcal F=\{g,-g\}$, express the conditional complexity in terms of $g(X_1)$.
Why is the expected complexity at most $B$ when every function in the class is bounded in absolute value by $B$?
In the two-input worked example with $n=2$, what is the conditional complexity when both observed inputs equal $b$, and why?
Why can a singleton class of constant functions have zero non-absolute Rademacher complexity even though its function values are nonzero?