Problem Workshop: From Symmetrization to a Risk Bound

From Empirical Fit to a Risk Guarantee

An empirical risk minimizer is chosen to perform well on the observed sample. The central question is whether that fit also implies small population risk. A useful answer is built in stages: compare population and empirical risks uniformly over the model class, represent the comparison with an independent ghost sample, introduce random signs, and then use Lipschitz contraction to express the resulting complexity through the prediction class.

We work with independent observations $Z_1,\ldots,Z_n$ from a distribution $P$. A predictor $h$ incurs loss $g_h(z)$, where $g_h$ takes values in $[0,1]$. Boundedness supplies concentration, while a Lipschitz condition on the loss will connect the complexity of the losses to that of the predictions.

Definition: For a predictor $h$, its population risk is $R(h)=E[g_h(Z)]$, and its empirical risk is $\hat R_n(h)=n^{-1}\sum_{i=1}^n g_h(Z_i)$. Given a class $\mathcal H$, write $\mathcal G=\{g_h:h\in\mathcal H\}$. Its expected Rademacher complexity is $$ \mathfrak R_n(\mathcal G) = E_{Z_1,\ldots,Z_n,\sigma_1,\ldots,\sigma_n} \left[ \sup_{g\in\mathcal G} \frac{1}{n}\sum_{i=1}^n \sigma_i g(Z_i) \right], $$ where the $\sigma_i$ are independent, take values $+1$ and $-1$ with probability $1/2$, and are independent of the observations. This definition uses a supremum without an absolute value.

Assume throughout that the relevant suprema are measurable; for example, it is enough to work with a countable class. The expectation defining $\mathfrak R_n$ averages over both the observations and the signs. Because the class is nonempty, this expected supremum is nonnegative: for any fixed $g$, the signed sum has expectation zero and the supremum is at least that sum.

Worked Example: A Ghost Sample for a Two-Function Class

Let $Z$ be Bernoulli with $P(Z=1)=P(Z=0)=1/2$, and consider $g_0(z)=0$ and $g_1(z)=z$, with sample size $n=1$. First calculate the expected one-sided deviation $A=E[\sup_g(Pg-\hat P_1g)]$, where $Pg=E[g(Z)]$.

For $g_0$, the deviation is always zero. For $g_1$, $Pg_1=1/2$, while $\hat P_1g_1=Z_1$. Thus the supremum is $1/2$ when $Z_1=0$ and zero when $Z_1=1$, so $A=(1/2)(1/2)+(1/2)(0)=1/4$.

Now calculate the Rademacher complexity. If $Z_1=0$, both signed function values are zero. If $Z_1=1$, the supremum over $g_0,g_1$ is $\max(0,\sigma_1)$, whose sign expectation is $1/2$. Averaging over $Z_1$ gives $\mathfrak R_1(\mathcal G)=(1/2)(0)+(1/2)(1/2)=1/4$. The bound $A\leq 2\mathfrak R_1(\mathcal G)$ therefore holds: $1/4\leq1/2$.

The ghost observation $Z_1'$ is an independent draw from the same Bernoulli distribution. Replacing $Pg$ by its conditional sample average $g(Z_1')$ gives an upper bound in expectation by Jensen's inequality. The next result makes this argument precise for general $n$.

Symmetrization and Concentration

Result: Define $A=\sup_{g\in\mathcal G}(Pg-\hat P_ng)$ and $B=\sup_{g\in\mathcal G}(\hat P_ng-Pg)$, where $Pg=E[g(Z)]$ and $\hat P_ng=n^{-1}\sum_i g(Z_i)$. If $g\in[0,1]$, then $$ E[A]\leq 2\mathfrak R_n(\mathcal G) \qquad\text{and}\qquad E[B]\leq 2\mathfrak R_n(\mathcal G). $$ Moreover, for any $0<\delta<1$, with probability at least $1-\delta$, $$ A+B \leq 4\mathfrak R_n(\mathcal G) + \sqrt{\frac{2\log(2/\delta)}{n}}. $$

To prove the expectation bound for $A$, let $Z_1',\ldots,Z_n'$ be an independent ghost sample from $P$. Conditional on the observed sample, $Pg=E[n^{-1}\sum_i g(Z_i')]$. The supremum of expectations is no larger than the expectation of the supremum, so

E[A] \leq E\left[\sup_{g\in\mathcal G} \frac{1}{n}\sum_{i=1}^n\bigl(g(Z_i')-g(Z_i)\bigr)\right].

For each $i$, swapping $Z_i$ and $Z_i'$ leaves their joint distribution unchanged. Consequently, the vector of differences has the same distribution after multiplying each coordinate by an independent Rademacher sign. Applying this distributional identity and then $\sup_g(u_g+v_g)\leq\sup_g u_g+\sup_g v_g$ gives

\begin{aligned} E[A] &= E\left[\sup_g\frac{1}{n}\sum_i \sigma_i\bigl(g(Z_i')-g(Z_i)\bigr)\right]\\ &\leq E\left[\sup_g\frac{1}{n}\sum_i\sigma_i g(Z_i')\right] + E\left[\sup_g\frac{1}{n}\sum_i(-\sigma_i)g(Z_i)\right]\\ &=2\mathfrak R_n(\mathcal G). \end{aligned}

The last equality uses the identical distributions of the ghost and observed samples, and the fact that $(-\sigma_i)$ has the same distribution as $(\sigma_i)$. Interchanging the roles of the sample and ghost sample proves the same bound for $E[B]$.

For concentration, changing one observation changes either $A$ or $B$ by at most $1/n$: every empirical average changes by at most $1/n$, since each loss lies in $[0,1]$. McDiarmid's bounded-differences inequality therefore gives $P(A>E[A]+t)\leq e^{-2nt^2}$, and the same inequality holds for $B$. Taking $t=\sqrt{\log(2/\delta)/(2n)}$, each failure probability is at most $\delta/2$. A union bound and the two expectation bounds yield

A+B \leq 4\mathfrak R_n(\mathcal G)+2t = 4\mathfrak R_n(\mathcal G)+\sqrt{\frac{2\log(2/\delta)}{n}}. \qquad\square

Contraction and the Excess-Risk Bound

Suppose observations have the form $Z=(X,Y)$, and $g_h(X,Y)=\ell(Y,h(X))$. Assume predictions lie in a set $\mathcal T$, losses lie in $[0,1]$, and for every possible $y$, the map $t\mapsto\ell(y,t)$ is $L$-Lipschitz on $\mathcal T$: $|\ell(y,t)-\ell(y,s)|\leq L|t-s|$. For a sample $X_1,\ldots,X_n$, define the conditional prediction complexity by $$ \widehat{\mathfrak R}_n(\mathcal H) = E_\sigma\left[ \sup_{h\in\mathcal H}\frac{1}{n}\sum_{i=1}^n\sigma_i h(X_i) \right]. $$

The Rademacher contraction inequality says that coordinatewise $L$-Lipschitz transforms satisfy $E_\sigma\sup_h n^{-1}\sum_i\sigma_i\ell(Y_i,h(X_i)) \leq L\widehat{\mathfrak R}_n(\mathcal H)$. The maps may have nonzero values at zero: their additive offsets contribute a signed sum with conditional expectation zero. Averaging over the sample gives $\mathfrak R_n(\mathcal G)\leq L E[\widehat{\mathfrak R}_n(\mathcal H)]$.

Theorem: Assume $g_h\in[0,1]$ for every $h\in\mathcal H$, the relevant suprema are measurable, and $h\mapsto g_h$ satisfies the $L$-Lipschitz loss condition above. Let $\hat h$ be an empirical risk minimizer, so $\hat R_n(\hat h)=\inf_{h\in\mathcal H}\hat R_n(h)$. Then, with probability at least $1-\delta$, $$ R(\hat h)-\inf_{h\in\mathcal H}R(h) \leq 4L E[\widehat{\mathfrak R}_n(\mathcal H)] + \sqrt{\frac{2\log(2/\delta)}{n}}. $$ A slightly looser, convenient version replaces the final term by $2\sqrt{\log(2/\delta)/n}$.

For any $h\in\mathcal H$, the empirical minimizer property gives $\hat R_n(\hat h)\leq\hat R_n(h)$. Hence $R(\hat h)-R(h)\leq [R(\hat h)-\hat R_n(\hat h)]+[\hat R_n(h)-R(h)]\leq A+B$. Taking the infimum over $h$, applying the symmetrization-and-concentration result, and then applying contraction proves the theorem. The looser version follows because $\sqrt{2}\leq2$.

Worked Example: Checking Contraction on a Two-Point Sample

Take $n=2$, inputs $X_1=0,X_2=1$, labels $Y_1=0,Y_2=1$, and two predictors $h_a(0)=0,h_a(1)=1$ and $h_b(0)=1,h_b(1)=0$. Use squared loss $\ell(y,t)=(y-t)^2$ on $y,t\in[0,1]$.

The losses of $h_a$ are $(0,0)$; those of $h_b$ are $(1,1)$. Thus the conditional loss complexity is $E_\sigma[\max(0,(\sigma_1+\sigma_2)/2)]$. For the four equally likely sign pairs, the maximum is respectively $1,0,0,0$, so this complexity is $1/4$.

The prediction complexity is $E_\sigma[\max(\sigma_2/2,\sigma_1/2)]$. Its four values are $1/2,1/2,1/2,-1/2$, so it equals $1/4$. Finally, for $y,t,s\in[0,1]$, $|(y-t)^2-(y-s)^2|=|t-s||2y-t-s|\leq2|t-s|$; the loss is $2$-Lipschitz in the prediction. The contraction bound is therefore $1/4\leq2(1/4)=1/2$, as required.

Worked Example: A Finite-Class Risk Guarantee

Suppose $\mathcal H$ contains $M=5$ predictors with outputs in $[0,1]$, use squared loss on labels in $[0,1]$, and let $n=1000$, $\delta=0.1$. Squared loss is in $[0,1]$ and is $L=2$-Lipschitz, as verified above. For a finite class of $M$ functions taking values in $[0,1]$, the finite-class Rademacher bound gives $E[\widehat{\mathfrak R}_n(\mathcal H)]\leq\sqrt{2\log(2M)/n}$.

Here $2M=10$, so the complexity contribution in the theorem is $4L\sqrt{2\log(2M)/n}=8\sqrt{2\log(10)/1000}$. Since $\log(10)\approx2.302585$, the square root is approximately $0.0678614$, and this contribution is approximately $0.542891$.

The theorem's concentration term is $2\sqrt{\log(2/\delta)/n}=2\sqrt{\log(20)/1000}$. Since $\log(20)\approx2.995732$, this term is approximately $2(0.0547333)=0.109467$. The resulting looser guarantee is approximately $0.542891+0.109467=0.652358$, or $0.6524$ to four decimal places. Thus, with probability at least $0.9$, the empirical minimizer's excess risk is at most approximately $0.6524$. This can be a conservative bound; its purpose is a valid guarantee, not a prediction of the realized excess risk.

Common Mistake: Losing a Factor in the Complexity Term

A frequent error is to substitute the finite-class bound using $2n$ in its denominator, as if the factor $2$ inside $\log(2M)$ also doubled the sample size. It does not. The bound is $\sqrt{2\log(2M)/n}$; for $n=1000$ and $M=5$, the denominator remains $1000$. Using $2000$ would make the complexity contribution too small by a factor of $\sqrt{2}$, and the resulting risk guarantee would not follow from the stated theorem.

A second pitfall is to interpret a small empirical risk as a risk guarantee for one chosen predictor without accounting for the selection over the whole class. The uniform deviation controls all predictors simultaneously, which is why it can be applied to the data-dependent $\hat h$. The complexity term measures the cost of that uniform comparison.

Key takeaway: The risk-bound chain is explicit: ghost-sample symmetrization bounds expected one-sided deviations by Rademacher complexity; concentration makes the bound high probability; contraction transfers loss complexity to prediction complexity; and empirical risk minimization costs at most the sum of the two one-sided deviations.

Check Your Understanding

Check that you can track the assumptions and constants through the argument.

Why is an independent ghost sample useful when bounding $E[\sup_g(Pg-\hat P_ng)]$?
In the symmetrization proof, why does swapping each observed-ghost pair preserve the joint distribution?
What boundedness condition makes changing one observation alter $A$ or $B$ by at most $1/n$?
If the loss is $L$-Lipschitz in the prediction, which complexity in the risk theorem is replaced by prediction complexity?
For $M=5$ and $n=1000$, why does $\log(2M)$ not change the denominator in the finite-class bound?

Problem Workshop: From Symmetrization to a Risk Bound

What You'll Learn

From Empirical Fit to a Risk Guarantee

Worked Example: A Ghost Sample for a Two-Function Class

Worked Example: A Ghost Sample for a Two-Function Class

Symmetrization and Concentration

Contraction and the Excess-Risk Bound

Worked Example: Checking Contraction on a Two-Point Sample

Worked Example: A Finite-Class Risk Guarantee

Common Mistake: Losing a Factor in the Complexity Term

Check Your Understanding

Previous

Next