Preferent Compression Bounds Are Tight

Dario Paccagnan; Marius Tirlea

cs.LGSep 28, 2026

Preferent Compression Bounds Are Tight

Authors: Dario Paccagnan, Marius Tirlea

Organizations: Department of Computing, Imperial College London, London, UK

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.

Figures & tables

Panel of Figure 1 — Figure 1: A compression function $c$ is preferent if it maps any subset contained between $U$ and $c(U)$ , e.g., $V$ in the figure, onto $c(U)$ itself.

Panel of Figure 2 — Figure 2: The compression $c_{\eta}(U)$ lists all the elements of $U$ in non-decreasing order (including repetitions) as $u_{(1)}\leq u_{(2)}\leq\dots\leq u_{(|U|)}$ . It then iterates over this list, starting from $u_{(1)}$ , and checking whether each element $u_{(j)}$ falls below the corresponding threshold $t_{j-1}=\varepsilon(j-1,N,\delta)+\eta$ , stopping at the first failure or upon reaching $N$ . In this example $u_{(1)}$ , $u_{(2)}$ , $u_{(3)}$ pass the test; but not $u_{(4)}$ since $u_{(4)}>t_{3}$ . Thus, independently of the values taken by $u_{(5)},~\dots~,u_{(|U|)}$ the compression returns $c_{\eta}(U)=\{u_{(1)},~u_{(2)},~u_{(3)}\}$ .

Panel of Figure 3 — Figure 3: Construction 5 is such that for every $0\leq k\leq N-1$ , when $|c_{\eta}(\bm{D})|=k$ , the probability of change of compression equals exactly $\varepsilon_{k}+\eta$ (represented as blue point masses), sitting exactly $\eta$ above the bound $\varepsilon_{k}$ (red curve), and thus strictly violating it. When $|c_{\eta}(\bm{D})|=N$ , the bound equals $1$ and is thus never violated.

Panel of Figure 4 — Figure 4: Illustration of Construction 5 for $N=10$ and $\delta=0.05$ . (a) The violation probability $\mathbb{P}\{\phi(\mathbf{D})>\varepsilon(|c(\mathbf{D})|,N,\delta)\}$ converges to $\delta$ from below as $\eta\to 0^{+}$ , as per Theorem 4 . (b) Distribution of $\bm{k}_{\eta}^{*}=|c_{\eta}(\bm{D})|$ for $\eta=10^{-5}$ . Note that the y-axis is broken to accommodate the height of the last bin. In accordance with the discussion above, as $\eta\to 0^{+}$ , $1-\delta=0.95$ of the probability mass concentrates at $k_{\eta}^{*}=10$ , while the remaining $\delta=0.05$ is spread across $k_{\eta}^{*}\in\{0,\ldots,9\}$ . Both plots were generated by sampling $10^{9}$ datasets.

Panel of Figure 5 — Figure 5: Visualization of the triangular array $\{p_{k,m}:0\leq k\leq m\leq N\}$ . The first relation, reported in blue, controls the weighted sum along each row; the second relation, reported in red, links adjacent entries within each column. Thanks to ( 5 ), it suffices to bound $\sum_{k=0}^{N-1}\binom{N}{k}p_{k,N}$ , which is a linear combination of the terms in the top row of the triangular array.

Explore similar work

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
Oct 9, 2026Simone Garatti, Marco C. CampiStatistical Learning Theory Information-Theoretic Generalization Bounds
Dipartimento di Elettronica, Informazione e Bioingegneria - Politecnico di Milano, piazza Leonardo da Vinci 32, 20133 Milano, Italia. · Dipartimento di Ingegneria dell’Informazione - Universit`a di Brescia, via Branze 38, 25123 Brescia, Italia.
Pricing the Risk of Runtime Compression: Anytime-Valid Admission and a Served-Output Law for Compressed Serving State
Aug 16, 2026Fanzhe Wei, Li LiuRuntime Assurance Anytime-Valid Inference
Metask Lab
High-arity Sample Compression
May 12, 2026Leonardo N. Coregliano, William OpichPAC Learning Statistical Learning Theory

Oct 9, 2026, stat.MLJ/K move · Enter open · S save

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

Simone Garatti, Marco C. Campi

Dipartimento di Elettronica, Informazione e Bioingegneria - Politecnico di Milano, piazza Leonardo da Vinci 32, 20133 Milano, Italia. · Dipartimento di Ingegneria dell’Informazione - Universit`a di Brescia, via Branze 38, 25123 Brescia, Italia.

Statistical Learning Theory Information-Theoretic Generalization Bounds

Open paper AskPDF arXiv

Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity

\boldsymbol{k}

, defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order

O(\sqrt{\ln N/N})

above

\boldsymbol{k}/N

. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level

1-δ

, the risk is bounded with probability at least

1-δ

\frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right),

uniformly over all possible values of

\boldsymbol{k}

. Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term

\boldsymbol{k}/N

is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the

O(1/\sqrt{N})

convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the

O(1/\sqrt{N})

rate.

Abstract

Explore similar work

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

Pricing the Risk of Runtime Compression: Anytime-Valid Admission and a Served-Output Law for Compressed Serving State

High-arity Sample Compression