Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?
Not on the map. Why?
Abstract (arXiv)
A central challenge in understanding generalization is to obtain non-vacuous guarantees that go beyond worst-case complexity over data or weight space. Among existing approaches, PAC-Bayes bounds stand out as they can provide tight, data-dependent guarantees even for large networks. However, in ReLU networks, rescaling invariances mean that different weight distributions can represent the same function while leading to arbitrarily different PAC-Bayes complexities. We propose to study PAC-Bayes bounds in an invariant, lifted representation that resolves this discrepancy. This paper explores both the guarantees provided by this approach (invariance, tighter bounds via data processing) and the algorithmic aspects of KL-based rescaling-invariant PAC-Bayes bounds.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 34 of its 45 references that are in the map. First posted on arXiv 30 Sep 2025.
Builds on
34 of 45 references.
References · 34
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
- 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
- 2015Norm-Based Capacity Control in Neural Networkscited by 299
- 2021Deep learning: a statistical viewpointcited by 239
- 2021User-friendly introduction to PAC-Bayes boundscited by 234
- 2017Generalization in Deep Learningcited by 146
- 2019A Primer on PAC-Bayesian Learningcited by 130
- 2020Tighter risk certificates for neural networkscited by 112
- 2020On the role of data in PAC-Bayes boundscited by 64
- 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 60
- 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 45
- 2023Abide by the Law and Follow the Flow: Conservation Laws for Gradient Flowscited by 44
22 more
- 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
- 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
- 2020Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networkscited by 29
- 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
- 2021An Embedding of ReLU Networks and an Analysis of their Identifiabilitycited by 20
- 2021On Margins and Derandomisation in PAC-Bayescited by 19
- 2017Comparison of Batch Normalization and Weight Normalization Algorithms for the Large-scale Image Classificationcited by 18
- 2019Equi-normalization of Neural Networkscited by 16
- 2019Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variationcited by 14
- 2020PAC-Bayesian Bound for the Conditional Value at Riskcited by 13
- 2024A PAC-Bayesian Link Between Generalisation and Flat Minimacited by 13
- 2022Local Identifiability of Deep ReLU Neural Networks: the Theorycited by 12
- 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 11
- 2022Change of measure through the Legendre transformcited by 10
- 2023A path-norm toolkit for modern networks: consequences, promises and challengescited by 10
- 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
- 2022Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficultycited by 9
- 2023Comparing Comparators in Generalization Boundscited by 5
- 2024A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizationscited by 4
- 2022Controlling Multiple Errors Simultaneously with a PAC-Bayes Boundcited by 3
- 2023Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisationcited by 3
- 2023A note on regularised NTK dynamics with an application to PAC-Bayesian trainingcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.