Is Pick-to-Learn Loose Because It Is Greedy? Teaching Orders as Reconstructors for Compression Certificates

A sample compression scheme summarizes a labeled training set by a few of its own examples, chosen so that a fixed rule (the "reconstructor") can rebuild a classifier from those examples alone. If the rebuilt classifier also labels every discarded example correctly, its test error is provably small. The bound depends only on how many examples were kept, not on how many parameters the model has. Pick-to-Learn (P2L) turned this into a practical tool. It wraps any learner, repeatedly adds the training point with the highest loss, and retrains on the growing subset. The result is a held-out-free error certificate, even for a 66-million-parameter transformer (The Pick-to-Learn Algorithm; Sample Compression Unleashed).

Machine teaching asks a related question. If a cooperative teacher picks the examples, how many does a learner need to pin down a target concept, compared with the VC dimension $d$, the usual measure of how hard learning from random examples is? That theory has produced orderings of the concept class that yield compression schemes of size $O(d^2)$ (A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension). It has also shown that greedy teaching-set construction can be badly suboptimal (Lower Bounds for Greedy Teaching Set Constructions). This note asks whether P2L's certificates are looser than they need to be because of how it builds the compression set, and whether the teaching-theoretic object that matters is the selection rule or the reconstructor's preference among hypotheses.

Core Claim

P2L's gap can come from three different sources, and the existing literature cannot separate them. The first is greedy selection, which may pick too many points. The second is the reconstructor: plain ERM on the subset, with arbitrary tie-breaking, may need more points to reproduce the right labels than a reconstructor with a fixed, well-chosen preference would. The third is intrinsic: the class may simply need that many points.

Our claim is that the second source is the overlooked one. The decompressor in the RT*-based scheme of Mansouri et al. is "output the earliest concept, in a fixed recursive-teaching order, that is consistent with the kept points." That is exactly a preference-based reconstructor of the kind P2L's validity argument requires. We propose to use the teaching order as the reconstructor inside P2L, which we call teaching-order P2L. We predict it shrinks compression sets on structured finite classes more than any change to the selection rule does. If that holds, it is a concrete answer to the call in Sample Compression Unleashed for structured rather than greedy compression. It also gives certificates whose worst-case size is governed a priori by RTD*, the parameter behind the $O(d^2)$ scheme, which is at most quadratic in $d$ by Quadratic Upper Bound for Recursive Teaching Dimension.

The certificate we track is the standard consistent-compression bound. With probability at least $1-\delta$, a hypothesis reconstructed from $k$ of $n$ points and consistent with the other $n-k$ has risk at most

$$ \epsilon(k,n,\delta) = \frac{1}{n-k}\left(\ln\binom{n}{k} + \ln\frac{n}{\delta}\right), $$

where the $\binom{n}{k}$ term pays for not knowing in advance which subset was kept, and the $\ln n$ term pays for not knowing $k$. P2L's own bound is tighter than this generic one, but every bound in this family is monotone in $k$. So "smaller $k$ at equal test error" is the quantity to beat.

Research Program

The first component is a controlled measurement on finite, enumerable hypothesis classes, where all relevant quantities can be computed exactly. We build classes in two ways.

Some are synthetic, taken from the teaching literature. They include powersets and Warmuth's class from On Batch Teaching with Sample Complexity Bounded by VCD, the Head-and-Tail bit-vector class from Lower Bounds for Greedy Teaching Set Constructions, and the class reaching the largest known RTD/VCD ratio of 5/3 from Quadratic Upper Bound.

Others are data-derived, with sizes kept roughly between $10^4$ and $10^6$ concepts. Examples are conjunctions and short decision lists over binarized MNIST pixels, in the spirit of The Decision List Machine, and depth-2 threshold trees on a fixed grid over low-dimensional projections of MNIST.

For each class and each sample drawn from it, we compute five things. The first is the VC dimension. The second is the RTD* order and its teaching sets, using integer programming at each recursion level. The third is the smallest valid compression set for that sample, found exactly by integer programming. The fourth is P2L's compression size with an ERM base learner. The fifth is the size reached by each variant described below.

We also check the stable-scheme floor of $\lceil d/2 \rceil$ proved via the no-clash teaching dimension in Mansouri et al.. P2L is stable: removing a never-selected point never changes the argmax, so the floor applies to it. This gives a principled lower reference.

The second component is a two-by-two factorial design that separates selection from reconstruction. Selection is either greedy max-loss, as in P2L, or the RT* scheme's sample-based selection. Reconstruction is either ERM with fixed seeded tie-breaking, or earliest-in-teaching-order. The off-diagonal cell, greedy max-loss selection with the teaching-order reconstructor, is teaching-order P2L. For this cell we must re-verify that P2L's preference and non-associativity conditions still hold. We expect them to, because a fixed total order over hypotheses induces a consistent preference. We will write the argument out rather than assume it.

The third component is a deliberately limited transfer to models that cannot be enumerated. Neural networks admit no explicit teaching order. The nearest usable analogue is a deterministic, structured preference: among hypotheses fitting the kept set, prefer one under a fixed ranking. We will test two such rankings on frozen-feature linear heads. One is minimum norm, which is natural for linear heads on frozen features. The other is earliest checkpoint along a fixed training trajectory. We compare their compression sizes against P2L's default retraining on the binary MNIST setup.

This phase is a go/no-go stage. It proceeds only if the second component shows that reconstruction preference, not selection, drives the gap.

Baselines

The naive reference point is a random held-out split. We train on 80% of the data and certify the trained model with a Hoeffding-style test-set bound on the remaining 20%. Matching The Pick-to-Learn Algorithm, on the noisy-sine regression task at $N=200$ this baseline is reported at a test-set bound of 0.250 with actual risk 0.173, against P2L's 0.172 and 0.064. We rerun it on every dataset with the same base learner and the same total $n$.

The strongest existing method is P2L itself, with its own tighter certificate. On binary MNIST (digits 0–4 vs 5–9, $N=1000$), The Pick-to-Learn Algorithm reports a risk bound of 0.143 and test error 0.072. On Amazon Polarity with DistilBERT, Sample Compression Unleashed reports a 13.91% error certificate. We run P2L with an identical base learner, the same retraining budget, and the same $\delta$. Every variant uses the same certificate formula, so differences reflect only $k$ and test error.

On the finite classes, beating P2L means two things together. Compression size must fall by at least 25% on median across samples, and test error must not rise beyond seed-to-seed spread. On binary MNIST in the third component, beating P2L means a certificate below 0.143 at test error no worse than 0.072. We do not expect to reach the Amazon Polarity result in this project. It is listed so that a future scale-up has a fixed target.

Weight-space PAC-Bayes is the second strong competitor. It is reported at 0.177 bound and 0.088 test error on the same binary MNIST task (The Pick-to-Learn Algorithm). We cite those figures and rerun it only on the third-component task.

The key ablation is the factorial design itself. It isolates the reconstructor's preference as the ingredient under test. The exact-optimum compression size, found by integer programming, acts as an oracle ceiling that no method can beat.

Why not just…?

Why not just prune P2L's set backward, removing points while the reconstruction stays consistent? This is the most serious threat, because it attacks the selection source of looseness with no teaching theory at all. We include backward pruning as a full selection arm in the factorial design and also combine it with each reconstructor. If greedy-plus-pruning with ERM reconstruction matches teaching-order P2L, our central claim is wrong, and we will report it that way. Our prediction rests on the difference in kind between the two. Pruning can only remove points that ERM's arbitrary tie-breaking makes redundant. A fixed preference changes which points are redundant in the first place. This is the mechanism by which RTD-style elimination teaches the empty concept with zero examples.

Why not just select points in batches, or use a coreset heuristic? Batching reduces P2L's retraining cost, which is a real limitation flagged in The Pick-to-Learn Algorithm. It cannot reduce $k$, however, and usually increases it. Coreset heuristics are not compression schemes unless the reconstructor depends only on the kept set. We include top-$m$ batch P2L as a selection variant to quantify how much compression size it costs.

Why not just trust the greedy lower bounds and declare P2L suboptimal? Those lower bounds concern greedy teaching-set construction over an explicitly known class, on adversarial instances (Lower Bounds for Greedy Teaching Set Constructions). P2L's max-loss rule is a different greedy rule, and natural data are not adversarial. We therefore run P2L directly on the Head-and-Tail class to see whether the $\Omega(\log|\mathcal{C}|)$ blow-up transfers. It may well not, and that negative result would itself be informative.

Proposed Experiments

The first decisive check is the factorial design on finite classes. For each class we plot median compression size against $d$, RTD*, the exact optimum, and the $\lceil d/2 \rceil$ floor. We then ask which factor, selection or reconstruction, accounts for most of P2L's excess over the optimum. Success means the reconstruction factor explains the larger share on the data-derived classes. Failure means selection, or neither factor, dominates. Failure also tells us that P2L's accuracy-certificate trade-off reflects intrinsic class complexity rather than poor design.

The second check is the Head-and-Tail stress test. We track how P2L's compression size grows with $|\mathcal{C}|$ at fixed $d$, with and without the teaching-order reconstructor. Logarithmic growth under P2L that disappears under the teaching order would be the first empirical link between the greedy-teaching lower bounds and compression certificates.

The third check runs only if the first succeeds. On binary MNIST with $N=1000$ and frozen-feature heads, minimum-norm or earliest-checkpoint reconstruction must give a certificate below P2L's reported 0.143 without exceeding its 0.072 test error. Across all experiments we use five seeds, a single $\delta=0.05$, and identical retraining budgets. Wall-clock cost is reported alongside every certificate.