Computational learning theory

Computational learning theory studies what an algorithm can learn under an explicit observation model, accuracy requirement and resource bound. Sample complexity measures how much information is needed; time complexity measures the computation used to turn it into a predictor. A class can admit statistically sufficient samples while presenting a difficult computational Search problem.

In realizable probably approximately correct learning, labelled examples are sampled independently from a fixed but unknown distribution and some hypothesis in the class labels them perfectly. The learner must return a hypothesis whose true error is at most $\epsilon$ with probability at least $1-\delta$. For a finite class $H$, any consistent learner satisfies this guarantee whenIndeed, a fixed hypothesis with error greater than $\epsilon$ matches all $m$ examples with probability at most $(1-\epsilon {)}^m\le e^{-m\epsilon }$; a union bound over $H$ proves the claim. The argument bounds information requirements, but does not supply an efficient method for finding a consistent hypothesis.