Sample Complexity Lower Bounds

Upper bounds in learning theory tell you that a given algorithm succeeds if it sees enough examples. Sample complexity lower bounds answer the opposite, arguably more fundamental, question: is there some hard-to-learn member of a concept class for which no algorithm, however clever, can succeed with fewer than a certain number of examples? If so, that number is a genuine floor — not an artifact of a particular method's inefficiency, but a limit imposed by the concept class itself.

The standard technique constructs an adversarial scenario: pick a small set of points the concept class can label in every possible way (a set the class "shatters," of size equal to its VC dimension $d$), and show that from any dataset smaller than roughly $d$, an adversary can always choose a true labeling consistent with the data seen so far that the learner cannot distinguish from another equally consistent, but different, labeling. Formally, this shows that learning any class with VC dimension $d$ to reasonable accuracy requires on the order of $d$ examples — matching, up to constants, the sample sizes that generic upper bounds (built from the Sauer-Shelah lemma) already guarantee are sufficient.

The practical payoff is knowing when more cleverness in the learning algorithm can't substitute for more data: if a concept class has VC dimension in the thousands, no algorithm — no matter how well-engineered — can reliably learn it from a few hundred examples, because the lower bound proves a genuine information deficiency, not merely a weakness of the specific method being used.