Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities
Provides a new theoretical tool for deriving tighter probabilistic guarantees in learning theory, information theory, and statistics.
The authors propose a unified framework for change of measure inequalities that yields tighter bounds than existing methods, and apply it to generalization error analysis, PAC-Bayesian theory, differential privacy, and data memorization, recovering or improving best-known results.
Change of measure inequalities translate divergences between probability measures into explicit bounds on event probabilities, and play an important role in deriving probabilistic guarantees in learning theory, information theory, and statistics. We propose novel change of measure inequalities via a unified framework based on the data processing inequality, which is surprisingly elementary yet powerful enough to yield novel, tighter inequalities. We provide change of measure inequalities in terms of a broad family of information measures, including $f$-divergences (with Kullback-Leibler divergence and $χ^2$-divergence as special cases), Rényi divergence, and $α$-mutual information (with maximal leakage as a special case). We apply these results to generalization error analysis, PAC-Bayesian theory, differential privacy, and data memorization, obtaining stronger guarantees while recovering best-known results through simplified analyses.