Preferent compression bounds proven exactly right for safety guarantees
Preferent Compression Bounds Are Tight
Machine Learning
Summary
Ensuring that machine learning methods are safe and reliable is hard because it’s tricky to prove how well they perform. One approach uses something called sample compression, which helps give safety certificates, especially when the algorithm follows a preference or stability rule. The authors show that the best-known mathematical limits for this kind of compression are exactly correct and cannot be improved. They also provide a simpler proof that doesn’t rely on complicated math, making the result easier to understand and verify.
What this means in practice
- •For machine learning engineers: Use exact stability bounds to certify model safety in real-world learning systems.
- •For optimization algorithm designers: Design algorithms with provably tight compression bounds to improve learning efficiency and reliability.
A theory result. No direct application yet.
Authors
Dario Paccagnan, Marius Tirlea
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.