Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms
Understanding generalization in modern machine learning settings has been one of the major challenges in statistical learning theory. In this context, recent years have witnessed the development of various generalization bounds suggesting different complexity notions such as the mutual information between the data sample and the algorithm output, compressibility of the hypothesis space, and the fractal dimension of the hypothesis space. While these bounds have illuminated the problem at hand from different angles, their suggested complexity notions might appear seemingly unrelated, thereby restricting their high-level impact. In this study, we prove novel generalization bounds through the lens of rate-distortion theory, and explicitly relate the concepts of mutual information, compressibility, and fractal dimensions in a single mathematical framework. Our approach consists of (i) defining a generalized notion of compressibility by using source coding concepts, and (ii) showing that the compression error rate' can be linked to the generalization error both in expectation and with high probability. We show that in the lossless compression' setting, we recover and improve existing mutual information-based bounds, whereas a `lossy compression' scheme allows us to link generalization to the rate-distortion dimension -- a particular notion of fractal dimension. Our results bring a more unified perspective on generalization and open up several future research directions.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsLearning TheorySimilar Papers 제목 키워드 기반
Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning
In this paper, we use tools from rate-distortion theory to establish new upper bounds on the generalization error of statistical distributed learning algorithms. Specifically, there are $K$ clients whose individually cho…
Federated LearningGeneralization BoundsInformation Theoretic Lower Bounds for Information Theoretic Upper Bounds
We examine the relationship between the mutual information between the output model and the empirical sample and the generalization of the algorithm in the context of stochastic convex optimization. Despite increasing in…
Generalization BoundsInformation-Theoretic Generalization Bounds for Stochastic Gradient Descent
We study the generalization properties of the popular stochastic optimization method known as stochastic gradient descent (SGD) for optimizing general non-convex loss functions. Our main contribution is providing upper b…
Generalization BoundsStochastic OptimizationAn Information-Theoretic Framework for Out-of-Distribution Generalization with Applications to Stochastic Gradient Langevin Dynamics
We study the Out-of-Distribution (OOD) generalization in machine learning and propose a general framework that establishes information-theoretic generalization bounds. Our framework interpolates freely between Integral P…
Generalization BoundsOut-of-Distribution GeneralizationInformation-Theoretic Bayes Risk Lower Bounds for Realizable Models
We derive information-theoretic lower bounds on the Bayes risk and generalization error of realizable machine learning models. In particular, we employ an analysis in which the rate-distortion function of the model param…