Sample complexity

Sample complexity is the number of training observations needed for a specified learning guarantee. It depends on the allowed prediction error $ϵ$, 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 $ϵ$ fits $m$ examples with probability at most $(1-ϵ{)}^m\le e^{-mϵ}$. The union bound makes the probability that any such bad hypothesis fits at most $|H|e^{-mϵ}$. Thus any consistent learner succeeds with probability at least $1-\delta$ whenThe derivation assumes realizability and establishes an information guarantee; it does not give an efficient search for a consistent hypothesis.