# Tag Info

The standard no-free-lunch argument can be stated and understood without any knowledge or deep understanding of VC theory. (The upper bound, with its reliance on Sauer’s lemma, is intimately intertwined with VC theory.) Let $\mathcal{X}=\mathbb{N}$ be the set of all natural numbers and let $\mathcal{C}$ be the collection of all Boolean functions (classifiers)...