= 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 <probability distribution>[distribution] and some <hypothesis> in the class labels them perfectly. The learner must return a <hypothesis> whose true error is at most $\varepsilon$ with <probability> at least $1-\delta$. For a finite class $H$, any consistent learner satisfies this guarantee when
$$
m\geq\frac{\log|H|+\log(1/\delta)}{\varepsilon}.
$$
Indeed, a fixed <hypothesis> with error greater than $\varepsilon$ matches all $m$ examples with <probability> at most $(1-\varepsilon)^m\leq e^{-m\varepsilon}$; 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>.
Back to article page
