Sharper Than VC: Margins, Localization, Compression, PAC-Bayes

The looseness problem

Classical VC bounds are honest but pessimistic. They take the worst distribution, the worst hypothesis, and a complexity that scales with raw dimension — so for a modern overparameterized model the bound is often greater than one, i.e. it promises nothing. Yet these models generalize. The modern program is not to discard uniform convergence but to refine it with extra structure the worst case ignores: the size of the margin, the variance of the relevant functions, the compressibility of the output, and the role of a prior. Four refinements, four sources of slack recovered.

Margins: confidence as capacity control

Margin theory observes that a classifier which separates the data with room to spare should be more trustworthy than one that barely squeaks by. Formalize the margin as the signed confidence of the prediction, and you can prove a bound that depends on the Rademacher complexity of the class scaled by 1/margin, with the raw dimension dropping out entirely. A large-margin linear separator in a million dimensions has a generalization bound governed by the margin, not the million.

This is the theoretical heart of the support vector machine — maximizing the margin is literally minimizing this capacity term, the SRM principle of guide 2 made concrete. Margin bounds also gave the first credible explanation for boosting's refusal to overfit even as you add classifiers, and margin-style normalized-complexity arguments are a live thread in trying to explain deep networks today.

Localization: only the relevant ball matters

Global Rademacher complexity measures the whole class, but ERM only ever lands near the best hypothesis — the high-risk junk is irrelevant. Localized Rademacher complexity exploits this by restricting the complexity to the sub-ball of functions with small variance (equivalently, small excess risk). Because low-risk functions also have low variance, this localized quantity is much smaller, and feeding it back through a fixed-point argument yields fast rates — a generalization gap of order 1/m instead of the pessimistic 1/sqrt(m).

\mathbb{E}\,\sup_{f\in\mathcal{F},\ \mathrm{Var}(f)\le r}\big(\mathbb{E}f-\hat{\mathbb{E}}f\big)\le \psi(r),\qquad \psi(r^\star)=r^\star

Localization restricts the supremum to the low-variance ball around the best hypothesis; the rate is set by the fixed point r⋆ of the sub-root function ψ.

The cost is sharper machinery: localization needs Talagrand's inequality for the concentration of the supremum, and the variance term Bernstein gave us in guide 3. The payoff is the gap between a bound that says 'eventually' and one that matches the empirically observed rate — localization is how learning theory earns the right to be quantitatively believed.

Compression: the hypothesis you can summarize

Sample compression offers a strikingly different guarantee with no capacity measure at all. If your algorithm's output can be reconstructed from just k of the m training examples — a compression set — then it generalizes, with a bound that depends only on k and m. The SVM is the poster child: it is fully determined by its support vectors, so the number of support vectors is a compression size, and few support vectors directly certify good generalization.

R(h)\le \hat{R}(h)+\sqrt{\frac{k\ln m+\ln\frac{1}{\delta}}{2(m-k)}}

A sample-compression bound: read the compression size k off your trained model and the risk is controlled with no capacity measure at all.

PAC-Bayes: bounds over distributions of hypotheses

PAC-Bayes reframes everything in terms of distributions over hypotheses. Fix a data-independent prior P, let learning produce a posterior Q, and the theorem bounds the average true risk under Q by the average empirical risk plus a complexity term of the form sqrt(KL(Q‖P) / m). The capacity is no longer a class size but the KL divergence from prior to posterior — how much information the data forced you to add. Stay close to the prior and you pay little.

\mathbb{E}_{h\sim Q}\,R(h)\le \mathbb{E}_{h\sim Q}\,\hat{R}(h)+\sqrt{\frac{\mathrm{KL}(Q\,\|\,P)+\ln\frac{m}{\delta}}{2(m-1)}}

The PAC-Bayes bound: the average true risk under posterior Q is controlled by its empirical risk plus the KL information distance from the fixed prior P.

Two things make PAC-Bayes special. First, it is the framework that has produced non-vacuous generalization bounds for genuine deep networks: by optimizing the posterior — typically a noise distribution around the trained weights — researchers get numbers below one on real image classifiers, where every VC or norm-based bound is astronomically loose. Second, it gives a principled account of flatness: a posterior that tolerates weight noise concentrates on flat minima, formally linking PAC-Bayes to the benign-overfitting and double-descent phenomena that classical theory cannot touch.

# PAC-Bayes (McAllester form), with prob >= 1 - delta:
#   E_{h~Q}[ risk(h) ]
#       <=  E_{h~Q}[ emp_risk(h) ]
#         + sqrt( ( KL(Q || P) + log(m/delta) ) / (2(m-1)) )
# choose Q to minimize the RHS -> a trainable, computable bound

Complexity = information distance from a fixed prior, not the size of a class.