# sample size

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-08. [HTML](https://dictionaryofml.org/terms/samplesize.html) · [typeset PDF](https://dictionaryofml.org/terms/samplesize.pdf) · [LaTeX](https://dictionaryofml.org/terms/samplesize.tex) · [Python demo](https://dictionaryofml.org/terms/samplesize.py) · [notebook](https://dictionaryofml.org/terms/samplesize.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

The sample size is the number $m$ of data points in a sample. It is the basic measure of how much a sample carries, but not a universal one: listing a data point twice raises the count and adds nothing, correlated data points make the count overstate what a sample carries, and it says nothing about how well the data points cover the feature space. Many machine learning methods model the data points as realizations of independent and identically distributed RVs and judge a hypothesis by its expected loss, the risk; since the probability distribution is unknown, the risk is estimated by the average loss on the sample, for training by empirical risk minimization and for validation. How close that average is to the risk depends on the sample size. A concentration inequality such as Hoeffding's inequality bounds the deviation of the average from the risk and turns a required accuracy $\epsilon$ and confidence $1 - \delta$ into a sample size of order $\ln(1/\delta) / \epsilon^{2}$ for validation; for training, the sample size must also be compared with the size of the model. For data points recorded in sequence, autocorrelation lowers the effective sample size. The same reasoning gives the sample size for a statistical test, such as whether two features are correlated: the sample size needed to detect a correlation grows as the inverse square of that correlation.

## Definition

A frost warning for Krems an der Donau predicts, from the minimum and the maximum temperature of a day, whether the next day brings frost. A hypothesis $h$ for this task is judged by its expected loss, the risk $\bar{L} \big( h \big) = \mathbb{E} \{ L\left({\mathbf z},h \right) \}$, where the expectation is over a data point ${\mathbf z}$ drawn from the probability distribution $\mathbb{P}^{({\mathbf z})}$ of the days. Many machine learning methods use the independent and identically distributed assumption: the data points are realizations of independent and identically distributed RVs ${\mathbf z}^{(1)}, \ldots, {\mathbf z}^{(m)} \sim
\mathbb{P}^{({\mathbf z})}$. In practice, $\mathbb{P}^{({\mathbf z})}$ is unknown, and a method observes only these $m$ data points, a sample. Their number $m$ is the sample size.

With the probability distribution unknown, the risk is estimated by the average loss on the sample,

\begin{equation}
\tag{1}
\widehat{L}\big(h|\mathcal{D}\big) := \frac{1}{m}
\sum_{r=1}^{m}
L\left({\mathbf z}^{(r)},h \right) \text{,}
\end{equation}

which is the empirical risk. Empirical risk minimization minimizes this average over the hypotheses of a model on a training set, and validation compares the learned hypotheses by the same average on a validation set. Both uses require the average to be close to the risk, and how close it is depends on the sample size: by the law of large numbers, the average Eq. (1) converges to $\bar{L} \big( h \big)$ as $m$ grows (Papoulis and Pillai, 2002, Sect. 8-4; Shalev-Shwartz and Ben-David, 2014, Sect. 4.2). Fig. 1 shows this for the frost warning: the sample average of the 0/1 loss of one fixed hypothesis, computed on samples of $m = 10$ to $1585$ days, scatters around the risk $0.118$ with a spread that falls like $1/\sqrt{m}$. The spread is the standard deviation of the average over repeated samples, and Hoeffding's inequality, stated below, turns it into a deviation that holds with a prescribed probability.

![Figure 1 of the entry samplesize](https://dictionaryofml.org/terms/fig/samplesize-fig1.svg)

*Figure 1: The sample average of the 0/1 loss of a fixed frost-warning hypothesis on $m$ days of 2024 at Krems an der Donau, drawn uniformly with replacement, against the sample size. The solid curve is the standard deviation (spread) of the average over $400$ draws, the dotted curve $1/(2\sqrt{m})$, the largest standard deviation a loss in $[0,1]$ allows; the dashed curve is the deviation $\epsilon$ that Hoeffding's inequality Eq. (2) guarantees with probability $0.95$, and the vertical line marks the sample size $738$ at which that guarantee reaches $\epsilon = 0.05$. Data generated by pythondemos/samplesize.py*

The sample must be large enough, and one approach to deciding how large uses a concentration inequality, which bounds the probability that the average deviates from the risk by more than a given amount. For a loss function with values in $[0, 1]$, such as the 0/1 loss, Hoeffding's inequality gives, for every $\epsilon > 0$,

\begin{equation}
\tag{2}
\mathbb{P}\left( \big| \widehat{L}\big(h|\mathcal{D}\big) - \bar{L} \big( h \big) \big| > \epsilon \right)
\leq 2 \exp\big( -2 m \epsilon^{2} \big) \text{,}
\end{equation}

see Hoeffding (1963) and Shalev-Shwartz and Ben-David (2014, Lemma 4.5). The bound holds for a hypothesis chosen before the sample is drawn, which is the situation of validation: the hypothesis was learned on the training set, and the validation set is a fresh sample. Setting the right-hand side to a tolerated failure probability $\delta$ and solving for $m$ turns a required accuracy $\epsilon$ and confidence $1 - \delta$ into a sample size:

\begin{equation}
\tag{3}
m \geq \frac{\ln(2/\delta)}{2 \epsilon^{2}} \text{,}
\end{equation}

and this many data points make the validation error lie within $\epsilon$ of the risk with probability at least $1 - \delta$ (Shalev-Shwartz and Ben-David, 2014, Thm. 11.1). For the frost warning, $\epsilon
= 0.05$ and $\delta = 0.05$ give $m \geq 738$ days; at that sample size all of $2000$ drawn samples (pythondemos/samplesize.py) lie within $0.05$ of the risk. The bound is loose, since it holds for every probability distribution and every loss function in $[0, 1]$; the sample size Eq. (3) is therefore enough, but not always needed. Its shape is what carries over: halving $\epsilon$ quadruples the sample size, while the sample size grows only logarithmically in $1/\delta$.

For training, the same question has a second answer. The hypothesis is then chosen by looking at the sample, so the bound Eq. (2) for a fixed hypothesis no longer applies to the learned one. The sample size then has to be compared with the size of the model. For a model of Vapnik–Chervonenkis dimension $d$, a sample size proportional to $d / \epsilon^{2}$ makes the training error of every hypothesis in the model lie within $\epsilon$ of its risk at once (Shalev-Shwartz and Ben-David, 2014, Thm. 6.8). A sample that is small against the effective dimension of the model is the typical cause of overfitting, and the learning curve shows the validation error of the learned hypothesis as a function of the sample size (Hastie et al., 2009, Sect. 7.10).

Sample size enters a third task, hypothesis testing: are two features of a data point correlated? For the days of 2024 at Krems, is the minimum temperature of a day correlated with its diurnal range, the maximum minus the minimum? Over the whole year, the Pearson correlation coefficient of the two features is $\rho = 0.16$. A test is given a sample of $m$ days and computes the sample correlation $r$, a function of sample means. Under the hypothesis that the two features are independent, $r$ scatters around $0$ with a standard deviation close to $1/\sqrt{m}$. For features that are Gaussian RVs, the variance of $r$ is exactly $1/(m-1)$ (Anderson, 2003, Thm. 4.2.1). For independent features with finite variances of any other probability distribution, $\sqrt{m}\, r$ converges to a standard Gaussian random variable by the central limit theorem applied to the products of the standardized features, whose variance is one under independence. For features that are Gaussian RVs, Fisher's transformation $\operatorname{artanh}(r)$ is approximately a Gaussian random variable with mean $\operatorname{artanh}(\rho)$ and standard deviation $1/\sqrt{m - 3}$ (Anderson, 2003, Thm. 4.2.5; Fisher, 1921). The test rejects ``uncorrelated'' when $|\operatorname{artanh}(r)| \sqrt{m - 3}$ exceeds the quantile $z_{1-\alpha/2}$ of the standard Gaussian random variable, which bounds the probability of a false rejection by the significance level $\alpha$. A correlation $\rho$ is then detected with probability at least $1 - \beta$, the power of the test, once

\begin{equation}
\tag{4}
m \geq 3 + \bigg( \frac{z_{1-\alpha/2} + z_{1-\beta}}
{\operatorname{artanh}(\rho)} \bigg)^{2} \text{.}
\end{equation}

For $\rho = 0.16$, $\alpha = 0.05$ ($z_{0.975} = 1.96$) and a power of $0.8$ ($z_{0.8} = 0.84$), the sample size Eq. (4) is $304$ days. Fig. 2 shows the power of the test against the sample size: $0.84$ at $m = 304$, and $0.10$ for a sample of $30$ days. The shape is that of Eq. (3) again: halving the correlation to be detected quadruples the sample size, so a weak correlation needs a large sample before ``uncorrelated'' can be rejected.

![Figure 2 of the entry samplesize](https://dictionaryofml.org/terms/fig/samplesize-fig2.svg)

*Figure 2: The power of the correlation test at significance level $\alpha = 0.05$ for the minimum temperature and the diurnal range of a day at Krems an der Donau, whose Pearson correlation coefficient over 2024 is $\rho = 0.16$, against the sample size (solid curve, the fraction of $1000$ samples of $m$ days on which the test rejects ``uncorrelated''). The dashed line marks the power $0.8$, the vertical line the sample size $304$ of Eq. (4). Data generated by pythondemos/samplesize.py*

The count $m$ is not by itself a measure of how much a sample carries. If it were, information could be created by copying: listing every day of a sample twice gives a sample of sample size $2m$ that says exactly what the original says. Its empirical distribution is unchanged, since each day now holds two entries of probability $1/(2m)$. So is the average loss Eq. (1) of every hypothesis, and so is the spread of that average over repeated samples. Only $2m$ days drawn afresh reduce that spread, by the factor $\sqrt{2}$. Read with $2m$ in place of $m$, the bound Eq. (2) would promise a deviation smaller by that same factor. That promise does not follow, since a copy of a day is not independent of the day it copies, while Hoeffding's inequality holds for realizations of independent and identically distributed RVs. The sample size counts the entries of a list, and how much they carry depends on how the list was generated.

Dependence is rarely as extreme as an outright copy. The sample sizes above assume independent and identically distributed RVs, and data points recorded in sequence, such as consecutive days, often show autocorrelation: a frost day is more likely after a frost day, and so is a wrong prediction. Dependent data points carry less information than independent ones. For a stationary sequence with autocorrelation $\rho_{\ell}$ at lag $\ell$, the variance of the average of $m$ consecutive values is that of $m$ independent values multiplied by

\begin{equation}
\tag{5}
1 + 2 \sum_{\ell=1}^{m-1}
\Big( 1 - \frac{\ell}{m} \Big) \rho_{\ell} \text{,}
\end{equation}

see Brockwell and Davis (1991, Thm. 7.1.1). The average is therefore as accurate as that of $m$ divided by Eq. (5) independent values, the effective sample size. For the 0/1 loss of the frost warning, the sample autocorrelation of consecutive days is $0.24$ at lag $1$ and stays positive for a week, and the factor Eq. (5) is $4.2$ for $m = 30$. The average over $30$ consecutive days therefore scatters as much as that over $7$ days drawn at random. A sample of consecutive data points must then be larger than Eq. (3) or Eq. (4) say, by the factor Eq. (5), or be drawn at random from the whole record, as the days of Fig. 1 are.

Dependence aside, the count says nothing about where the data points lie. Two samples of the same size can cover the feature space differently: one spread over the whole range of the features, the other crowded in a part of it. For a method whose prediction at a feature vector depends on the data points near it, the largest distance from a point of the feature space region of interest to the nearest data point governs the prediction error there, however large $m$ is (see covering). A weather record of summer days alone, however long, leaves the winter part of the feature space empty, and no sample size compensates for it.

**See also:** sample, [data point](https://dictionaryofml.org/terms/datapoint.html), [dataset](https://dictionaryofml.org/terms/dataset.html), [independent and identically distributed assumption](https://dictionaryofml.org/terms/iidasspt.html), risk, empirical risk, law of large numbers, concentration inequality, Hoeffding's inequality, validation, [validation error](https://dictionaryofml.org/terms/valerr.html), Vapnik–Chervonenkis dimension, learning curve, [overfitting](https://dictionaryofml.org/terms/overfitting.html), autocorrelation, empirical distribution, hypothesis testing, Pearson correlation coefficient.

## References

- Papoulis and Pillai (2002). Probability, Random Variables, and Stochastic Processes. *McGraw-Hill Higher Education*.
- Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. *Cambridge Univ. Press*. <https://doi.org/10.1017/cbo9781107298019>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- Anderson (2003). An Introduction to Multivariate Statistical Analysis. *Wiley*.
- Fisher (1921). On the ``probable error'' of a coefficient of correlation deduced from a small sample. *Metron*.
- Hoeffding (1963). Probability Inequalities for Sums of Bounded Random Variables. *J. Amer. Statistical Assoc.*. <https://doi.org/10.1080/01621459.1963.10500830>
- Brockwell and Davis (1991). Time Series: Theory and Methods. *Springer-Verlag*.

## Cite this entry

```bibtex
@misc{dictml_samplesize,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {sample size},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-11},
  url = {https://dictionaryofml.org/terms/samplesize.html}
}
```