Realisable PAC-Learnable Hypothesis Class

machine-learning

Definition

Realisable PAC-Learnable Hypothesis Class

A hypothesis class $\mathcal{H}$ is realisable PAC-learnable if there exists a learning algorithm $A$ and a sample complexity function $m(ϵ,\delta )$ such that:

For any parameters $ϵ,\delta \in (0,1)$ and any distribution $\mathcal{D}$ over $\mathcal{X}\times \mathcal{Y}$ (assuming realisability), if the algorithm receives $m\ge m(ϵ,\delta )$ i.i.d. samples, it produces a hypothesis $h_S$ such that:

$${\mathrm{Pr}}_{S\sim {\mathcal{D}}^m}\left(R_{\mathcal{D}}(h_S)\le ϵ\right)\ge 1-\delta$$

Key Guarantees:

• Approximately Correct: The true risk is bounded by error parameter $ϵ$ (i.e., $R_{\mathcal{D}}(h_S)\le ϵ$).
• Probably: This low error is achieved with probability at least $1-\delta$.

Empirical Risk Minimisation

A hypothesis class $\mathcal{H}$ is realisable PAC-learnable by any ERM algorithm with sample complexity:

$$m(\epsilon ,\delta )\le \mathcal{O}\left(\frac{\left(d\cdot \ln \left(\frac{1}{\epsilon }\right)+\ln \left(\frac{1}{\delta }\right)\right)}{\epsilon }\right)$$