Finite-Class Bounds from Rademacher Complexity

Why Finite Classes Admit a Logarithmic Complexity Bound

Suppose a learning procedure compares a finite collection of candidate functions using data drawn from an unknown distribution. The empirical average of each function is random, and the quantity of interest is often the largest discrepancy between an empirical average and its population expectation. Bounding this discrepancy simultaneously over the whole collection is harder than bounding it for one fixed function, but the cost of considering $M$ functions grows only as $\sqrt{\log M}$, rather than linearly in $M$.

The route to this result has two parts. Symmetrization replaces deviations from unknown expectations by differences involving an independent sample. Rademacher signs then express the fluctuation of those differences. For a finite class, a moment-generating-function argument controls the largest signed sum. Together these steps give an expected uniform-deviation bound of order $\sqrt{\log M/n}$.

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed observations with distribution $P$. For an integrable function $f$, write $Pf=E[f(X)]$ and $P_n f=n^{-1}\sum_{i=1}^n f(X_i)$. The uniform deviation of a finite class $\mathcal F$ is $\sup_{f\in\mathcal F}|P_n f-Pf|$. Its expected uniform deviation is $E[\sup_{f\in\mathcal F}|P_n f-Pf|]$.

Throughout, assume $\mathcal F$ is a nonempty finite class of $M$ measurable functions and that $|f(x)|\le B$ for every $f\in\mathcal F$ and every $x$, where $B>0$. Boundedness ensures integrability, and finiteness ensures that all suprema below are measurable. Let $\sigma_1,\ldots,\sigma_n$ be independent Rademacher signs, independent of the data: each sign equals $1$ or $-1$, each with probability $1/2$.

Definition: For a fixed observed sample $x_1,\ldots,x_n$, the conditional two-sided Rademacher complexity is $$ \widehat{\mathfrak R}^{\,\pm}_n(\mathcal F;x_1,\ldots,x_n) =E_\sigma\left[\sup_{f\in\mathcal F}\left|\frac{1}{n}\sum_{i=1}^n\sigma_i f(x_i)\right|\right]. $$ The expected two-sided Rademacher complexity is $\mathfrak R^{\,\pm}_n(\mathcal F)=E_X[\widehat{\mathfrak R}^{\,\pm}_n(\mathcal F;X_1,\ldots,X_n)]$.

From Uniform Deviations to Rademacher Complexity

The first result is the expected symmetrization inequality. It says that the expected uniform deviation is at most twice the expected two-sided Rademacher complexity. The factor two arises because a ghost-sample difference contains one signed sum from each of two samples.

Theorem: Under the assumptions above, $$ E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le 2\mathfrak R^{\,\pm}_n(\mathcal F). $$

Introduce a ghost sample.
Let $X'_1,\ldots,X'_n$ be an independent sample from $P$, and write $P'_n f=n^{-1}\sum_i f(X'_i)$. For each fixed original sample, $Pf=E_{X'}[P'_n f]$.

Use convexity of the supremum.
Conditional Jensen's inequality bounds the original supremum by the conditional expectation of the supremum of the two-sample difference.

Insert signs and separate the samples.
Swapping each pair $(X_i,X'_i)$ leaves its joint distribution unchanged. The triangle inequality then produces two equal Rademacher terms.

For completeness, condition on $X_1,\ldots,X_n$. For every $f$, $P_n f-Pf=E_{X'}[P_n f-P'_n f\mid X_1,\ldots,X_n]$. Since the class is finite, the supremum commutes with no problematic measurability operation, and

\sup_{f\in\mathcal F}|P_n f-Pf| \le E_{X'}\left[\sup_{f\in\mathcal F}|P_n f-P'_n f|\mid X_1,\ldots,X_n\right].

After taking expectations, consider the differences $f(X_i)-f(X'_i)$. The pairs $(X_i,X'_i)$ are independent across $i$, and each pair has the same distribution after its two entries are swapped. Consequently, multiplying each difference by an independent sign $\sigma_i$ does not change the joint distribution of the vector of differences, simultaneously for every $f$. Therefore

E\sup_f\left|\frac{1}{n}\sum_i(f(X_i)-f(X'_i))\right| = E\sup_f\left|\frac{1}{n}\sum_i\sigma_i(f(X_i)-f(X'_i))\right|.

For each realization of the samples and signs, the triangle inequality gives

\sup_f\left|\frac{1}{n}\sum_i\sigma_i(f(X_i)-f(X'_i))\right| \le \sup_f\left|\frac{1}{n}\sum_i\sigma_i f(X_i)\right| + \sup_f\left|\frac{1}{n}\sum_i\sigma_i f(X'_i)\right|.

The two terms on the right have the same expectation, each equal to $\mathfrak R^{\,\pm}_n(\mathcal F)$. Combining the inequalities proves the theorem. $\square$

A Finite-Class Estimate

For a finite class, the Rademacher complexity itself has a direct upper bound. The absolute value in its definition means that each function contributes both a signed sum and its negative. That is why the logarithm involves $2M$, not just $M$.

Theorem: If $\mathcal F$ contains $M\ge1$ functions and $|f(x)|\le B$, then for every fixed sample, $$ \widehat{\mathfrak R}^{\,\pm}_n(\mathcal F;x_1,\ldots,x_n) \le B\sqrt{\frac{2\log(2M)}{n}}. $$ Consequently, $$ E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le 2B\sqrt{\frac{2\log(2M)}{n}}. $$

Here is a proof of the finite-class estimate. Fix the sample and let $S_f=\sum_{i=1}^n\sigma_i f(x_i)$. The supremum of $|S_f|$ over $f$ is the maximum of $2M$ signed sums, namely $S_f$ and $-S_f$ for each $f$. For any real $\lambda>0$, the inequality $\cosh(u)\le e^{u^2/2}$ implies

E_\sigma[e^{\lambda S_f}] =\prod_{i=1}^n\cosh(\lambda f(x_i)) \le \exp\left(\frac{\lambda^2}{2}\sum_{i=1}^n f(x_i)^2\right) \le \exp\left(\frac{\lambda^2 B^2 n}{2}\right).

The same bound holds for $-S_f$. For the maximum $Z=\max_{f\in\mathcal F}\max(S_f,-S_f)$, the exponential of the maximum is at most the sum of the exponentials. Jensen's inequality for the exponential therefore yields

e^{\lambda E_\sigma[Z]} \le E_\sigma[e^{\lambda Z}] \le 2M\exp\left(\frac{\lambda^2B^2n}{2}\right), \qquad E_\sigma[Z]\le\frac{\log(2M)}{\lambda}+\frac{\lambda B^2n}{2}.

Choosing $\lambda=\sqrt{2\log(2M)/(B^2n)}$ minimizes the final expression and gives $E_\sigma[Z]\le B\sqrt{2n\log(2M)}$. Dividing by $n$ proves the conditional complexity bound. Taking expectation over the sample preserves the bound, and the expected symmetrization inequality gives the stated uniform-deviation result. $\square$

Worked Examples

Worked Example: Bounded Classification Losses

A procedure compares $M=32$ candidate classifiers using a loss that takes values in $[0,1]$, so $B=1$. With $n=500$ independent observations, the theorem gives $$ E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le 2\sqrt{\frac{2\log(64)}{500}}. $$ Since $\log(64)\approx4.1589$, the quantity inside the square root is $8.3178/500=0.0166356$. Its square root is approximately $0.1290$, giving an upper bound of approximately $0.2580$. This is an expected bound applying to all 32 loss functions at once; it is not a separate bound for just one prespecified classifier.

Worked Example: A Class Bounded by Two

Suppose four candidate functions satisfy $|f(x)|\le2$ and are evaluated on $n=200$ observations. Here $M=4$, $B=2$, and $2M=8$. Thus $$ E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le 4\sqrt{\frac{2\log(8)}{200}}. $$ Using $\log(8)\approx2.0794$, the fraction inside the square root is $4.1588/200=0.020794$, whose square root is approximately $0.1442$. The resulting upper bound is $4(0.1442)\approx0.5768$. The factor $B=2$ matters: doubling the uniform bound on function magnitudes doubles this guarantee.

Worked Example: Computing a Conditional Complexity Exactly

Let the class consist of two functions $\mathcal F=\{f,-f\}$, and consider a fixed sample of size four on which the values of $f$ are $1,1,0,0$. For either function, taking the absolute value makes the signed sum the same, so the conditional two-sided complexity is $$ \frac{1}{4}E_\sigma|\sigma_1+\sigma_2|. $$ The sum $\sigma_1+\sigma_2$ equals $2$ with probability $1/4$, $0$ with probability $1/2$, and $-2$ with probability $1/4$. Therefore $E_\sigma|\sigma_1+\sigma_2|=2(1/4)+0(1/2)+2(1/4)=1$, and the conditional complexity is $1/4$. This exact calculation can be much smaller than the generic finite-class bound $ \sqrt{2\log(4)/4}\approx0.833$. The finite-class estimate is uniform over all possible samples and coefficient patterns, so it need not be sharp for a particular observed sample.

Interpretation and a Common Pitfall

The bound $$ E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le 2B\sqrt{\frac{2\log(2M)}{n}} $$ displays two separate costs. The magnitude bound $B$ scales the fluctuations, while the number of candidates enters only through $\log(2M)$. At fixed $M$ and $B$, the guarantee decreases at rate $n^{-1/2}$. Increasing the class size by a fixed multiplicative factor increases the logarithm modestly, rather than multiplying the error bound by that factor.

For a finite class of losses, this result can be applied by taking $f$ to be the loss associated with each candidate. It controls the largest empirical-to-population loss discrepancy in expectation. It does not assert that every particular realized sample has small discrepancy, and it is not itself a high-probability statement.

Pitfall: dropping the two-sided factor. For a one-sided maximum, one may count $M$ signed sums. Here the target contains absolute values, so both $S_f$ and $-S_f$ must be included. The proof therefore counts $2M$ possibilities.
Pitfall: using the bound without a common envelope. The stated estimate needs one finite $B$ that bounds every function throughout the domain. If some functions are unbounded, this proof does not establish the result.
Pitfall: treating the generic bound as an exact complexity. The finite-class estimate is an upper bound. The conditional complexity may be smaller, as the preceding calculation shows.

Key takeaway: Ghost-sample symmetrization bounds expected uniform deviation by twice the expected two-sided Rademacher complexity. For $M$ functions uniformly bounded in magnitude by $B$, a finite-class exponential-moment argument then gives the rate $2B\sqrt{2\log(2M)/n}$.

Check Your Understanding

Use the definitions and arguments above to answer the following questions.

Why is an independent ghost sample useful when bounding $E[\sup_f|P_n f-Pf|]$?
For a two-sided supremum over $M$ functions, why does the moment-generating-function proof count $2M$ signed sums?
If $M=8$, $B=1/2$, and $n=100$, write the resulting expected uniform-deviation bound before evaluating it.
Which assumptions ensure that the suprema and expectations in the symmetrization argument are well defined?
Does the finite-class expected bound guarantee that the realized uniform deviation is below its right-hand side for every sample? Explain.