Why Linear Probing Works: Non-Vacuous Generalization Bounds via Effective Dimension

Linear probing on frozen features is the standard evalua-tion protocol for vision foundation models, yet classical theory for d-dimensional classifiers demands Ω(d) labeled samples, far more thanpractitioners actually need. We resolve this discrepancy with the first non-vacuous PAC-Bayes generalization bounds for linear probing on frozenvision foundation-model features. The key insight is that foundation-modelfeatures do not fill Rd : covariance spectra decay steeply, concentratingvariance in a subspace of effective dimension deff ≪ d. A data-dependentGaussian prior aligned to this spectral structure yields a certificate whosecomplexity is governed by deff and the classification margin γ rather thanthe ambient dimension d. We validate the theory on ImageNet across 12vision encoders spanning discriminative, language-supervised, generative,and predictive pretraining: the bound is non-vacuous for all discrimi-natively pretrained models and ranks among the tightest PAC-Bayescertificates reported for any vision model. Three empirical predictionsfollow: generative pretraining yields markedly less certifiable features thandiscriminative pretraining, deff alone ranks foundation models withoutany labels, and larger models tend to be more certifiable because scalesteepens spectral decay.