= Sample complexity
<Sample complexity> is the number of training observations needed for a specified learning guarantee. It depends on the allowed prediction error $\epsilon$, failure probability $\delta$, the <hypothesis> class and assumptions about data generation. It counts observations, whereas <computational complexity theory> measures the work of processing them.
For a finite class $H$ containing the true binary labeling rule, suppose examples are <independent and identically distributed>. A fixed <hypothesis> with error greater than $\epsilon$ fits $m$ examples with probability at most $(1-\epsilon)^m\le e^{-m\epsilon}$. The <union bound> makes the probability that any such bad <hypothesis> fits at most $|H|e^{-m\epsilon}$. Thus any consistent learner succeeds with probability at least $1-\delta$ when
$$
m\ge\frac{\log |H|+\log(1/\delta)}{\epsilon}.
$$
The derivation assumes realizability and establishes an information guarantee; it does not give an efficient search for a consistent <hypothesis>.
Back to article page
