Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?
This work addresses a foundational problem in machine learning theory for researchers, providing incremental improvements to generalization bounds by handling invariances in neural networks.
The paper tackles the challenge of obtaining non-vacuous generalization bounds for ReLU networks by addressing rescaling invariances that cause PAC-Bayes complexities to vary arbitrarily for the same function, proposing a lifted representation to resolve this and exploring tighter bounds and algorithmic aspects.
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.