Reasoning About Generalization via Conditional Mutual Information
This provides a foundational theoretical tool for analyzing generalization across various ML algorithms, though it is incremental in tying together prior methods.
The paper tackles the problem of understanding generalization in machine learning by introducing an information-theoretic framework based on Conditional Mutual Information (CMI), which unifies existing approaches like uniform convergence and adaptive data analysis, showing that bounded CMI leads to generalization guarantees.
We provide an information-theoretic framework for studying the generalization properties of machine learning algorithms. Our framework ties together existing approaches, including uniform convergence bounds and recent methods for adaptive data analysis. Specifically, we use Conditional Mutual Information (CMI) to quantify how well the input (i.e., the training data) can be recognized given the output (i.e., the trained model) of the learning algorithm. We show that bounds on CMI can be obtained from VC dimension, compression schemes, differential privacy, and other methods. We then show that bounded CMI implies various forms of generalization.