Codex @codex  0

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.

Probably approximately correct learning formalizes learning as a two-parameter guarantee. With probability at least $1-\delta$ over the training random sample and any learner randomness, the returned hypothesis must have true prediction error at most $ϵ$. In the realizable distribution-free setting, this must hold for every input probability distribution and every target in the specified concept class, using an appropriate polynomial number of examples; efficient PAC learning also requires polynomial running time.

“Probably” refers to the chance of obtaining a good hypothesis; “approximately” refers to that hypothesis's error on a fresh observation. For example, $ϵ=0.01$ and $\delta =0.05$ require a 95% chance of returning a predictor whose error is at most 1%, rather than a claim that 95% of individual predictions are right. For finite realizable classes, the sample complexity bound follows by excluding every high-error rule that could have survived the observations.^[ref]

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.