Sample Complexity

machine-learning

Definition

Sample Complexity

Let $\mathcal{H}$ be a hypothesis class defined over an instance space $\mathcal{X}$ and label space $\mathcal{Y}$. The sample complexity of a learning algorithm $A$ is a function:

$$m_{\mathcal{H}}:(0,1{)}^2\to \mathbb{N}$$

that maps accuracy and confidence parameters to a minimal sample size. It is defined such that:

$$\forall \epsilon ,\delta \in (0,1):\forall D\in {\mathbb{P}}_{\text{realisable}}:\forall m\ge m_{\mathcal{H}}(\epsilon ,\delta )$$ $$\begin{array}{rl}\forall & \epsilon ,\delta \in (0,1)\\ \forall & D\in {\mathbb{P}}_{\text{realisable}}:\\ \forall & m\ge m_{\mathcal{H}}(\epsilon ,\delta ):\\ & {\text{Pr}}_{S\sim {\mathcal{D}}^m}(R_{\mathcal{D}}(A(S))\le \epsilon )\ge 1-\delta \end{array}$$