Symmetrization & the Rademacher Generalization Bound
Empirical Processes, STAT 210B2 minute read
Part of the STAT 210B Results Toolbox: the result as stated in my 210B notes (Prop. 6.3 in §6, and the §7.1 excess-risk application), plus the one proof step to recall to remember why it is true.
Statement
The core inequality — symmetrization proper — is Proposition 6.3 (Symmetrization):
\[\mathbb{E}\sup_{f\in\mathcal{F}}\left( \mathbb{E}f(X) - \frac1n\sum_{i=1}^n f(X_i) \right) \;\le\; 2\cdot\mathbb{E}\sup_{f\in\mathcal{F}}\left( \frac1n\sum_{i=1}^n \epsilon_i f(X_i) \right),\]where the \(\epsilon_i\) are iid Rademacher signs; sometimes the RHS is called the Rademacher complexity. The notes state it three ways — this one, the flipped one-sided version, and the absolute-value version, all with the same factor \(2\).
The §7.1 application (excess risk of ERM):
\[\mathbb{E}\big[R(\hat f) - \inf_{f\in\mathcal{F}} R(f)\big] \;\le\; 2\,\mathbb{E}\sup_{f\in\mathcal{F}}\big\lvert R(f) - R_n(f)\big\rvert \;\le\; 4\,\mathbb{E}\sup_{f\in\mathcal{F}}\Big\lvert\frac1n\sum_{i=1}^n \epsilon_i\, \ell(f(X_i),Y_i)\Big\rvert.\]The Lipschitz-composition step (via Talagrand’s contraction lemma) runs through the notes’ one-sided “another route”:
\[\mathbb{E}\big[R(\hat f) - R_n(\hat f) + R_n(f^\star) - R(f^\star)\big] \;\le\; \mathbb{E}\sup_{f\in\mathcal{F}}\big(R(f) - R_n(f)\big) \;\le\; 2\,\mathbb{E}\sup_{f\in\mathcal{F}}\Big(\frac1n\sum_{i=1}^n \epsilon_i\, \ell(f(X_i),Y_i)\Big),\]and then, assuming \(u\mapsto\ell(u,Y)\) is \(L\)-Lipschitz for all \(Y\)’s,
\[2\,\mathbb{E}\sup_{f\in\mathcal{F}}\Big(\frac1n\sum_{i=1}^n \epsilon_i\, \ell(f(X_i),Y_i)\Big) \;\le\; 2L\,\mathbb{E}\sup_{f\in\mathcal{F}}\Big(\frac1n\sum_{i=1}^n \epsilon_i f(X_i)\Big).\]🤖 Claude: the two routes are deliberately separate in the notes: the absolute-value chain stops at the \(4\,\mathbb{E}\sup\lvert\cdot\rvert\) display, and the \(L\)-Lipschitz contraction is applied only on the one-sided route (no absolute values) — contracting through \(\lvert\cdot\rvert\) would invoke the harder abs-value contraction lemma, which costs a factor \(2\) and requires \(\phi(0)=0\).
🤖 Claude: Remark 6.25 of the 210B notes (“Roadmap: from VC dimension to uniform convergence”) chains three arrows — symmetrization → sub-Gaussian increments → Sauer–Shelah — with symmetrization first; worth pasting that roadmap here when you polish, since this page is the natural home for it.
The fundamental step
The ghost sample. Introduce an independent copy \(X_1’,\dots,X_n’\) of the data and write the population mean as its empirical average in expectation:
\[\mathbb{E}\sup_f \big[ P f - P_n f \big] = \mathbb{E}\sup_f\ \mathbb{E}'\big[ P_n' f - P_n f \big] \le \mathbb{E}\,\mathbb{E}'\sup_f \frac1n\sum_{i=1}^n \big( f(X_i') - f(X_i) \big).\]Now each difference \(f(X_i’) - f(X_i)\) is a symmetric random variable — swapping \(X_i \leftrightarrow X_i’\) flips its sign without changing the joint distribution — so multiplying by independent Rademacher signs \(\epsilon_i\) changes nothing:
\[= \mathbb{E}\sup_f \frac1n\sum_i \epsilon_i\big( f(X_i') - f(X_i) \big) \;\le\; 2\,\mathbb{E}\sup_f \frac1n\sum_i \epsilon_i f(X_i).\]The memory hook: replace the population by an independent ghost copy; the differences are sign-symmetric, so you can sprinkle in Rademacher signs for free, then split the sup to drop the ghost — paying the factor 2. The unknown distribution \(P\) has been traded for pure coin flips on the observed sample.
Where it’s used
- The heart of the Rademacher generalization bound (Ma Thm. 4.18) — step 2 of the four-move proof recorded in the Rademacher complexity notes; McDiarmid supplies the high-probability packaging on either side of it.
- Term (1) of the excess risk decomposition in the STAT 241A day-1 notes is bounded by the uniform generalization error, and symmetrization is the first tool applied to it.
Leave a Comment