Strengthened Information-theoretic Bounds on the Generalization Error

2019/03/09 by Issa, Ibrahim, Esposito, Amedeo Roberto, Gastpar, Michael · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1903.03787

Abstract

The following problem is considered: given a joint distribution P_XY and an event E, bound P_XY(E) in terms of P_XP_Y(E) (where P_XP_Y is the product of the marginals of P_XY) and a measure of dependence of X and Y. Such bounds have direct applications in the analysis of the generalization error of learning algorithms, where E represents a large error event and the measure of dependence controls the degree of overfitting. Herein, bounds are demonstrated using several information-theoretic metrics, in particular: mutual information, lautum information, maximal leakage, and J_∞. The mutual information bound can outperform comparable bounds in the literature by an arbitrarily large factor.

Cited by

• Tight Generalization Error Bounds for Stochastic Gradient Descent in Non-convex Learning

Related

• Generalization Error Bounds Via R 'enyi-, f-Divergences and Maximal\n Leakage
• Robust Generalization via α-Mutual Information
• Fast Rate Information-theoretic Bounds on Generalization Errors
• A unified framework for information-theoretic generalization bounds
• Generalization Error Bounds via mth Central Moments of the Information Density