A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

arXiv:2607.06382 · stat.ML, cs.LG · Submitted 2026-07-07 · Read on arXiv

Arkaprabha Ganguli, Emil Constantinescu

stat.ML, cs.LG

Submitted: 2026-07-07

License: http://creativecommons.org/licenses/by/4.0/

The gist: A persistent empirical observation is that trained neural networks outperform their neural tangent kernel (NTK) limit on tasks with compositional structure, yet a quantitative account of when and by

Terminology

Abstract

A persistent empirical observation is that trained neural networks outperform their neural tangent kernel (NTK) limit on tasks with compositional structure, yet a quantitative account of when and by how much has been lacking. Working on the unit circle, we give such an account through a dichotomy between two complexity measures of the target: its Fourier complexity, which controls NTK kernel regression, and its architectural complexity, which controls learning over depth- L, width- w ReLU networks with the variation norm of the weights bounded by R. We first characterize the minimax rate of the architecture class C L,w,R, pinning it down up to a single factor of L: between (Lw 2R 2/n) and (L 2w 2R 2/n). We then show the NTK estimator sits exponentially above this floor whenever the two complexities decouple: for the depth- L iterated sawtooth, NTK regression needs (4 L) samples while the minimax floor is polynomial in L. Numerical experiments confirm the theoretical claims: on bandlimited smooth targets, the NTK is competitive or better, while on the hypercube sparse-parity model, a standard two-layer network beats the NTK by four to six orders of magnitude in test error. The gap is thus a function-space property, a mismatch between the kernel's smoothness bias and the target's compositional structure, rather than a generic kernel-versus-network phenomenon.

Related papers