The symmetrisation lemma

ProofGraduate⏱ 1 hourLearning Theorysymmetrisationghost samplerademacherflagship

Problem

Prove that for a class $\mathcal G$ of functions into $[0,1]$ ,

\E_S\left[\sup_{g\in\mathcal G}\Big(\E g - \frac1n\sum_ig(x_i)\Big)\right] \le 2\,\E_{S,\eps}\left[\sup_{g\in\mathcal G}\frac1n\sum_i\eps_ig(x_i)\right].

Identify precisely where the ghost sample is introduced, where Jensen is used, and where the symmetry of the Rademacher signs is used.

Write a complete argument. Every inequality you use should be one you could state precisely.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
The excess risk decomposition for ERM	Learning Theory	Proof	Beginner	15 min
The psi-2 norm of a Rademacher sign	High-Dim Probability	Numerical	Beginner	15 min
The fast rate in the realizable case	Learning Theory	Proof	Intermediate	30 min
Massart's finite maximal inequality	Learning Theory	Proof	Advanced	30 min