Formal limitations of sample-wise information-theoretic generalization bounds

Abstract

Some of the tightest information-theoretic generalization bounds depend on the average information between the learned hypothesis and a single training example. However, these sample-wise bounds were derived only for expected generalization gap. We show that even for expected squared generalization gap no such sample-wise information-theoretic bounds exist. The same is true for PAC-Bayes and single-draw bounds. Remarkably, PAC-Bayes, single-draw and expected squared generalization gap bounds that depend on information in pairs of examples exist.

2022 IEEE Information Theory Workshop

References in corpus (7)

• Fantastic Generalization Measures and Where to Find Them
• Generalization Bounds via Information Density and Conditional Information Density
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• Tighter risk certificates for neural networks
• On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm
• Tighter expected generalization error bounds via Wasserstein distance
• Information-theoretic generalization bounds for black-box learning algorithms