A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel Arkaprabha Ganguli,
Emil Constantinescu
Mathematics & Computer Science Division, Argonne National Laboratory, Lemont, IL, USA [email protected] [email protected]
arXiv:2607.06382v1 [stat.ML] 7 Jul 2026
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 depthL 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 Ω(Lw2 R2 /n) and Õ(L2 w2 R2 /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 Ω(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.
1
Introduction
A central tool for the theory of deep learning is the neural tangent kernel (NTK) (Jacot et al. 2018). It rests on a striking fact: when a network is very wide and trained by gradient descent at the standard initialization scale, its weights barely move, the network behaves like its linearization about initialization, and in the infinite-width limit training reduces exactly to kernel ridge regression with a fixed, architecturedetermined kernel. The network’s effective hypothesis class is then a reproducing kernel Hilbert space (RKHS), a classical and well-understood object. A large literature uses this equivalence to reason about how deep networks converge and generalize (Du et al. 2019; Arora et al. 2019; Lee et al. 2019). The difficulty is that this “lazy” regime, though analytically convenient, is empirically the wrong model of how useful networks learn. On tasks with hierarchical or compositional structure, networks trained the ordinary way (finite width, weight decay, genuine feature learning) consistently
and substantially outperform their own NTK (Arora et al. 2020; Geiger et al. 2020). When a theoretical proxy systematically mispredicts what the real system can do, conclusions drawn from it can mislead. This motivates a precise question: on which targets, and by how much, is the NTK sub-optimal, and what is it about those targets that the kernel cannot exploit? Existing answers are largely about input dimension: kernels need exponentially more samples than networks when the target depends on a low-dimensional projection of a highdimensional input (Bach 2017; Ghorbani et al. 2020; Daniely and Malach 2020), reflecting the curse of dimensionality and the value of feature learning. But the empirical advantage of trained networks also grows with depth, at fixed input dimension, on compositionally structured targets, and here a quantitative account has been missing. We give one, and trace the gap to a single interpretable mechanism. Two notions of a target’s complexity. Our analysis compares, for the same target function, two ways of measuring how hard it is to learn. The lazy (NTK) cost of a target is its RKHS norm; on the circle we show this equals, up to a depth-dependent constant, the classical Sobolev norm, which penalizes high-frequency oscillation. Call this the target’s Fourier complexity: a function whose Fourier mass is concentrated at frequency k ⋆ costs about (k ⋆ )2 . The rich cost, the one governing weight-decay training, is instead the deep variation norm (Parhi and Nowak 2022), which measures the size of the smallest network that builds the target, its architectural complexity, and is small for functions with compact compositional descriptions even when they oscillate wildly. The NTK is sub-optimal exactly when these two diverge: a target can be cheap to assemble with depth yet look hugely complex to a smoothness-biased kernel. The canonical example is the depth-L “sawtooth” (Telgarsky 2016), which a width-2 network of depth L builds with O(L) weights but which oscillates 2L−1 times. Contributions. On the unit circle S1 , where the NTK admits a clean Fourier description, we make this precise: 1. A minimax characterization of the depth-L, widthw architecture class CL,w,R (variation norm ≤ R): the minimax L2 rate is pinned between Ω(Lw2 R2 /n) and Õ(L2 w2 R2 /n), i.e. tight up to a single factor of L (Theorem 4). This is the statistical floor: the best any estimator
can do on the class. 2. An exponential NTK gap against that floor (Theorem 6): the ratio of NTK to minimax sample complexity is ≳ (k ⋆ )2 /(D2 L2 w2 R2 ), exponential exactly when Fourier and architectural complexity decouple. For the sawtooth this is Ω(4L ) NTK samples against a polynomial-in-L floor (Corollary 8). 3. Empirical validation on three fronts: the NTK spectrum matches the predicted k −2 decay; on smooth (bandlimited) targets the NTK is competitive or better, with no gap; and on hypercube sparse parities a standard two-layer network beats the NTK by four-to-six orders of magnitude, realizing the predicted separation end-to-end. What is new. The two ingredients above are individually known: the NTK-RKHS is a Sobolev space (Bietti and Bach 2021), and the sawtooth is a high-frequency target (Telgarsky 2016). Our contribution is to make the consequence of these two facts precise using the appropriate baseline. Earlier separations usually compare a kernel with a specific competitor, such as a particular neural network or training algorithm, and the resulting bounds often scale with the input dimension. Here, we instead compare the NTK with the minimax floor, namely, the best performance achievable by any method. This yields a separation in depth while keeping the input dimension fixed. This comparison makes the usual intuition that “kernels dislike oscillation” quantitative. For this target, the NTK is exponentially worse than the information-theoretic optimum. The result relies on the minimax characterization in contribution 1, which, to our knowledge, has not previously been used in the kernel-versus-network literature. The gap should not be interpreted as a general comparison between kernels and networks. It arises because the smoothness bias of the kernel is poorly matched to the compositional structure of the target. In contrast, Corollary 9 shows that smooth compositional targets do not exhibit an exponential gap. Roadmap. Section 2 situates the contribution; Section 3 fixes the setup (the NTK and its spectrum, the architecture class, and the sawtooth witness); Section 4 establishes the minimax rate and Section 5 the exponential NTK gap; Section 6 reports experiments and Section 7 discusses scope. The main text gives proof outlines; the complete proofs are in the supplementary material.
2
Related Work
Function spaces of networks. Going back to Barron (1993), a line of work characterizes the functions networks represent efficiently. The variation-norm framework (Bach 2017) considers shallow ReLU networks as integrals over neuron parameters with the total-variation norm of the output measure; Savarese et al. (2019) identified the univariate space with bounded second-order variation, Ongie et al. (2020) gave the multivariate Radon-domain version RBV2 (Rd ), and representer theorems (Parhi and Nowak 2021) realize regularized minimizers as finite-width networks. Parhi and Nowak (2022) give the deep extension RBV2deep (L) we adopt, whose norm is the layerwise sum of variation norms
and whose minimizers are depth-L ReLU networks. This is the rich-regime lens. The lazy regime and the NTK. Jacot et al. (2018) showed that infinitely wide networks trained by gradient descent under lazy scaling are kernel ridge regression with the NTK; the ReLU NTK is built from the arc-cosine kernels of Cho and Saul (2009). Bietti and Mairal (2019); Bietti and Bach (2021) computed the deep-NTK spectrum on the sphere, establishing depth-invariant k −d eigenvalue decay (“deep equals shallow”), the fact we use to make our lower bound hold at every depth. Separations. The classical depth separations are within the network family (Telgarsky 2016; Eldan and Shamir 2016); they show depth buys expressivity but do not compare to kernels. Kernel-versus-network sample-complexity gaps are exponential in input dimension d: variation-norm adaptivity (Bach 2017), multi-index models (Ghorbani et al. 2020), ResNet feature learning (Allen-Zhu and Li 2020), and parities (Daniely and Malach 2020). These compare the kernel to a specific competing predictor; ours is depth-explicit at fixed dimension and against the minimax floor. Closest in spirit is the line of Cagnetta et al. (2023, 2024), which shows that deep networks gain a sample-complexity advantage over kernels on hierarchically structured data (the random hierarchy model, and the wide-CNN RKHS viewed as an additive model of patch interactions). That work studies hierarchical classification with convolutional networks and compares against a fixed kernel; ours studies regression with an exact analytic witness and compares against the minimax floor. Kumar et al. (2025)’s recent Gaussian-RKHS-vsshallow-network gap runs in the opposite direction and, on bounded domains, does not separate kernels from the NTK: the Gaussian RKHS, with super-polynomial spectral decay, sits strictly inside the more slowly decaying NTK-RKHS. Minimax rates. A parallel literature gives minimax rates over smoothness-defined target classes (Höldercompositional (Schmidt-Hieber 2020), Besov (Suzuki 2019)) or over the shallow variation space (Parhi and Nowak 2023; Yang and Zhou 2024). We instead characterize the minimax rate of the deep architecture class, indexed by (L, w, R): quantities directly accessible to a practitioner, and to our knowledge the first minimax rate paired with the deep variation space RBV2deep (Parhi and Nowak 2022) (whose representer theory supplies the class but no estimation lower bound). Any rate over the architecture class also lower-bounds it over any smoothness subclass intersected with it.
3
Setup
We work on the unit circle S1 , identified with [0, 2π), with L2 (S1 ) and Fourier basis {eikθ }k∈Z ; fˆ(k) denotes Fourier P coefficients and ∥f ∥2H 1 = k (1 + k 2 )|fˆ(k)|2 the Sobolev norm. ReLU is σR (z) = max{0, z}.
The bias-augmented deep NTK. The building blocks are the arc-cosine kernels (Cho and Saul 2009) value
κ0 (u) = π1 (π − arccos u), p κ1 (u) = π1 u(π − arccos u) + 1 − u2 ,
(D)
(D)
Θ(D) (x, y) = (1 + u) κ0 (u) + κ1 (u), whose rank-one term removes the parity gaps of the vanilla spectrum while preserving its decay rate. On S1 it is translation-invariant, so it diagonalizes in the Fourier basis, P Θ(D) (x, y) = k µk (D)eik(θx −θy ) , with (combining Bietti and Mairal 2019, Prop. 5 and Bietti and Bach 2021, Cor. 3) eigenvalue decay c D2 /k 2 ≤ µk (D) ≤ C D2 /k 2 ,
k ̸= 0.
(1)
(D)
KRR with Θ is the t → ∞ limit of lazy-trained infinite-width networks (Jacot et al. 2018), so KRR samplecomplexity lower bounds also bound idealized NTK training. Throughout, D is the depth of the kernel (a fixed property of the NTK), while L will denote the depth of the target’s compositional realization; the two are independent, and our separation holds for every fixed D ≥ 2. The decay rate in (1) is not incidental but the crux of everything that follows, so we record its origin. Because Θ(D) is a dot-product kernel and ⟨x, y⟩ = cos(θx − θy ) on S1 , it is stationary; its integral operator is therefore a convolution, diagonalized by the Fourier characters {eikθ } with eigenvalues equal to the Fourier coefficients of the kernel profile, and positive-definiteness (the kernel is a limit of Gram matrices) is, by Bochner’s theorem, exactly the statement that µk (D) ≥ 0. The exponent −2 is set by the regularity √ of the arc-cosine profile at the diagonal: κ0 , κ1 have a 1 − u singularity at u = 1, which in the angle variable is a |θ| kink at θ = 0, and a kink has Fourier coefficients decaying as k −2 . Depth enters only through the prefactor C(d, L) ≍ D2 , not the exponent. This is the “deep equals shallow” phenomenon (Bietti and Bach 2021): stacking layers does not let the lazy kernel favor higher frequencies. (Equivalently, the NTK-RKHS coincides with that of the Laplace kernel, a Sobolev space (Geifman et al. 2020; Chen and Xu 2021).) The deep variation space and architecture class. For P a univariate single-hidden-layer network s(z) = k vk σR (wk z P− bk ) + cz + c0 , the variation norm is ∥s∥RBV2 = k |vk ||wk | + |s(0)| + |s(1) − s(0)| (Parhi and Nowak 2022, Lem. 2.8). The deep space RBV2deep (L) consists of L-fold compositions = f (L) ◦ · · · ◦ f (1) with P f (ℓ) norm ∥f ∥RBV2deep (L) = inf ℓ ∥f ∥RBV2 over decompositions (Parhi and Nowak 2022). We study the architecture class of bounded, norm-constrained compositional networks. Definition 1 (Architecture class). CL,w,R is the set of f : S1 → R admitting f = f (L) ◦ · · · ◦ f (1) with each f (ℓ) a
g3 (22 peaks)
g2 (21 peaks)
0.5 0.0
from which the depth-D NTK profile is assembled by the standard recursion: iterate the covariance Σ(ℓ) = κ1 (Σ(ℓ−1) ) and accumulate Θ(ℓ) = Θ(ℓ−1) κ0 (Σ(ℓ−1) ) + Σ(ℓ) (Jacot et al. 2018; Bietti and Bach 2021). Writing u = ⟨x, y⟩, we use the bias-augmented kernel (Basri et al. 2019)
g1 (20 peaks)
1.0
0.0
0.5 z
1.0 0.0
0.5 z
1.0 0.0
0.5 z
1.0
Figure 1: The Telgarsky sawtooth gL for L = 1, 2, 3. Each added layer doubles the number of oscillations (2L−1 peaks) while adding only a constant to the variation norm (∥gL ∥RBV2deep ≤ 6L): exponential Fourier complexity at linear architectural cost. single-hidden-layer ReLU network of width ≤ w, total norm ∥f ∥RBV2deep (L) ≤ R, and ∥f ∥∞ ≤ R. Any f ∈ CL,w,R has W = O(Lw2 ) parameters; functions act on S1 via the embedding θ 7→ z = θ/π and periodization. This is the hypothesis class whose minimax rate we characterize, and within which the sawtooth witness lives. A witness: the Telgarsky sawtooth. Our theory applies to any target whose Fourier and architectural complexities decouple; the iterated sawtooth below is one clean, analytically tractable representative, chosen because its spectrum is exactly computable. It is not special: the sparse parity of Proposition 10 (a different domain, the hypercube) exhibits the same gap, and iterated/hierarchical maps generally do (we return to this breadth in the discussion). We use the sawtooth as the running univariate witness precisely because it isolates the mechanism with no extraneous structure. With τ (z) = 2σR (z) − 4σR (z − 1/2) (so ∥τ ∥RBV2 = 6), the depth-L sawtooth gL = τ ◦ · · · ◦ τ is a triangle wave with 2L−1 peaks on [0, 1] (Figure 1), realized by a depth-L width-2 network; hence gL ∈ CL,2,6L , a tiny architectural budget. Embedding on S1 by even reflection concentrates its spectrum at the exponentially high frequency k ⋆ = 2L−1 (Lemma 2). It is thus the prototype of a target with low architectural but exponentially high Fourier complexity. Lemma 2 (Spectrum of the embedded sawtooth). The evenreflected gL on S1 has Fourier series X cos(j 2L−1 θ) gL (θ) = 12 − π42 . j2 j≥1, j odd
Hence its mass concentrates at k ⋆ = 2L−1 , with dominant coefficient |ĝL (k ⋆ )| = 2/π 2 , total ∥gL ∥2L2 = 2π/3 (independent of L), and concentration fraction δ := |ĝL (k ⋆ )|2 /(∥gL ∥2L2 /(2π)) = 12/π 4 ≈ 0.12. Proof. The unit P triangle wave on [0, 1] has the classical series 12 − π42 j odd j −2 cos(jω). The depth-L sawtooth is this wave dilated to 2L−1 periods, so ω 7→ 2L−1 θ; even reflection to [0, 2] in the θ = πz parameterization retains only the cosine terms, giving the stated series. Parseval yields ∥gL ∥2L2 = 2π/3, and the ratio of the dominant term gives δ = (2/π 2 )2 /(1/3) = 12/π 4 . However, we also note that, although its exact, analytically tractable spectrum makes the sawtooth an ideal theoretical
witness, it is notoriously hard to fit by gradient descent: training a network to recover gL fails for moderate L, a welldocumented phenomenon in the depth-separation literature (Malach et al. 2021; Shamir 2018). This is an optimization obstacle, separate from the statistical question we study, and is out of scope here; accordingly, our empirical separation (Section 6) uses a different SGD-learnable compositional structure, the sparse parity, while the sawtooth serves only as an analytical example in our theoretical investigation.
is exponential whenever k ⋆ is exponential in the architectural parameters, which the sawtooth realizes with k ⋆ = 2L−1 at architectural complexity O(L).
Estimators and sample complexity. We observe (θi , yi )ni=1 with θi uniform on S1 and yi = f ⋆ (θi ) + ξi . ˆKRR = The lazy estimator is PNTK kernel ridge regression, f arg minf ∈HΘ(D) n1 i (yi − f (θi ))2 + λ∥f ∥2H (D) , the t → Θ ∞ (λ → 0) limit of lazy-trained networks (Jacot et al. 2018); the rich estimator is ERM over CL,w,R . We write nF (f ⋆ ; ϵ) for the smallest n at which some estimator over class F achieves E∥fˆ − f ⋆ ∥2L2 ≤ ϵ2 , and compare nKRR to the minimax floor nminimax (CL,w,R ; ϵ).
Theorem 4 (Minimax rate, tight up to a depth factor). Let R⋆n := inf fˆn supf ⋆ ∈CL,w,R E∥fˆn − f ⋆ ∥2L2 be the minimax risk in the Gaussian model with σ 2 ≍ R2 . There are absolute constants c5 , c6 > 0 such that, for n ≥ L2 w2 log(Lw),
Two background facts. Our analysis uses two known characterizations, which we record without claiming as new. First (lazy lens), (1) implies the NTK-RKHS norm equals the Sobolev norm up to depth scaling:
Proof. The two bounds use different complexity measures of the class; the residual factor of L is exactly their mismatch (Remark 5). Upper bound (VC ⇒ Rademacher). Each f ∈ CL,w,R is piecewise linear with W = O(Lw2 ) parameters, so VCdim = O(W L log W ) = O(L2 w2 log(Lw)) (Bartlett et al. 2019, Thm. 6) (the norm constraint only shrinks it). Sauer–Shelah/Massart then bound the Rademacher complexp ity of the [−R, R]-valued class by Õ(R L2 w2 /n), and Talagrand contraction (squared loss is 4R-Lipschitz) lifts this to the loss class. The standard VC excess-risk bound in the σ 2 -noisy model gives R⋆n ≤ Õ(σ 2 L2 w2 /n); with σ 2 ≍ R2 , the upper bound follows. Lower bound (Fano over a parameter packing). Perturb (j) a reference f0 ∈ CL,w,R/2 at generic θ0 ∈ RW by θz = √ (j) θ0 + δ(2z (j) − 1), z ∈ {0, 1}W . For δ = cϵ/ W , local biLipschitzness gives ∥fz − fz′ ∥2L2 ≍ δ 2 dH (z, z ′ ) with every fz ∈ CL,w,R . Varshamov–Gilbert extracts Z ⊂ {0, 1}W of size 2Ω(W ) with pairwise Hamming distance ≥ W/8, so log |Z| = Ω(W ) = Ω(Lw2 ) and pairwise separation ≍ ϵ. For Gaussian observations KL(Pz ∥Pz′ ) = 2σn2 ∥fz −fz′ ∥2L2 , so I(z; y) ≤ Cnϵ2 /σ 2 . Fano then forces error probability ≥ 21 once ϵ2 = σ 2 log |Z|/(4Cn) ≍ σ 2 Lw2 /n, whence R⋆n ≥ Ω(σ 2 Lw2 /n) = Ω(Lw2 R2 /n) at σ 2 ≍ R2 .
Proposition 3 (NTK-RKHS ≍ Sobolev; Bietti and Mairal 2019; Bietti and Bach 2021). For all D ≥ 2 and f ∈ L2 (S1 ), 1 X ˆ 2 2 ∥f ∥2H (D) ≍ |f (k)| k , Θ D2 k
i.e. HΘ(D) is the Sobolev space H 1 (S1 ) with norm rescaled by 1/D. Proof. The Mercer expansion gives ∥f ∥2H (D) = Θ P ˆ 2 k |f (k)| /µk (D) over k with µk (D) > 0 (bias augmentation makes this all k). Substituting the bracket (1) termwise, c1 P c2 P 2 ˆ 2 2 ˆ 2 2 k |f (k)| k ≤ ∥f ∥H (D) ≤ D 2 k |f (k)| k . The D2 Θ
middle and outer sums are, up to the constant 1/D2 and the harmless k = 0 term, the squared Sobolev H 1 norm P 2 ˆ 2 k (1 + k )|f (k)| . Thus the NTK is a smoothness-class kernel: a target with Fourier mass at frequency k ⋆ costs Ω((k ⋆ )2 /D2 ) in NTKRKHS norm. Second (rich lens),P composing the single-layer norm gives ∥gL ∥RBV2deep (L) ≤ ℓ ∥τ ∥RBV2 = 6L, so the sawtooth is cheap architecturally (a compositional-sparsityclass object) despite its 2L−1 oscillations. The exponential gap below is precisely the tension between these two costs on a target where they diverge. Overview of the argument. The exponential gap follows from two bounds that meet at the architecture class. First (this section) we sandwich the minimax floor of CL,w,R , the smallest error any estimator can guarantee, between Ω(Lw2 R2 /n) and Õ(L2 w2 R2 /n), both polynomial in (L, w, R). Second (next section) we lower-bound the NTK’s sample complexity on a frequency-k ⋆ target by Ω((k ⋆ )2 /D2 ), using the Sobolev spectrum of Proposition 3. Dividing the NTK lower bound by the (polynomial) minimax upper bound yields a ratio that
4
The Minimax Rate of Compositional Learning
We consider regression yi = f ⋆ (θi ) + ξi , θi uniform on S1 , with sub-Gaussian noise of variance σ 2 .
c5
Lw2 R2 L2 w2 R2 log(Lwn) ≤ R⋆n ≤ c6 . n n
The rate is thus pinned down up to a single factor of L.
Remark 5 (The factor-L gap). The lower bound reflects the W = O(Lw2 ) free parameters; the upper bound’s extra L is the depth factor in the VC bound. Neither side closes with current tools: the VC lower bound Ω(L2 w2 ) uses bitextraction weights that grow with depth and fall outside the norm ball, while a matching Lw2 upper bound would need a depth-linear Rademacher bound for RBV2deep (L) under a sum-of-norms constraint. Such a bound is unavailable in current norm-based analyses, which depend on the product of layer norms (Golowich et al. 2018). We conjecture the truth is the depth-linear lower rate. Crucially (next section), the NTK gap divides by the minimax upper bound, so it is unaffected by where in [Lw2 , L2 w2 ] the floor lies.
5
Exponential Sub-Optimality of the NTK
Combining the Sobolev lens (Proposition 3) with the minimax floor yields the gap. Theorem 6 (Sample-complexity gap). Let f ⋆ ∈ CL,w,R have Fourier mass δ-concentrated at k ⋆ : |fˆ⋆ (k ⋆ )|2 ≥ δ∥f ⋆ ∥2L2 /(2π). Then for any D ≥ 2,
L
4L (NTK)
L3
L4
4L /L4
2 4 6 8 12
16 256 4096 6.6×104 1.7×107
8 64 216 512 1728
16 256 1296 4096 2.1×104
1.0 1.0 3.2 16 810
δ (k ⋆ )2 ∥f ⋆ ∥2L2 nKRR (f ⋆ ; ϵ) ≳ . nminimax (f ⋆ ; ϵ) D2 L2 w2 R2 log(·)
Table 1: Sample-complexity scale for the depth-L sawtooth: NTK requirement Ω(4L ) versus the minimax floor (between L3 and L4 ). Comparable for L ≤ 4; exponentially separated for L ≥ 5.
Proof. The idea is a one-line accounting: the NTK pays for the target’s frequency, the architecture class pays for its compositional size, and the gap is the quotient. We make each charge precise, then divide. Step 1: the NTK is charged (k ⋆ )2 . Applying the lower bracket of Proposition 3 to the single frequency k ⋆ ,
Corollary 8 (Sawtooth). For the embedded sawtooth gL and any D ≥ 2,
∥f ⋆ ∥2H (D) ≥ Θ
c1 ˆ⋆ ⋆ 2 ⋆ 2 c1 δ |f (k )| (k ) ≥ (k ⋆ )2 ∥f ⋆ ∥2L2 . D2 2πD2
Step 2: a large RKHS norm forces many samples. For any kernel, a two-point Fano argument (the truth against 0 at RKHS radius R′ ) gives the minimax KRR bound inf fˆ sup∥f ∥H ≤R′ E∥fˆ − f ∥2L2 ≥ CKRR R′2 /n (Caponnetto and De Vito 2007, Thm. 2). Taking R′ = ∥f ⋆ ∥HΘ(D) and Step 1, then setting the risk to ϵ2 , nKRR (f ⋆ ; ϵ) ≥
CKRR c1 δ (k ⋆ )2 ∥f ⋆ ∥2L2 . 2π D2 ϵ2
Step 3: divide by the (polynomial) floor. Theorem 4 bounds the denominator by nminimax ≤ Õ(L2 w2 R2 /ϵ2 ); the quotient is the stated ratio. Because we divide by the minimax upper bound, the ratio is a valid lower bound on the gap, hence insensitive to the factor-L ambiguity of Remark 5. Remark 7 (The dichotomy). Theorem 6 expresses the gap as the ratio of two complexity measures of the same target: its Fourier complexity k ⋆ , which governs NTK regression (via Proposition 3), and its architectural complexity L2 w2 R2 , which governs the minimax upper bound (via Theorem 4). The two are independent quantities, and the gap is exponential exactly when they decouple: high frequency, compact realization. Depth versus dimension. Prior kernel-versus-network gaps (Bach 2017; Ghorbani et al. 2020; Daniely and Malach 2020) are exponential in the input dimension d, exploiting that an isotropic kernel cannot concentrate on a lowdimensional relevant subspace; ours is exponential in depth L at fixed dimension, exploiting that a smoothness-biased kernel cannot cheaply represent the high-frequency content that composition generates. The two axes are orthogonal and in principle compound. Isolating the depth axis is what lets us compare against the minimax floor rather than a dimensiondependent competitor, and is why the univariate setting is the cleanest place to see the mechanism. The sawtooth realizes this decoupling:
nKRR (gL ; ϵ) ≥ D2cϵ2 4L , nminimax (gL ; ϵ) ≤ Õ(L4 /ϵ2 ), so nKRR /nminimax = Ω(4L /(D2 L4 log L)), exponential in L for every fixed D. (The floor is in fact between L3 and L4 by Theorem 4; either way the gap is exponential.) Proof sketch. Apply Theorem 6 with k ⋆ = 2L−1 , δ = 12/π 4 , ∥gL ∥2L2 = 2π/3, giving nKRR = Θ(4L /(D2 ϵ2 )); the floor uses L2 w2 R2 = L2 · 4 · 36L2 = 144L4 . Table 1 makes the scale concrete: the NTK requirement 4L and the floor (between L3 and L4 ) are comparable for L ≤ 4 but diverge explosively after, the NTK needing ∼ 107 times more samples by L = 12. The separation is asymptotic in L, not a small-L artifact. The gap is not generic. If f ⋆ is bandlimited (fˆ⋆ (k) = 0 for |k| > K, K constant) and compositionally realized with L2 w2 R2 = poly(K), then both sample complexities are poly(K). Corollary 9 (No gap for bandlimited targets). Under the above conditions, nKRR (f ⋆ ; ϵ) ≤ O(K 2 /(D2 ϵ2 )) and nminimax ≤ Õ(poly(K)/ϵ2 ). Proof. Bandlimitedness gives K 2 ∥f ⋆ ∥2L2 , so by Proposition
ˆ⋆ (k)|2 k 2 3, ∥f ⋆ ∥2H (D)
P
k |f
≤ ≤
Θ
c2 K 2 ∥f ⋆ ∥2L2 /D2 ; the classical KRR upper bound (Caponnetto and De Vito 2007) gives the NTK side, and Theorem 4 the floor. The gap is therefore a property of the target’s spectral structure relative to its architectural realization, not of kernels versus networks as such. A multivariate companion. The same Fourier-versusarchitecture mechanism applies beyond S1 . On the hypercube {−1, +1}d the Q relevant “frequencies” are the Walsh characters χS (x) = i∈S xi , and the rotation-equivariant ReLU NTK has eigenvalue Θ(d−|S| ) on level-|S| characters (Daniely and Malach 2020). The same kernel-regression lower bound then gives the hypercube analog of Theorem 6.
This furnishes a target on which, unlike the sawtooth, SGD provably succeeds: a two-layer network learns χ[k] in poly(d) · 2O(k) samples by aligning neurons to the relevant coordinates (Glasgow 2023), so the predicted separation is realizable end-to-end (E3 below).
6
Experiments
We validate the three predictions. Throughout, the NTK is the depth-4 bias-augmented kernel from the arc-cosine recursion, solved in closed form by ridge regression with λ = 10−4 (E3) or validation-tuned λ ∈ {10−6 , 10−4 , 10−2 } (E1–E2); the n×n Gram matrix is formed exactly and capped at n ≤ 5000 for memory (for E3 at d=30, k=4 we additionally solve n=104 ). ERM uses two-layer ReLU networks trained full-batch by Adam (learning rate 10−2 , weight decay 10−5 ); for the smooth targets of E2 we use width 2048 with a cosine learning-rate schedule and a final L-BFGS step so that ERM reaches its O(1/w2 ) approximation floor rather than an optimization plateau, and for E3 width 512. Sample sizes sweep n ∈ {50, . . . , 104 } on a log grid; each cell reports the median of three independent runs on a held-out test set of 5000 points. All seeds are fixed and figures are regenerated from saved CSVs; the full protocol, the noiseless/noisy variants, and the reproducibility checklist are in the supplementary material. The code is available here: https: //anonymous.4open.science/r/ntk-suboptimality-B02C/. (E1) NTK spectrum. Diagonalizing the NTK Gram matrix on N = 5000 grid points for depths D ∈ {2, 3, 5, 10}, the four spectra are parallel on log–log axes (Figure 3), confirming the depth-invariant exponent of (1). The fitted slopes in the asymptotic-clean window k ∈ [N/40, N/8] are −1.980, −1.989, −1.989, −1.988 for D = 2, 3, 5, 10, all within 1% of the predicted −2 (deviations at very low k and near the Nyquist frequency are the expected preasymptotic and discretization artifacts of a finite grid). Since the sawtooth’s 4L NTK cost follows from this k −2 decay plus its frequency-2L−1 concentration, this experiment establishes the kernel side of the gap. (E2) No gap on smooth targets. On fk (z) = cos(kπz), k ∈ {1, . . . , 5}, NTK-KRR and a wide (w=2048) two-layer ReLU ERM both converge polynomially with no gap that grows in k (Figure 2); at small n they are indistinguishable (ERM even beats NTK at k=1, e.g. 2.5 × 10−6 vs. 3.4 × 10−5 at n=50), and at large n NTK leads only by a constant-to-polynomial factor (∼ 10−11 vs. ∼ 10−7 at n=5000), consistent with its near-minimax optimality on H 1 -smooth targets (Corollary 9). The wide network is used deliberately so that ERM’s O(1/w2 ) approximation floor lies below the statistical error across the tested range, isolating the statistical comparison from an architecture-imposed ceiling. This experiment is the essential control: it rules out the
10 2
Bandlimited targets cos(k z) on 1 (solid = ERM, dashed = NTK)
10 4 Test L 2 error
Proposition 10 (Hypercube parity gap). For the sparse parQk ity f ⋆ = χ[k] = i=1 xi on {−1, +1}d , NTK-KRR requires nKRR (f ⋆ ; ϵ) ≥ Ω(dk /ϵ2 ), whereas f ⋆ is a depth-⌈log2 k⌉, O(k)-neuron network. The gap is thus exponential in k at fixed sample budget.
10 6 10 8 10 10
k=1, ERM k=2, ERM k=3, ERM
k=4, ERM k=5, ERM
102
Sample size n
103
Figure 2: Bandlimited targets cos(kπz), k ∈ {1, . . . , 5} (solid: ERM; dashed: NTK). Both converge polynomially with no exponential gap; the inter-method gap does not grow with k. The mirror image of the compositional regime (Corollary 9).
alternative explanation that networks simply beat kernels everywhere, and confirms the dichotomy’s prediction that the gap appears only when Fourier and architectural complexity decouple: present for the parity, absent here. (E3a) The sawtooth plateaus at the trivial predictor. Confirming the note of Section 3: although gL ∈ CL,2,6L is exactly width-2 representable, no run recovered it for L ≳ 5. Since the tent map is measure-preserving, gL is uniform with Var = 1/12, and every configuration we tried (depth/width scaling, residual connections, layer normalization, smooth activations, Adam with warmup–cosine schedules, full-batch L-BFGS) plateaued at test loss ≈ 1/12, the constant-mean predictor. This optimization failure is algorithmic, not statistical, so the empirical gap below uses the SGD-learnable parity instead. (E3b) Exponential gap on parity, realized by SGD. We test the gap on the sparse parity of Proposition 10 (d=30, k=4, the setting of Daniely and Malach 2020). Figure 4: NTK-KRR stays at the trivial baseline (L2 ≈ Var = 1) for all tested n, while ERM phase-transitions and reaches ≈ 3 × 10−7 at n=104 , a head-to-head gap of four to six orders of magnitude, realized end-to-end by standard SGD. Table 2 shows the phase transition shifting with d and k exactly as the Ω(dk ) barrier predicts, with ERM reaching nearmachine-precision in every cell while NTK never leaves the baseline.
7
Discussion
The results give a clean, depth-explicit picture: the NTK is the near-optimal estimator for H 1 -smooth targets but exponentially miscalibrated for compositionally sparse, oscillatory ones, and the boundary is exactly whether the target’s Fourier complexity decouples from its architectural complexity. This complements Bietti and Bach’s “deep equals shallow” theorem: adding depth does not enlarge the NTK function class, but it does enlarge the rich-regime class, by granting access to compositionally sparse functions, and our
k
30 30 30 30 50 50
3 3 4 4 3 4
NTK / ERM test L2
n 2000 5000 5000 10000 5000 5000
Sparse parity f (x) =
−3
0.95 / 5.0 × 10 0.76 / 5.0 × 10−5 1.07 / 2.8 × 10−4 1.01 / 3.2 × 10−7 1.02 / 5.6 × 10−3 1.09 / 6.8 × 10−2
NTK eigenvalue decay on 1 (bias-augmented) 100
xi, d = 30
10 1 10 2 10 3 10 4 10 5
Table 2: Sparse-parity sweep (median of 3 runs). NTK-KRR remains at the baseline (≈ 1) throughout, while ERM transitions to near-zero error; the transition point grows with d and k as predicted by Ω(dk ).
4 i=1
100
Test L 2 error
d
10 6
NTK kernel ridge regression 2-layer ReLU ERM (Adam) 103
Sample size n
104
Figure 4: Sparse parity f ⋆ = x1 x2 x3 x4 on {−1, +1}30 . NTK-KRR remains at the baseline (≈ 1) for all tested n (its Ω(dk ) ≈ 8 × 105 requirement); two-layer ReLU ERM phase-transitions and reaches ≤ 10−4 by n = 5000.
10 1
k(D)
10 2
sitional.
10 3 10 4 10 5 10 6
D=2 D=3 D=5
10 7 100
D = 10 k 2 reference fit window [125, 625]
101
102
Eigenvalue rank k
103
Figure 3: NTK eigenvalue decay on S1 for depths D ∈ {2, 3, 5, 10}: parallel log–log spectra with slope ≈ −2, confirming µk (D) ≍ D2 /k 2 (Proposition 3). gap quantifies the statistical price of being confined to the former. We emphasize that the minimax characterization (Theorem 4) is a contribution in its own right: to our knowledge it is the first sample-complexity rate for deep ReLU networks indexed by the architectural parameters (L, w, R) rather than by a target smoothness exponent. The paper’s order is deliberate: we first establish this statistical floor for the architecture class, then obtain NTK sub-optimality as the gap to it. Practical relevance. The witness is stylized but the mechanism is not: many structured targets are “compositionally cheap but spectrally rich” in exactly the sense the gap requires (iterated or hierarchical feature maps, multiplicative or parity-like interactions, periodic signals), and on any such target a fixed-kernel surrogate (the NTK, but equally a Laplace or Gaussian kernel of comparable decay) pays the Fouriercomplexity price while a trained network pays only the architectural one. This is the function-space reason kernelized approximations of deep models degrade on hierarchical tasks. Two takeaways follow: Proposition 3 pins down where the NTK is well-adapted (H 1 -smooth targets), so its failure on compositional ones is intrinsic, not incidental; and Theorem 4 shows architecture-matched learning pays only the polynomial floor, arguing concretely for rich-regime training (or architectural priors) when a problem is believed compo-
Limitations and future work. (i) The function-space results are on S1 ; the multivariate extension to Sd−1 is structurally available through Bietti and Bach (2021, Cor. 3) but needs a separate Fourier-coefficient calculation for a multivariate witness (e.g. via Telgarsky’s affine-projection construction), and would combine the depth and dimension axes. (ii) The minimax rate is tight only up to a factor of L; closing it requires a depth-linear RBV2deep Rademacher bound under the sum-of-layer-norms constraint, which current normbased analyses (depending on the product of layer norms (Golowich et al. 2018)) do not provide (Remark 5). (iii) Our guarantees are statistical, not algorithmic: as E3a shows, a target can lie in the architecture class yet be unreachable by gradient descent (the sawtooth), while another in the same spirit is reachable (the parity). Characterizing which compositional targets are SGD-learnable, the boundary between these two, is the natural next question, and an algorithmiccomplexity counterpart of Theorem 6, addressing whether weight-decay SGD implicitly realizes the variational objective, would settle whether the statistical floor is also the algorithmic one.
8
Conclusion
We established two results for compositional learning. First, a fundamental statistical limit for deep ReLU networks: the minimax rate over the depth-L, width-w class CL,w,R is Θ̃(L2 w2 R2 /n) up to a factor of L, indexed by architectural rather than smoothness parameters; since (L, w, R) are readable from a target architecture, this gives a direct, kernel-free estimate of a compositional problem’s sample complexity. Second, the NTK sits exponentially above this floor exactly when a target’s Fourier complexity decouples from its architectural complexity, as on the depth-L sawtooth (Ω(4L ) samples versus a polynomial floor), matched empirically by no gap on smooth targets and a large separation on parities. Whether a kernel surrogate suffices is thus decided by comparing these two complexities of the target, not by kernels versus networks as such.
Acknowledgements This work was supported by the Office of Science, U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research (ASCR) and the Scientific Discovery through Advanced Computing (SciDAC) FASTMath Institute program, the SciDAC Nuclear Physics partnership titled “Femtoscale Imaging of Nuclei using Exascale Platforms,” and Competitive Portfolios Project on “Energy Efficient Computing: A Holistic Methodology” under Contract No. DE-AC02-06CH11357. Government License (will be removed at publication): The submitted manuscript has been created by UChicago Argonne, LLC, Operator of Argonne National Laboratory (“Argonne"). Argonne, a U.S. Department of Energy Office of Science laboratory, is operated under Contract No. DE-AC0206CH11357. The U.S. Government retains for itself, and others acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan. http://energy.gov/downloads/doe-public-access-plan.
References Z. Allen-Zhu and Y. Li. What Can ResNet Learn Efficiently, Going Beyond Kernels? In NeurIPS, 2019. A. R. Barron. Universal Approximation Bounds for Superpositions of a Sigmoidal Function. IEEE Trans. Information Theory, 39(3):930–945, 1993. Y. Cho and L. K. Saul. Kernel Methods for Deep Learning. In NeurIPS, 2009. S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On Exact Computation with an Infinitely Wide Neural Net. In NeurIPS, 2019. S. Arora, S. S. Du, Z. Li, R. Salakhutdinov, R. Wang, and D. Yu. Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks. In ICLR, 2020. F. Bach. Breaking the Curse of Dimensionality with Convex Neural Networks. Journal of Machine Learning Research, 18(19):1–53, 2017. P. L. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian. Nearlytight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks. Journal of Machine Learning Research, 20(63):1–17, 2019. R. Basri, D. Jacobs, Y. Kasten, and S. Kritchman. The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies. In NeurIPS, 2019. A. Bietti and F. Bach. Deep Equals Shallow for ReLU Networks in Kernel Regimes. In ICLR, 2021. A. Bietti and J. Mairal. On the Inductive Bias of Neural Tangent Kernels. In NeurIPS, 2019. A. Caponnetto and E. De Vito. Optimal Rates for the Regularized Least-Squares Algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007. T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006. A. Daniely and E. Malach. Learning Parities with Neural Networks. In NeurIPS, 2020.
S. S. Du, J. D. Lee, H. Li, L. Wang, and X. Zhai. Gradient Descent Finds Global Minima of Deep Neural Networks. In ICML, 2019. R. Eldan and O. Shamir. The Power of Depth for Feedforward Neural Networks. In COLT, 2016. M. Geiger, A. Jacot, S. Spigler, F. Gabriel, L. Sagun, S. d’Ascoli, G. Biroli, C. Hongler, and M. Wyart. Scaling Description of Generalization with Number of Parameters in Deep Learning. J. Stat. Mech., 2020(2):023401, 2020. B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. When Do Neural Networks Outperform Kernel Methods? In NeurIPS, 2020. A. Jacot, F. Gabriel, and C. Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In NeurIPS, 2018. A. Kumar, R. Parhi, and M. Belkin. A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis. In COLT, 2025. J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. SohlDickstein, and J. Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. In NeurIPS, 2019. M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, 2nd edition, 2018. G. Ongie, R. Willett, D. Soudry, and N. Srebro. A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case. In ICLR, 2020. R. Parhi and R. D. Nowak. Banach Space Representer Theorems for Neural Networks and Ridge Splines. Journal of Machine Learning Research, 22(43):1–40, 2021. R. Parhi and R. D. Nowak. What Kinds of Functions Do Deep Neural Networks Learn? Insights from Variational Spline Theory. SIAM J. Math. Data Sci., 4(2):464–489, 2022. R. Parhi and R. D. Nowak. Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks. IEEE Trans. Information Theory, 69(2):1125–1140, 2023. P. Savarese, I. Evron, D. Soudry, and N. Srebro. How do Infinite Width Bounded Norm Networks Look in Function Space? In COLT, 2019. J. Schmidt-Hieber. Nonparametric Regression Using Deep Neural Networks with ReLU Activation Function. Annals of Statistics, 48(4):1875–1897, 2020. S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. E. M. Stein and R. Shakarchi. Fourier Analysis: An Introduction. Princeton University Press, 2003. T. Suzuki. Adaptivity of Deep ReLU Network for Learning in Besov and Mixed Smooth Besov Spaces: Optimal Rate and Curse of Dimensionality. In ICLR, 2019. M. Telgarsky. Benefits of Depth in Neural Networks. In COLT, 2016. A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009.
Y. Yang and A. Barron. Information-Theoretic Determination of Minimax Rates of Convergence. Annals of Statistics, 27(5):1564–1599, 1999. O. Shamir. Distribution-Specific Hardness of Learning Neural Networks. Journal of Machine Learning Research, 19(32):1–29, 2018. E. Malach, G. Yehudai, S. Shalev-Shwartz, and O. Shamir. The Connection Between Approximation, Depth Separation and Learnability in Neural Networks. Conference on Learning Theory (COLT), 2021. N. Golowich, A. Rakhlin, and O. Shamir. Size-Independent Sample Complexity of Neural Networks. In Conference on Learning Theory (COLT), 2018. M. Glasgow. SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR Problem. International Conference on Learning Representations (ICLR), 2024 (preprint 2023). B. L. Edelman, S. Goel, S. Kakade, E. Malach, and C. Zhang. Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck. Advances in Neural Information Processing Systems, 36, 2023. A. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and R. Basri. On the Similarity between the Laplace and Neural Tangent Kernels. Advances in Neural Information Processing Systems, 33, 2020. L. Chen and S. Xu. Deep Neural Tangent Kernel and Laplace Kernel Share the Same RKHS. In International Conference on Learning Representations (ICLR), 2021. F. Cagnetta, L. Petrini, U. M. Tomasini, A. Favero, and M. Wyart. How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model. Physical Review X, 14:031001, 2024. F. Cagnetta, A. Favero, and M. Wyart. What Can Be Learnt With Wide Convolutional Neural Networks? In International Conference on Machine Learning (ICML), 2023. Y. Yang and D.-X. Zhou. Nonparametric Regression Using Over-parameterized Shallow ReLU Neural Networks. Journal of Machine Learning Research, 25, 2024.
Supplementary Material: A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel This supplement gives the full proofs underlying the outlines in the main paper, in the order the results appear: the NTK–Sobolev spectral characterization (Supplementary Section 2), the minimax rate (Supplementary Section 3), the sample-complexity gap and the sawtooth instantiation (Supplementary Section 4), the hypercube-parity companion (Supplementary Section 5), and full experimental details (Supplementary Section 6). Numbering of results matches the main text where applicable, and Table 3 collects the notation. Throughout, c, C, c1 , c2 , . . . denote absolute positive constants whose value may change between displays, D is the depth of the NTK, and L the depth of the target’s compositional realization.
1
Notation
Symbol
Meaning
S1 fˆ(k) H 1 (S1 ) σR κ0 , κ 1 Σ(ℓ) , Θ(ℓ) Θ(D) µk (D) HΘ(D) ∥ · ∥RBV2 RBV2deep (L) CL,w,R W D L, w, R gL , τ k⋆ δ VCdim R̂n R⋆n nKRR , nminimax σ2 χS ≍, ≲ Õ, Θ̃, Ω̃
unit circle, identified with [0, 2π) k-th Fourier coefficient of f first-order Sobolev space ReLU activation max{0, ·} arc-cosine kernels NNGP / NTK recursion at layer ℓ bias-augmented depth-D NTK k-th NTK eigenvalue NTK reproducing-kernel Hilbert space second-order variation norm (one layer) deep variation space, depth L depth-L, width-w class, norm ≤ R parameter count, O(Lw2 ) depth of the NTK (the kernel) target depth, width, variation-norm bound Telgarsky sawtooth, tent map dominant frequency of the target Fourier-mass concentration fraction Vapnik–Chervonenkis dimension empirical Rademacher complexity minimax L2 risk over CL,w,R samples to reach L2 -error ϵ observation-noiseQvariance Walsh character i∈S xi (hypercube) (in)equality up to absolute constants asymptotics up to polylog factors
Table 3: Notation used in the main paper and this supplement.
2
The NTK Spectrum and the Sobolev Equivalence
We prove the eigenvalue bracket µk (D) ≍ D2 /k 2 (main eq. (1)) and the resulting norm equivalence (main Proposition 3). The argument has four steps: Mercer diagonalization,
endpoint-regularity control of the decay at depth D ≥ 3, the shallow case D = 2 with removal of parity gaps, and substitution into the RKHS norm. Step 1: Mercer diagonalization of a stationary kernel. By construction Θ(D) (x, y) = gD (⟨x, y⟩) is a dot-product kernel, and on S1 we have ⟨x, y⟩ = cos(θx − θy ), so Θ(D) depends only on θx − θy : it is a stationary (convolution) kernel on the circle, Θ(D) (x, y) = g̃D (θx − θy ) with g̃D (φ) = gD (cos φ). Convolution operators on the compact abelian group S1 are simultaneously diagonalized by the characters {eikθ }k∈Z , and the eigenvalues are the Fourier coefficients of the profile: Z 2π 1 µk (D) = g̃D (φ) e−ikφ dφ. 2π 0 The kernel is positive semidefinite (it is the pointwise limit of the finite-width Gram kernels ⟨∇θ f (x), ∇θ f (y)⟩, each PSD), so by Bochner’s theorem on S1 all µk (D) ≥ 0. Mercer’s theorem (continuity and PSD-ness on the compact S1 ) then yields the expansion Θ(D) (x, y) = P ik(θx −θy ) , and the associated RKHS norm is k µk (D)e ∥f ∥2H (D) =
X
Θ
k: µk (D)>0
|fˆ(k)|2 . µk (D)
(2)
Step 2: eigenvalue decay at depth D ≥ 3. The asymptotic decay of µk (D) is governed by the regularity of the kernel profile at the diagonal endpoint u = 1. We use the following fact (Bietti and Bach 2021, Thm. 1): if a dot-product kernel κ : [−1, 1] → R is C ∞ on (−1, 1) and admits, as t → 0+ , κ(1 − t) = p(t) + c+ tν + o(tν ), with p a polynomial of degree < ν and ν > 0 non-integer, then the eigenvalues of its integral operator on Sd−1 satisfy µk ≍ k −d−2ν+1 . The arc-cosine √ kernels admit such expansions: using arccos(1 − t) = 2t (1 + O(t)), √
κ0 (1 − t) = 1 − π2 t1/2 + O(t3/2 ),
√ κ1 (1 − t) = 1 − t + 23π2 t3/2 + O(t5/2 ),
(ν = 12 ), (ν = 32 ).
(D)
The deep profile κNTK , assembled by the recursion of the main paper, inherits the strongest (smallest-ν) endpoint singularity, namely the ν = 12 term carried by κ0 : composition is smooth away from the endpoint and cannot cancel the leading t1/2 contribution at the diagonal. Hence with d = 2 and ν = 21 , µk (D) ≍ k −d−2ν+1 = k −2 , and the depth-dependent prefactor scales as C(d, L) ≍ D2 (Bietti and Bach 2021, Cor. 3). Thus there are absolute c, C > 0 with c D2 /k 2 ≤ µk (D) ≤ C D2 /k 2 for all D ≥ 3, k ̸= 0.
Intuition. On the circle, µk is the k-th Fourier coefficient of φ 7→ g̃D (φ); near φ = 0, t = 1 − cos φ ≍ φ2 /2, so a t1/2 endpoint singularity becomes a |φ| kink in g̃D , and the Fourier coefficients of a kink decay as k −2 . The −2 exponent is exactly the order of that kink. Step 3: depth D = 2 and parity gaps. The shallow NTK on Sd−1 has the explicit spherical-harmonic decomposition of Bietti and Mairal (2019, Prop. 5), with the same k −d rate but a different constant. The vanilla kernel has parity gaps (µk = 0 for one parity of k), an artifact of the ReLU’s parity under the harmonic decomposition. The bias-augmented (D) (D) kernel Θ(D) = (1 + u)κ0 + κ1 adds a rank-one term (Basri et al. 2019) that fills the gaps while preserving the diagonal-endpoint regularity, hence the k −2 rate. The bracket µk (D) ≍ D2 /k 2 therefore holds uniformly for all D ≥ 2 and k ̸= 0. Step 4: the Sobolev norm. Substituting the bracket into (2) termwise, c1 X ˆ 2 2 c2 X ˆ 2 2 |f (k)| k ≤ ∥f ∥2H (D) ≤ 2 |f (k)| k , 2 Θ D D k
k
with c1 = 1/C, c2 = 1/c. The right-hand side is, up P to the k = 0 term, the squared Sobolev H 1 (S1 ) norm k (1 + k 2 )|fˆ(k)|2 . Hence HΘ(D) = H 1 (S1 ) as sets, with norms equivalent up to the depth factor 1/D, proving Proposition 3 of the main paper. □ Remark 11. The composition-preserves-the-leadingsingularity claim in Step 2 is used as stated by Bietti and Bach (2021); a self-contained proof that the deep recursion does not raise the endpoint exponent above 12 is a natural auxiliary lemma we omit for space, as the bracket is in any case established for all D ≥ 2 via Steps 2–3.
3
The Minimax Rate
We restate and fully prove the main minimax theorem. Theorem 4 (Minimax rate, tight up to a depth factor; restated). Let R⋆n = inf fˆn supf ⋆ ∈CL,w,R E∥fˆn − f ⋆ ∥2L2 in the Gaussian model with noise variance σ 2 ≍ R2 . For n ≥ L2 w2 log(Lw), c5
L2 w2 R2 log(Lwn) Lw2 R2 ≤ R⋆n ≤ c6 . n n
The lower and upper bounds differ by a single factor of L; whether the rate is Θ(Lw2 R2 /n) or Θ(L2 w2 R2 /n) is left open (see the remark below).
3.1
Upper bound
Step U1 (VC-dimension). Every f ∈ CL,w,R ⊂ FL,w is piecewise linear with W = O(Lw2 ) real parameters (each of the L layers has O(w2 ) weights). By the sharp piecewiselinear bound (Bartlett et al. 2019, Thm. 6), a ReLU network with W parameters and L layers has VCdim = O(W L log W ). Substituting W = O(Lw2 ), VCdim(FL,w ) = O L2 w2 log(Lw) .
The norm constraint ∥f ∥RBV2deep (L) ≤ R defines a subset, which only decreases the VC-dimension; write V := VCdim(CL,w,R ) ≤ O(L2 w2 log(Lw)). Step U2 (Rademacher complexity). For a class of [−R, R]valued functions of VC-dimension V , the Sauer–Shelah lemma with Massart’s finite-class bound (Mohri et al. 2018) gives empirical Rademacher complexity q q 2 2 n R̂n (CL,w,R ) ≤ c R V log = Õ R L nw . n Step U3 (loss class). The squared loss ℓ(y, ŷ) = (y − ŷ)2 is 4R-Lipschitz in ŷ on [−R, R] for |y| ≤ R. Talagrand’s contraction pprinciple gives R̂n (ℓ◦CL,w,R ) ≤ 4R R̂n (CL,w,R ) = Õ(R2 L2 w2 /n). Step U4 (excess risk). In the σ 2 -noisy model, the standard uniform-deviation excess-risk bound for a VC class of range R gives, in expectation, (σ 2 + R2 ) V σ 2 L2 w2 R⋆n ≤ Õ = Õ , n n using σ 2 ≍ R2 and V = Õ(L2 w2 ). (In the noiseless realizable case the fast-rate ERM bound (Shalev-Shwartz and Ben-David 2014, Thm. 6.7) gives the same R2 V /n scaling.) With σ 2 ≍ R2 this is the claimed upper bound.
3.2
Lower bound
Step L1 (local packing). Fix a reference network f0 ∈ CL,w,R/2 whose parameter vector θ0 ∈ RW is generic, i.e. the parameter-to-function map Φ : θ 7→ fθ is locally bi-Lipschitz at θ0 (true for all but a measure-zero set of architectures, since each layer is locally Lipschitz and locally injective in its weights away from degeneracies). For z ∈ {0, 1}W set (j)
θz(j) = θ0 + δ (2z (j) − 1), j = 1, . . . , W, √ with δ = c ϵ/ W chosen small enough to stay in the biLipschitz neighborhood. Then ∥fz − fz′ ∥2L2 ≍ δ 2 dH (z, z ′ ), and, for R large enough relative to ∥f0 ∥, every fz ∈ CL,w,R . Step L2 (Varshamov–Gilbert). By the Varshamov–Gilbert bound (Tsybakov 2009, Lem. 2.9), as used in the Yang– Barron minimax framework (Yang and Barron 1999), there is Z ⊂ {0, 1}W with |Z| ≥ 2W/8 and dH (z, z ′ ) ≥ W/8 for distinct z, z ′ ∈ Z. Hence log |Z| = Ω(W ) = Ω(Lw2 ), and pairwise c′ δ 2 W ≤ ∥fz − fz′ ∥2L2 ≤ C ′ δ 2 W ≍ ϵ2 . Step L3 (Fano). Under Pz (observations yi = fz (θi ) + ξi , ξi ∼ N (0, σ 2 )), Cnϵ2 n ∥fz − fz′ ∥2L2 ≤ , 2 2σ σ2 so the mutual information under a uniform prior on Z satisfies I(z; y) ≤ maxz,z′ KL(Pz ∥Pz′ ) ≤ Cnϵ2 /σ 2 . Fano’s inequality (Cover and Thomas 2006, Thm. 2.10.1) gives, for any estimator ẑ, KL(Pz ∥Pz′ ) =
Pr(ẑ ̸= z) ≥ 1 −
Cnϵ2 /σ 2 + log 2 . log |Z|
Choosing ϵ2 = σ 2 log |Z|/(4Cn) ≍ σ 2 Lw2 /n makes the right-hand side ≥ 12 . Step L4 (risk and R-scaling). A standard reduction (separation ≥ ϵ between packing elements) converts the ≥ 21 testing error into R⋆n ≥ ϵ2 /16 = Ω(σ 2 Lw2 /n). The worst case over targets with ∥f ∥∞ ≤ R is attained at σ 2 ≍ R2 (the standard signal-to-noise normalization), giv□ ing R⋆n ≥ Ω(Lw2 R2 /n). Remark 5 (On the factor-L gap). The upper bound uses VCdim = O(L2 w2 log), which carries an extra L relative to the W = O(Lw2 ) free parameters the lower bound exploits. Closing the gap in either direction is open: the VC lower bound Ω(L2 w2 ) (Bartlett et al. 2019) is achieved only by bit-extraction networks whose weights grow with depth, hence lie outside the norm ball CL,w,R ; a matching Lw2 upper bound would require a depth-linear Rademacher bound for RBV2deep (L) under the sum-of-layer-norms constraint, which current norm-based analyses (depending on the product of layer norms, e.g. Golowich et al. 2018) do not provide. We conjecture the truth is the depth-linear lower rate.
4
The Sample-Complexity Gap and the Sawtooth
Theorem 6 (Gap, restated). If f ⋆ ∈ CL,w,R has |fˆ⋆ (k ⋆ )|2 ≥ δ∥f ⋆ ∥2L2 /(2π), then for any D ≥ 2, δ (k ⋆ )2 ∥f ⋆ ∥2L2 nKRR (f ⋆ ; ϵ) . ≳ nminimax (f ⋆ ; ϵ) D2 L2 w2 R2 log(·) Proof. Step G1 (NTK norm from one frequency). By the lower bracket of Supplementary Section 2 applied to the single term k ⋆ , |fˆ⋆ (k ⋆ )|2 c1 ∥f ⋆ ∥2H (D) ≥ ≥ 2 |fˆ⋆ (k ⋆ )|2 (k ⋆ )2 Θ µk⋆ (D) D c1 δ (k ⋆ )2 ∥f ⋆ ∥2L2 . ≥ 2πD2 Step G2 (KRR minimax lower bound). For any kernel K with RKHS H, observations yi = f ⋆ (θi ) + ξi with subGaussian noise of variance σ 2 , the minimax L2 risk over the RKHS-ball of radius R′ obeys inf
sup
fˆ ∥f ∥H ≤R′
E∥fˆ − f ∥2L2 ≥ CKRR
R′2 n
for a constant CKRR depending only on the noise and the kernel spectrum (Caponnetto and De Vito 2007, Thm. 2). The bound follows from a two-point Fano argument: take the hypotheses {0, R′ ϕ} for a unit-norm ϕ ∈ H and balance separation against KL. Step G3 (apply at the target’s norm). Setting R′ = ∥f ⋆ ∥HΘ(D) and using Step G1, inf E∥fˆ − f ⋆ ∥2L2 ≥ fˆ
CKRR c1 δ(k ⋆ )2 ∥f ⋆ ∥2L2 . 2πD2 n
Setting the right side to ϵ2 and solving for n, nKRR (f ⋆ ; ϵ) ≥
CKRR c1 δ(k ⋆ )2 ∥f ⋆ ∥2L2 . 2πD2 ϵ2
Step G4 (divide). Theorem 4 gives nminimax (f ⋆ ; ϵ) ≤ Õ(L2 w2 R2 /ϵ2 ). Dividing yields the stated ratio. Since we divide by the minimax upper bound, the ratio is a valid lower bound on the true gap and is insensitive to the factor-L ambiguity. Lemma 2 (Spectrum of the embedded sawtooth, restated). The even-reflected gL on S1 has gL (θ) = 12 − π42
X j≥1, j odd
cos(j 2L−1 θ) , j2
with |ĝL (2L−1 )| = 2/π 2 , ∥gL ∥2L2 = 2π/3, and δ = 12/π 4 ≈ 0.12. Proof. On [0, 1] theP unit triangle wave has the classical cosine series 21 − π42 j odd j −2 cos(jω), ω ∈ [0, 2π) (Stein and Shakarchi 2003, §1.4). By Telgarsky (2016, Lem. 3.11), gL |[0,1] is the triangle wave compressed to 2L−1 periods; in the variable ω = 2L−1 · (2πz) this replaces ω by 2L−1 θ under θ = πz. Even reflection from [0, 1] to [0, 2] (i.e. to S1 ) cancels all sine terms, leaving the stated cosine series. The dominant coefficient is the j = 1 term, |ĝL (2L−1 )| = 2/π 2 . Parseval gives ∥gL ∥2L2 = 2π( 41 ) + P P −4 π j odd ( π24j 2 )2 = π2 + π6 = 2π = j odd j 3 (using 4 π /96). The single-coefficient concentration fraction, matching the gap theorem’s hypothesis |fˆ(k ⋆ )|2 ≥ δ∥f ∥2L2 /(2π), is δ = |ĝL (2L−1 )|2 /(∥gL ∥2L2 /(2π)) = (4/π 4 )/(1/3) = 12/π 4 ≈ 0.12. Corollary 8 (Sawtooth, restated). For gL and any D ≥ 2: nKRR (gL ; ϵ) ≥ c 4L /(D2 ϵ2 ) and nminimax (gL ; ϵ) ≤ Õ(L4 /ϵ2 ), so the ratio is Ω(4L /(D2 L4 log L)). Proof. Apply Theorem 6 with k ⋆ = 2L−1 , δ = 12/π 4 , ∥gL ∥2L2 = 2π/3 (Lemma 2); the NTK side is Θ(4L /(D2 ϵ2 )) since (k ⋆ )2 = 4L−1 . For the floor, gL ∈ CL,2,6L (each ∥τ ∥RBV2 = 6, L layers), so L2 w2 R2 = L2 · 4 · (6L)2 = 144L4 , and Theorem 4’s upper bound gives Õ(L4 /ϵ2 ).
5
The Hypercube-Parity Companion
Proposition 10 (Hypercube parity gap, restated). For Qk d the sparse parity f ⋆ = i=1 xi on {−1, +1} under the uniform measure, NTK-KRR requires nKRR (f ⋆ ; ϵ) ≥ Ω(dk /ϵ2 ), while f ⋆ is realized by a depth-⌈log2 k⌉, O(k)neuron ReLU network. Proof. On the hypercube with Q the uniform measure, the Walsh characters {χS (x) = i∈S xi }S⊆[d] are orthonormal eigenfunctions of every dot-product (hence rotationequivariant) kernel, including the ReLU NTK. The eigenvalue on level-|S| characters is Θ(d−|S| ) (Daniely and Malach 2020, Thm. 4); in particular µ[k] = Θ(d−k ). Since f ⋆ = χ[k] , its NTK-RKHS norm is ∥f ⋆ ∥2H = 1/µ[k] = Θ(dk ). The KRR minimax lower bound (Step G2) with R′ = ∥f ⋆ ∥H gives nKRR ≥ Ω(∥f ⋆ ∥2H /ϵ2 ) = Ω(dk /ϵ2 ).
For realizability, a product of k inputs is computed by a balanced binary tree of two-input products, each implementable by an O(1)-neuron ReLU block via ab = 1 2 2 4 ((a + b) − (a − b) ) and a piecewise-linear approximation of the square on the bounded domain; the tree has depth ⌈log2 k⌉ and O(k) neurons. A complementary upper bound shows the gap is realizable: SGD on a two-layer ReLU network of width poly(d) 2O(k) learns χ[k] in poly(d) 2O(k) samples by aligning first-layer neurons to the relevant coordinates (Glasgow 2023; Edelman et al. 2023); this is the feature-learning step the lazy/NTK regime forgoes.
6
Experimental Details
Compute and code. All experiments ran on a single NVIDIA H200 GPU. The NTK is computed in closed form from the arc-cosine recursion; networks are trained in PyTorch. All random seeds are fixed and derived deterministically per cell; figures are regenerated from saved CSV files, so reported values are exactly reproducible. Code and scripts accompany the submission. E1 (NTK spectrum). We form the N × N NTK Gram matrix on a uniform grid of N = 5000 points on S1 for depths D ∈ {2, 3, 5, 10} and diagonalize it. Slopes are leastsquares fits of log µk on log k over the asymptotic-clean window k ∈ [N/40, N/8] = [125, 625], chosen to avoid low-k preasymptotic curvature and near-Nyquist discretization bias. Fitted slopes: −1.980, −1.989, −1.989, −1.988 for D = 2, 3, 5, 10. E2 (bandlimited, no gap). Targets fk (z) = cos(kπz), k ∈ {1, . . . , 5}, noiseless. NTK-KRR uses depth D = 4 with λ validation-selected from {10−6 , 10−4 , 10−2 } on an 80/20 split; the Gram matrix is capped at n ≤ 5000. ERM uses a two-layer ReLU network of width 2048, trained full-batch with Adam (lr 3×10−3 , weight decay 10−5 , cosine schedule, 5000 epochs) followed by an L-BFGS finetune (strong-Wolfe, up to 1000 iters); best of two seeds. The wide network and second-order finetune ensure ERM reaches its O(1/w2 ) approximation floor rather than an optimization plateau. Sample sizes n ∈ {50, 100, 200, 500, 1000, 2000, 5000}, three runs per cell, test grid of 5000 points. E3 (sparse parity). Inputs uniform on {−1, +1}d , tarQ get i≤k xi , sweeping d ∈ {30, 50}, k ∈ {3, 4}, n ∈ {200, 500, 1000, 2000, 5000, 10000}, three runs per cell, test set of 5000 fresh draws. NTK: depth-4 arc-cosine √ kernel with inputs normalized to the unit sphere by 1/ d, λ = 10−4 ; Gram matrix formed exactly (capped at n ≤ 5000, except the d=30, k=4 cell where n = 104 is also solved). ERM: twolayer ReLU width 512, Adam (lr 10−2 , weight decay 10−5 , 3000 full-batch epochs), best of three seeds. The reported gap is the ratio of median test errors. E3a (sawtooth optimization failure). For the depth-L sawtooth (L ∈ {2, . . . , 8}), we attempted to fit gL with a wide range of configurations: MLPs and ResMLPs of depth up to
2L and width up to 256, exact Telgarsky initialization, LayerNorm, GELU, Adam with warmup/cosine schedules, and full-batch L-BFGS. For L ≥ 5 every configuration plateaued at test loss ≈ Var(gL ) = 1/12 (constant-mean prediction). This is an optimization, not statistical, failure and is consistent with hardness results for compositional ReLU learning (Malach et al. 2021; Shamir 2018); it motivates the use of the SGD-learnable sparse parity for the empirical gap. Reproducibility checklist. The AAAI reproducibility checklist is submitted as a separate form; all items concerning data generation, hyperparameters, compute, and statistical reporting are covered by the protocols above.