A sample compression scheme summarizes a labeled training set by a small subset of its own examples. Some fixed procedure can rebuild, from that subset alone, a classifier that labels every training example correctly. The smaller the subset, the stronger the generalization guarantee, and the guarantee needs no held-out data and no assumptions about the data distribution. The classical theory sizes these subsets by the VC dimension, a worst-case measure of how many patterns a model class can fit. For a linear classifier on top of $D$ fixed features, that dimension is $D+1$, and the bound becomes useless once $D$ is in the thousands. Real feature representations, however, usually have low effective dimension: most of the data's variance lies in a few directions, even when $D$ is huge. Machine teaching shows that the gap between ambient size and real difficulty can be large. Here a teacher hand-picks the examples a learner sees, and for regularized linear learners one or two well-chosen synthetic points are enough to pin down the trained model in any ambient dimension.
This note proposes treating sample compression as teaching from a fixed pool. The compression set is a teaching set that a regularized learner, here ridge regression used as a classifier, turns back into a correct classifier. We hypothesize that the smallest such set scales with the data's ridge effective dimension rather than with $D$ or with the margin-based count. The selected points then carry the relevant subspace themselves, so no data-dependent projection has to be paid for separately. We will analyze this claim, test it on high-dimensional random-feature problems, and report how much it tightens distribution-free risk certificates. We will also measure how far pool-constrained teaching falls short of synthetic teaching.
Core Claim
The reconstruction map is fixed in advance. It is ridge regression on $\pm 1$ labels with regularization $\lambda$, followed by taking the sign. The compression map may be any deterministic search over subsets of the sample $S$ of size $n$. Its job is to find a small $C \subseteq S$ whose ridge classifier agrees with every label in $S$. The quantity we expect to govern $|C|$ is the ridge effective dimension of the sample's feature matrix,
$$d_\lambda = \sum_{j} \frac{\sigma_j^2}{\sigma_j^2 + \lambda},$$
where $\sigma_j$ are the singular values of the $n \times D$ feature matrix. This sum counts the directions that carry more signal than the regularizer suppresses, and it can be far below $D$ when the spectrum decays. Any consistent $C$ gives a certificate through the classical bound of Floyd and Sokolova et al.. The bound has to include the bits $b$ that encode the choice of $\lambda$ from a fixed grid:
$$R(h) \le \frac{1}{n-k}\left(k \ln \frac{en}{k} + b\ln 2 + \ln \frac{1}{\delta}\right),$$
with $k = |C|$ and $\delta$ the failure probability. The claim is empirical and partly theoretical. On data with decaying spectra, the minimal pool teaching set should have size close to $d_\lambda$ up to logarithmic factors, and it should be clearly smaller than both the support-vector count and the greedy selections used today.
We are explicit about what this does not do. It does not touch the worst-case sample compression conjecture. That conjecture asks for size $O(\text{VCD})$ for every class, and the best general results remain quadratic (Mansouri) or cardinality-dependent (Moran et al.). The conjecture serves as context. Our result is a data-dependent refinement for one learner family, in a regime where the VC dimension is the wrong yardstick.
Where This Sits
Two teaching results motivate the idea. The Teaching Dimension of Linear Learners shows, through the optimality conditions of regularized learning, that ridge, SVM and logistic regression can be taught with 1 or 2 examples whatever the ambient dimension, confirmed at $D = 10{,}000$. The Teaching Dimension of Regularized Kernel Learners extends this to an $\epsilon$-approximate teaching dimension of $O(1/\epsilon^2)$ for Gaussian kernels, independent of input dimension. Both papers assume the teacher can synthesize any point, and the kernel paper names pool-based selection as left open. A compression scheme cannot synthesize: it must choose among observed examples. Our proposal sits exactly in that gap, and the size of the gap is a measurable teaching-to-learning quantity. We call it the pool cost, defined as $k_{\text{pool}}$ divided by the synthetic teaching dimension.
Two compression results constrain the design. Stable Sample Compression Schemes proves that SVMs and the cycling Perceptron are stable compression schemes of size at most $(r/\gamma)^2$, where $r$ is the data radius and $\gamma$ the margin. This yields the optimal margin bound $O(r^2/(\gamma^2 n) + \log(1/\delta)/n)$. It is our main theoretical competitor, because it is also independent of $D$. Our bet is that $d_\lambda$ can be much smaller than $(r/\gamma)^2$ when the spectrum decays but the margin is thin.
Lower Bounds for Greedy Teaching Set Constructions proves that greedy, maximum-elimination selection can be far from optimal on adversarial classes. That result tells us not to build the compression search as a purely greedy procedure. Pick-to-Learn is exactly such a greedy wrapper: it repeatedly adds the worst-fit example and retrains. It gives our proposal a direct empirical foil.
Finally, PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization uses low effective dimension in parameter space. It trains in a random low-dimensional subspace, then quantizes and arithmetic-codes the weights. We use low effective dimension in data space instead, and our certificate counts examples rather than bits of weights. A useful consequence follows. Projecting onto principal components estimated from $S$ would break a distribution-free bound unless the basis were itself encoded. In our scheme the selected examples span the subspace, so the bound already pays for it through $k$.
Research Program
The compression search is the main thing we build. Its first step scores every example by its ridge leverage, meaning how much that example alone pins down a direction of the regularized fit. It then seeds a subset by deterministic leverage-ordered selection. The search adds violated examples, but ranks them jointly by leverage and violation. In other words, it searches with a structural score rather than with elimination counts alone. After the subset becomes consistent, a removal pass tries deleting each member and keeps any deletion that preserves consistency. The procedure is run over a small fixed grid of $\lambda$ values, and the bound pays $b = \log_2(\text{grid size})$ bits. Because ridge solutions on a growing set can be updated in low-rank steps, the cost is one factorization per accepted point. A full retrain is not needed, which addresses the latency problem the file flags for Pick-to-Learn.
The theoretical work has a precise target and a known risk. Standard leverage-sampling arguments from randomized linear algebra suggest that roughly $d_\lambda \log d_\lambda$ examples approximate the full ridge solution. Consistency, however, requires the approximation error to stay below the normalized margin of the full ridge classifier. A naive analysis therefore produces a factor like $d_\lambda/\epsilon^2$ with $\epsilon$ tied to the margin, and that could lose to $(r/\gamma)^2$. We will try to prove a bound in which the margin enters only through the choice of $\lambda$. We will also prove the easy direction: any consistent $C$ must span the directions on which the full ridge fit depends, so $k$ is at least of order the number of non-negligible terms in $d_\lambda$. If we cannot close the upper bound, the empirical part still decides whether the scaling holds in practice.
Baselines
The naive reference point is the held-out test-set bound. We hold out a fraction of the data, train ridge on the rest, and report a binomial upper confidence bound on the held-out error. It is often tight, and any compression certificate should be compared with it at equal $n$. The "doing nothing structural" compression reference is the VC bound for linear classifiers with $D+1$ parameters. It is expected to be vacuous at large $D$, but it calibrates the pool-cost ratio.
The strongest existing compression competitor is the stable SVM scheme of Hanneke and Kontorovich. We will run a hard-margin or near-hard-margin SVM on the same features, with the same $\lambda$/C grid encoded at the same bit cost. Its certificate uses the actual support-vector count and, separately, the $(r/\gamma)^2$ value inside their margin bound. The file reports no number for this bound on any benchmark below: no reported result found on Lacuna for stable SVM compression certificates on MNIST or random-feature data. We will compute it ourselves. Beating it means a strictly smaller $k$ and a strictly lower certified risk on the same split at the same $\delta$.
The strongest algorithmic competitor is Pick-to-Learn wrapped around the same ridge learner, given the same compute. No reported result found on Lacuna for Pick-to-Learn's certificate values on these datasets, so we rerun it.
For the ImageNet comparison only, we cite Finzi et al., who report a data-independent error bound of 93.5% and a data-dependent bound of 40.9% on ImageNet. That comparison is not like-for-like: they bound a whole network, while we bound a linear head on frozen features. We report it as context, not as a claim of superiority.
Three ablations isolate the key ingredient. The first replaces leverage-guided selection with uniform random subsets grown to consistency. The second replaces ridge leverage with plain (unregularized) leverage. The third removes the pruning pass. If uniform subsets reach the same $k$, the structural score adds nothing.
Why not just…?
Why not just use the SVM's support vectors? This is the real threat. The stable-compression result already gives a dimension-free certificate, and on clean, large-margin data the support set may be as small as anything we find. Our case rests on regimes with decaying spectra and small margins, where $(r/\gamma)^2$ grows but $d_\lambda$ does not. The synthetic sweep below varies the two independently. If support-vector counts track or beat our $k$ throughout, the proposal is refuted.
Why not just run Pick-to-Learn? It already produces non-vacuous certificates from a compressed subset. But it is greedy by maximum error, and Compton et al. show that greedy selection can be badly suboptimal. We test this directly by comparing subset sizes at matched compute. If they agree within a few points, our contribution reduces to the faster updates.
Why not just project onto the top principal components and use a $(d+1)$-parameter VC bound? The projection is estimated from the training sample, so the standard bound does not apply unless the basis is paid for. Encoding a $d$-dimensional basis in $D$ coordinates is costly. In our scheme, the compression set encodes the subspace at a cost of $k$ examples. We will also report the PCA-plus-VC bound computed honestly, with the basis bits charged, to make that cost visible.
Why not just hold out a test set? For a single number this may well win. The compression certificate keeps all data for training, and it also explains which examples determine the classifier. We will report both, and we treat the held-out bound as a target to approach rather than a straw man.
Proposed Experiments
The decisive experiment is a synthetic sweep in the style of the $D = 10{,}000$ setting of Liu and Zhu. We generate inputs whose covariance has $d$ dominant directions and a tunable tail, and labels from a halfspace with controlled margin. We vary $d$, the tail decay, the margin and $n$. Each instance yields the minimal $k$ found, $d_\lambda$, the support-vector count, $(r/\gamma)^2$, the Pick-to-Learn size, and the four certificates. The hypothesis passes if $k$ grows roughly linearly in $d_\lambda$ (up to logarithms), stays flat as $D$ grows, and grows more slowly than $(r/\gamma)^2$ as the margin shrinks. It fails if $k$ tracks the support-vector count.
The second experiment uses MNIST, the benchmark on which Finzi et al. report compressed models of 0.38 KB. The features are random Fourier features of dimension 10,000. They are drawn independently of the data, so the bound stays valid. We use one-vs-rest binary tasks, and the multiclass reduction follows Sample Compression Scheme Reductions. We report certified risk against test error, against the held-out bound, and against the pool cost ratio $k/\text{TD}_{\text{synth}}$, where the synthetic teaching dimension is 2 for inhomogeneous ridge.
The third experiment is an ImageNet linear probe on features from a network pretrained on disjoint data. It is reported alongside, not against, the 93.5% and 40.9% figures. If its certificates are non-vacuous while ridge features have $D$ in the thousands, that shows effective-dimension compression scales to realistic representations.
References
- Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension
- The Decision List Machine
- A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension
- Teaching and compressing for low VC-dimension
- The Teaching Dimension of Linear Learners
- The Teaching Dimension of Regularized Kernel Learners
- Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound
- Lower Bounds for Greedy Teaching Set Constructions
- The Pick-to-Learn Algorithm: Empowering Compression for Tight Generalization Bounds and Improved Post-training Performance
- PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization
- Sample Compression Scheme Reductions