Do Gradient-Trained Learners Hit the Discrete Speed Limits of Universal Learning Theory?

Learning theory has recently proved something unusual about how fast a learner's error can shrink as it sees more data. If you fix the distribution the inputs come from and ask how quickly error falls for every possible target concept, the answer does not vary smoothly. It falls into a few fixed classes: error drops exponentially, like $1/n$, like $\log(n)/n$, or arbitrarily slowly. Which class applies depends on whether certain infinite combinatorial structures exist inside the hypothesis class. None of these results has ever been checked against an actual training run. The learners analyzed for the $\log(n)/n$ regime are worst-case empirical risk minimizers, meaning the theory lets an adversary pick the worst hypothesis that still fits the training data. Practitioners use gradient descent, which picks a specific fitting hypothesis for reasons of its own.

We propose to build hypothesis classes whose rate regime is known exactly, train them with gradient descent, and measure whether gradient descent's choice of fitting hypothesis lands in the slow regime the theory reserves for the worst case. The study is designed so that a theorist can contribute a class as runnable code and an empiricist can contribute a learner. The deliverable has two parts. The first is an answer to the open question of whether the implicit preferences of gradient descent remove the logarithmic penalty. The second is a calibrated statistical test of whether these rate regimes can be told apart at all at realistic sample sizes.

Core Claim

Universal Rates of Empirical Risk Minimization proves that worst-case empirical risk minimization (ERM) obeys a four-way split, with error decaying as $e^{-n}$, $1/n$, $\log(n)/n$, or arbitrarily slowly. It works only with mathematical toy classes such as thresholds on the natural numbers, singletons, and two-dimensional halfspaces, and it explicitly analyzes the worst fitting hypothesis. A Theory of Universal Learning proves the coarser three-way split for optimal learners. That paper uses learners built from infinite games, which cannot be implemented directly.

Our claim is that the gap between worst-case ERM and the ERM that gradient descent actually performs can be measured directly. We make it measurable by parametrizing the toy classes themselves as differentiable models. Gradient descent then returns a member of exactly the theorized class whenever it reaches zero training error. We test three things in turn. First, whether worst-case ERM on the lower-bound distributions from the proofs visibly shows the $\log(n)/n$ penalty. Second, whether gradient-descent ERM shows the same penalty or escapes it. Third, whether an unconstrained network, which is an improper learner free to output functions outside the class, reaches the faster optimal rate.

The existing literature does not contain any of these measurements. The Shape of Learning Curves: a Review fits 14 parametric curve families to empirical curves and concludes that "no universal model can be identified." It never links curve shape to these combinatorial regimes. Its conclusion motivates us: perhaps diversity in curve shape partly reflects which regime a class sits in, with the boundaries blurred by finite-sample noise.

Research Program

The first component is a regime atlas. Each entry is a class taken from Hanneke and Xu's examples and packaged as code with four parts. The first is a sampler for the marginal distribution, including the specific hard distributions used in the lower-bound proofs. The second is a target concept. The third is an exact or near-exact worst-case ERM oracle. For singletons and thresholds over integers, the version space (the set of hypotheses consistent with the sample) is simple enough that we can enumerate it and pick the consistent hypothesis with maximal true error. The fourth is a differentiable parametrization of the class. A singleton becomes a learned softmax over positions whose argmax is the predicted point. A threshold becomes a learned scalar passed through a sharpening sigmoid. A halfspace becomes a linear model.

For each entry we run several selection rules on identical samples: worst-case ERM, uniformly random consistent ERM, gradient-descent ERM from several initializations and step sizes, and an unconstrained multilayer network fed the same inputs as an improper learner. The selection rule is the only variable. This is the ingredient whose effect the study is built to isolate.

Throughout, we summarize a learning curve by how $n$ times the error grows with the logarithm of $n$. We fit

$$n\,\bar{e}(n) \approx a + s\log n,$$

where $\bar{e}(n)$ is mean test error over $R$ independent samples of size $n$, $a$ is an intercept, and $s$ is the log-excess slope. Under a $1/n$ regime, $n\bar{e}(n)$ settles to a constant, so $s=0$. Under $\log(n)/n$, it grows linearly in $\log n$, so $s>0$. Under exponential decay, it collapses toward zero. Because the integer-domain classes are cheap to simulate, we can span $n$ from $10^2$ to $10^7$ with thousands of replicates. A logarithmic factor will only be visible over a range that wide.

Before interpreting any learner, we run a power study on worst-case ERM, where the ground truth is known. It determines how many decades of $n$ and how many replicates are needed for $s$ to separate the regimes at a fixed false-positive rate. This study is itself a contribution. If the separation requires $n$ far beyond any realistic dataset, the honest conclusion is that the $1/n$ versus $\log(n)/n$ distinction is invisible in practice. That would be worth publishing.

The second component moves toward real data while keeping the theory's realizable assumption, which says the true target lies inside the class. We use a teacher–student design. We freeze image features from a network trained on CIFAR-10 and label images with a fixed linear halfspace on those features, so the target is in the class by construction. We then compare a gradient-trained linear student with an approximate worst-case consistent halfspace. The worst-case halfspace is found by linear programming that pushes the decision boundary to the edge of the version space along directions that maximize disagreement on a held-out pool.

We use the 180 domains of CIFAR-10-Warehouse, which contains 608,691 images drawn from search engines and diffusion models, as 180 different input distributions under the same teacher. The theory makes a falsifiable one-sided prediction here. A class's universal rate is a guarantee for every input distribution, though individual distributions can be faster. So no domain should show decay slower than the class's regime, while constants should vary widely. The benchmark's reported spread of target accuracies, 40% to 99% across domains, suggests the constants will indeed differ substantially.

The collaboration component is practical rather than rhetorical. Conference on Learning Theory 2015: Preface documents learning theory's push to import tools from neighboring fields, but it offers no route to empirical checks. Datathons and Software to Promote Reproducible Research shows that a shared, preconfigured environment cut setup time for mixed clinician–data-scientist teams from days to minutes. We borrow that lesson and release the atlas with a fixed interface: theorists submit a class with its sampler and worst-case oracle, empiricists submit a learner, and the harness returns calibrated slope estimates. We will measure transfer concretely by whether outside groups contribute classes or learners.

Baselines

The naive reference point is a continuous power law with a free exponent, the POW3 family $a n^{-\alpha}+c$ surveyed by The Shape of Learning Curves: a Review. It is the strongest descriptive competitor, because a free exponent near 1 can imitate a $\log(n)/n$ curve over a limited range. We fit it to exactly the same curves with the same data budget, choosing between models by held-out extrapolation error at the largest $n$ and by information criteria. The discrete-regime account beats it only if fitting the regime family (choosing among $e^{-n}$, $1/n$, $\log(n)/n$ with fitted constants) extrapolates better at equal or fewer free parameters, or if the power-law exponents fitted across classes cluster at the theoretical values rather than spreading continuously. No reported result was found on Lacuna for POW3 extrapolation error on these classes, so we will produce this number ourselves.

The strongest existing method for working with learning curves in practice is LCRankNet from Learning to Rank Learning Curves. It ranks partial training curves with neural networks and reports finding a CIFAR-10 architecture with 2.99% error in 20 GPU hours. LCRankNet solves a different problem, ranking configurations rather than identifying an asymptotic regime, so we do not claim to beat it at architecture search. We include it in one fair comparison: given curves truncated at $n=10^4$, predict which of two classes will have lower error at $n=10^7$. Both methods see the same truncated curves, and LCRankNet is trained on atlas curves held out by class. A regime classifier that matches it without any learned parameters would show that the theory carries predictive information.

The key ablation is the selection rule itself. We hold the class, distribution, and sample fixed and compare worst-case ERM, random consistent ERM, and gradient-descent ERM. Any difference in slope $s$ is then attributable to which consistent hypothesis was picked, not to the class. A second ablation varies how integer inputs are encoded for the unconstrained network (one-hot versus binary). This tests whether an improper learner's rate depends on representation, which the theory does not model.

Why not just…?

Why not just fit power laws, since they already describe empirical curves well? This is the main threat. Over two decades of $n$, a $\log(n)/n$ curve is close to $n^{-0.9}$, so a free exponent may absorb the logarithm entirely. We do not argue this away. The power study on worst-case ERM, where the true regime is known, measures exactly when a power law becomes distinguishable from the regime family. If it never does at feasible $n$, we report that the regimes cannot be identified from curves alone. Even then, the selection-rule comparison remains informative, because it compares slopes between learners on identical data rather than requiring a fit to identify an absolute regime.

Why not just use classical VC-dimension bounds? Thresholds on the integers and singletons both have VC dimension 1. The distribution-free PAC (probably approximately correct) bound, which must hold uniformly over all input distributions, is therefore the same for both. Yet Hanneke and Xu use them to illustrate different ERM regimes. Any observed difference in slope between these two classes under worst-case ERM is a difference that VC theory cannot express. The first experiment tests this difference directly.

Why not just simulate worst-case ERM and stop? That would check the theorems numerically, which matters mostly for the power study. The open question named in Hanneke and Xu's own framing is about learners that are not adversarial. Only the gradient-descent and unconstrained-network arms address it.

Why not just run this on standard CIFAR-10 training curves? Real labels are not realizable within a known class, and the combinatorial structures of a deep network's function class cannot be computed. A slope measured there would have no theoretical prediction to test against. The teacher–student construction keeps realizability while using real image distributions.

Proposed Experiments

The first decisive check is a sanity test of the theory. On the lower-bound distribution for singletons, worst-case ERM should show a slope $s$ significantly above zero. On thresholds, it should show $s$ near zero, with the confidence intervals set by the power study. If even worst-case ERM fails to separate the two at $n=10^7$, the regimes are practically invisible and the remaining experiments are reframed as constant-estimation studies.

The second check is the main result. We ask whether gradient-descent ERM on singletons shows the positive slope or a flat one, across initializations and step sizes. A flat slope would be evidence that the implicit preference of gradient descent prunes the obstruction behind the logarithmic penalty. A positive slope would be evidence that gradient descent behaves like a worst case on these distributions. Either outcome answers the question. We also check whether the unconstrained network reaches the optimal-learner rate from A Theory of Universal Learning, which would mean an improper learner beats every proper ERM on the class.

The third check covers the teacher–student halfspaces across the CIFAR-10-Warehouse domains. The one-sided prediction is falsified if any domain shows reliably slower decay than the regime the theory assigns to the class. We will also report how the fitted constant $a$ varies with domain, because a widely varying constant is how the theory accommodates the 40%-to-99% accuracy spread.

All curves, oracles, and slope estimates will be released through the atlas harness, so that each claim can be rerun by someone from the other side of the theory–practice divide.