The no-free-lunch theorem

ProofAdvanced⏱ 1 hourLearning Theoryno free lunchinductive biaslower bound

Theory: Empirical Risk Minimisation and Uniform Convergence →

Problem

Let $|\Xcal| = 2m$ and $\Hcal$ be all functions $\Xcal\to\{0,1\}$ . Prove that for any learning algorithm $\mathcal A$ using $n\le m$ samples there is a distribution on which $\E_S\big[R(\mathcal A(S))\big]\ge1/4$ , while some $h\in\Hcal$ has zero risk. State the philosophical consequence precisely.

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
Single-stream decode latency floors	LLM Ops	Numerical	Intermediate	30 min
The fast rate in the realizable case	Learning Theory	Proof	Intermediate	30 min
The irreducible loss is the conditional entropy	LLMs	Proof	Intermediate	30 min