= Weak PAC learning
{title2=$\operatorname{err}_D(h)\leq\tfrac12-\gamma$}
A <concept class> $C$ is weakly PAC learnable using a <hypothesis class> $H$ when a learning procedure has a fixed edge $\gamma>0$ such that, for every target in $C$, every input <probability distribution>, and every confidence parameter $\delta$, sufficiently many independent target-labelled examples let it return an $h\in H$ satisfying the displayed bound with probability at least $1-\delta$. The example bound must be polynomial in $1/\delta$ under this definition. Computational efficiency is an additional requirement when explicitly imposed. This distribution-wide guarantee should be distinguished from merely obtaining an advantage on one finite training sample.
Back to article page
