Generalization Bounds via Information Density and Conditional Information Density

Abstract

We present a general approach, based on exponential inequalities, to derive bounds on the generalization error of randomized learning algorithms. Using this approach, we provide bounds on the average generalization error as well as bounds on its tail probability, for both the PAC-Bayesian and single-draw scenarios. Specifically, for the case of sub-Gaussian loss functions, we obtain novel bounds that depend on the information density between the training data and the output hypothesis. When suitably weakened, these bounds recover many of the information-theoretic bounds available in the literature. We also extend the proposed exponential-inequality approach to the setting recently introduced by Steinke and Zakynthinou (2020), where the learning algorithm depends on a randomly selected subset of the available training data. For this setup, we present bounds for bounded loss functions in terms of the conditional information density between the output hypothesis and the random variable determining the subset choice, given all training data. Through our approach, we recover the average generalization bound presented by Steinke and Zakynthinou (2020) and extend it to the PAC-Bayesian and single-draw scenarios. For the single-draw scenario, we also obtain novel bounds in terms of the conditional $\alpha$-mutual information and the conditional maximal leakage.

Published in Journal on Selected Areas in Information Theory (JSAIT). This version incorporates a correction to the JSAIT version. The correction is detailed at https://gdurisi.github.io/files/2021/jsait-correction.pdf

References in corpus (5)

• Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• On the role of data in PAC-Bayes bounds
• Generalization Error Bounds Via Rényi-, $f$-Divergences and Maximal Leakage
• Still no free lunches: the price to pay for tighter PAC-Bayes bounds

Cited by in corpus (11)

• User-friendly introduction to PAC-Bayes bounds
• Recent advances in deep learning theory
• On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm
• Reasoning About Generalization via Conditional Mutual Information
• Information Complexity and Generalization Bounds
• PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
• Information-Theoretic Analysis of Minimax Excess Risk
• Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data
• Formal limitations of sample-wise information-theoretic generalization bounds
• Comparing Comparators in Generalization Bounds
• PAC-Bayes-Chernoff bounds for unbounded losses