 Weak PAC learning

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.