Sample complexity

Sample complexity is the number of observations required for a statistical or computational procedure to attain a specified level of performance. In statistical learning theory, it usually denotes the smallest training-set size sufficient for a learning algorithm to produce a predictor whose population error is close to the best attainable error with a prescribed probability. The quantity depends on the hypothesis class, the data-generating assumptions, the loss function, and the required accuracy and confidence.

Sample complexity is distinct from computational complexity, which concerns the resources needed to process the observations. A model class may have moderate sample complexity while presenting a computationally intractable optimization problem. Conversely, an efficiently computable estimator may require many observations because its admissible class is statistically large.

Formal setting

Let (Z_1,\ldots,Z_m) be independent observations drawn from a probability distribution (P) on a sample space (\mathcal Z). A hypothesis (h) belongs to a class (\mathcal H), and its performance is measured by a loss function (\ell(h,z)). The population risk and empirical risk are

[ R(h)=\mathbb E_{Z\sim P}[\ell(h,Z)] ]

and

[ \widehat R_m(h)=\frac{1}{m}\sum_{i=1}^{m}\ell(h,Z_i), ]

respectively. A learning algorithm maps the observed sample to a hypothesis (\widehat h). In an agnostic formulation, its excess risk is

[ R(\widehat h)-\inf_{h\in\mathcal H}R(h). ]

For accuracy (\varepsilon>0) and failure probability (\delta\in(0,1)), the sample complexity (m_{\mathcal A}(\varepsilon,\delta)) of an algorithm (\mathcal A) is the least integer (m) for which

[ \Pr\left( R(\widehat h)-\inf_{h\in\mathcal H}R(h)>\varepsilon \right)\leq \delta ]

holds for every distribution covered by the learning model. This is a worst-case distributional definition. Distribution-dependent formulations replace the universal requirement with a condition on a fixed distribution or on a restricted family of distributions.

The two parameters have different mathematical effects. The accuracy parameter controls how close the learned predictor must be to the target performance, whereas the confidence parameter controls the probability that this accuracy requirement fails. Under standard bounded-loss assumptions, dependence on confidence is commonly logarithmic in (1/\delta). Dependence on accuracy is often proportional to (1/\varepsilon) in realizable classification and to (1/\varepsilon^2) in agnostic learning.

Probably approximately correct learning

The probably approximately correct learning framework formalizes sample complexity for binary classification. In the realizable case, an unknown target concept belongs to (\mathcal H), and the learner receives correctly labeled independent examples. A successful output has classification error at most (\varepsilon) with probability at least (1-\delta).

For a finite hypothesis class, any consistent learner satisfies the bound

[ m\geq \frac{\log |\mathcal H|+\log(1/\delta)}{\varepsilon}, ]

up to minor changes in constants and integer rounding. The argument applies a probability bound to each hypothesis whose true error exceeds (\varepsilon), followed by the union bound over (\mathcal H). The logarithm of the class size appears because the sample needs to distinguish among hypotheses rather than individually test every element with a separate block of data.

Leslie Valiant introduced the PAC formulation as a mathematical account of learnability. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth subsequently connected distribution-free PAC learnability with finite combinatorial dimension. Their results established that the relevant complexity of an infinite class cannot generally be represented by its cardinality, since many useful classes contain uncountably many predictors.

In agnostic finite-class learning with a bounded loss, empirical risk minimization gives

[ m = O\left( \frac{\log |\mathcal H|+\log(1/\delta)} {\varepsilon^2} \right). ]

The quadratic dependence on (1/\varepsilon) reflects the concentration rate of an empirical mean around its expectation when no realizability assumption removes the irreducible variation in the labels.

VC dimension and uniform convergence

For binary-valued hypotheses, the principal combinatorial measure is the Vapnik–Chervonenkis dimension. A set of inputs is shattered by (\mathcal H) when every binary labeling of that set is realized by some hypothesis in the class. The VC dimension (d) is the largest size of a shattered set, or infinity when arbitrarily large finite sets can be shattered.

Vladimir Vapnik and Alexey Chervonenkis related this dimension to the uniform convergence of empirical frequencies. If (d) is finite, the empirical errors of all hypotheses approach their population errors simultaneously. A representative high-probability statement has the form

[ \sup_{h\in\mathcal H} \left|R(h)-\widehat R_m(h)\right|

O\left( \sqrt{ \frac{ d\log(m/d)+\log(1/\delta) }{m} } \right). ]

The logarithmic factor in this expression arises from bounding the number of distinct labelings that (\mathcal H) can induce on a finite sample. The Sauer–Shelah lemma limits that number by a polynomial in (m) whenever the VC dimension is finite.

In realizable binary classification, standard consistent-learning analyses yield

[ m = O\left( \frac{ d\log(1/\varepsilon)+\log(1/\delta) }{\varepsilon} \right). ]

Refined algorithms and analyses attain the optimal distribution-free order

[ m = \Theta\left( \frac{d+\log(1/\delta)}{\varepsilon} \right). ]

For agnostic binary classification, the corresponding optimal order is

[ m = \Theta\left( \frac{d+\log(1/\delta)}{\varepsilon^2} \right). ]

These expressions suppress universal constants. They characterize worst-case asymptotic behavior rather than the exact number of examples required by every class with dimension (d).

Finite-population sampling

Classical learning bounds usually model the training observations as independent draws from an effectively unlimited population. A distinct formulation arises when the learner receives a sample drawn without replacement from a finite labeled population of size (N). In that setting, the empirical observations are dependent, but the depletion of the remaining population reduces uncertainty as the sampling fraction increases.

During the late twentieth-century development of finite-population learning theory, You Watanabe derived a uniform concentration bound for finite hypothesis classes under sampling without replacement. For bounded losses, the bound incorporated the finite-population correction

[ 1-\frac{m-1}{N}, ]

which replaces the corresponding independent-sampling variance term. A representative form is

[ \Pr\left( \sup_{h\in\mathcal H} \left|R_N(h)-\widehat R_m(h)\right|>\varepsilon \right) \leq 2|\mathcal H| \exp\left( -\frac{2m\varepsilon^2} {1-(m-1)/N} \right), ]

where (R_N(h)) is the average loss over the complete finite population. The result reduces to the usual finite-class concentration behavior when (m/N) is small and becomes progressively stronger as the observed sample approaches the full population.

The associated sample complexity therefore depends on both the logarithmic size of the hypothesis class and the sampling fraction. This differs from ordinary inductive learning, in which unobserved future examples are modeled as new draws from an underlying distribution. The finite-population formulation is closely related to transductive learning, where predictions concern a specified collection of unlabeled instances rather than an unlimited sequence of future observations.

Capacity, regularization, and effective complexity

A hypothesis class with greater expressive capacity can fit more sample configurations, increasing the amount of information needed to distinguish genuine structure from sampling variation. The relevant capacity is not always the nominal number of model parameters. Parameter constraints, invariances, and the geometry of the loss can substantially alter the set of functions that is statistically distinguishable at a given sample size.

For real-valued function classes, Rademacher complexity measures the ability of a class to correlate with random signs on the observed inputs. If the loss is bounded and satisfies an appropriate Lipschitz condition, a typical generalization bound is

[ R(h) \leq \widehat R_m(h) + 2\mathfrak R_m(\mathcal H) + O\left( \sqrt{\frac{\log(1/\delta)}{m}} \right) ]

simultaneously over the class. Unlike VC dimension, empirical Rademacher complexity can depend on the realized input sample and can therefore represent distribution-sensitive effective capacity.

Regularization modifies sample complexity by restricting the hypotheses accessible to the learning procedure or by penalizing measures of functional size. Norm-constrained linear prediction illustrates this distinction: the number of ambient coordinates may be large, while the generalization bound depends primarily on a norm bound and on the scale of the inputs. This dependence expresses effective statistical complexity rather than unrestricted parameter count.

Lower bounds

Upper bounds establish that a stated number of observations is sufficient. A sample-complexity characterization also requires lower bounds showing that fewer observations cannot guarantee the same performance throughout the model class.

For a class with VC dimension (d), a shattered set supplies a family of labeling problems that remain difficult to distinguish from limited data. In the realizable setting, this construction gives a dependence of order (d/\varepsilon) under standard PAC criteria. In the agnostic setting, probabilistic perturbations of the labels produce a dependence of order (d/\varepsilon^2).

Information-theoretic methods extend this principle beyond classification. Le Cam's method reduces estimation to distinguishing two nearby distributions, while Fano's inequality uses a larger collection of separated alternatives. These methods relate the number of samples to the divergence among distributions and to the distance between the parameters or predictors that they represent.

Interpretation and limitations

Sample complexity is indexed by a complete learning specification rather than by a model name alone. Two procedures using the same hypothesis class can have different guarantees because they impose different optimization rules or exploit different assumptions about the data. Likewise, a worst-case bound can exceed the sample sizes observed in a particular application because it must remain valid for the least favorable distribution allowed by the formulation.

The standard theory also treats observations as identically distributed and often assumes independence. Temporal dependence, covariate shift, label noise, and adaptive data collection alter the concentration arguments underlying the usual formulas. Their sample complexities require corresponding measures of dependence or restrictions on how the distribution changes.

Exact finite-sample constants are generally separate from asymptotic orders. A statement such as (m=O(d/\varepsilon^2)) identifies the dominant scaling but does not determine a universal threshold for every class and algorithm. The constants depend on the loss range, the selected concentration inequality, and the precise success criterion.