Generalization Error Bounds via Information-Theoretic Methods and Convex Analysis

Generalization error bounds are critical to understanding the performance of machine learning models. The last few years have witnessed important new advancements in the study of these bounds. The purpose of this work is to offer an overview of some of these developments and of the related theoretical tools. Russo and Zou, Xu and Raginsky were the first to obtain bounds that provided an information-theoretic understanding of generalization in learning problems. In this survey we study the generalization error of supervised learning algorithms, first in terms of the mutual information between their input and the output and then, we study the recent generalization of the results of Neu and Lugosi beyond the choice of the mutual information to measure the dependence between the input and the output. They showed that it is possible to replace the mutual information by any strongly convex function of the joint input-output distribution. This new approach provides us generalization bounds that improve the previously known ones or are entirely new. Moreover, we show some bounds constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm, which can be tighter and easier to evaluate in several applications

Recommended citation: Gnazzo, Angelo. (2022). "Generalization Error Bounds via Information-Theoretic Methods and Convex Analysis." Se ester Paper, ETH Zürich.
Download Paper