A standard two-layer neural network outperforms its own theoretical "lazy" limit by four to six orders of magnitude on compositional tasks, according to a new arXiv preprint [S1]. That is the gap between a model that nails a problem and one that barely moves the needle — and until now, nobody could say precisely why it appears or how wide it gets. The paper claims to put hard numbers on a divide that has shadowed kernel methods for years, and the mechanism it identifies could reshape where we think deep learning's real advantage lives.

The kernel that couldn't compose

The neural tangent kernel, or NTK, is a mathematical shortcut for what happens when a network's weights barely shift during training — the so-called lazy regime. Instead of tracking millions of moving parameters, you treat the whole network as a fixed kernel and solve a clean regression problem. It is elegant, well-understood, and, as practitioners have observed for years, consistently beaten by actual trained networks on tasks with compositional structure — functions built from nested sub-functions, like f(g(h(x))) [S1].

The authors note that this performance gap was a long-standing empirical pattern without a quantitative explanation of when it shows up or how large it grows [S1]. Their preprint, posted to arXiv's cs.AI and cs.LG categories and not yet peer-reviewed, sets out to close that gap [S1].

Two complexities, one gap

The core idea is a dichotomy between two ways of measuring how hard a target function is [S1]:

  • Fourier complexity — how complicated the function looks when broken into sine waves. This governs the NTK, because kernel regression is essentially a smoothing operation in frequency space.
  • Architectural complexity — how hard the function is to represent as a composition of simple pieces through a depth-L, width-w ReLU network with weight variation bounded by R. This governs what a trained network can actually achieve.

When these two measures agree — when a function that is simple in Fourier terms is also simple to compose — the NTK does fine. When they decouple, it falls off a cliff.

The authors pin the best achievable performance for the architecture class — the minimax rate — between Ω(Lw²R²/n) and Õ(L²w²R²/n), where n is the number of training samples [S1]. The NTK estimator, they show, sits exponentially above this floor whenever the two complexities decouple [S1].

The sawtooth that breaks the kernel

The paper's sharpest example is the depth-L iterated sawtooth — a function built by repeatedly composing a simple zigzag. For this target, NTK regression needs Ω(4^L) samples to learn it well, while the minimax floor is merely polynomial in L [S1].

To feel the difference: at depth 10, the NTK would need on the order of 4^10 — roughly one million — samples. A method hitting the minimax floor needs something proportional to 10. That is not a marginal gap. It is the difference between a dataset that fits on a laptop and one that would not fit in a data centre.

Numerical experiments in the paper confirm the theoretical predictions [S1]. On the hypercube sparse-parity model, a standard compositional benchmark, a two-layer network beats the NTK by four to six orders of magnitude in test error [S1] — a factor between 10,000 and 1,000,000.

Where the kernel still wins

The news is not all bad for the NTK. On bandlimited smooth targets — functions without sharp compositional structure, where Fourier and architectural complexities stay aligned — the NTK is competitive with or better than trained networks [S1].

The authors are explicit about this boundary. The gap, they argue, is a function-space property: a mismatch between the kernel's built-in smoothness bias and the target's compositional structure, not a generic failure of kernels versus networks [S1]. Pick the right function class and the NTK is perfectly adequate. Pick a compositional one and it is exponentially the wrong tool.

What it means

For anyone trying to understand why deep learning works, this paper offers a concrete answer to a question that has been waved away with hand-me-down intuitions. The advantage of trained networks over their kernel limits is not magic, and it is not universal. It shows up precisely when the target function has compositional structure — when the answer is a hierarchy of simpler pieces — and the NTK's Fourier-based smoothing cannot see that hierarchy.

In plain terms: the NTK tries to learn a function by fitting its wiggles in frequency space. A trained network can learn by building the function from the inside out, composing simple parts into complex wholes. When the target is compositional, the inside-out approach is exponentially more sample-efficient. When it is not — when the function is just a smooth wave — both approaches are roughly equivalent.

What it means for business

For most operators — a suburban agency running off-the-shelf models, a two-person firm using API-based AI, a cafe experimenting with demand forecasting — this paper will not change anything on the desk this quarter. The NTK is a theoretical tool, not a product, and the compositional tasks studied here are mathematical benchmarks, not business workflows.

But the finding carries a practical signal for anyone choosing between approaches. If your problem has hierarchical, compositional structure — predicting outcomes that depend on chained decisions, modelling systems where causes nest inside causes — a trained neural network may be exponentially more sample-efficient than a kernel method. If your problem is essentially smooth pattern matching — recognising objects in clean images, interpolating between similar data points — a kernel approach may be just as good and far simpler to deploy.

The takeaway is direct: understand the structure of your target function before choosing your architecture. A compositional problem rewards depth. A smooth problem does not.

What we don't know yet

The paper is a preprint and has not been peer-reviewed [S1]. Its theoretical bounds are derived for specific architectures — depth-L, width-w ReLU networks with bounded variation norm — and for the unit-circle setting [S1]. Whether the exponential gap survives in more general regimes, with different activation functions, optimisers, or data distributions, remains open.

The experimental results, including the striking four-to-six-orders-of-magnitude gap, come from specific model setups: the hypercube sparse-parity model and a standard two-layer network [S1]. Real-world compositional tasks — language modelling, multi-step reasoning, hierarchical decision-making — may or may not exhibit the same decoupling of Fourier and architectural complexity.

The next thing to watch is whether independent groups reproduce the experimental gaps on more realistic benchmarks, and whether the theory extends beyond the unit circle. Until peer review and replication, this is a compelling theoretical claim, not an established result.

If you want to understand where deep learning's edge actually comes from — and where it does not — this is a paper worth tracking. Subscribe to keep reading as the review process unfolds.

Sources

Generated from an audited evidence pack with primary-source research. Social-media items are discussion signals, not verified facts. Nothing here is financial, legal or medical advice.