Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses
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.
Code (1)
Tasks
Generalization BoundsvalidSimilar Papers 제목 키워드 기반
Sample Compression Hypernetworks: From Generalization Bounds to Meta-Learning
Reconstruction functions are pivotal in sample compression theory, a framework for deriving tight generalization bounds. From a small sample of the training set (the compression set) and an optional stream of information…
Generalization BoundsMeta-LearningStronger generalization bounds for deep nets via a compression approach
Deep nets generalize well despite having more parameters than the number of training samples. Recent works try to give an explanation using PAC-Bayes and Margin-based analyses, but do not as yet result in sample complexi…
Generalization BoundsStable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound
We analyze a family of supervised learning algorithms based on sample compression schemes that are stable, in the sense that removing points from the training set which were not selected for the compression set does not …
Generalization BoundsOpen-Ended Question AnsweringRate-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…
Generalization BoundsLearning TheorySupervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysis
This paper presents a novel information-theoretic perspective on generalization in machine learning by framing the learning problem within the context of lossy compression and applying finite blocklength analysis. In our…