Escaping Parameter Space: Tight Generalization Bounds via Representation Quality

arXiv:2610.23729v1 Announce Type: new Abstract: We derive a tight generalization bound for deterministic neural We derive a tight generalization bound for deterministic neural networks based on their last hidden layer representations. By evaluating representation quality with a parameter-free k-nearest-neighbor (k-NN) classifier, our certificate avoids traditional parameter-space complexity measures, KL divergences to a posterior, weight norms, and compression. The bound is tight: trained from scratch, it reaches an 8.0 percentage point gap to test error on CIFAR-10 (ResNet-18) and yields the first non-vacuous certificates we are aware of on CIFAR-100; with frozen DINOv2 representations, it certifies at 1.4% on CIFAR-10 and 23.1% on 1,000-class ImageNet. It decomposes additively into three empirical, independently measurable quantities: local class geometry (k-NN decoder error), decoder-network agreement, and training stability. This allows the bound to act as a diagnostic tool: we demonstrate that actively destroying local class geometry eliminates generalization while leaving dataset memorization intact, identifying class geometry as a causally relevant mechanism for generalization. Finally, we show that learned representations are significantly less sensitive to weight noise than linear readouts, suggesting why parameter-space certificates often struggle to remain tight.

Related

• A Survey on Data-Dependent Worst-Case Generalization Bounds
• Dimension-Free PAC-Bayes Generalization for Deep Neural Networks via Dirichlet Processes
• CGRL: Causal-Guided Representation Learning for Node-Level Out-of-Distribution Generalization
• Representation Gap: Explaining the Unreasonable Effectiveness of Neural Networks from a Geometric Perspective

Source: arXiv cs.LG | 2026-10-19