On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm

Abstract

In this work, we unify several expected generalization error bounds based on random subsets using the framework developed by Hellström and Durisi [1]. First, we recover the bounds based on the individual sample mutual information from Bu et al. [2] and on a random subset of the dataset from Negrea et al. [3]. Then, we introduce their new, analogous bounds in the randomized subsample setting from Steinke and Zakynthinou [4], and we identify some limitations of the framework. Finally, we extend the bounds from Haghifam et al. [5] for Langevin dynamics to stochastic gradient Langevin dynamics and we refine them for loss functions with potentially large gradient norms.

arXiv commentTo appear in the Information Theory Workshop (ITW 2020) conference. 10 pages, 5 of the main text, and 5 of appendices

References in corpus (5)

• Information-theoretic analysis of generalization capability of learning algorithms
• Tightening Mutual Information Based Bounds on Generalization Error
• Generalization Bounds via Information Density and Conditional Information Density
• 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

Cited by in corpus (6)

• Tighter expected generalization error bounds via Wasserstein distance
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data
• Formal limitations of sample-wise information-theoretic generalization bounds
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• Comparing Comparators in Generalization Bounds