margin theory of generalization

A classifier that barely separates its training points, with predictions hovering near the decision boundary, is fragile, while one that classifies confidently, pushing every correct point far onto its own side, is robust. Margin theory turns this confidence into a generalization guarantee: what matters is not merely whether you got the training labels right, but by how large a margin. Big margins let you bound error with a complexity that ignores the ambient dimension and even the number of parameters.

For real-valued scorers, replace the zero-one training error with the margin loss — the fraction of examples classified correctly but with confidence below a threshold gamma. The bound then reads: true misclassification error is at most the empirical gamma-margin error plus the complexity of the scaled class divided by gamma, plus lower-order terms, where the complexity is typically a Rademacher term that scales with the norms, not the count, of the weights. Dividing by gamma is the crux: a larger margin shrinks the effective complexity. This is the engine behind support vector machine and boosting generalization theory.

Margin theory explains otherwise paradoxical observations — why AdaBoost keeps improving test error after training error reaches zero, because it keeps enlarging margins, and why norm-controlled overparameterized networks generalize. Modern spectrally-normalized margin bounds extend it to deep nets. The caveat: such bounds are typically still numerically loose for deep learning, useful more for the qualitative scaling, norms over counts, than for exact numbers.