Failure Probability (PAC-learning)

Definition

Failure Probability (PAC-learning)

The failure probability $\delta >0$ specifies the maximum probability that a PAC learner outputs a hypothesis whose error exceeds the required accuracy $\epsilon$.

Equivalently, the learner must succeed with probability at least

$$1-\delta .$$

Thus,

$$\underset{S\sim D^m}{\mathrm{Pr}}\left[\underset{x\sim D}{\mathrm{Pr}}\left[h(x)\ne c(x)\right]>\epsilon \right]\le \delta .$$