The excess risk decomposition for ERM

ProofBeginner⏱ 15 minLearning Theoryermdecompositionuniform convergence

Theory: Empirical Risk Minimisation and Uniform Convergence →

Problem

Prove that the ERM solution satisfies $R(\hat h) - \inf_{h\in\Hcal}R(h)\le2\Delta_n$ where $\Delta_n = \sup_{h\in\Hcal}|R(h)-\hat R_n(h)|$ , and explain why the factor $2$ is necessary.

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
Law of total variance and its use	Probability	Proof	Intermediate	30 min
The fast rate in the realizable case	Learning Theory	Proof	Intermediate	30 min
The supremum is 1-Lipschitz in the uniform norm	Foundations	Proof	Intermediate	15 min
What fitting random labels rules out	DL Theory	Proof	Intermediate	30 min