mlsanityData to 7 Oct 2026

Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses

arXiv 2409.17932 ↗First posted 26 Sep 2024cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 25 of its 89 references that are in the map. First posted on arXiv 26 Sep 2024.

Builds on

25 of 89 references.

References · 25

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lightercited by 4,243
  3. 2015Character-level Convolutional Networks for Text Classificationcited by 2,293
  4. 2020Tighter risk certificates for neural networkscited by 112
  5. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  6. 2023Non-Vacuous Generalization Bounds for Large Language Modelscited by 53
  7. 2015Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithmcited by 50
  8. 2015Sample compression schemes for VC classescited by 46
  9. 2020PAC-Bayes unleashed: generalisation bounds with unbounded lossescited by 43
  10. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  11. 2020Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Boundcited by 31
  12. 2024Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Modelscited by 25
13 more
  1. 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
  2. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  3. 2023Compression, Generalization and Learningcited by 21
  4. 2024Mission Impossible: A Statistical Perspective on Jailbreaking LLMscited by 21
  5. 2018Sample Compression for Real-Valued Learnerscited by 19
  6. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  7. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  8. 2024List Sample Compression and Uniform Convergencecited by 10
  9. 2024PAC-Bayes-Chernoff bounds for unbounded lossescited by 9
  10. 2018Agnostic Sample Compression Schemes for Regressioncited by 7
  11. 2023Comparing Comparators in Generalization Boundscited by 5
  12. 2018On the Perceptron's Compressioncited by 3
  13. 2018Sample Compression, Support Vectors, and Generalization in Deep Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2024Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworkscited by 3
  2. 2025A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votescited by 3
  3. 2026Bound to Disagree: Generalization Bounds via Certifiable Surrogatescited by 2
  4. 2025Sample Compression for Self Certified Continual Learningcited by 1