PAC learning

“Probability approximately correct” learning theory was introduced by Leslie Valiant in 1984 (A theory of the learnable). While Valiant and early results in PAC learning were mostly focused on simple and finite model classes, the theory extends to more general settings.

Let $\mathcal{F}$ be a class of functions from a covariate space $\mathcal{X}$ to some label space $\mathcal{Y}\subset \mathbb{R}$. We witness from data drawn from a distribution $P$ over $\mathcal{X}$ and chosen some $\hat{f}\in \mathcal{F}$ as our model (perhaps via empirical risk minimization, or perhaps some other way). The question is, how well does $\hat{f}$ generalize?

To answer this question, Valiant proposed that we look for bounds of the form: For all $\delta \in (0,1)$, there exists some $ϵ>0$ such that

$$\mathbb{P}(|R_n(\hat{f})-R(f)|>ϵ)\le \delta .$$

Thus, the algorithm is probably (with high probability, $1-\delta$), approximately (off by at most $ϵ$) correct (true risk matches empirical risk).

PAC bounds are often proved using uniform convergence bounds (though not always, see eghere). This results in bounds that depend on the complexity of $\mathcal{F}$ in some way, such as VC dimension or covering and packing numbers.

An alternative way to think about generalization bounds are PAC-Bayes bounds.