Comparing Comparators in Generalization Bounds
arXiv:2310.10534
Abstract
We derive generic information-theoretic and PAC-Bayesian generalization bounds involving an arbitrary convex comparator function, which measures the discrepancy between the training and population loss. The bounds hold under the assumption that the cumulant-generating function (CGF) of the comparator is upper-bounded by the corresponding CGF within a family of bounding distributions. We show that the tightest possible bound is obtained with the comparator being the convex conjugate of the CGF of the bounding distribution, also known as the Cramér function. This conclusion applies more broadly to generalization bounds with a similar structure. This confirms the near-optimality of known bounds for bounded and sub-Gaussian losses and leads to novel bounds under other bounding distributions.
AISTATS 2024
References in corpus (26)
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
- Information-theoretic analysis of generalization capability of learning algorithms
- Statistical exponential families: A digest with flash cards
- A Note on the PAC Bayesian Theorem
- Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
- User-friendly introduction to PAC-Bayes bounds
- Generalization Bounds via Information Density and Conditional Information Density
- Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
- Simpler PAC-Bayesian Bounds for Hostile Data
- Tighter risk certificates for neural networks
- On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm
- On the role of data in PAC-Bayes bounds
- Information-theoretic generalization bounds for black-box learning algorithms
- PAC-Bayesian Bound for the Conditional Value at Risk
- PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
- Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks
- PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization
- Generalization Bounds: Perspectives from Information Theory and PAC-Bayes
- A New Family of Generalization Bounds Using Samplewise Evaluated CMI
- On Margins and Derandomisation in PAC-Bayes
- Online-to-PAC Conversions: Generalization Bounds via Regret Analysis
- More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity
- Tighter Information-Theoretic Generalization Bounds from Supersamples
- Exponential Stochastic Inequality
- Fast Rate Information-theoretic Bounds on Generalization Errors
- PAC-Bayes-Chernoff bounds for unbounded losses