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

TL;DR. Take a single target function and price it two ways: by how much Fourier mass it has at high frequencies (which is what kernel regression pays for), and by how small a deep ReLU network can build it (which is what weight-decay training pays for). This paper proves that whenever those two price tags decouple — high frequency, compact compositional recipe — the neural tangent kernel is exponentially sample-inefficient relative to the information-theoretic optimum for the network class. For the depth-L iterated sawtooth, NTK regression needs \Omega(4^L) samples while the minimax floor is polynomial in L. Along the way it proves what appears to be the first minimax rate for deep ReLU networks indexed by architecture parameters (L, w, R) rather than by a smoothness exponent. It's a "why it works" result: it turns the folklore that "kernels can't do feature learning" into a quantitative, target-by-target criterion — at fixed input dimension, which is new.

The lazy-network story, and where it breaks

The NTK result of Jacot et al. is one of the cleanest facts in deep learning theory: at infinite width and standard initialization scale, gradient descent barely moves the weights, the network behaves like its linearization, and training reduces exactly to kernel ridge regression (KRR) with a fixed, architecture-determined kernel. Suddenly a deep network is a classical object — a function in a reproducing kernel Hilbert space (RKHS) — and decades of kernel theory apply.

The catch is well known empirically: real, finite-width networks with weight decay consistently and substantially beat their own NTK on tasks with hierarchical or compositional structure. The existing theoretical explanations of this gap are almost all about input dimension: kernels can't concentrate on a low-dimensional relevant subspace of a high-dimensional input, so on things like sparse parities or multi-index models they need d^{\Theta(k)} samples where a network needs polynomially many. But the empirical advantage of trained networks also grows with depth of the target's structure, at fixed input dimension, and there the quantitative account has been missing.

This paper isolates that depth axis by working in the simplest possible place — the unit circle \mathbb{S}^1, one-dimensional input — where the NTK diagonalizes exactly in the Fourier basis and every quantity can be computed.

One function, two price tags

The central move is to compare two complexity measures of the same target function f^\star:

Fourier complexity (the lazy price). On \mathbb{S}^1, the depth-D ReLU NTK is translation-invariant, so its eigenfunctions are the Fourier modes e^{ik\theta} and its eigenvalues are the Fourier coefficients of the kernel profile. Those decay as \mu_k(D) \asymp D^2/k^2 — and, crucially, the exponent -2 is the same at every depth. The reason is lovely and worth internalizing: the arc-cosine kernels underlying the ReLU NTK have a \sqrt{1-u} singularity at the diagonal u=1, which in angle coordinates is a |\theta| kink, and a kink's Fourier coefficients decay as k^{-2}. Composition (stacking layers) can't smooth away that leading singularity; depth only rescales the prefactor. This is Bietti–Bach's "deep equals shallow" phenomenon: the NTK's RKHS is just the Sobolev space H^1(\mathbb{S}^1), at any depth. Concretely (Proposition 3), \|f\|^2_{\mathcal H_{\Theta^{(D)}}} \asymp \frac{1}{D^2}\sum_k |\hat f(k)|^2 k^2, so a target whose Fourier mass sits at frequency k^\star costs the kernel \Omega((k^\star)^2/D^2) in squared RKHS norm — and RKHS norm translates directly into sample complexity for KRR.

Architectural complexity (the rich price). The relevant function space for weight-decay training is Parhi–Nowak's deep variation space \mathcal{R}\mathrm{BV}^2_{\mathrm{deep}}(L): functions expressible as L-fold compositions f = f^{(L)} \circ \cdots \circ f^{(1)} of shallow ReLU networks, with norm equal to the sum of layerwise variation norms (roughly, sums of |v_k||w_k| over neurons — the quantity weight decay controls). This norm is small for anything with a compact compositional description, no matter how wildly it oscillates.

The paper's dichotomy: NTK regression is governed by the first price, learning over the architecture class by the second, and the two are independent quantities. When they agree (smooth targets), the kernel is fine. When they decouple, the kernel pays exponentially more than it should.

The witness. The Telgarsky sawtooth makes this maximally concrete. Take the tent map \tau(z) = 2\sigma(z) - 4\sigma(z - \tfrac12) (variation norm 6) and compose it L times: g_L = \tau \circ \cdots \circ \tau is a triangle wave with 2^{L-1} peaks, realized by a depth-L width-2 network with total variation norm \leq 6L. Embedded on the circle by even reflection, its spectrum is exactly computable (Lemma 2): a constant fraction \delta = 12/\pi^4 \approx 0.12 of its L^2 mass sits at the single frequency k^\star = 2^{L-1}. Exponential Fourier complexity, linear architectural complexity — the decoupling in its purest form.

The floor: a minimax rate indexed by architecture

The most consequential clause of the paper's framing is what the NTK is compared against. Prior separations compare a kernel with some specific competitor — a particular network, a particular training algorithm. This paper compares against the minimax floor: the best any estimator whatsoever can guarantee over the class of functions the architecture can express. That requires knowing the floor, and Theorem 4 supplies it, apparently for the first time in this parametrization.

Define \mathcal{C}_{L,w,R} as depth-L compositions of width-\leq w shallow ReLU nets with total variation norm \leq R. Then for noise level \sigma^2 \asymp R^2:

where \mathcal{R}^\star_n is the minimax expected squared L^2 error from n noisy samples. The rate is pinned down to within a single factor of L. Both directions are classical machinery deployed carefully: the upper bound counts parameters (W = O(Lw^2)), invokes the Bartlett et al. VC bound O(WL\log W) for piecewise-linear networks, and runs it through Rademacher complexity and Talagrand contraction. The lower bound is a Fano argument over a Varshamov–Gilbert packing of 2^{\Omega(W)} parameter perturbations around a generic network. The residual factor of L is an honest open problem — closing it would need a depth-linear Rademacher bound under a sum-of-layer-norms constraint, where current tools only handle products of layer norms. Importantly, the headline result divides by the minimax upper bound, so it's immune to this ambiguity.

The authors note this theorem is useful independently: (L, w, R) are quantities a practitioner can read off an architecture, giving a direct, kernel-free estimate of a compositional problem's sample complexity.

The gap

With both sides in hand, Theorem 6 is almost bookkeeping. If f^\star \in \mathcal{C}_{L,w,R} has a \delta-fraction of its mass at frequency k^\star, then Step 1 charges the NTK (k^\star)^2/D^2 in RKHS norm; Step 2 converts RKHS norm into a KRR sample-complexity lower bound \propto \|f^\star\|^2_{\mathcal H}/\epsilon^2 (a two-point Fano argument via Caponnetto–De Vito); Step 3 divides by the minimax upper bound:

For the sawtooth, k^\star = 2^{L-1} and L^2w^2R^2 = 144 L^4, giving n_{\mathrm{KRR}} \gtrsim 4^L/(D^2\epsilon^2) against a floor of \tilde O(L^4/\epsilon^2) — exponential in L for every fixed kernel depth D. That last point deserves emphasis: making the NTK deeper doesn't help, because "deep equals shallow" means depth never changes the kernel's k^{-2} smoothness bias.

And, crucially, the paper proves the converse (Corollary 9): for bandlimited targets (\hat f(k) = 0 beyond a constant K), both sample complexities are polynomial in K — no gap. The separation is a property of the target's spectral structure relative to its compositional realization, not a blanket "networks beat kernels" claim.

The experiments, including the awkward one

Three empirical checks, plus one honest failure the authors foreground rather than bury.

E1 diagonalizes the NTK Gram matrix on 5000 circle points for depths D \in \{2,3,5,10\}: fitted spectral slopes are -1.980 to -1.989, within 1% of the predicted -2, and parallel across depths — the kernel side of the story, verified.

E2 is the essential control: on \cos(k\pi z), k \le 5, NTK-KRR and a wide two-layer network converge together, with NTK actually ahead at large n (\sim 10^{-11} vs \sim 10^{-7} at n=5000). This kills the alternative reading that networks generically dominate.

E3a is the awkward part: nobody could train a network on the sawtooth. Although g_L is exactly width-2 representable, every configuration tried (depth/width scaling, residual connections, LayerNorm, smooth activations, L-BFGS, even exact Telgarsky initialization) plateaued at the constant-mean predictor's loss of 1/12 for L \gtrsim 5. This is a known optimization hardness result (Malach et al., Shamir), and the paper's guarantees are explicitly statistical — ERM over the class, not SGD. But it means the headline sawtooth separation is never demonstrated end-to-end.

E3b substitutes a compositional target where SGD provably does succeed: sparse parity \prod_{i=1}^k x_i on \{-1,+1\}^d. The hypercube analog of the theorem (Proposition 10) says the NTK needs \Omega(d^k/\epsilon^2) samples because the Walsh character \chi_{[k]} has NTK eigenvalue \Theta(d^{-k}), while a small network realizes it with O(k) neurons — and Glasgow's result guarantees two-layer SGD learnability. Empirically, at d=30, k=4: NTK stays at the trivial baseline (test error \approx 1) for all tested n up to 10^4 (its barrier is \approx 8\times 10^5), while the trained network phase-transitions and hits 3.2\times 10^{-7}.

What to make of it, and what to be skeptical of

What's genuinely new. The two ingredients are individually known — NTK-RKHS \approx Sobolev space (Bietti–Bach), sawtooth = high-frequency target (Telgarsky) — and the authors say so plainly. The novelty is the baseline and the axis. Comparing against the minimax floor of the architecture class (rather than one hand-picked competitor) makes the sub-optimality information-theoretic: the NTK isn't just worse than some network, it's exponentially above the best any method could do on that class. And the separation is in depth at fixed input dimension — orthogonal to, and in principle compounding with, the classical dimension-based separations. The architecture-indexed minimax rate is a reusable tool regardless of the NTK story.

Skepticism where due. First, the clean theory lives on \mathbb{S}^1; the multivariate extension is sketched as "structurally available" but not done. Second, the sawtooth witness is unfittable by gradient descent, so the exact target the theorems concern is empirically inert — the parity experiment realizes the mechanism but on a different domain with a somewhat different proof. Third, the whole framework compares KRR against ERM; whether weight-decay SGD actually achieves the variational objective (i.e., whether the statistical floor is also the algorithmic floor) is stated as open, and E3a shows the answer is "not always." Fourth, the gap statement requires Fourier mass concentrated at a single high frequency; realistic compositional targets have spread spectra, and it's less clear how the constants play out there. The discussion's claim that "many structured targets are compositionally cheap but spectrally rich" is plausible but is intuition, not theorem.

What changes if it holds. The practical takeaway is a decision criterion: whether a fixed-kernel surrogate (NTK, Laplace, Gaussian — anything with polynomial spectral decay) suffices for your problem is decided by comparing the target's Fourier complexity to its architectural complexity, not by ideology about kernels versus networks. The NTK is provably near-optimal on H^1-smooth targets and provably, intrinsically miscalibrated on compositionally-sparse oscillatory ones. It also sharpens the interpretation of "deep equals shallow": depth doesn't enlarge the lazy function class, but it enlarges the rich one, and this paper quantifies the statistical price of being stuck in the former.

Where to spend your reading time. Section 3 (Setup) is the heart — the k^{-2}-from-a-kink argument and the two "background facts" (Proposition 3 and the sawtooth's variation norm) contain the entire idea; once you have them, Theorems 4 and 6 feel inevitable. Then read Remark 5 and the E3a paragraph for the two honest open edges: the factor-L gap in the minimax rate, and the statistical-versus-algorithmic divide that the sawtooth so vividly exposes.