Search papers, labs, and topics across Lattice.
This paper investigates the performance disparity between neural networks and their neural tangent kernel (NTK) limit in compositional learning tasks, identifying a critical dichotomy between Fourier complexity and architectural complexity. By establishing minimax rates for depth-$L$, width-$w$ ReLU networks and demonstrating that the NTK estimator requires exponentially more samples than necessary under certain conditions, the authors quantify the sub-optimality of NTK in these contexts. Their findings reveal that while NTK performs well on smooth targets, it significantly underperforms compared to standard neural networks on tasks with complex compositional structures, highlighting a fundamental mismatch in function space properties.
NTK regression can require exponentially more samples than necessary for compositional tasks, revealing a critical gap in our understanding of neural network performance.
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 $\textbf{when}$ and $\textbf{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 $\textbf{Fourier complexity}$, which controls NTK kernel regression, and its $\textbf{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 $\mathcal{C}_{L,w,R}$, pinning it down up to a single factor of $L$: between $惟(Lw^2R^2/n)$ and $\tilde{O}(L^2w^2R^2/n)$. We then show the NTK estimator sits $\textbf{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.
