2023/03/09 by Milad Sefidgaran, Sefidgaran, Milad, Abdellatif Zaidi +1
Computer Science · Engineering · #FOS: Computer and information sciences #Image and Signal Denoising Methods #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Medical Image Segmentation Techniques #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2303.05369
openalex publication_date 2023/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a "variable-size compressibility" framework that we introduce newly here. 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. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds. Moreover, it is shown that our framework also allows to derive general bounds on any function of the input data and output hypothesis random variables. In particular, these general bounds are shown to 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.