Sample complexity¶

Quantify how many observations a learner needs to attain a stated accuracy with a stated confidence under an explicit hypothesis class, data model, and learning criterion.

Version: v3 · 2026-09-06 · History
Domain-specific #: 2704
Origin domain: computer science
Subdomain: computational learning theory
Aliases: Learning sample complexity, Sample requirement

Core Idea¶

Sample complexity is the number of examples required for a learning procedure to meet a declared performance guarantee. A typical supervised-learning statement asks for a sample size \(m(\epsilon,\delta)\) such that, with probability at least \(1-\delta\) over the sampled training data, the returned hypothesis has true error at most \(\epsilon\), or at most \(\epsilon\) above the best error available in a specified class. The quantity is therefore not a free-standing count. It is a relation among accuracy, confidence, hypothesis-class capacity, distributional assumptions, noise conditions, the information carried by each example, and the learning objective.

Valiant's PAC formulation made this relation explicit by treating learnability as the existence of an algorithm whose sample and computational requirements are polynomial in the relevant parameters.^[1] Later statistical-learning accounts separate realizable and agnostic settings, distribution-free and distribution-dependent guarantees, passive and active acquisition, expectation and high-probability criteria, and upper and lower bounds. The same hypothesis class can have different sample complexity under different feedback models or margin, smoothness, sparsity, stability, privacy, and noise assumptions. A numerical claim without its quantifiers is thus incomplete.

The abstraction distinguishes sample complexity from computational complexity. An information-theoretically sufficient number of examples does not guarantee that a tractable algorithm can exploit them. Conversely, a fast algorithm may require more data than an optimal but impractical one. It also distinguishes a theoretical requirement from a dataset's observed size. A bound states what a class of problems and procedures can guarantee under assumptions; a learning curve estimates behavior in a particular empirical setting. Vapnik–Chervonenkis dimension supplies one important capacity measure: for binary classification, finite VC dimension characterizes distribution-free PAC learnability and governs familiar upper and lower sample bounds.^[2] Other settings require Rademacher complexity, covering numbers, information measures, compression size, or problem-specific parameters.

A complete sample-complexity claim specifies the task, data-generation model, loss, comparator, probability space, success criterion, and whether the statement is an upper bound, lower bound, minimax rate, or exact threshold. Shalev-Shwartz and Ben-David present this dependency as a central part of learnability rather than a single universal formula.^[3] The resulting abstraction manages a core question across learning theory: how much evidence is needed before limited observations support a controlled generalization claim?

Structural Signature¶

Learning task. Classification, regression, density estimation, bandit identification, representation learning, or another task fixes what must be learned.
Observation model. Examples may be i.i.d., dependent, actively queried, labeled, partially labeled, corrupted, private, or otherwise constrained.
Hypothesis or model class. The candidate solutions and their capacity are specified.
Accuracy parameter. An error, excess-risk, estimation, or identification tolerance such as epsilon is declared.
Confidence parameter. A failure probability such as delta states how often the guarantee may fail over samples or randomness.
Learning criterion. Realizable, agnostic, proper, improper, online, minimax, Bayesian, or other success semantics are fixed.
Sample-size function or rate. A bound relates required observations to the parameters and assumptions.
Upper/lower pairing. Algorithms provide sufficiency while information-theoretic or adversarial arguments establish necessity.
Generalization bridge. The sample is used to justify performance beyond the observed examples.
Assumption ledger. Noise, margins, smoothness, distribution family, privacy, adaptivity, and dependence remain attached to the result.

What It Is Not¶

Not dataset size. Having (n) records is an empirical fact; sample complexity is a requirement or bound tied to a guarantee.
Not time complexity. The number of examples and the operations required to process them are distinct resources.
Not model parameter count. Parameter count can influence capacity but does not alone determine the observation requirement.
Not power analysis generally. Statistical power asks about detecting effects under a test; learning sample complexity asks about a learner's performance criterion.
Not one universal PAC formula. Different loss functions, access models, assumptions, and capacity measures produce different bounds.
Not an empirical learning curve. Curves can estimate realized behavior but do not by themselves prove a distributional guarantee.
Not proof that more data always helps. Distribution shift, label error, selection bias, and misspecification can defeat the stated model.

Scope of Application¶

The construct applies wherever a learning or estimation problem asks for an evidence requirement under explicit performance and uncertainty semantics. It must travel with its access model and assumptions.

PAC learning. Distribution-free realizable and agnostic guarantees for concept or hypothesis classes.
Statistical learning. Excess-risk and uniform-convergence rates governed by capacity or stability.
Active learning. Label complexity when a learner chooses which observations receive labels.
Online learning. Conversion between regret behavior, mistakes, and stochastic sample guarantees under stated conditions.
Reinforcement learning. Environment-interaction requirements for policy evaluation or near-optimal control.
High-dimensional estimation. Observation rates depending on sparsity, rank, smoothness, or structural priors.
Privacy and robustness. Additional samples required to satisfy privacy, adversarial, or contamination constraints.
Lower-bound analysis. Demonstrating that no learner can succeed below a rate through indistinguishability or information limits.
Experimental planning. Translating a trustworthy theoretical model into a defensible data-collection target.

Clarity¶

State the guarantee before quoting the number. A defensible sentence identifies the data distribution or admissible family, whether examples are independent, the hypothesis class, the loss, the comparator, epsilon, delta, and whether the learner is proper or may return a hypothesis outside the class. It says whether the bound is sufficient, necessary, asymptotic, minimax, expected, or high probability. Big-O notation must name hidden dependencies when they matter. In an agnostic setting, error is normally measured relative to the best class member rather than zero. A distribution-dependent bound must not be advertised as worst-case distribution-free. Label complexity in active learning should not be confused with the number of unlabeled examples inspected. In reinforcement learning, samples may mean transitions, episodes, or generative-model queries. Empirical sample-size recommendations should be labeled as extrapolations unless the theoretical assumptions have been checked. Finally, a lower bound for one oracle or feedback model does not automatically apply to a richer information source.

Manages Complexity¶

Learning performance depends simultaneously on model capacity, approximation error, estimation error, confidence, optimization, data quality, and acquisition design. Sample complexity isolates the evidence dimension while retaining explicit interfaces to the others. Instead of saying vaguely that a method 'needs lots of data', an analyst can ask which parameter drives the rate, whether a structural assumption reduces capacity, and whether a lower bound proves the dependence unavoidable. Capacity measures compress enormous hypothesis spaces into quantities relevant to generalization. Epsilon and delta separate precision from reliability. Upper and lower bounds distinguish algorithmic weakness from intrinsic information scarcity. The abstraction also organizes improvements: a margin condition may sharpen the rate, active selection may reduce label needs, transfer information may change the effective class, and privacy may impose a penalty. These comparisons are meaningful only because the guarantee and observation model remain fixed. Sample complexity therefore functions as a resource-accounting language for evidence, much as runtime complexity accounts for computation, while preventing one resource from silently standing in for another.

Abstract Reasoning¶

Define the target performance and loss on future or unobserved data.
Specify the observation process and what information each sample contains.
Fix the hypothesis class, comparator, and whether the learner must be proper.
Declare accuracy and confidence parameters with their probability space.
Select a capacity or information measure appropriate to the task.
Prove an upper bound by showing a learner succeeds once the sample exceeds a function of the parameters.
Test necessity with a lower bound based on hard-to-distinguish alternatives or shattering.
Compare upper and lower rates and identify gaps due to algorithms, logarithmic factors, or assumptions.
Audit dependence, noise, shift, privacy, and adaptive collection before transferring the bound.
Use empirical curves as validation evidence, not as a substitute for the quantified claim.

Knowledge Transfer¶

The strict parent is Complexity because the node assigns a resource requirement to achieving a task under a model. The reusable skeleton is desired guarantee + problem family + access assumptions → required resource as a function of parameters. The domain accent is essential: the resource is observations, the task is learning or estimation, and the guarantee concerns generalization or recovery from data. Within machine learning, the abstraction transfers across supervised, active, online, reinforcement, private, and robust settings only by redefining what counts as a sample and what success means. Outside that habitat, a loose statement that a social process has 'sample complexity' is analogy unless it includes a formal learner, observations, a performance criterion, and quantified uncertainty.

Examples¶

Canonical¶

For binary classification in a realizable PAC setting, suppose hypotheses come from a class (H) with finite VC dimension (d). A representative guarantee states that a consistent learner requires on the order of \((d\log(1/\epsilon)+\log(1/\delta))/\epsilon\) examples, with refinements depending on the theorem. The key is not the displayed constants. The class capacity (d), target error epsilon, failure probability delta, i.i.d. sampling, realizability, binary loss, and consistency criterion jointly define the claim. Remove or change one and the sample requirement can change.

Mapped back: task and class → capacity d → accuracy epsilon + confidence delta → sufficient i.i.d. sample count → high-probability generalization.

Applied / In Practice¶

A team trains a sparse predictor and asks whether an existing dataset is adequate. It does not compare row count only with parameter count. It states a noise model, sparsity level, feature conditions, desired prediction error, and confidence, then chooses a theorem whose access model matches the data. A theoretical rate supplies a planning baseline; dependence and distribution shift in the collected records are audited separately. A held-out learning curve is used to challenge the assumptions. The final recommendation reports both the theorem-derived requirement and uncertainty about model mismatch.

Mapped back: deployment criterion → matched theoretical model → parameterized sample bound → assumption audit → empirical challenge → qualified collection target.

Structural Tensions¶

Distribution-free breadth vs. sharpness. Worst-case guarantees travel broadly but can be loose. Diagnostic: Which distributional assumption would justify a smaller rate?
Information vs. computation. Sufficient data may not yield an efficient learner. Diagnostic: Is the claim information-theoretic, algorithm-specific, or both?
Capacity vs. approximation. A smaller class generalizes faster but may omit the target. Diagnostic: Does the bound account for excess risk relative to the class?
Upper vs. lower bound. A large sufficient bound may reflect proof technique. Diagnostic: Is there a matching impossibility result?
Passive vs. active access. Query choice can reduce labels while increasing other costs. Diagnostic: What exactly is counted as a sample?
Asymptotic rate vs. finite constants. Big-O comparisons can mislead at operational scales. Diagnostic: Are constants and lower-order terms material?
Model guarantee vs. shifted data. A correct theorem can be irrelevant to deployment. Diagnostic: Do dependence, selection, and distribution assumptions hold?

Structural–Framed Character¶

Task, observation model, class, accuracy, confidence, capacity, guarantee, and upper/lower status are structural. Dataset names, numerical constants tied to a proof, chosen notation, software, and application sector are framed. Particular capacity measures sit between: they are structural for the theorem that uses them but replaceable across learning models.

Structural Core vs. Domain Accent¶

The liftable core is problem family + performance threshold → parameterized resource requirement, which is Complexity. The domain accent consists of observations, learners, hypothesis classes, probability over samples, and generalization or estimation. Removing those yields generic resource complexity; retaining them gives an autonomous learning-theoretic quantity that supports comparisons not captured by time, space, or descriptive dataset size.

Complexity is the strict parent because sample complexity measures the amount of one resource needed to achieve a parameterized task. Theoretical Sampling and Learnable Function Class are close collaborators, but neither alone supplies the resource-bound identity.

The prospective workspace queue contains one strict upward edge to prime:complexity. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Sample complexity Domain-specific

Parents (1) — more general patterns this builds on

Sample complexity is a kind of Complexity Prime

Complexity is the strict parent because sample complexity measures the amount of one resource needed to achieve a parameterized task.

Hierarchy path (1) — routes to 1 parentless root

Sample complexity → Complexity

Neighborhood in Abstraction Space¶

Sample complexity sits in a sparse region of the domain-specific corpus (91^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Computational complexity. Counts operations, time, or memory rather than observations.
VC dimension. A class-capacity measure that can govern sample complexity, not the requirement itself.
Learning curve. An empirical performance-versus-data plot rather than a general guarantee.
Power analysis. Plans hypothesis tests for effect detection under a statistical model.
Dataset size. The number collected, which may be above or below the justified requirement.
Learnability. An existence property often characterized partly through finite or polynomial sample complexity.

References¶

[1] Leslie G. Valiant, ‘A Theory of the Learnable,’ Communications of the ACM 27, no. 11 (1984): 1134–1142, https://doi.org/10.1145/1968.1972. registry ↩

[2] Vladimir N. Vapnik, Statistical Learning Theory (Wiley, 1998). registry ↩

[3] Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, 2014), https://doi.org/10.1017/CBO9781107298019. registry ↩