What fitting random labels rules out

ProofIntermediate⏱ 30 minDL Theoryrandom labelscapacityuniform convergencevacuous bounds

Theory: Why Does Deep Learning Optimization Work? →

Problem

Suppose a hypothesis class $\Hcal$ can fit arbitrary $\pm1$ labellings of a sample of size $n$ . Show that its empirical Rademacher complexity on that sample is $1$ , and deduce that every uniform-convergence bound over $\Hcal$ is vacuous. Explain what does and does not follow about the network's generalisation.

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
The excess risk decomposition for ERM	Learning Theory	Proof	Beginner	15 min
Apply Little's law to a serving target	LLM Ops	Proof	Intermediate	30 min
How many users fit on one GPU	LLM Ops	Numerical	Intermediate	30 min
Implicit bias of gradient descent on underdetermined least squares	DL Theory	Proof	Intermediate	30 min
The supremum is 1-Lipschitz in the uniform norm	Foundations	Proof	Intermediate	15 min