Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses

• URL: http://arxiv.org/abs/2409.17932v2
• Date: Tue, 22 Oct 2024 17:16:43 GMT
• Title: Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses
• Authors: Mathieu Bazinet, Valentina Zantedeschi, Pascal Germain,
• Abstract summary: We present a general framework for deriving new sample compression bounds that hold for real-valued unbounded losses. We empirically demonstrate the tightness of the bounds and their versatility by evaluating them on random forests and multiple types of neural networks.
• Score: 9.180445799821717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The sample compression theory provides generalization guarantees for predictors that can be fully defined using a subset of the training dataset and a (short) message string, generally defined as a binary sequence. Previous works provided generalization bounds for the zero-one loss, which is restrictive notably when applied to deep learning approaches. In this paper, we present a general framework for deriving new sample compression bounds that hold for real-valued unbounded losses. Using the Pick-To-Learn (P2L) meta-algorithm, which transforms the training method of any machine-learning predictor to yield sample-compressed predictors, we empirically demonstrate the tightness of the bounds and their versatility by evaluating them on random forests and multiple types of neural networks.

Related papers

• Sample Compression Hypernetworks: From Generalization Bounds to Meta-Learning [47.83977297248753]
  Reconstruction functions are pivotal in sample compression theory. We derive a new sample compression generalization bound for real-valued messages. We present a new hypernetwork architecture that outputs predictors with tight generalization guarantees.
  arXiv  Detail & Related papers  (2024-10-17T14:12:35Z)
• 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)
• 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)
• Federated Random Reshuffling with Compression and Variance Reduction [0.0]
  Random Reshuffling (RR) is an immensely popular method for training supervised machine learning models via empirical risk minimization. It is embedded and often set as default in standard machine learning software. We introduce three new algorithms to improve FedRR further: one for taming the variance coming from shuffling and the other for taming the variance due to compression.
  arXiv  Detail & Related papers  (2022-05-08T16:46:11Z)
• Approximability and Generalisation [0.0]
  We study the role of approximability in learning, both in the full precision and the approximated settings of the predictor. We show that under mild conditions, approximable target concepts are learnable from a smaller labelled sample. We give algorithms that guarantee a good predictor whose approximation also enjoys the same generalisation guarantees.
  arXiv  Detail & Related papers  (2022-03-15T15:21:48Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  In particular, we seek to understand the behaviour of the em generalization error of iterative SSL algorithms using information-theoretic principles. Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates.
  arXiv  Detail & Related papers  (2021-10-03T05:38:49Z)
• Predicting Unreliable Predictions by Shattering a Neural Network [145.3823991041987]
  Piecewise linear neural networks can be split into subfunctions. Subfunctions have their own activation pattern, domain, and empirical error. Empirical error for the full network can be written as an expectation over subfunctions.
  arXiv  Detail & Related papers  (2021-06-15T18:34:41Z)
• RATT: Leveraging Unlabeled Data to Guarantee Generalization [96.08979093738024]
  We introduce a method that leverages unlabeled data to produce generalization bounds. We prove that our bound is valid for 0-1 empirical risk minimization. This work provides practitioners with an option for certifying the generalization of deep nets even when unseen labeled data is unavailable.
  arXiv  Detail & Related papers  (2021-05-01T17:05:29Z)
• Compressive Sensing and Neural Networks from a Statistical Learning Perspective [4.561032960211816]
  We present a generalization error analysis for a class of neural networks suitable for sparse reconstruction from few linear measurements. Under realistic conditions, the generalization error scales only logarithmically in the number of layers, and at most linear in number of measurements.
  arXiv  Detail & Related papers  (2020-10-29T15:05:43Z)
• Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
  We advance the understanding of the relations between the network's architecture and its generalizability from the compression perspective. We propose a series of intuitive, data-dependent and easily-measurable properties that tightly characterize the compressibility and generalizability of neural networks.
  arXiv  Detail & Related papers  (2020-01-14T22:26:57Z)

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.