Probably Approximately Correct (PAC) Learning Model (Valiant 1984):

Framework to analyze learnability: when can learner, with high probability, find approximately correct hypothesis with polynomial sample/computation?

Setup: Instance space $X$, concept class $C$, hypothesis space $H$, distribution $D$ over $X$, target $c\in C$, training set $S\sim D^m$ labeled by $c$.

Learner outputs $h\in H$.

Definition: $C$ is PAC-learnable if exists algorithm $L$ and polynomial $poly(1/\epsilon,1/\delta,n,size(c))$ such that for any $\epsilon,\delta\in(0,1)$, any $D$, any $c\in C$, given $m\ge poly(...)$ examples, $L$ outputs $h$ with $P(Error_D(h)\le \epsilon) \ge 1-\delta$.

Error: $Error_D(h)=P_{x\sim D}[h(x)
eq c(x)]$, training error zero for consistent learner.

$\epsilon$: Accuracy parameter (approximately correct, error ≤$\epsilon$). $\delta$: Confidence (probably, with probability 1-$\delta$).

Sample complexity bounds:
For finite $|H|$: $m \ge \frac1\epsilon(\ln|H| + \ln1/\delta)$ sufficient for consistent learner (if realizable). Using Hoeffding: $P(\exists h\in H: Error_{train}=0 but Error_{true}>\epsilon) \le |H|e^{-\epsilon m}$.

For infinite $H$, VC-dimension $d=VC(H)$: $m = O(\frac1\epsilon(d\log1/\epsilon +\log1/\delta))$ (agnostic: $m=O(\frac1{\epsilon^2}(d+\log1/\delta))$).

Examples:

• Conjunctions of $n$ literals: PAC-learnable with $m=O(\frac1\epsilon(n\log n +\log1/\delta))$
• Axis-aligned rectangles in $\mathbb{R}^2$ PAC-learnable, $VC=4$.
• Parity not efficiently PAC-learnable.

Agnostic PAC: $c
otin H$or noise, learner finds$h$with error ≤$\min_{h\in H}Error_D(h)+\epsilon$.

Implications: PAC gives theoretical guarantee linking sample size, hypothesis complexity ($|H|$ or VC), accuracy and confidence. Guides Occam's razor: simpler $H$ needs fewer samples.

Limitations: Distribution-free worst-case, often loose bounds, assumes i.i.d.