A Compressibility Approach to Generalization and (No) Memorization

The lecture is composed of two parts. In the first one, I will present a novel framework for studying the generalization error of statistical learning algorithms, through the lens of a variable-size compressibility of algorithms. In this framework, the generalization error of an algorithm is linked to a variable-size 'compression rate’ of its input data. This is shown to yield bounds that depend on the empirical measure of the given input data at hand, rather than its unknown distribution. Moreover, it is shown that these general bounds subsume and possibly improve over several existing PAC-Bayes and data-dependent intrinsic dimension-based bounds that are recovered as special cases, thus unveiling a unifying character of our approach. For instance, a new data-dependent intrinsic dimension-based bound is established, which connects the generalization error to the optimization trajectories and reveals various interesting connections with the rate-distortion dimension of a process, the Rényi information dimension of a process and the metric mean dimension. The second part revolves around the important question of the relationship between generalization and data memorization in machine learning, which is yet to be fully understood. Indeed, the intuition that good algorithms should only extract relevant information and discard all irrelevant ones, which is also supported by some theoretic works, is challenged by the enormous success of modern overparametrized deep neural networks. I will be showing how suitable usage of the presented compressibility framework of the first part leads to bounds that are non-vacuous for certain instances problems for which classic MI and CMI bounds fail; and allows to characterize whether memorization is necessary for generalization for certain instance problems as was recently claimed. If time permits, I will also discuss various other implications, in particular on sample-compression schemes, fingerprinting codes and privacy attacks.