Prove the Sauer–Shelah lemma

ProofGraduate⏱ 3 hoursLearning Theorysauershatteringinductiongrowth functionflagship

Theory: VC Dimension, Sauer's Lemma and Rademacher Complexity →

Problem

Prove that a class of VC dimension $d$ has growth function $\Pi_\Hcal(n)\le\sum_{k=0}^d\binom nk \le (en/d)^d$ for $n\ge d$ . Use the shifting/induction argument that proves the stronger statement: any set family shatters at least as many sets as it has members.

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

Hints

Hints — 0 of 3 revealed

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
VC dimension of halfspaces	Learning Theory	Proof	Intermediate	30 min
A one-parameter class with infinite VC dimension	Learning Theory	Proof	Advanced	1 hour
Massart's finite maximal inequality	Learning Theory	Proof	Advanced	30 min
Prove the O(1/t) rate for gradient descent abyss	Optimization	Proof	Advanced	1 hour
Rademacher complexity of a norm-bounded linear class	Learning Theory	Proof	Advanced	30 min