Metraipolis › archive › dc_cee06caca206

Preferent Compression Bounds Are Tight — arXiv:2609.36030

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.36030
License (as archived)
CC0-1.0
Archived
2026-10-07T17:28:39.115Z
SHA-256 of the archived text
d1f540033e25614dda2c193e8c09b0e5807db45784d1f7863a9a5141b587e18e
Stable URL of this page
https://metraipolis.com/documento/dc_cee06caca206

How to cite

Preferent Compression Bounds Are Tight — arXiv:2609.36030 — arXiv (en), https://arxiv.org/abs/2609.36030 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cee06caca206 (Metraipolis archive dc_cee06caca206, sha256 d1f540033e25614dda2c193e8c09b0e5807db45784d1f7863a9a5141b587e18e)
BibTeX
@misc{dccee06caca206,
  title = {Preferent Compression Bounds Are Tight — arXiv:2609.36030},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.36030},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cee06caca206; sha256 d1f540033e25614dda2c193e8c09b0e5807db45784d1f7863a9a5141b587e18e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36030. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-30 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Systems and Control (eess.SY); Optimization and Control (math.OC); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.36030 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T16:59:48.091Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).