Tightening Mutual Information Based Bounds on Generalization Error
This work provides a tighter and more practical bound on generalization error for machine learning researchers, though it is incremental as it builds on existing information-theoretic frameworks.
The paper tackles the problem of bounding generalization error in supervised learning by deriving an information-theoretic upper bound based on mutual information between individual training samples and algorithm output, which is tighter and more applicable under general loss conditions than existing bounds, with examples showing improved tightness for algorithms like SGLD.
An information-theoretic upper bound on the generalization error of supervised learning algorithms is derived. The bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm. The bound is derived under more general conditions on the loss function than in existing studies; nevertheless, it provides a tighter characterization of the generalization error. Examples of learning algorithms are provided to demonstrate the the tightness of the bound, and to show that it has a broad range of applicability. Application to noisy and iterative algorithms, e.g., stochastic gradient Langevin dynamics (SGLD), is also studied, where the constructed bound provides a tighter characterization of the generalization error than existing results. Finally, it is demonstrated that, unlike existing bounds, which are difficult to compute and evaluate empirically, the proposed bound can be estimated easily in practice.