# Preferent Compression Bounds Are Tight

arXiv: https://arxiv.org/abs/2609.36030 · HTML: https://mlsanity.com/paper/2609.36030/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 10 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 4 of 4)

- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Compression, Generalization and Learning](https://mlsanity.com/paper/2301.12767/) (2023)
- [Pick-to-Learn for Systems and Control: Data-driven Synthesis with State-of-the-art Safety Guarantees](https://mlsanity.com/paper/2512.04781/) (2025)

## Abstract (arXiv)

The lack of rigorous safety and performance certificates remains a key bottleneck to the deployment of modern learning-based methods. Sample compression has recently emerged as a powerful tool for deriving such certificates, with particularly sharp bounds available for algorithms satisfying a so-called preference property -- also known as stability in the learning theory literature. These bounds find direct application across domains as different as the Scenario Approach, Pick-to-Learn, and Support Vector methods. However, whether they are tight has remained an open problem. In this paper we resolve this question affirmatively and show that the state-of-the-art bound for preferent compressions is provably tight. We establish this by exhibiting an explicit construction based on the uniform distribution and order statistics that attains the bound in the limit. Along the way, we also provide a considerably shorter and more accessible proof of this bound, requiring only elementary counting arguments and no infinite-dimensional duality.