A recent impossibility result says that no rule for estimating a model's test error from its training data can be reliable across all learning algorithms and data distributions once the sample is smaller than about half the capacity of the model class. The hard cases in that proof are parity functions. Parities are also the standard example of problems that gradient-based learners cannot solve efficiently. That overlap invites an appealing conjecture: perhaps the impossibility goes away if we only ask about efficient learners. This note argues that the conjecture is false as stated, and proposes the version that is true. Noiseless parities can be learned in polynomial time by Gaussian elimination, so restricting runtime does not save estimability. What does save it is restricting how much information the learner pulls out of the data. Suppose a learner touches the sample only through a short sequence of rounded averages, which is how a statistical-query learner (one that only asks for approximate expectations) works, and roughly how quantized-gradient training works. Then its test error can be estimated from training data alone. The estimate comes from a bound that takes polynomial time to compute and that tightens when the training run is "predictable."
The two-sentence version is this. A learner can only be audited from its own training data if its interaction with that data can be written down in few bits, and we give a computable bound that measures those bits. The classes where auditing provably fails are exactly those that force the learner to extract many bits. For gradient-style learners, those are the same classes that make learning statistically-query hard.
Core Claim
The impossibility theorem in Fantastic Generalization Measures are Nowhere to be Found proves that for sample size $n \le d/2$, any generalization estimator misses by more than $1/8$ on at least 49% of (algorithm, distribution) pairs. It names this a learnability-estimability trade-off and builds its counterexamples from parities over finite fields. Its own discussion leaves open whether computational restrictions shrink the failure set. We resolve that question in two parts. The negative half: the failure survives for polynomial-time learners, because Gaussian elimination learns the counterexample classes efficiently and is still not estimable. The positive half concerns learners whose dependence on the sample $S$ passes through a transcript $\pi(S)$ of statistical-query answers, each rounded to a grid of width $\tau$. Fix any prefix code $c$ over transcripts before seeing data. Then with probability at least $1-\delta$,
$$\big|\,\mathrm{err}_D(A(S)) - \mathrm{err}_S(A(S))\,\big| \;\le\; \sqrt{\frac{|c(\pi(S))|\,\ln 2 + \ln(2/\delta)}{2n}},$$
where $\mathrm{err}_D$ and $\mathrm{err}_S$ are the population and training errors and $|c(\pi(S))|$ is the code length in bits of the realized transcript. The proof is an Occam-style argument: the output hypothesis is a deterministic function of the transcript, and the code defines a prior over transcripts.
The worst case for this bound is $q\log_2(2/\tau)$ bits for $q$ queries. Data-dependence enters because the code length is measured on the realized transcript. A code that predicts each answer from earlier ones assigns short lengths to smooth, predictable training runs, which makes this a version of Algorithmic Luckiness applied to the training trajectory rather than to the hypothesis. The converse links the bound to the computational side. On the parity constructions of the impossibility paper, any learner that succeeds must produce transcripts of $\Omega(d)$ bits. Any statistical-query learner must make many queries. So the bound becomes vacuous exactly in the regime where estimation is provably impossible, and nowhere else on those families.
We are explicit about what is new. The upper bound is a compression bound, and its novelty lies in what it compresses: the query transcript, not the output weights. The contribution is threefold. First, the negative result that runtime alone is the wrong restriction. Second, the matching characterization of when the Gastpar et al. failure set collapses. Third, a polynomial-time computable bound for gradient-style learners that can be compared directly with existing computable bounds.
Research Program
The theoretical work has three pieces. The first formalizes the negative half. We show that the learner in the impossibility construction, or an equivalent Gaussian-elimination learner, runs in polynomial time and keeps the 49% failure rate. This rules out "efficient learners" as the fix.
The second proves the transcript bound and its lower-bound partner. The partner states that, on the impossibility paper's parity families, any learner with expected transcript length $o(d)$ cannot reach the accuracy level that drives the impossibility. That argument reduces to the information a $b$-bit transcript can carry about a uniformly random parity.
The third connects transcript length to query complexity, using the statistical-query lower bounds behind the hardness of parity. The resulting statement is a trade-off with three resources: estimation error, query count, and sample size. It mirrors how Computational-Statistical Tradeoffs from NP-hardness treats nondeterminism as a resource that can be exchanged for samples. Here the transcript plays the role of that resource.
The algorithmic work builds the bound for real training. A gradient method is put in transcript form by rounding each minibatch gradient coordinate, or a random low-dimensional projection of the gradient, to a grid of width $\tau$. The code $c$ is a fixed predictive coder that encodes each rounded gradient's residual against a data-independent extrapolation of previous steps. Computing the bound costs one pass of entropy coding over the run, which is linear in training time.
This directly targets the obstacle left by Generalization Guarantees via Algorithm-dependent Rademacher Complexity. That paper bounds SGD through the hypotheses produced over all $2^n$ splits of a double sample, so it is valid but cannot be evaluated on a real run. Our bound is evaluated on the single run that actually happened.
We expect the bound to be vacuous for full-width gradients of million-parameter networks, because the transcript is enormous. Projection dimension and rounding width therefore become controlled design choices, and we will report honestly where the bound stops being informative.
Baselines
The naive reference is training error used as the estimate of test error. On the parity families it is known to fail, and the impossibility theorem says how badly. Any proposed estimator must beat it on the fraction of (algorithm, distribution) pairs where the estimate lands within $1/8$ of the truth.
The strongest computable competitor for neural networks is the directly optimized PAC-Bayes bound of Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. That method uses SGD to fit a Gaussian distribution over weights against a prior fixed before training. It reports a bound of 0.201 for the roughly 1.2-million-parameter T-600^3 network on binary MNIST, with observed test error around 3%, while the VC bound exceeds 121 million. We rerun it on the same binary MNIST task, architecture, and seeds as our quantized-gradient learner, with an equal number of tuning trials over its prior variance and over our $\tau$ and projection dimension. Matching 0.201 with a lighter computation would count as competitive. Going below it would count as beating it. A clear win on the parity and sparse-parity families, where PAC-Bayes is not designed to detect impossibility, would count as a qualitative advance even if MNIST is lost.
The data-dependent-prior baseline is Entropy-SGLD from Entropy-SGD optimizes the prior of a PAC-Bayes bound: Data-dependent PAC-Bayes priors via differential privacy. It reports bounds between 3 and 8% at about 2% observed error on MNIST. Its validity relies on the noisy sampler reaching stationarity, and it reports test error roughly 5 to 10 times worse than standard training. We compare on bound value and on the test error of the trained model together, because our method also degrades the learner by rounding its gradients.
For algorithm-dependent Rademacher complexity there is no reported numerical result on Lacuna. We implement a Monte Carlo estimate using $K$ random splits under the same total compute as our method and report it as a heuristic, since a subsampled version does not carry the original guarantee.
The hold-out baseline splits the $n$ samples, trains on a fraction $1-\rho$, and estimates error on the rest, sweeping $\rho$.
The key ablation replaces the predictive code with a uniform code of $q\log_2(2/\tau)$ bits. This isolates how much of the bound's tightness comes from data-dependent luckiness in the trajectory and how much from rounding alone.
Why not just…?
Why not just restrict to polynomial-time learners, as the open question suggests? Gaussian elimination learns noiseless parities in polynomial time and inherits the full failure rate, so this restriction provably does not shrink the 49% set. We will verify this numerically in the parity experiment below. This is the central negative result motivating the transcript restriction.
Why not just use a hold-out set? A hold-out estimate is uniformly valid, so it is a real threat. Its cost is samples. In the $n \le d/2$ regime, giving up a fraction $\rho$ of the data can push the learner out of the regime where it learns at all. Our experiments report the full curve of model accuracy against estimate accuracy as $\rho$ varies, next to the transcript bound, which spends no samples. If hold-out dominates that curve on MNIST, we will say so and confine the claim to the explanatory result on parities.
Why not just apply a compression or Occam bound to the trained weights? For overparameterized networks, the description length of the output weights is huge. That is why Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data needed stochastic weights. A short training trajectory can still produce complicated-looking weights. We measure the gap by computing a quantized-weight Occam bound on the same runs.
Why not just add privacy noise for stability? The Entropy-SGLD results show the cost: a 5 to 10 times higher test error, plus a stationarity assumption that bounded-time training does not meet. Rounding gives a guarantee that holds after any number of steps. Whether it costs less accuracy is the empirical question the MNIST comparison answers.
Proposed Experiments
The decisive synthetic experiment reproduces the parity families of the impossibility paper over $\mathbb{F}_2^d$ for $d$ from 20 to 200 with $n \le d/2$, along with sparse parities with $k$ relevant bits. For each (learner, distribution) pair it records the fraction of pairs where each estimator is within $1/8$ of the true test error. The learners are Gaussian elimination, full-batch gradient descent on a two-layer network with rounded gradients at several $\tau$, and an explicit statistical-query learner.
Three predictions are falsifiable. Gaussian elimination should stay near the 49% failure rate under every training-data estimator. The transcript bound should be non-vacuous exactly when the gradient learner fails to learn, and vacuous when it succeeds. On sparse parities, the predictive-code length should grow with the number of steps gradient descent needs, so the bound tracks the known statistical-query cost.
The real-data experiment uses binary MNIST with the T-600^3 architecture and smaller networks against the 0.201 reference. It reports bound value, test error of the rounded learner, and computation, and plots bound against projection dimension to locate where it becomes vacuous.
A third, smaller experiment applies the bound to learned Branch-and-Cut scoring policies on the packing instances of Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming, with 10 to 15 constraints, 1 to 100 training instances, and 30 trials. There the reported generalization gap follows a $1/\sqrt{N}$ curve with $R^2$ above 0.95. Policy training is low-dimensional, so a transcript bound should be tight, and checking whether it reproduces that $1/\sqrt{N}$ fit is a clean outside test.
The project fails if the transcript bound is vacuous on sparse parities that gradient descent learns with few steps, because that would mean transcript length does not track estimability.
References
- Fantastic Generalization Measures are Nowhere to be Found
- Algorithmic Luckiness
- Computational-Statistical Tradeoffs from NP-hardnes
- Generalization Guarantees via Algorithm-dependent Rademacher Complexity
- Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
- Entropy-SGD optimizes the prior of a PAC-Bayes bound: Data-dependent PAC-Bayes priors via differential privacy
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming