Generalisation for a finite class

ProofBeginner⏱ 30 minLearning Theoryfinite classunion boundhoeffding

Problem

Prove that for $|\Hcal| = N$ and losses in $[0,1]$ , with probability at least $1-\delta$ ,

\sup_{h\in\Hcal}\big|R(h)-\hat R_n(h)\big| \le \sqrt{\frac{\log(2N/\delta)}{2n}} .

Then compute the sample size needed for $\Delta_n\le0.01$ at $\delta = 0.05$ with $N = 2^{10^6}$ (a million binary parameters).

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
When is the union bound tight?	Probability	Proof	Foundation	15 min
The excess risk decomposition for ERM	Learning Theory	Proof	Beginner	15 min
Derive Hoeffding's inequality from Hoeffding's lemma	High-Dim Probability	Proof	Intermediate	30 min
Locating the Bernstein crossover	High-Dim Probability	Numerical	Intermediate	30 min
Majority voting via Hoeffding	Agents	Proof	Intermediate	30 min