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.

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.

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.

Abstract Reasoning¶

Define the target performance and loss on future or unobserved data. 2. Specify the observation process and what information each sample contains. 3. Fix the hypothesis class, comparator, and whether the learner must be proper. 4. Declare accuracy and confidence parameters with their probability space. 5. Select a capacity or information measure appropriate to the task. 6. Prove an upper bound by showing a learner succeeds once the sample exceeds a function of the parameters.

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.

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