The fast rate in the realizable case

ProofIntermediate⏱ 30 minLearning Theoryrealizablefast ratemultiplicative bound

Theory: Empirical Risk Minimisation and Uniform Convergence →

Problem

Prove that if some $h^\star\in\Hcal$ has zero risk and $|\Hcal|=N$ , then any ERM solution satisfies $R(\hat h)\le\log(N/\delta)/n$ with probability at least $1-\delta$ — a $1/n$ rate rather than $1/\sqrt n$ . Explain where the improvement comes from.

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

Solution

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

Related problems

All problems

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 no-free-lunch theorem	Learning Theory	Proof	Advanced	1 hour
The symmetrisation lemma abyss	Learning Theory	Proof	Graduate	1 hour