Realisability Assumption

machine-learning learning-theory

Definition

Realisability Assumption

The realisability assumption posits that there exists an optimal hypothesis $h^{\ast }\in \mathcal{H}$ within the pre-defined hypothesis class that achieves a true risk of zero. Formally:

$\exists h^{\ast }\in \mathcal{H}:R_P(h^{\ast })=0$

This assumption implies that the target labels $y$ are a deterministic function of the inputs $x$ (i.e., the data is noise-free) and that the true underlying mapping is contained within the functional capacity of the learner.

Theoretical Significance

Under the condition of realisability, the analysis of sample complexity is significantly simplified. An ERM algorithm only needs to identify any hypothesis that is consistent with the training set to provide probabilistic guarantees on its generalisation performance. This serves as the foundation for the PAC learning framework in the realisable case.