Sample Complexity

machine-learning learning-theory statistics

Definition

Sample Complexity

The sample complexity of a learning algorithm is the minimum number of training examples $m$ required to achieve a specified level of error $ϵ$ and confidence $\delta$ within the PAC learning framework. Formally, it is a function $m_{\mathcal{H}}(ϵ,\delta )$ such that for all $m\ge m_{\mathcal{H}}(ϵ,\delta )$:

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

Complexity Bounds

The number of required samples is primarily determined by the complexity of the hypothesis class.

Finite Classes: Under the realisability assumption, the complexity scales logarithmically with the cardinality of the class:
$m\ge \frac{1}{ϵ}\left(\ln |\mathcal{H}|+\ln \frac{1}{\delta }\right)$

Infinite Classes: For classes with infinite elements, the complexity is determined by the VC dimension $d$:
$m\le \mathcal{O}\left(\frac{d\ln (1/ϵ)+\ln (1/\delta )}{ϵ}\right)$
This result highlights that the “richness” of the functional space is the fundamental constraint on sample efficiency.