Sample complexity

In machine learning, sample complexity is the number of examples needed for the estimate of a target function to be within a given error rate.^[1] The sample complexity of a machine learning algorithm characterizes its rate of consistency.

Mathematical Setup

Given a samples ${\displaystyle S_{n}=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}$  drawn i.i.d. according to a distribution ${\displaystyle \rho }$  from some input space ${\displaystyle {\mathcal {X}}\times {\mathcal {Y}}}$ , a supervised learning algorithm chooses a function ${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$  from some hypothesis class ${\displaystyle {\mathcal {H}}}$ . A desirable property of the algorithm is that it chooses functions with small expected prediction error with respect to ${\displaystyle \rho }$  and some loss function ${\displaystyle V:{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}}$ . Specifically, it is desirable to have a consistent algorithm, or an algorithm that generates functions whose expected loss or risk

$${\displaystyle {\mathcal {R}}(f)=\mathbb {E} _{\rho }[V(f(x),y)],}$$ 

converge to the best possible risk

$${\displaystyle {\mathcal {R}}_{\mathcal {H}}^{*}={\underset {f\in {\mathcal {H}}}{\inf }}{\mathcal {R}}(f).}$$ 

Formally, let ${\displaystyle f_{n}}$  be the functions generated by an algorithm as the number of data points ${\displaystyle n}$  grows. The algorithm is consistent if

$${\displaystyle {\underset {n\to \infty }{\lim }}\mathbb {P} _{S_{n}}({\mathcal {R}}(f_{n})-{\mathcal {R}}_{\mathcal {H}}^{*}>\epsilon )\to 0}$$ 

for all ${\displaystyle \epsilon >0}$ , where ${\displaystyle \mathbb {P} _{S_{n}}}$  denotes the i.i.d. sampling measure ${\displaystyle \rho ^{n}}$ .

The consistency property is nice, but it says nothing about how fast the risks converge. Since in practice one always deals with finite data, it is important to answer the question of how large a sample is needed to achieve a risk that is close, in the ${\displaystyle \epsilon }$  sense, to the best possible for the function class. The notion of sample complexity answers this question. The sample complexity of a learning algorithm is a function ${\displaystyle n(\rho ,\epsilon ,\delta )}$  such that for all ${\displaystyle n\geq n(\rho ,\epsilon ,\delta )}$ ,

$${\displaystyle \mathbb {P} _{S_{n}}({\mathcal {R}}(f_{n})-{\mathcal {R}}_{\mathcal {H}}^{*}>\epsilon )<\delta .}$$ 

In words, the sample complexity ${\displaystyle n(\rho ,\epsilon ,\delta )}$  defines the rate of consistency of the algorithm. Given a desired accuracy ${\displaystyle \epsilon }$  and confidence ${\displaystyle \delta }$ , one needs to sample at most ${\displaystyle n(\rho ,\epsilon ,\delta )}$  data points to guarantee that the risk of the output function is within ${\displaystyle \epsilon }$  of the best possible, with probability at least ${\displaystyle 1-\delta }$ .^[2]

No Free Lunch Theorem (Machine Learning)

Optimistically one could hope for a stronger notion of sample complexity that is independent of the distribution ${\displaystyle \rho }$  on the input and output spaces. However, it has been shown that without restrictions on the hypothesis class ${\displaystyle {\mathcal {H}}}$ , there always exists "bad" distributions for which the sample complexity is arbitrarily large.^[3] Thus in order to make statements about the rate of convergence of the quantity

$${\displaystyle {\underset {\rho }{\sup }}\ \mathbb {P} _{S_{n}}({\mathcal {R}}(f_{n})-{\mathcal {R}}_{\mathcal {H}}^{*}>\epsilon ),}$$ 

one must either

• Constrain the set of probability distributions ${\displaystyle \rho }$ , e.g. via a parametric approach, or
• Constrain the set ${\displaystyle {\mathcal {H}}}$  to be small, as in distribution free approaches.

The latter approach leads to concepts such as VC dimension and Rademacher complexity which control the complexity of the space ${\displaystyle {\mathcal {H}}}$ . A smaller hypothesis space introduces more bias into the inference process, meaning that ${\displaystyle {\mathcal {R}}_{\mathcal {H}}^{*}}$  may be larger than the best possible expected risk in a larger space. However, by restricting the complexity of the hypothesis space it becomes possible for an algorithm to produce functions converging in expected risk to ${\displaystyle {\mathcal {R}}_{\mathcal {H}}^{*}}$ . This trade-off leads to the concept of regularization.^[2]

Other Settings

In addition to the supervised learning setting, sample complexity is relevant to semi-supervised learning problems including active learning,^[1] where the algorithm can ask for labels to specifically chosen inputs in order to reduce the cost of obtaining many labels. The concept of sample complexity also shows up in reinforcement learning,^[4] online learning, and unsupervised algorithms, e.g. for dictionary learning.^[5]

References

1. Balcan, Maria-Florina (2010). "The true sample complexity of active learning". Machine Learning. 80 (2–3): 111–139. doi:10.1007/s10994-010-5174-y.
2. Rosasco, Lorenzo (2014), Consistency, Learnability, and Regularization, Lecture Notes for MIT Course 9.520.
3. Vapnik, Vladimir (1998), Statistical Learning Theory, New York: Wiley.
4. Kakade, Sham (2003), On the Sample Complexity of Reinforcement Learning (PDF), PhD Thesis, University College London: Gatsby Computational Neuroscience Unit.
5. Vainsencher, Daniel; Mannor, Shie; Bruckstein, Alfred (2011). "The Sample Complexity of Dictionary Learning" (PDF). Journal of Machine Learning Research. 12: 3259–3281.