How Much Certificate Does Pick-to-Learn Lose to Greedy Teaching?

Pick-to-Learn (P2L) certifies a trained model without a held-out test set. It rebuilds the model from a small subset of the training data and bounds the test error using only the size of that subset. The subset is grown greedily: at each step it adds the one training point the current model gets most wrong, retrains, and repeats. A smaller subset gives a tighter certificate, so the whole guarantee depends on how good that greedy choice is. Teaching theory has studied almost the same problem for thirty years. It asks for the fewest examples that make a learner land on the right hypothesis, and its central lesson is that greedy example choice can be far from optimal. Well-chosen elimination orders avoid that loss.

This note proposes to measure how large that gap is in practice, exactly where it can be computed and approximately where it cannot, and to test whether teaching-style search closes it. The question has a clean answer either way. If greedy P2L is already close to the smallest possible subset, the worst-case lower bounds from teaching theory are irrelevant to certification practice, and people can stop looking for better selectors. If it is far from optimal, certified bounds on standard benchmarks are loose for a reason that can be fixed.

Core Claim

P2L is a greedy teacher of its own inner learner. Given a fixed, deterministic training procedure $A$ (for example, SGD with a fixed seed on the canonically ordered subset), the smallest valid compression set for a sample $S$ is exactly a minimum teaching set for $A$ on $S$: the fewest points $T \subseteq S$ such that $A(T)$ fits $S$ to the required tolerance. P2L's max-loss rule is the one-step greedy approximation to this minimum.

This framing splits the certificate's looseness into two measurable parts. The first is a selection gap: greedy subset size versus the minimum teaching set for the same learner $A$. The second is a learner gap: the minimum teaching set for $A$ versus that of a learner that uses a recursive elimination order, the kind of order-aware reconstruction behind Mansouri's quadratic compression scheme.

The certificate depends on the subset size $k$ out of $n$ training points. In the classical consistent case its form is roughly

$$\text{risk} \lesssim \frac{k \ln(en/k) + \ln(n/\delta)}{n-k},$$

where $\delta$ is the failure probability. This form comes from a union bound over the at most $\binom{n}{k}$ subsets the reconstruction could have used, as in Floyd and Warmuth. Any reduction in $k$ at matched fit therefore tightens the bound almost proportionally.

The claim that would be new is quantitative. Nobody has measured either gap, and the file contains no work that treats P2L selection as a teaching problem. The closest work splits into two camps that never meet. Mansouri builds compression from a recursive teaching order but reports no certificates and no experiments. P2L and its real-valued extension by Bazinet, Zantedeschi and Germain produce certificates but never ask how far their greedy set is from optimal. Bazinet et al. explicitly flag better selection heuristics as future work.

Where the Directions Fit

The four directions play different roles here.

Compression-based generalization is the application regime. It supplies the quantity we care about, the certified bound, along with the reference algorithm, P2L. It also supplies the master theorems of Bazinet et al., which keep a bound valid for real-valued losses and for any compression function whose reconstruction depends only on the chosen subset. This validity point matters: it means non-greedy selectors still yield sound certificates, provided the reconstruction is a deterministic function of the set.

The teaching-to-learning ratio work supplies the warning. Compton, Pabbaraju and Zhivotovskiy prove that one-point greedy teaching-set construction can need on the order of $\log|\mathcal{C}|$ examples rather than $O(d)$, where $d$ is the VC dimension. Their "head and tail" classes are built so that greedy choices chase immediate gains while missing global structure. Two-point lookahead improves this only to $\log\log|\mathcal{C}|$. These are worst-case constructions, and whether natural learning problems resemble them is exactly what is unknown.

Recursive concept elimination supplies the alternative mechanism. The recursive teaching dimension (RTD) is a teaching cost in which concepts are removed layer by layer, and the learner exploits the agreed order. Its value is bounded quadratically in VC dimension by Hu et al., and Mansouri converts it into a compression scheme of size $O(d^2)$.

The sample compression conjecture is the theoretical constraint. It says that optimal compression should be $O(d)$, which bounds how small any selector's subsets could possibly become on classes where $d$ is known.

Research Program

The work has three parts that share one piece of infrastructure: exact solvers for small combinatorial problems. These are satisfiability (SAT) solvers and integer linear programming, in the spirit of the SAT search by Chen, Cheng and Tang that found the class $C_0$.

Part 1: an exact atlas on finite classes. For small finite concept classes we will compute exactly six quantities:

  • the VC dimension;
  • the RTD;
  • the smallest stable labeled compression size;
  • the minimum teaching set for a fixed "first consistent concept in index order" learner, on every realizable sample;
  • the subset size that greedy P2L produces for that same learner;
  • the subset size under an RT-order reconstructor.

Computing optimal teaching sequences is hard in general, as shown in the hardness note on RTD. We therefore restrict to domains of at most 14 points, where solvers finish.

The families are:

  • thresholds, intervals and axis-aligned boxes on grids;
  • maximum classes, which are known to compress to exactly $d$ (Rubinstein et al.);
  • Warmuth's class;
  • $C_0$;
  • the $C^{pair}_u$ family from Mansouri, Simon and Singla;
  • head-and-tail classes as a greedy stress test;
  • random classes with VC dimension up to 4.

This part yields the exact selection and learner gaps as functions of $d$ and class structure. As a by-product it computes the smallest stable compression size of $C_0$, the class with $\text{RTD}/\text{VCD} = 5/3$. The file reports no compression size for $C_0$. It would be informative either way: a value above 3 would be a class whose optimal stable compression exceeds its VC dimension, and a value of 3 would show that the teaching ratio and the compression ratio come apart.

Part 2: finite classes induced on real data. We will run decision lists and conjunctions over binarized features of binary MNIST and the MNIST 4-vs-9 and 5-vs-6 subtasks. Decision lists are a natural setting because the Decision List Machine already treats them as compression learners. For short lists over few features the class can be enumerated or encoded for a solver, so we can compute the true minimum compression set on real samples and compare it with greedy P2L. This part tests whether real data behaves more like thresholds, where greedy is near-optimal, or more like head-and-tail classes.

Part 3: teaching-set search for neural learners. Here the minimum is not computable, so we will build a selector that attacks the two failure modes teaching theory identifies.

The first failure mode is redundancy: points added early become unnecessary once later points are present. The recursive elimination view says the learner should get these points "for free." The selector handles this with a backward elimination pass. It tries removing each point from the greedy set, retrains warm-started, and keeps the removal if the fit on the full sample still meets the threshold.

The second failure mode is myopia. The selector handles this with a bounded exchange search. At each round it scores the $r$ highest-loss candidates by how many remaining errors disappear after adding each one, rather than by its own loss. In teaching terms this is lookahead on version-space elimination.

To keep the certificate valid, reconstruction always trains on the chosen set in a canonical order with a fixed seed, so it depends only on the set. The bound is then computed with the Bazinet et al. master theorem, with a union over $k$. We report the compute cost, counted in retrains, alongside every result, because P2L's retraining overhead is already its main practical limitation.

Baselines

Naive reference: random selection. The naive reference is P2L's stopping rule with points added in random order. It uses the same inner learner, the same error threshold and the same certificate computation. It tells us how much of P2L's advantage comes from selection at all. Any selector that fails to beat it clearly is not worth its compute.

Strongest existing method: max-loss P2L. The strongest competitor is P2L exactly as in Paccagnan et al. and Bazinet et al.. It is the only published method that produces non-vacuous sample-compression certificates for deep networks, and it already beats held-out and PAC-Bayes certificates on its own benchmarks.

On binary MNIST (digits 0–4 vs 5–9, $N=1000$), Paccagnan et al. report a P2L risk bound of 0.143 with test error 0.072. On noisy-sine regression with $N=200$ they report a bound of 0.172 with actual risk 0.064. Bazinet et al. report a certificate of "around 5%" with test error as low as 0.25% for CNNs on MNIST subtasks, and a certificate of 13.91% for 66M-parameter DistilBERT on Amazon Polarity.

We will rerun P2L ourselves under identical architecture, optimizer, data, error threshold and seeds, rather than rely only on reported numbers. To compare at equal wall-clock cost, the rerun also gets a larger retraining budget, equal to what our selector uses, spent on multiple seeds and tolerance tuning. Our selector counts as beating it only if two conditions hold. It must give a strictly lower certified bound, with test error no worse, averaged over at least five seeds and with non-overlapping seed intervals. And the improvement must survive when P2L receives the same total retrain budget.

Reference certificates. We will also report the held-out test-set bound and the PAC-Bayes baseline as references. Paccagnan et al. report 0.250 for the test-set bound on sine at $N=200$ and 0.177 for PAC-Bayes on binary MNIST. These show where sample compression already stands, but they are not the question here.

Exact optimum. On the finite classes of Parts 1 and 2 the true minimum compression set is itself a baseline. It turns "better than greedy" into "fraction of the achievable gap closed."

Ablations. Two ablations isolate the key ingredient. The first uses backward elimination alone on top of greedy P2L. The second uses lookahead exchange alone without pruning. Together they show whether any gain comes from removing redundancy (the recursive elimination idea) or from avoiding myopic additions (the Compton et al. failure mode).

Why not just…?

Why not just use diversity-based coreset selection instead of teaching-style search? Bazinet et al. themselves suggest sample diversity as the next heuristic, and this is a real threat. Diversity may shrink $k$ as much as anything proposed here, at lower cost. We will not argue it away. A k-center selector in the network's penultimate-layer features, run under the same stopping rule and certificate, is included as a full competitor in Part 3. It is also evaluated on the Part 2 finite classes, where we can see how close it gets to the true minimum. If diversity matches our selector, the finding becomes "the selection gap is real and diversity closes it." That is still the measured answer this proposal is after. There is one reason to expect a difference: diversity is blind to what the learner already gets right. Backward elimination targets exactly the points that become redundant.

Why not just add points in batches or prune the greedy set afterward, with no teaching theory at all? Batched P2L is a compute shortcut. It has no mechanism for making the set smaller, and there is reason to expect the opposite: adding several high-loss points at once can only increase redundancy. Post-hoc pruning, by contrast, is one of our two ingredients. The ablation reports it on its own, and we do not claim the teaching framing is needed to invent it. What the framing adds is Parts 1 and 2. There we can say how much of the remaining gap pruning closes relative to the exact optimum, which no heuristic comparison can show.

Why not just compute the optimal teaching set exactly? It is computationally hard in general, per the hardness results on RTD. It is also infeasible for neural learners, where every candidate evaluation is a retraining. We compute it exactly only where it is tractable, and we use those cases to calibrate the approximate selector.

Why not just use a held-out test set or a PAC-Bayes bound? P2L already beats both on the benchmarks in the file, as reported above. Finzi et al. show that parameter-compression PAC-Bayes needs heavy subspace and quantization machinery to be non-vacuous at all. This proposal takes P2L as the bar and asks whether its own looseness is avoidable.

Proposed Experiments and Decisive Checks

Part 1 check. The first decisive check is the exact atlas. For each family we report the selection gap and the learner gap as ratios to VC dimension. We also report whether greedy P2L ever exceeds the optimal compression by more than a constant factor on any class outside the adversarial head-and-tail construction. If greedy stays within a small constant of optimal on every natural family, the selection-gap hypothesis is largely refuted, and we will say so. The same run settles the smallest stable compression size of $C_0$.

Part 2 check. On binarized MNIST, MNIST 4-vs-9 and MNIST 5-vs-6 we compare the greedy subset size with the solver's true minimum. We then report the certified bounds each subset would give. This is the most direct test of whether real data triggers greedy failure.

Part 3 check. This check covers binary MNIST at $N=1000$, noisy sine at $N=200$ and $N=500$, and the MNIST subtasks with CNNs. Amazon Polarity with DistilBERT serves as a scale check, run only if compute allows. The selectors are random order, max-loss P2L, k-center diversity, batched P2L, pruning only, lookahead only, and the combined teaching-set search. We report subset size $k$, certified bound, test error and retrain count.

What counts as success. A positive result means the combined selector lowers the certified bound below our own rerun of P2L (the reported reference points being 0.143 on binary MNIST and 0.172 on sine) at no worse test error, and that the gain persists against diversity selection at equal compute. A negative result is also clean: selectors cluster within seed noise of P2L while Part 1 shows large gaps only on adversarial classes. Either way, the gap between teaching theory's worst case and certification practice gets its first measurement.