Is sample complexity always a single fixed number?

No; it depends on the task, tolerance, confidence, and assumptions.

Can an infinite hypothesis class be learnable?

Yes, when its relevant capacity is suitably controlled.

Does more data solve model mismatch?

Not necessarily; the chosen class may still be unable to represent a useful predictor.

AI Glossary / Statistics and probability / Intermediate

Sample complexity

Definition

Sample complexity describes how many observations a learning or estimation procedure needs to meet a specified performance criterion under stated assumptions. In statistical learning theory, it is often expressed in terms of an error tolerance and a failure probability. It concerns information required from data, which is distinct from computational time, memory use, or the number of model parameters.

What it means

Asking how much data an AI system needs is incomplete without saying what it must learn, how accurately, and with what level of reliability. Sample complexity formalizes that dependence for a defined learning setting.
A theorem may give a sufficient upper bound, a necessary lower bound, or an order of growth. These are not interchangeable. A sufficient bound can be conservative, while an empirical learning curve measures performance in a particular experiment rather than proving a universal guarantee.

How it works

Specify the task, loss, and data-generating assumptions. Binary classification, numerical prediction, and reinforcement learning use different notions of error and may count examples, labeled observations, transitions, or episodes differently.
Define the hypothesis class and learning rule. Restricting the possible predictors can reduce the amount of information needed to select among them, but an overly restricted class may exclude every useful solution. More data cannot by itself remove that approximation limitation.
State an accuracy tolerance, commonly epsilon, and a permitted failure probability, commonly delta. In a PAC-style guarantee, the learner succeeds to within the defined tolerance with probability at least 1−delta over the sampled training data.
Distinguish realizable from agnostic settings. Realizability assumes some predictor in the class achieves zero true classification error. Agnostic learning allows noise or model mismatch and often targets performance close to the best predictor in the class rather than arbitrarily small absolute error.
For a finite class H in the realizable binary setting, with independent identically distributed labeled examples and a consistent empirical-risk minimizer, a familiar sufficient bound is n ≥ ln(|H|/delta)/epsilon. The logarithm is natural. This particular expression is not a universal data requirement for all AI systems.
The intuition is that a genuinely inaccurate classifier is unlikely to agree with every independent training label for long. A union bound accounts for the many classifiers that might appear successful by chance. This reasoning relies on the sampling and consistency assumptions.
Infinite classes require other measures of capacity, such as VC dimension in suitable classification settings. The number of trainable parameters is not automatically a complete description of statistical complexity, and modern practical performance can depend on additional structure.
Assess applicability before budgeting data collection. Dependence, label errors, distribution shift, rare subgroups, and changing objectives can make a simple theoretical setting unrealistic. Use theory to understand tradeoffs, then validate with careful learning curves, held-out evaluation, and checks on the deployment population.

Three practical examples

Label-budget planning: a team studies how tighter accuracy requirements affect the amount of labeled data needed.
Algorithm comparison: researchers distinguish a method that needs fewer examples from one that merely runs faster.
Experimental design: analysts ask whether a restricted model class permits a useful guarantee under a defensible sampling model.

Think of it this way

Think of identifying a hidden rule from examples. If only a few rules are possible, fewer examples may eliminate the wrong ones. If many rules remain plausible or the labels are noisy, the task becomes harder. The relevant count depends on the rules and the standard of success, not just the size of the spreadsheet.

Worked example

Consider an original theoretical example with 100 possible binary classifiers. Assume realizability, independent identically distributed labeled examples, and a learner that finds a classifier with zero training error. Set epsilon = 0.05 and delta = 0.05.
The finite-class sufficient bound is ln(100/0.05)/0.05 = ln(2,000)/0.05, approximately 152.018. Rounding upward gives 153 examples.
As an arithmetic check, 100 exp(−0.05×153) is approximately 0.0476, below the permitted failure probability 0.05. The bound therefore certifies the stated guarantee under these assumptions; it does not show that 153 is the smallest possible sample size.
If the error tolerance is halved to 0.025 with the other quantities unchanged, the bound becomes approximately 304.036 and rounds to 305. These values are not a prescription for training a noisy, unrestricted real-world classifier.

Illustrative case study

Fictional case: Oakline Analytics considers a small collection of rule-based routing classifiers. Its research team uses a finite-class bound to explain why accuracy and confidence requirements affect data needs.
Before using the result operationally, it finds that historical labels disagree and that new ticket categories are emerging. The team therefore does not claim the realizable guarantee applies. It builds learning curves on appropriately separated data and reports subgroup performance and uncertainty alongside the theoretical illustration.

Common misconceptions and mistakes

Sample complexity is not the time complexity of training.
A sufficient upper bound is not proof that fewer observations cannot work.
Zero training error alone does not guarantee low future error without control of the learning setting.
More data from the wrong population may not improve the intended deployment performance.
Duplicating existing examples does not create the same information as collecting new independent observations.
The failure probability is about the learning guarantee across samples, not a claim that each future prediction has that same error probability.

Business use

Use sample complexity to make data requirements explicit and to distinguish uncertainty about the learning task from computational constraints. For a business project, record the target error, evaluation population, label quality, and assumptions before translating any bound into a budget. Empirical validation remains necessary when the theoretical model is an approximation to operating conditions.

Check your understanding

What changes when epsilon becomes smaller?

Answer: The required accuracy is stricter, generally increasing data needs.

What does the example's 153 represent?

Answer: A sufficient bound under a specific realizable finite-class setup, not a universal minimum.

Related terms

Learn next

Compare a theoretical sample bound with an empirical learning curve for a clearly defined task. List which theorem assumptions hold and which are doubtful before interpreting the difference.

Learning curve

Sources

MIT 6.790, Learnability and VC Dimension: https://gradml.mit.edu/supervised/learnability_and_vc/ Shalev-Shwartz and Ben-David, Understanding Machine Learning: https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf The finite-class numerical example and case are original illustrations.

Previous: Sample augmentation Next: Sample covariance matrix