Pith. sign in

REVIEW 4 minor 43 references

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

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The neural tangent kernel is exponentially worse than the best possible estimator whenever a target is compositionally cheap but spectrally rich.

desk verdict Clean depth-explicit NTK-vs-minimax gap on compositional targets, with a new architecture-class rate that is tight up to one L; the exponential claim holds and the residual looseness is honestly flagged. read the letter →

arxiv 2607.06382 v1 pith:AU2E7YK6 submitted 2026-07-07 stat.ML cs.LG

Arkaprabha Ganguli , Emil Constantinescu This is my paper
classification stat.MLcs.LG MSC 68T0762G0846E22
keywords neuraltangentkernelcompositionallearningminimaxratesFouriercomplexityarchitecturaldeepvariationnormsawtoothfunctionsparseparity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Trained neural networks often beat their own neural-tangent-kernel (NTK) limit on hierarchical tasks, but theory has lacked a precise account of when and by how much. This paper supplies one by comparing two complexity measures of the same target function: its Fourier complexity (which governs how hard the NTK finds it) and its architectural complexity (how cheaply a depth-L ReLU network of bounded variation can build it). On the unit circle the authors pin the minimax sample complexity of the architecture class between two rates that differ by only a single factor of depth L. Whenever the two complexities decouple—as they do for the classic iterated sawtooth, which oscillates exponentially often yet has linear architectural cost—the NTK sits exponentially above that floor: it needs order 4^L samples while any good estimator needs only a polynomial in L. Smooth band-limited targets show no such gap, confirming that the separation is a function-space mismatch between the kernel’s smoothness bias and compositional structure, not a generic network-versus-kernel effect.

What carries the argument

The dichotomy between Fourier complexity (Sobolev / NTK-RKHS norm controlled by the k^{-2} eigenvalue decay of the bias-augmented arc-cosine NTK) and architectural complexity (the deep variation norm that places the target inside C_{L,w,R}). The gap ratio is simply the quotient of the two.

What would settle it

Construct a family of targets whose Fourier mass concentrates at frequency exponential in architectural cost, yet for which NTK ridge regression empirically reaches the same polynomial sample complexity as ERM over the architecture class (or prove that no such family exists).

Watch

Extended reading notes

Core claim

The NTK estimator sits exponentially above the minimax floor of the depth-L, width-w, variation-norm-R architecture class precisely when a target’s Fourier mass concentrates at a frequency that grows exponentially with its architectural complexity. For the depth-L sawtooth the NTK requires Ω(4^L) samples while the floor remains polynomial in L.

Load-bearing premise

The upper bound on the minimax floor relies on a VC-dimension estimate that carries an extra factor of depth L relative to the number of free parameters; the true floor might be tighter, though the exponential gap itself survives that ambiguity.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper gives a quantitative function-space account of when and by how much the NTK is sub-optimal for compositional targets. On the unit circle it introduces two complexity measures of a target: Fourier complexity (Sobolev/H1 norm controlling NTK-KRR via the known k^{-2} spectrum of the bias-augmented ReLU NTK) and architectural complexity (deep variation norm of Parhi-Nowak controlling the class C_{L,w,R} of depth-L width-w ReLU networks with total variation bound R). Theorem 4 pins the minimax L2 rate of C_{L,w,R} between Omega(L w^2 R^2 / n) and tilde-O(L^2 w^2 R^2 / n). Theorem 6 and Corollary 8 then show that whenever Fourier and architectural complexities decouple, NTK sample complexity sits exponentially above this floor; the depth-L iterated sawtooth requires Omega(4^L) NTK samples against a polynomial-in-L floor. Complementary results (Corollary 9, Proposition 10) and experiments confirm no gap on bandlimited targets and a large realized gap on sparse parity.

Significance. If correct, the work supplies the first depth-explicit, fixed-dimension separation of NTK from the information-theoretic floor of an architecture class, rather than from a hand-chosen competitor. The comparison is cleanly reduced to a mismatch between two independently defined complexities of the same target, and the residual factor-L ambiguity is openly flagged and does not cancel the exponential. Full proofs appear in the supplement (Mercer + endpoint singularity, VC/Rademacher upper bound, local packing + Fano lower bound, one-line quotient for the gap), the sawtooth spectrum is classical, and the experiments correctly isolate the statistical claim from the known optimization hardness of the sawtooth by using sparse parity. The result is therefore a genuine, usable contribution to the kernel-versus-network literature.

minor comments (4)
  1. [Section 4, Remark 5] Remark 5 and the discussion of the factor-L gap between the Fano lower bound and the VC upper bound could be moved earlier (or flagged already in the abstract/introduction) so that a reader does not first encounter the residual looseness only after Theorem 4.
  2. [Section 6, E2 / Figure 2] Figure 2 caption and the surrounding text should state more explicitly that the wide (w=2048) ERM is deliberately driven to its approximation floor so that the comparison remains statistical rather than optimization-limited.
  3. [Section 3, Lemma 2 and E3a] A short forward pointer from the sawtooth construction (Lemma 2) to the optimization-hardness paragraph in Section 3 would make the later switch to sparse parity feel less abrupt.
  4. [Supplement, Notation / Theorems 6, 8] Notation table in the supplement is helpful; a one-line reminder that D (NTK depth) and L (target depth) are independent would reduce occasional reader confusion in Theorems 6 and Corollary 8.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the exponential gap is a derived ratio of two independently established complexity measures, not a self-definitional or fitted construction.

full rationale

The paper's central claim (Theorem 6 / Corollary 8) obtains the NTK-to-minimax sample-complexity ratio by dividing a standard two-point Fano lower bound on KRR risk (Caponnetto–De Vito) that uses the NTK-RKHS norm, by the VC-based minimax upper bound on the architecture class C_{L,w,R}. The NTK-RKHS norm is identified with a rescaled Sobolev H^1 norm via the known eigenvalue decay µ_k(D) ≍ D²/k² (Bietti–Bach / Bietti–Mairal, Proposition 3); the sawtooth spectrum (Lemma 2) is the classical Fourier series of the dilated triangle wave (Telgarsky construction + Stein–Shakarchi). Architectural membership g_L ∈ C_{L,2,6L} follows from the definition of the deep variation norm (Parhi–Nowak). None of these ingredients is defined in terms of the gap itself, none is fitted to the target claim, and the authors introduce no self-citation of a uniqueness theorem or ansatz that forces the result. The residual factor-L looseness in the minimax rate (Remark 5) is openly acknowledged and does not cancel the exponential 4^L term. Experiments use pre-specified protocols and serve only as validation. The derivation is therefore self-contained against external, independently established results.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The central exponential-gap claim is obtained by dividing a standard RKHS lower bound (from the known NTK-Sobolev equivalence) by a new minimax upper bound on the architecture class. All spectral, VC, and KRR ingredients are imported from the literature; the paper adds the architecture-class rate and the quotient. No free parameters enter the theory. The architecture class itself and the named dichotomy are the main invented organizing devices.

assumptions (5)
  • domain assumption Bias-augmented deep ReLU NTK on S^1 has eigenvalues μ_k(D) ≍ D²/k² for k≠0 (Bietti-Bach 2021, Bietti-Mairal 2019).
    Used to equate NTK-RKHS norm with Sobolev H¹ norm (Proposition 3); load-bearing for the Fourier-complexity charge.
  • standard math VC-dimension of depth-L width-w ReLU networks is O(L² w² log(Lw)) (Bartlett et al. 2019, Thm. 6).
    Supplies the Rademacher/upper bound half of the minimax rate (Theorem 4); introduces the residual factor L.
  • standard math Kernel ridge regression minimax risk over an RKHS ball of radius R' is Ω(R'²/n) (Caponnetto-De Vito 2007).
    Converts the NTK-RKHS norm lower bound into a sample-complexity lower bound (Step G2 of Theorem 6).
  • domain assumption Deep variation space RBV²_deep(L) and its representer theorem (Parhi-Nowak 2022).
    Defines the architectural complexity and the class C_{L,w,R} whose minimax rate is the floor.
  • domain assumption Telgarsky sawtooth g_L = τ∘⋯∘τ is realized by a depth-L width-2 network with RBV norm O(L) and has dominant frequency 2^{L-1} (Telgarsky 2016).
    Supplies the concrete witness that realizes exponential Fourier complexity at linear architectural cost (Lemma 2, Corollary 8).
invented entities (2)
  • Architecture class C_{L,w,R} independent evidence
    purpose: Hypothesis class of depth-L width-w ReLU networks with deep variation norm ≤R and bounded range; its minimax rate is the statistical floor against which NTK is compared.
    Defined in Definition 1; the paper's first contribution is the minimax rate of this class. Independent evidence is the packing/VC arguments themselves plus the fact that the sawtooth and sparse parity lie in it.
  • Fourier complexity vs. architectural complexity dichotomy independent evidence
    purpose: Organizing principle that predicts when the NTK is exponentially suboptimal: the gap is the ratio of the two complexities of the same target.
    Named and used in the abstract, Theorem 6 and Remark 7. Independent evidence comes from the matching experiments (gap present on parity, absent on band-limited targets).

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel." pith.science (2026). https://pith.science/paper/AU2E7YK6

@misc{pith2026260706382,
  author       = {Pith},
  title        = {Pith review of: A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AU2E7YK6}},
  note         = {Machine review of arXiv:2607.06382}
}
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 $\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 $\Omega(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 $\Omega(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.

Figures

Figures reproduced from arXiv: 2607.06382 by the authors.

Figure 1
Figure 1. The Telgarsky sawtooth gL for L = 1, 2, 3. Each added layer doubles the number of oscillations (2 L−1 peaks) while adding only a constant to the variation norm (∥gL∥RBV2 deep ≤ 6L): exponential Fourier complexity at linear architectural cost. single-hidden-layer ReLU network of width ≤ w, total norm ∥f∥RBV2 deep(L) ≤ R, and ∥f∥∞ ≤ R. Any f ∈ CL,w,R has W = O(Lw2 ) parameters; functions act on S 1 via the embedding θ… view at source ↗
Figure 2
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 (Corol￾lary 9). alternative explanation that networks simply beat kernels ev￾erywhere, and confirms the dichotomy’s prediction that the gap appears only when Fourier and architectural complexity decouple… view at source ↗
Figure 4
Figure 4. Sparse parity f ⋆ = x1x2x3x4 on {−1, +1} 30 . NTK-KRR remains at the baseline (≈ 1) for all tested n (its Ω(d k ) ≈ 8 × 105 requirement); two-layer ReLU ERM phase-transitions and reaches ≤ 10−4 by n = 5000. sitional. Limitations and future work. (i) The function-space re￾sults are on S 1 ; the multivariate extension to S d−1 is struc￾turally available through Bietti and Bach (2021, Cor. 3) but needs a separate Fouri… view at source ↗
Figures from the paper (1 more)
Figure 3
Figure 3. Figure 3: NTK eigenvalue decay on S 1 for depths D ∈ {2, 3, 5, 10}: parallel log–log spectra with slope ≈ −2, con￾firming µk(D) ≍ D2/k2 (Proposition 3). gap quantifies the statistical price of being confined to the former. We emphasize that the minimax characterization (Theo￾rem…

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

  1. [1]

    Allen-Zhu and Y

    Z. Allen-Zhu and Y. Li. What Can ResNet Learn Efficiently, Going Beyond Kernels? In NeurIPS, 2019

    work page 2019

  2. [2]

    A. R. Barron. Universal Approximation Bounds for Superpositions of a Sigmoidal Function. IEEE Trans.\ Information Theory, 39(3):930--945, 1993

    work page 1993

  3. [3]

    Cho and L

    Y. Cho and L. K. Saul. Kernel Methods for Deep Learning. In NeurIPS, 2009

    work page 2009

  4. [4]

    Arora, S

    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

    work page 2019

  5. [5]

    Arora, S

    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

    work page 2020

  6. [6]

    F. Bach. Breaking the Curse of Dimensionality with Convex Neural Networks. Journal of Machine Learning Research, 18(19):1--53, 2017

    work page 2017

  7. [7]

    P. L. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks. Journal of Machine Learning Research, 20(63):1--17, 2019

    work page 2019

  8. [8]

    Basri, D

    R. Basri, D. Jacobs, Y. Kasten, and S. Kritchman. The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies. In NeurIPS, 2019

    work page 2019

Show all 43 references
  1. [9]

    Bietti and F

    A. Bietti and F. Bach. Deep Equals Shallow for ReLU Networks in Kernel Regimes. In ICLR, 2021

    2021

  2. [10]

    Bietti and J

    A. Bietti and J. Mairal. On the Inductive Bias of Neural Tangent Kernels. In NeurIPS, 2019

    2019

  3. [11]

    Caponnetto and E

    A. Caponnetto and E. De Vito. Optimal Rates for the Regularized Least-Squares Algorithm. Foundations of Computational Mathematics, 7(3):331--368, 2007

    2007

  4. [12]

    T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006

    2006

  5. [13]

    Daniely and E

    A. Daniely and E. Malach. Learning Parities with Neural Networks. In NeurIPS, 2020

    2020

  6. [14]

    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

    2019

  7. [15]

    Eldan and O

    R. Eldan and O. Shamir. The Power of Depth for Feedforward Neural Networks. In COLT, 2016

    2016

  8. [16]

    Geiger, A

    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

    2020

  9. [17]

    Ghorbani, S

    B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. When Do Neural Networks Outperform Kernel Methods? In NeurIPS, 2020

    2020

  10. [18]

    Jacot, F

    A. Jacot, F. Gabriel, and C. Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In NeurIPS, 2018

    2018

  11. [19]

    Kumar, R

    A. Kumar, R. Parhi, and M. Belkin. A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis. In COLT, 2025

    2025

  12. [20]

    J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. In NeurIPS, 2019

    2019

  13. [21]

    Mohri, A

    M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, 2nd edition, 2018

    2018

  14. [22]

    Ongie, R

    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

    2020

  15. [23]

    Parhi and R

    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

    2021

  16. [24]

    Parhi and R

    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

    2022

  17. [25]

    Parhi and R

    R. Parhi and R. D. Nowak. Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks. IEEE Trans.\ Information Theory, 69(2):1125--1140, 2023

    2023

  18. [26]

    Savarese, I

    P. Savarese, I. Evron, D. Soudry, and N. Srebro. How do Infinite Width Bounded Norm Networks Look in Function Space? In COLT, 2019

    2019

  19. [27]

    Schmidt-Hieber

    J. Schmidt-Hieber. Nonparametric Regression Using Deep Neural Networks with ReLU Activation Function. Annals of Statistics, 48(4):1875--1897, 2020

    2020

  20. [28]

    Shalev-Shwartz and S

    S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014

    2014

  21. [29]

    E. M. Stein and R. Shakarchi. Fourier Analysis: An Introduction. Princeton University Press, 2003

    2003

  22. [30]

    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

    2019

  23. [31]

    Telgarsky

    M. Telgarsky. Benefits of Depth in Neural Networks. In COLT, 2016

    2016

  24. [32]

    A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009

    2009

  25. [33]

    Yang and A

    Y. Yang and A. Barron. Information-Theoretic Determination of Minimax Rates of Convergence. Annals of Statistics, 27(5):1564--1599, 1999

    1999

  26. [34]

    O. Shamir. Distribution-Specific Hardness of Learning Neural Networks. Journal of Machine Learning Research, 19(32):1--29, 2018

    2018

  27. [35]

    Malach, G

    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

    2021

  28. [36]

    Golowich, A

    N. Golowich, A. Rakhlin, and O. Shamir. Size-Independent Sample Complexity of Neural Networks. In Conference on Learning Theory (COLT), 2018

    2018

  29. [37]

    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)

    2024

  30. [38]

    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

    2023

  31. [39]

    Geifman, A

    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

    2020

  32. [40]

    Chen and S

    L. Chen and S. Xu. Deep Neural Tangent Kernel and Laplace Kernel Share the Same RKHS. In International Conference on Learning Representations (ICLR), 2021

    2021

  33. [41]

    Cagnetta, L

    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

    2024

  34. [42]

    Cagnetta, A

    F. Cagnetta, A. Favero, and M. Wyart. What Can Be Learnt With Wide Convolutional Neural Networks? In International Conference on Machine Learning (ICML), 2023

    2023

  35. [43]

    Yang and D.-X

    Y. Yang and D.-X. Zhou. Nonparametric Regression Using Over-parameterized Shallow ReLU Neural Networks. Journal of Machine Learning Research, 25, 2024

    2024

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.