Dictionary of Applied Machine Learning

sample size

Updated on 2026-10-14

▶ Run the Python demo open in Colab Typeset PDF Cite this entry

See also data point dataset independent and identically distributed assumption validation error overfitting

The sample size is the number $\samplesize$ of data points in a sample. Many machine learning (ML) methods model the data points as realizations of independent and identically distributed (i.i.d.) random variables (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 (ERM) 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 $\log(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 sizes the sample 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

B-riskA frost warning for Krems an der Donau predicts, from the minimum and the maximum temperature of a day, whether the next day brings frost. Whether a hypothesis $\hypothesis$ for this task is any good is judged by its expected loss, the risk $\risk{\hypothesis} = \expect \{ \lossfunc{\datapoint}{\hypothesis} \}$, where the expectation is over a data point $\datapoint$ drawn from the probability distribution $\probdist^{(\datapoint)}$ of the days. Many machine learning (ML) methods use the independent and identically distributed assumption (i.i.d. assumption): the data points are realizations of independent and identically distributed (i.i.d.) random variables (RVs) $\datapoint^{(1)}, \ldots, \datapoint^{(\samplesize)} \sim \probdist^{(\datapoint)}$. In practice, $\probdist^{(\datapoint)}$ is unknown, and a method observes only these $\samplesize$ data points, a sample. Their number $\samplesize$ is the sample size.

B-sampleWith the probability distribution unknown, the risk is estimated by the average loss on the sample, \begin{equation} \label{equ_samplesize_emprisk_dict} \emprisk{\hypothesis}{\dataset} \defeq \frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \lossfunc{\datapoint^{(\sampleidx)}}{\hypothesis} \text{,} \end{equation} which is the empirical risk. Empirical risk minimization (ERM) 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 \(\eqref{equ_samplesize_emprisk_dict}\) converges to $\risk{\hypothesis}$ as $\samplesize$ grows (Shalev-Shwartz and Ben-David, 2014, Sect. 2.2; Papoulis and Pillai, 2002). Fig. 1 shows this for the frost warning: the sample average of the $0/1$ loss of one fixed hypothesis, computed on samples of $\samplesize = 10$ to $1000$ days, scatters around the risk $0.118$ with a spread that falls like $1/\sqrt{\samplesize}$.

Figure 1 of the entry samplesize
Figure 1: The sample average of the $0/1$ loss of a fixed frost-warning hypothesis on $\samplesize$ 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{\samplesize})$, the largest standard deviation a loss in $[0,1]$ allows; the dashed curve is the deviation $\epsilon$ that Hoeffding's inequality \(\eqref{equ_samplesize_hoeffding_dict}\) 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
How large should the sample be? One approach 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} \label{equ_samplesize_hoeffding_dict} \prob{ \big| \emprisk{\hypothesis}{\dataset} - \risk{\hypothesis} \big| > \epsilon } \leq 2 \exp\big( -2 \samplesize \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 $\samplesize$ turns a required accuracy $\epsilon$ and confidence $1 - \delta$ into a sample size: \begin{equation} \label{equ_samplesize_choice_dict} \samplesize \geq \frac{\log(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 $\samplesize \geq 738$ days; at that sample size all of $2000$ drawn samples in Fig. 1 land 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 \(\eqref{equ_samplesize_choice_dict}\) is therefore enough, but not always needed. Its shape is what carries over: halving $\epsilon$ quadruples the sample size, while a smaller $\delta$ costs only a logarithm.

For training, the same question has a second answer. The hypothesis is then chosen by looking at the sample, so the bound \(\eqref{equ_samplesize_hoeffding_dict}\) 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 (VC 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).

B-dependentThe sample sizes above assume i.i.d. RVs. 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_{\lagidx}$ at lag $\lagidx$, the variance of the average of $\samplesize$ consecutive values is that of $\samplesize$ independent values multiplied by \begin{equation} \label{equ_samplesize_acf_dict} 1 + 2 \sum_{\lagidx=1}^{\samplesize-1} \Big( 1 - \frac{\lagidx}{\samplesize} \Big) \rho_{\lagidx} \text{,} \end{equation} see (Brockwell and Davis, 1991, Sect. 7.1). The average is therefore as accurate as that of $\samplesize$ divided by \(\eqref{equ_samplesize_acf_dict}\) 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 \(\eqref{equ_samplesize_acf_dict}\) is $4.2$ for $\samplesize = 30$. The average over $30$ consecutive days therefore scatters as much as that over $7$ days drawn at random: a month of consecutive days is worth a week of random ones. A sample of consecutive data points must then be larger than \(\eqref{equ_samplesize_choice_dict}\) or \(\eqref{equ_samplesize_corr_dict}\) say, by the factor \(\eqref{equ_samplesize_acf_dict}\), or be drawn at random from the whole record, as the days of Fig. 1 are.

B-corrSample 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 sees a sample of $\samplesize$ days and computes the sample correlation $r$, a function of sample means. Under the hypothesis that the two features are uncorrelated, $r$ scatters around $0$ with a standard deviation close to $1/\sqrt{\samplesize}$, whatever their probability distribution. For features that are Gaussian random variables (Gaussian RVs), Fisher's transformation $\operatorname{artanh}(r)$ is approximately a Gaussian RV with mean $\operatorname{artanh}(\rho)$ and standard deviation $1/\sqrt{\samplesize - 3}$ (Fisher, 1921). The test rejects "uncorrelated" when $|\operatorname{artanh}(r)| \sqrt{\samplesize - 3}$ exceeds the quantile $z_{1-\alpha/2}$ of the standard Gaussian RV, 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} \label{equ_samplesize_corr_dict} \samplesize \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 \(\eqref{equ_samplesize_corr_dict}\) is $304$ days. Fig. 2 shows the power of the test against the sample size: $0.84$ at $\samplesize = 304$, and $0.10$ for a sample of $30$ days. The shape is that of \(\eqref{equ_samplesize_choice_dict}\) 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
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 $\samplesize$ days on which the test rejects "uncorrelated"). The dashed line marks the power $0.8$, the vertical line the sample size $304$ of \(\eqref{equ_samplesize_corr_dict}\). Data generated by pythondemos/samplesize.py

See also: sample, data point, dataset, independent and identically distributed assumption, risk, empirical risk, law of large numbers, concentration inequality, Hoeffding's inequality, validation, validation error, Vapnik–Chervonenkis dimension, learning curve, overfitting, autocorrelation, hypothesis testing, Pearson correlation coefficient.

References

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

Cite this entry

@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-10-14},
  url = {https://dictionaryofml.org/terms/samplesize.html}
}