Tighter CMI-Based Generalization Bounds via Projection and Quantization
Milad Sefidgaran, Kimia Nadjahi, Abdellatif Zaidi
In this paper, we leverage stochastic projection and lossy compression to establish new conditional mutual information (CMI) bounds on the generalization error of statistical learning algorithms. It is shown that these bounds are generally tighter than existing ones. In particular, we prove that for certain problem instances for which existing MI and CMI bounds where shown recently in Attias et al. [2024] and Livni [2023] to become vacuous or fail to describe the right generalization behavior, our bounds yield suitable generalization guarantees of the order of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the size of the training dataset. Furthermore, we use our bounds to investigate the problem of data "memorization" raised in those works, and which asserts that there are learning problem instances for which for any learning algorithm there exist distributions under which the algorithm "memorizes'' the training dataset. We show that for every learning algorithm and every data distribution, there exists an algorithm that does *not* memorize and which yields comparable generalization error. Finally, we apply our approach to derive a novel generalization bound for random subspace algorithms and use it in the context of SGD and SGLD optimization to establish more explicit bounds.