Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses

Mathieu Bazinet, Valentina Zantedeschi, Pascal Germain
9/26/2024
cs.LG

No official code found. Best implementation: GRAAL-Research/pick-to-learn (0 stars, MIT, last commit 2025-12-16).

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.

View on arXivView PDF

Code Implementations(1)

GRAAL-Research/pick-to-learnCommunity100%
MIT

Picking-to-learn or learning to pick? That is the question

00Python, Jupyter NotebookJun 7, 202410 months agoMIT

Similar Papers

Slicing Mutual Information Generalization Bounds for Neural Networks

80% match1 repo12026

A Model-Driven Lossless Compression Algorithm Resistant to Mismatch

80% match2026

Sample Compression Scheme Reductions

80% match2024

R2 Loss: Range Restriction Loss for Model Compression and Quantization

80% match2023

Understanding The Effectiveness of Lossy Compression in Machine Learning Training Sets

80% match2024

Neural Normalized Compression Distance and the Disconnect Between Compression and Classification

80% match2024

Cite this paper

@article{bazinet2024sample,
  title  = {Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses},
  author = {Mathieu Bazinet and Valentina Zantedeschi and Pascal Germain},
  year   = {2024},
  eprint = {2409.17932},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2409.17932v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2409.17932.svg)](https://codeofpaper.com/paper/2409.17932)

Discussion