mlsanityData to 7 Oct 2026

Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound

arXiv 2011.04586 ↗First posted 9 Nov 2020cs.LG stat.MLcited by 31

Not on the map. Why?

Abstract (arXiv)

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 alter the resulting classifier. We use this technique to derive a variety of novel or improved data-dependent generalization bounds for several learning algorithms. In particular, we prove a new margin bound for SVM, removing a log factor. The new bound is provably optimal. This resolves a long-standing open question about the PAC margin bounds achievable by SVM.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 7; 2023: 3; 2024: 5; 2025: 3; 2026: 9.

31 papers.

Sort:

By area:

  1. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  2. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 34
  3. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  4. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  5. 2023Compression, Generalization and Learningcited by 21
  6. 2021On Margins and Derandomisation in PAC-Bayescited by 19
  7. 2022Optimal Weak to Strong Learningcited by 14
  8. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  9. 2022The One-Inclusion Graph Algorithm is not Always Optimalcited by 11
  10. 2024Minimum Description Length and Generalization Guarantees for Representation Learningcited by 11
  11. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  12. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
19 more
  1. 2024Sample Compression Unleashed: New Generalization Bounds for Real Valued Lossescited by 4
  2. 2022Metric-valued regressioncited by 3
  3. 2024Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworkscited by 3
  4. 2025System-Aware Unlearning Algorithms: Use Lesser, Forget Fastercited by 3
  5. 2024Sample Compression Scheme Reductionscited by 2
  6. 2025Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorscited by 2
  7. 2021VC dimension of partially quantized neural networks in the overparametrized regimecited by 1
  8. 2022On Error and Compression Rates for Prototype Rulescited by 1
  9. 2025Multiview Representation Learning via Distributed Joint Latent Space Structuringcited by 1
  10. 2026Learning Decision-Sufficient Representations for Linear Optimizationcited by 1
  11. 2026Bridging Conformal Prediction and Scenario Optimization: Discarded Constraints and Modular Risk Allocationcited by 1
  12. 2022A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimensioncited by 0
  13. 2026A Fine-Grained Understanding of Uniform Convergence for Halfspacescited by 0
  14. 2026Optimistic Rates for Multiclass PAC Learningcited by 0
  15. 2026Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certificationcited by 0
  16. 2026Stability and Generalization of Straight-Through Estimators for Training Two-Layer Quantized Neural Networkscited by 0
  17. 2026Sharp margin-based generalization bounds for realizable SVMcited by 0
  18. 2026An Order-Theoretic Characterization of Consistent Inductive Inferencecited by 0
  19. 2026Preferent Compression Bounds Are Tightcited by 0