PaperlayerView exact revision on arXiv

Source-linked AI summary

Preferent Compression Bounds Are Tight

Dario Paccagnan, Marius Tirlea

arXiv:2609.36030v1cs.LGcs.SYeess.SYmath.OCmath.PR

TL;DR

Risk certificates for unseen inputs matter to the deployment of data-driven methods, but whether state-of-the-art bounds for preferent compressions are tight was open. The paper proves the bound of Proposition 1 tight using an explicit construction and a shorter counting-based proof.

  • Problem

    Whether the sharp state-of-the-art bounds for preferent compressions are tight remained an open question relevant to risk certificates for unseen inputs.

    Source: §1 · pp. 1–2

  • Method

    The paper gives a shorter proof using elementary counting and constructs a uniform-distribution example with carefully arranged order statistics.

    Source: §1 · p. 2, §4 · p. 6

  • Results

    Theorem 4 establishes that Proposition 1's bound is tight for every N and δ.

    Source: §3 · p. 4

  • Takeaways & Limitations

    Under the sole preference property, Proposition 1's bound cannot be improved.

    Source: §3 · p. 4

    The analysis assumes N samples on a sample space and treats datasets as multisets.

    Source: §2 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether sharp bounds for preferent sample compressions are tight, a question relevant to certificates for unseen-input risk. It proves the state-of-the-art bound tight and supplies a simpler proof and an explicit construction.

1 Introduction

  • Sample compression can yield concentration inequalities and risk certificates for properties including constraint violation probability and misclassification rates.An algorithm's output can be reconstructed from a subset of the original dataset.Source: §1 · p. 1
  • Preferent-compression bounds support certificates in the Scenario Approach, Pick-to-Learn, and Support Vector methods.The applications use support constraints, transformations to preferent compression, and support vectors, respectively.Source: §1 · p. 2
  • The upper bound of [3, Thm 4] is tight and cannot be further improved.The construction uses the uniform distribution and carefully arranged order statistics.Source: §1 · p. 2
  • A shorter proof uses elementary counting instead of infinite-dimensional duality and underpins an explicit tightness construction.The construction uses the uniform distribution and order statistics.Source: §1 · p. 2

2 Preliminaries: Compression, Preference, and Risk Certificates

The preliminaries define compression and preference, then introduce probability of change as a quantity for risk certification. They also recall the sharpest available bound on that probability.

2 Preliminaries: Compression, Preference, and Risk Certificates

  • The setup treats the N observations as an i.i.d. dataset on sample space Z and accounts for repeated observations by treating the dataset as a multiset.Multiset operations and cardinality count elements according to their multiplicities.Source: §2 · pp. 2–3

2.1 Compression maps and preference

  • A compression function selects a subset c(U) of the input multiset U; the tightness result does not depend on a reconstruction map.The general compression scheme pairs a subset-selecting map with a map that reconstructs the learned model.Source: §2.1 · p. 3
  • Preference requires c(V)=T whenever c(U)=T and T⊆V⊆U, so restricting the data to an intermediate multiset preserves the selection.The property was previously called stability in learning theory [1] and preference in [3].Source: §2.1 · p. 3

2.2 Probability of change of compression and existing bounds

  • The probability of change measures whether adding a fresh independent sample to c(D) changes the compression, and its high-confidence bound depends on |c(D)|, N, and δ.The quantity is used for risk certification, and the fresh draw is independent of D.Source: §2 · p. 2, §2.2 · pp. 3–4
  • Proposition 1 recalls the upper bound from [3, Thm 4] for preferent compressions, with ε(k, N, δ) defined as a unique root for k≤N−1.Source: §2.2 · p. 4

3 Main result: Preferent compression bounds are tight

The Proposition 1 bound is tight: under the preference property alone, no better bound can be guaranteed. A uniform-distribution construction with ordered samples and rank-specific thresholds approaches the bound as η tends to zero.

3 Main result: Preferent compression bounds are tight

  • For any N and δ, the Proposition 1 bound is tight, so preference alone cannot guarantee a better bound.The construction makes the confidence in the bound arbitrarily close to 1−δ.Source: §3 · p. 4
  • Under the uniform distribution on [0, 1], Construction 5 sorts samples and retains the prefix that passes rank-specific thresholds ε(k, N, δ)+η.It stops at the first threshold failure or at position N.Source: §3 · pp. 4–5
  • The greedy left-to-right construction is preferent because adding a point outside the compressed set does not change the compression.Whether each sample passes its threshold depends on the samples to its left, not on other non-compressed samples.Source: §3 · p. 5
  • As η→0+, the probability of violating the bound converges to δ from below.For N=10 and δ=0.05, Figure 4 illustrates this convergence and the distribution of compression sizes.Source: §3 · p. 5, Figure 4 · p. 6
  • For compression sizes k<N, the probability of change equals εk+η, strictly above εk; at size N, the bound is 1 and is never violated.Figure 3 depicts the point masses above the bound for k<N.Source: Figure 3 · p. 5, §3 · p. 5

4 Proof of the main result

The proof first derives the Proposition 1 bound through a shorter counting argument, then uses a uniform-distribution construction whose limiting behavior attains that bound.

4.1 Simplified Proof of Proposition 1

  • The simplified proof replaces an infinite-dimensional measure program with elementary counting and two relations on a triangular array, deriving the same bound.The row and column relations govern the array entries and expose the counting structure used by the tightness construction.Source: §4 · p. 6, §4.1 · p. 7

4.2 Proof of Theorem 4

  • As η → 0+, the construction’s array relations become equalities, allowing the bound-proof argument to yield equality in the limiting violation probability.The proof evaluates the limiting probability by examining the compression at η = 0, then applies the same weighted-sum argument.Source: §4.2 · pp. 9, 11
  • The construction uses order statistics and thresholds t_k = ε_k + η; its compression c_η satisfies the preference property for every η ≥ 0.The proof considers finite multisets and shows that retaining the compressed elements preserves the compression.Source: §4.2 · p. 9
  • For η > 0 and compression size k* < N, the probability of change is min{ε_k* + η, 1}, strictly above ε_k*.When the compression size is N, the bound ε_N equals 1, so it is trivially satisfied.Source: §4.2 · p. 10

A Proof of second relationship

The proof establishes the stated bound on p_{k,m+1} in three steps. Preference and conditioning reduce the goal to bounding the probability of an event for each fixed dataset satisfying B.

B Removing the assumption of non-concentrated mass

To remove the non-concentrated-mass assumption, the proof augments each sample with an independent uniform variable and defines a preference-preserving compression on the augmented data. The resulting bound transfers back to the original compression.

Loading 2609.36030v1…