Preferent Compression Bounds Are Tight
Abstract
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.
Related
- Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
- Tight degeneracy bounds in online Ramsey games
- Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis
- Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
BibTeX
@misc{paccagnan2026preferent,
title = {{Preferent Compression Bounds Are Tight}},
author = {Dario Paccagnan and Marius Tirlea},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36030},
eprint = {2609.36030},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36030},
}
RIS
TY - UNPB
TI - Preferent Compression Bounds Are Tight
AU - Dario Paccagnan
AU - Marius Tirlea
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.36030
UR - https://arxiv.org/abs/2609.36030
AB - 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.
ER -