sample complexity bounds

How much data is enough? Sample complexity answers it precisely: the number of training examples a learner needs to reach a target accuracy epsilon with confidence one minus delta. It is the currency of learnability — a class is learnable exactly when this number is finite and grows only polynomially in the accuracy and confidence you demand. Think of it as the price tag, in examples, on a given guarantee.

For binary classification the canonical bound says order d plus log of one over delta, all over epsilon, examples suffice in the realizable case, and the same numerator over epsilon squared in the agnostic case, where d is the VC dimension — the quadratic-versus-linear difference in one over epsilon is the slow-versus-fast-rate distinction. More refined bounds replace d with Rademacher complexity, covering numbers, or margin-based quantities to capture data-dependent structure. Matching lower bounds, proved via the probabilistic method or information-theoretic arguments, show these counts cannot be reduced, pinning down the true difficulty.

Sample complexity is the practical heart of learning theory: it tells you whether a problem is feasible with the data you have, how accuracy scales as you collect more, and which structural assumptions — margin, sparsity, smoothness — buy you cheaper learning. It also frames active learning and semi-supervised learning, which aim to beat the passive bound. The caveat is the usual worst-case looseness — real distributions often need far fewer samples than the distribution-free bound predicts.