Data-dependent Generalization Bounds via Variable-Size Compressibility

• URL: http://arxiv.org/abs/2303.05369v3
• Date: Tue, 11 Jun 2024 17:12:22 GMT
• Title: Data-dependent Generalization Bounds via Variable-Size Compressibility
• Authors: Milad Sefidgaran, Abdellatif Zaidi,
• Abstract summary: We establish novel data-dependent upper bounds on the generalization error through the lens of a "variable-size compressibility" framework. In this framework, the generalization error of an algorithm is linked to a variable-size 'compression rate' of its input data. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds.
• Score: 16.2444595840653
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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\'enyi information dimension of a process, and the metric mean dimension.

Related papers

• Slicing Mutual Information Generalization Bounds for Neural Networks [14.48773730230054]
  We introduce new, tighter information-theoretic generalization bounds tailored for deep learning algorithms. Our bounds offer significant computational and statistical advantages over standard MI bounds. We extend our analysis to algorithms whose parameters do not need to exactly lie on random subspaces.
  arXiv  Detail & Related papers  (2024-06-06T13:15:37Z)
• A unified framework for information-theoretic generalization bounds [8.04975023021212]
  This paper presents a general methodology for deriving information-theoretic generalization bounds for learning algorithms. The main technical tool is a probabilistic decorrelation lemma based on a change of measure and a relaxation of Young's inequality in $L_psi_p$ Orlicz spaces.
  arXiv  Detail & Related papers  (2023-05-18T15:36:20Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Robustness Implies Generalization via Data-Dependent Generalization Bounds [24.413499775513145]
  This paper proves that robustness implies generalization via data-dependent generalization bounds. We present several examples, including ones for lasso and deep learning, in which our bounds are provably preferable.
  arXiv  Detail & Related papers  (2022-06-27T17:58:06Z)
• Generalization Bounds via Convex Analysis [12.411844611718958]
  We show that it is possible to replace the mutual information by any strongly convex function of the joint input-output distribution. Examples include bounds stated in terms of $p$-norm divergences and the Wasserstein-2 distance.
  arXiv  Detail & Related papers  (2022-02-10T12:30:45Z)
• Non-Linear Spectral Dimensionality Reduction Under Uncertainty [107.01839211235583]
  We propose a new dimensionality reduction framework, called NGEU, which leverages uncertainty information and directly extends several traditional approaches. We show that the proposed NGEU formulation exhibits a global closed-form solution, and we analyze, based on the Rademacher complexity, how the underlying uncertainties theoretically affect the generalization ability of the framework.
  arXiv  Detail & Related papers  (2022-02-09T19:01:33Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Dimension Free Generalization Bounds for Non Linear Metric Learning [61.193693608166114]
  We provide uniform generalization bounds for two regimes -- the sparse regime, and a non-sparse regime. We show that by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees.
  arXiv  Detail & Related papers  (2021-02-07T14:47:00Z)
• Learning Output Embeddings in Structured Prediction [73.99064151691597]
  A powerful and flexible approach to structured prediction consists in embedding the structured objects to be predicted into a feature space of possibly infinite dimension. A prediction in the original space is computed by solving a pre-image problem. In this work, we propose to jointly learn a finite approximation of the output embedding and the regression function into the new feature space.
  arXiv  Detail & Related papers  (2020-07-29T09:32:53Z)
• Generalization Bounds via Information Density and Conditional Information Density [14.147617330278662]
  We present a general approach, based on an exponential inequality, to derive bounds on the generalization error of randomized learning algorithms. We provide bounds on the average generalization error as well as bounds on its tail probability, for both the PAC-Bayesian and single-draw scenarios.
  arXiv  Detail & Related papers  (2020-05-16T17:04:24Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.