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

arXiv: https://arxiv.org/abs/2607.06382 · HTML: https://mlsanity.com/paper/2607.06382/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 37 references that are in the map.
- First posted on arXiv 7 Jul 2026.

## Builds on (most cited first, 30 of 30)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies](https://mlsanity.com/paper/1906.00425/) (2019)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks](https://mlsanity.com/paper/1910.01663/) (2019)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [Scaling description of generalization with number of parameters in deep learning](https://mlsanity.com/paper/1901.01608/) (2019)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks](https://mlsanity.com/paper/2109.08844/) (2021)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Nonparametric regression using over-parameterized shallow ReLU neural networks](https://mlsanity.com/paper/2306.08321/) (2023)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [What Can Be Learnt With Wide Convolutional Neural Networks?](https://mlsanity.com/paper/2208.01003/) (2022)
- [Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck](https://mlsanity.com/paper/2309.03800/) (2023)
- [A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis](https://mlsanity.com/paper/2502.16331/) (2025)

## Built on by (most cited first, 1 of 1)

- [Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression](https://mlsanity.com/paper/2608.17434/) (2026)

## Abstract (arXiv)

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 CL,w,R, pinning it down up to a single factor of L: between Omega(Lw2R2/n) and tildeO(L2w2R2/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 Omega(4L) 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.