Counting Teaching Examples in Low-Dimensional Training Subspaces

Why does a network with millions of weights generalize? One well-tested answer is that it can be compressed. Finzi and colleagues train networks inside a small random slice of weight space, then quantize and entropy-code the weights. The resulting code is short enough to give non-vacuous PAC-Bayes guarantees, which are generalization bounds that charge a model for its description length (PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization). A second, older answer compresses the data instead of the weights. If a learner retrained on only $k$ of its $n$ training examples still labels all $n$ correctly, those $k$ examples form a compression set. A small compression set certifies generalization without any prior, any quantization, or a held-out split (Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension; Pick-to-Learn). A compression set is exactly a teaching set: the handful of examples a teacher would show this learner to make it land on this hypothesis.

This proposal measures one number that links the two answers. The number is the ratio between the size of the smallest compression set we can find for a network trained in a $d$-dimensional weight subspace and $d$ itself. Learning theory makes sharp predictions about ratios of this kind. Teaching complexity for a class of combinatorial capacity $d$ is known to be at most quadratic and conjectured to be linear. Any stable compression scheme must use at least about $d/2$ points. The worst class known has a teaching-to-capacity ratio of only $5/3$. Nobody has checked whether real networks confined to low-dimensional subspaces behave like these idealized classes. Checking this also answers a practical question: when does counting examples certify a trained network more tightly than counting bits?

Core Claim

We claim that, for networks trained in a random subspace of dimension $d$, the compression set found by a retrain-and-add procedure grows linearly in the intrinsic dimension of the labeling rule. It does not grow with ambient input dimension, raw parameter count, or even $d$ once $d$ is large enough to fit the data. The empirical teaching ratio $\tau = k/d$ should settle at a small constant and track the known combinatorial scale: at least $1/2$ from the stable-scheme lower bound, and near the observed worst-case ratio of $5/3$. It should not grow the way greedy teaching can in adversarial constructions.

If this holds, a sample-compression certificate and a subspace PAC-Bayes certificate become directly comparable. A compression set of size $k$ costs roughly $\log_2 n$ bits per stored example. A quantized subspace model costs roughly $b$ bits per coordinate. The consistent-case compression bound, obtained by a union bound over which $k$ examples are kept, says that with probability $1-\delta$ the true error $\varepsilon$ satisfies

$$\varepsilon \le \frac{\ln \binom{n}{k} + \ln(n/\delta)}{n-k},$$

where $n$ is the training-set size. A version that allows $r$ training errors adds the corresponding binomial term. Compression wins exactly when $\tau \log_2 n < b$. Measuring $\tau$ therefore predicts, before any bound is computed, which certificate will be tighter.

The central question is not new: Gap 3 of the file notes that no paper formally relates subspace dimension to compression-set size. What is new here is treating that dimension as the "$d$" in the teaching and compression conjectures and measuring the ratio on trained networks. The closest work, Finzi et al., bounds parameter description length and never counts examples. Pick-to-Learn counts examples but never ties the count to any notion of dimension.

Research Program

The procedure has three parts, and each borrows its core step from prior work.

The learner comes from Finzi et al. It trains weights $w = w_0 + P z$, where $P$ is a fixed Kronecker-structured random projection and $z \in \mathbb{R}^d$. It uses the same architectures and the same seeds. The reconstructor is this learner run from a fixed initialization on the compression set, so the "hypothesis class" is exactly the set of functions reachable in the subspace.

The compressor starts from Pick-to-Learn. It retrains on the current set, adds the training examples that the retrained model gets wrong, and repeats until consistent or until the allowed error count $r$ is reached. The warning from Lower Bounds for Greedy Teaching Set Constructions is that greedy one-at-a-time selection can be forced to $\Omega(\log\log|\mathcal{C}|)$ on adversarial "head and tail" classes. So we also run a non-greedy compressor that periodically prunes the set: it deletes an example if the model retrained without it stays consistent.

The subspace dimension is not fixed in advance. We grow it the way BAXUS grows its search space (Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces). Training starts in a tiny nested subspace, and coordinates are split only when training accuracy stalls, with the existing solution kept. This avoids a problem the file documents for static embeddings: guessing $d$ too small excludes good solutions, and guessing it too large wastes capacity (Ginsbourger et al.). It also turns $d$ into a quantity measured from the data rather than a knob we set.

To separate intrinsic from ambient dimension, we build planted-structure tasks. In the spirit of the padded Branin and Hartmann6 benchmarks from high-dimensional optimization, labels depend on an $m$-dimensional linear or manifold feature of inputs padded to ambient dimension $D$. The theory of regression on manifolds predicts sample complexity governed by intrinsic dimension alone (Sample complexity and effective dimension for regression on manifolds). Our prediction is the analogue for compression sets: $k$ should scale with $m$ and stay flat in $D$.

Finally, we calibrate the compressor against exact answers where exact answers exist. On Warmuth's class and on the SAT-discovered class $C_0$ (12 points, capacity 3, recursive teaching dimension 5, from On the Recursive Teaching Dimension of VC Classes), everything is small enough to enumerate. We measure how far the greedy and pruned compressors are from the optimal teaching size, and how that gap compares with the ratio we see on networks.

Baselines

The naive reference is a Hoeffding bound on a held-out split. We train in the same subspace on a fraction of the data and bound error on the rest, sweeping the split fraction and reporting the best split, which favors this baseline. It is the reference PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization itself warns often beats data-dependent PAC-Bayes. Beating it means a tighter certificate while training on all $n$ points.

The strongest existing method is the full Finzi et al. pipeline: subspace training, learned quantization, arithmetic coding, and a data-independent prior. It is run with their architectures, the same subspace dimensions, and the same training budget, and we report bounds from their procedure recomputed on our runs. The file gives these reported figures: an ImageNet data-independent error bound of 93.5% (prior best 96.5%), 40.9% with data-dependent priors, and an MNIST description length of 0.38 KB versus 6.23 KB. No numerical bound values for MNIST, FashionMNIST, or CIFAR appear in the file ("no reported result found on Lacuna for" those bound values). We therefore reproduce them rather than quote them. For Pick-to-Learn on these networks, no reported result was found on Lacuna. Beating Finzi means a smaller certified error at matched test accuracy on at least one of MNIST, FashionMNIST, or CIFAR. Failing to beat it, together with a measured $\tau$ that predicts the loss, is itself a reportable outcome.

Two ablations isolate the key ingredient, the subspace constraint. The first runs the same compressor on the full-parameter network: if $k$ is similar, dimension is not what controls the compression set. The second swaps the adaptive nested subspace for fixed-$d$ subspaces over a grid of $d$, which tests whether the BAXUS-style growth matters or only the final size does. A third control, greedy versus pruned compression, isolates whether greedy selection inflates $k$.

Why not just…?

Why not just use a held-out Hoeffding bound? On large datasets it may well be tighter, and we treat that as a live threat, not a strawman. The two differ in what they explain. A holdout bound certifies the model but says nothing about why it generalizes. A small $\tau$ says the model is determined by roughly $d$ examples. The best-split comparison above settles tightness directly. We expect compression to win mainly at small $n$, where holding out data costs the most.

Why not just report Finzi's quantized PAC-Bayes bound? For large $n$, $\log_2 n$ bits per stored example is expensive compared with a few bits per quantized weight. PAC-Bayes may therefore win whenever $\tau$ is near 1. The proposal's value is that $\tau$ predicts the crossover in advance. We also test a hybrid in the style of the Moran-Yehudayoff scheme with side information (Teaching and compressing for low VC-dimension): a compression set plus a few coded bits that fix the subspace dimension and the random seed.

Why not just run Pick-to-Learn on the unconstrained network? That is exactly our first ablation. Without the subspace, the reconstructor can memorize, so we expect $k$ to approach the number of hard examples rather than any dimension. If the ablation shows otherwise, the claim that low effective dimension drives the teaching ratio is false.

Why not just pick examples greedily and stop? Compton et al. prove that greedy selection has adversarial failure modes. Whether those failures appear on natural data is open. The calibration on $C_0$ and Warmuth's class, together with the greedy-versus-pruned comparison, measures the gap instead of assuming it away.

Decisive Checks

The first check uses the planted tasks. We fix the intrinsic dimension $m$ and increase the ambient dimension $D$ over an order of magnitude. The claim fails if compression-set size grows with $D$ or with raw parameter count rather than with $m$.

The second check is on MNIST, FashionMNIST, and CIFAR. We plot $k$ against the adaptively chosen $d$, and against fixed-$d$ grids. The claim fails if $\tau$ does not settle, or if it lands well above the combinatorial range of $1/2$ to about $5/3$.

The third check repeats the pixel-shuffling test of Finzi et al., which destroys the input structure that convolutional networks rely on. If compression reflects real structure in the task, shuffling should raise both the adaptive $d$ and $k$, just as it erases compressibility in their weight-coding bounds.

The fourth check compares, per dataset, the crossover $\tau \log_2 n$ against the achieved bits per coordinate $b$. Whether this crossover correctly predicts which certificate is tighter is the practical deliverable. We restrict to these three datasets because the retrain loop is too costly at ImageNet scale; the ImageNet figures above serve only as context.