Binary Supervised Learning Algorithm (PAC-learning)

Definition

Binary Supervised Learning Algorithm ( PAC-learning)

A binary supervised learning algorithm in the PAC-learning framework is an algorithm $\mathcal{A}$ that, given an accuracy parameter $\epsilon$ and a failure probability $\delta$, has access to a sampling oracle $Q$.

Each query to $Q$ returns a labelled sample

$$(x,c(x))\in \mathcal{X}\times \{0,1\},$$

where $x$ is drawn according to an unknown distribution $D$ and $c$ is a hidden target concept. The algorithm outputs a hypothesis $h\in \mathcal{H}$.

The algorithm $\mathcal{A}$ is a PAC learner if, with probability at least $1-\delta$ over the randomly drawn training sample $S$, the hypothesis $h=\mathcal{A}(S)$ has misclassification probability at most $\epsilon$, i.e.,

$$\underset{S\sim D^m}{\mathrm{Pr}}\left[\underset{x\sim D}{\mathrm{Pr}}\left(\underset{h\in \mathcal{H}}{\underbrace{\mathcal{A}(S)}}(x)\ne c(x)\right)\le \epsilon \right]\ge 1-\delta .$$