Pick-to-Learn Is a Self-Directed Online Learner: Sequential Dimensions for Compression Certificates

Some of the tightest generalization certificates available today come from a very simple loop. Pick-to-Learn (P2L) trains a model on a small subset of the data, finds the training point it gets most wrong, adds that point to the subset, retrains, and stops once no remaining point is badly wrong. The final subset is a sample compression scheme: a small piece of the data from which a fixed procedure rebuilds a hypothesis that fits all of it. A small subset of this kind yields a generalization bound that needs no held-out data (The Pick-to-Learn Algorithm). Nobody knows how small that subset will be for a given hypothesis class. The combinatorial theory also sends mixed signals. Binary classes always admit compression schemes of size exponential in the VC dimension, meaning the size of the largest point set the class can label in every possible way (Sample compression schemes for VC classes). Multiclass classes with an unbounded number of labels can be learnable yet have no constant-size compression at all (Multiclass Learnability Does Not Imply Sample Compression). And greedy selection rules are provably bad at building small teaching sets (Lower Bounds for Greedy Teaching Set Constructions), yet P2L, a greedy rule, works well in practice.

We propose that all three observations fit together once P2L is viewed as an online learner rather than a batch one. Every point P2L adds is one the current model got badly wrong, so the compression size equals the number of mistakes an online learner makes. The online learner here is unusual: the learner chooses which example to see next, and only the label is out of its control. This is self-directed learning. The right measure of capacity is therefore a tree-based sequential dimension, the kind used to analyze adversarial online learning (Sequential complexities and uniform martingale laws of large numbers), adapted so that the learner picks the instance at each node. We will define a scale-sensitive self-directed dimension, prove it bounds P2L's compression size for regression and for multiclass problems with any number of labels, and test on exactly enumerable classes and the P2L benchmarks whether measured compression sizes track this dimension rather than VC, Daniely-Shalev-Shwartz (DS), or teaching dimensions.

Core Claim

Recall the sequential fat-shattering dimension $\mathrm{fat}_\gamma(\mathcal{F})$ of a real-valued class $\mathcal{F}$ (Online Learning: Random Averages, Combinatorial Parameters, and Learnability). It is the depth of the deepest binary tree of instances, with a threshold ("witness") at each node, such that every path of above/below-threshold signs is matched by some function in $\mathcal{F}$ to within margin $\gamma$. In that tree an adversary places the instances.

We define the self-directed version $\mathrm{sdfat}_\gamma(\mathcal{F}, S)$ on a finite sample $S$ as the value of a game. At each round the learner picks an unused point of $S$ and commits to a prediction. The adversary then reveals a value, consistent with some $f \in \mathcal{F}$ on everything revealed so far, that differs from the prediction by at least $\gamma$. The dimension is the number of rounds the adversary can force under the learner's best strategy. P2L with a worst-violator rule is one particular learner strategy in this game. The file lists no scale-sensitive, multiclass analogue of self-directed learning, although it treats the binary theory as classical.

Our first target result is a two-sided sandwich for a P2L variant whose base learner is a scale-sensitive analogue of the Standard Optimal Algorithm (SOA), the classical online learner that predicts so as to keep the remaining class's sequential dimension as low as possible:

$$\mathrm{sdfat}_\gamma(\mathcal{F}, S) \;\le\; |T_{\mathrm{P2L}}| \;\le\; \mathrm{fat}_{\gamma}(\mathcal{F}).$$

Here $T_{\mathrm{P2L}}$ is the final compression set, and the statement is in the realizable case, where some $f$ fits all labels. The upper bound follows because each added point is a $\gamma$-mistake of an optimal sequential learner, whatever order the points arrive in. The lower bound holds because P2L is a self-directed strategy. The open question is where between the two bounds the worst-violator rule falls.

For multiclass zero-one loss, the analogous upper bound uses the multiclass Littlestone dimension. This is the tree dimension that A Unified Theory of Supervised Online Learnability shows is a special case of its Sequential Minimax dimension. The resulting bound is independent of the number of labels. This gives a sharp, checkable consequence: the DS-dimension-1 class that Pabbaraju proves cannot be compressed below $\Omega((\log m)^{1-o(1)})$ must have self-directed dimension that grows with $m$.

The teaching connection is the second claim. A teacher who selects both points and labels plays the cooperative version of the same game. This places the recursive teaching dimension, the self-directed dimension, and the sequential dimension on a single ladder of "who chooses what." Two of those relations are hypotheses we will test, not facts from the file. The first is that recursive teaching dimension sits at or below the self-directed dimension. The second is that the ratio of self-directed dimension to VC dimension is exactly what separates classes where greedy selection succeeds from classes, like the Head-and-Tail construction of Compton et al., where it fails.

Research Program

The theory has three parts.

The first part proves the sandwich above for bounded regression and for multiclass loss. It also characterizes when the worst-violator rule is within a constant of the optimal self-directed strategy. We expect this to be true for classes with a natural order, such as thresholds and intervals. There the self-directed dimension is tiny while $\mathrm{fat}_\gamma$ is unbounded, which is exactly why a Littlestone-dimension bound alone would be useless. We expect it to be false in general, and we will look for the counterexample among the greedy-teaching lower-bound constructions.

The second part relates $\mathrm{sdfat}_\gamma$ to batch dimensions. We want to know whether it is bounded by a function of the static fat-shattering dimension, or of the DS dimension in the multiclass case, whenever compression is possible, and whether it is infinite on Pabbaraju's construction.

The third part is the teaching ladder. We will formalize a list-valued multiclass teaching map, where the learner may output a short list of labels. We will then test whether its size is bounded by the self-directed multiclass dimension. This would give a teaching quantity that respects the improperness barrier of A Characterization of Multiclass Learnability, whose optimal learners output hypotheses outside the class.

We do not claim to close the $d^{3/2}$ versus $d$ gap in multiclass sample complexity (Improved Sample Complexity for Multiclass PAC Learning). That gap serves as a constraint. Any compression-based multiclass bound we derive must be compared against it, and a self-directed bound that beat $d^{3/2}$ on some structured subfamily would be reported as a result specific to that subfamily.

The computational part builds an exact solver for these games on small finite classes. The tree games are exponential in general, as are computing the recursive teaching dimension (A Note on Hardness of Computing Recursive Teaching Dimension) and the Sequential Minimax dimension. For classes over up to roughly 12–16 points, memoized game-tree search is feasible. The solver outputs, for each class, the VC or DS dimension, the Littlestone or sequential fat dimension, the self-directed dimension, the recursive teaching dimension, and the P2L compression size under several base learners and selection rules.

Baselines

The naive reference point is the test-set bound: hold out part of the sample, train on the rest, and apply Hoeffding's inequality. P2L reports this bound on the noisy-sine regression task with $N=200$ at 0.250, with an actual risk of 0.173 (The Pick-to-Learn Algorithm). We will rerun it with the same 20% hold-out and the same model class.

The strongest existing certificate method on the two small benchmarks is original P2L. It reports a risk bound of 0.143 on binary MNIST ($N=1000$, digits 0–4 vs 5–9) and 0.172 on noisy sine with $N=200$. Its reported PAC-Bayes comparison on MNIST reaches a bound of 0.177. The compression-based PAC-Bayes approach of PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization is the strongest parameter-compression competitor. It explains CNN generalization through description length rather than sample subsets, and we will cite its ImageNet bound (93.5% data-independent) only as context, not as a comparison. We will rerun original P2L with the paper's base learners, data splits, and confidence level. Our variant, P2L with a sequential-optimal base learner and dimension-guided selection, gets the same number of retrainings. Beating P2L means a smaller compression set, and hence a tighter certificate, at matched test error, averaged over at least ten seeds with the difference exceeding seed variance. It does not mean lower test error alone.

Three baselines serve as ablations isolating the key ingredient, namely that the learner chooses the order. The first is P2L with uniformly random selection order. The second is P2L with the maximum-elimination greedy rule analyzed by Compton et al. The third is a classical Littlestone–Warmuth style mistake-set compression that processes points in a fixed, adversarially chosen order. If random order matches worst-violator order, then self-direction is not what makes P2L small. On the enumerable classes, the non-constructive $2^{O(d)}$ scheme is not implementable. Instead the reference is the exact minimum compression size found by brute force, alongside the exact recursive teaching dimension.

Why not just…?

Why not just use Littlestone–Warmuth mistake-bound compression and call the question settled? Mistake sets of an online learner are a classical compression scheme. This is the most serious threat, because our upper bound is essentially that argument. The difference lies in the lower end of the sandwich. On thresholds and intervals the Littlestone dimension is infinite, while self-directed P2L needs one or two points. The fixed-order ablation tests this directly. If fixed-order mistake compression is as small as worst-violator P2L on the enumerable classes and on MNIST, then the self-directed dimension adds nothing and we would reframe the work as a certificate study.

Why not just bound compression by VC or DS dimension via existing reductions? Sample Compression Scheme Reductions converts binary schemes into multiclass and regression schemes. It pays in the graph dimension and a $\log|\mathcal{Y}|$ factor, and its base binary scheme is exponential in $d$ and non-constructive. Pabbaraju's lower bound shows no function of the DS dimension alone can work when labels are unbounded. These approaches cannot predict what P2L will actually select. Experiment 1 measures how well each dimension predicts observed compression size.

Why not just keep a held-out test set? Holding out data is simple and valid. On noisy sine it gives 0.250 against P2L's 0.172 in the reported numbers, because it removes training data. It also offers no account of why a class compresses. We keep it as the floor every method must beat.

Why not just use greedy teaching sets directly? Compton et al. show that maximum-elimination greedy fails to reach linear size, so it is included as an ablation rather than a solution. Our hypothesis is that worst-violator greedy succeeds exactly where the self-directed dimension is small. We test this on their Head-and-Tail construction.

Proposed Experiments

The first decisive check runs on exact, small classes. We enumerate thresholds, intervals, unions of $k$ intervals, singletons plus the empty set (the case where the classical teaching dimension blows up), Head-and-Tail classes, and small disambiguated versions of Pabbaraju's multiclass construction. For each class we compute every dimension and compression size listed above.

The prediction is concrete. P2L compression size should correlate with the self-directed dimension, measured by rank correlation across classes, and should fall strictly below the Littlestone dimension on ordered classes. On Pabbaraju-style classes the self-directed dimension should grow with sample size $m$ at roughly the $\log m$ rate. A class with small self-directed dimension on which worst-violator P2L is large would refute the tightness conjecture and is an equally publishable outcome.

The second check uses the benchmarks. On binary MNIST ($N=1000$) and noisy sine ($N=200$ and $500$), we compare the certificate and test error of original P2L, the ablations, and our variant, targeting P2L's reported 0.143 and 0.172 bounds. We then extend to 10-class MNIST to test the claim that the certificate does not depend on the number of labels. We found no reported P2L or compression result on Lacuna for multiclass MNIST, so this regime will set its own baseline, with the test-set bound as the floor.

The success criterion across both checks is that dimension-guided selection shrinks the compression set on ordered or low-self-directed-dimension structure, and does not shrink it on classes where that dimension is large. That pattern is what would show the sequential view explains when compression certificates work.