📊 statistics

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

This paper establishes a function-space dichotomy demonstrating that the Neural Tangent Kernel suffers from exponential sub-optimality compared to finite-width neural networks on compositional tasks, a gap driven by the mismatch between the kernel's smoothness bias and the target's architectural complexity rather than a generic kernel-versus-network limitation.

Original authors: Arkaprabha Ganguli, Emil Constantinescu

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arkaprabha Ganguli, Emil Constantinescu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Why "Lazy" Learning Fails at Building Complex Things

Imagine you are trying to teach a computer to recognize patterns. For a long time, researchers have used a tool called the Neural Tangent Kernel (NTK) to predict how well a neural network will learn. Think of the NTK as a "lazy" teacher. This teacher is very good at smoothing out rough edges and learning gentle curves, but they refuse to change their mind or learn new tricks. They just stick to a very rigid, pre-set way of looking at the world.

The paper asks a simple question: When does this "lazy" teacher fail, and why?

The authors discovered that the lazy teacher fails spectacularly when the task involves composition—building something complex by stacking simple layers on top of each other (like a Russian nesting doll or a recipe with many steps). In these cases, a "rich" teacher (a standard neural network that actually learns and changes its weights) is exponentially better than the lazy one.

The Two Ways to Measure Difficulty

To explain this, the authors look at a target function (the pattern you want the computer to learn) through two different lenses:

The "Smoothness" Lens (Fourier Complexity):
Imagine the target is a musical note. If the note is a low, smooth hum, it's easy to describe. If it's a super-fast, jagged squeal that vibrates thousands of times per second, it's "complex" in terms of smoothness.
- The NTK's view: The lazy teacher hates jagged, fast-vibrating sounds. To learn a high-frequency squeal, the NTK needs a massive amount of data (samples) to figure it out. It treats every wiggle as a huge obstacle.
The "Architectural" Lens (Architectural Complexity):
Now, imagine you want to build a machine that makes that same squealing sound.
- The Network's view: A standard neural network is like a master builder. Even if the sound is a crazy, fast squeal, the builder might be able to create it by stacking just a few simple gears (layers) together. The "cost" to build it is low, even if the result looks chaotic.

The Conflict: The paper shows that for certain tasks, the "Smoothness" cost is astronomical, but the "Architectural" cost is tiny. The lazy teacher (NTK) sees the astronomical cost and gives up, while the smart builder (neural network) sees the tiny cost and builds it easily.

The Star Example: The "Sawtooth" Wave

The authors use a specific shape called the Sawtooth to prove their point. Imagine a triangle wave that goes up and down.

Depth 1: One triangle. Easy.
Depth 2: Two triangles inside one.
Depth 10: A wave that zig-zags back and forth thousands of times.

The Catch:

For the Network: You can build this crazy, zig-zagging wave by stacking just 10 simple layers. It's a cheap, efficient construction.
For the NTK: To the lazy teacher, this wave looks like it has a frequency of $2^{10}$ (over 1,000). Because the NTK is biased toward smoothness, it thinks this is incredibly hard.

The Result:
The paper proves that to learn this 10-layer sawtooth:

The Network needs a manageable number of examples (polynomial growth).
The NTK needs a number of examples that grows exponentially (like $4^{10}$ ).
In plain English: By the time the depth is just 12, the lazy teacher would need 10 million times more data than the smart builder to get the same result.

The "Lazy" vs. "Rich" Regime

The paper distinguishes between two ways neural networks learn:

The Lazy Regime (NTK): The network is so wide and trained so gently that its internal settings barely move. It acts like a fixed mathematical formula (a kernel). It's great for smooth, simple things but terrible for complex, layered things.
The Rich Regime (Standard Training): The network actually changes its internal weights. It learns features. This allows it to build complex structures efficiently, even if they look messy.

What the Experiments Showed

The authors didn't just do math; they ran experiments to confirm their theory:

Smooth Targets: When they gave the computer a smooth, simple wave (like a gentle sine wave), the lazy teacher (NTK) and the smart builder performed almost identically. The NTK is fine here.
Complex Targets (Parity): They tested a "sparse parity" problem (a logic puzzle involving multiplying specific numbers together).
- The NTK was stuck at the bottom, guessing randomly, no matter how much data they gave it.
- The Neural Network learned the pattern quickly, beating the NTK by a factor of 10,000 to 1,000,000.

The Takeaway

The paper concludes that the gap between neural networks and kernel methods isn't just about "kernels vs. networks." It's about mismatched tools.

If your problem is smooth and simple, the "lazy" kernel is a great, efficient tool.
If your problem is built from layers of composition (like deep hierarchies or complex logic), the "lazy" tool is the wrong instrument. It sees a mountain of difficulty where a smart builder sees a simple staircase.

The "exponential sub-optimality" mentioned in the title simply means that for these specific types of complex, layered problems, using the lazy kernel approach is not just slightly worse; it is catastrophically inefficient compared to letting the network actually learn.

Technical Summary: A Function-Space Dichotomy for Compositional Learning

Problem Statement
A persistent empirical observation in deep learning is that trained neural networks consistently outperform their Neural Tangent Kernel (NTK) limits on tasks with compositional or hierarchical structure. While existing literature attributes kernel-network gaps largely to the curse of dimensionality (where kernels struggle with low-dimensional projections of high-dimensional inputs), a quantitative account of the gap at fixed input dimension—specifically driven by network depth and compositional structure—has been lacking. This paper addresses the question: On which targets, and by how much, is the NTK sub-optimal, and what specific property of those targets prevents the kernel from exploiting them?

Methodology and Setup
The authors analyze this problem on the unit circle $S^1$ , where the NTK admits a clean Fourier description. They introduce a dichotomy between two complexity measures for a target function $f^*$ :

Fourier Complexity: Controls the cost of learning via the NTK (lazy regime). The NTK Reproducing Kernel Hilbert Space (RKHS) norm is shown to be equivalent (up to a depth-dependent constant) to the Sobolev $H^1$ norm, which penalizes high-frequency oscillations.
Architectural Complexity: Controls the cost of learning via weight-decay training in the "rich" regime. This is measured by the deep variation norm ( $RBV^2_{deep}$ ), which quantifies the size of the smallest depth- $L$ , width- $w$ ReLU network required to construct the target.

The authors define the architecture class $\mathcal{C}_{L,w,R}$ as depth- $L$ , width- $w$ ReLU networks with a bounded deep variation norm $R$ . They compare the sample complexity of the NTK estimator (Kernel Ridge Regression) against the minimax lower bound for this architecture class.

Key Contributions

Minimax Characterization of Deep Architecture Classes:
The paper establishes the minimax $L^2$ rate for the class $\mathcal{C}_{L,w,R}$ . The rate is pinned down between $\Omega(Lw^2R^2/n)$ and $\tilde{O}(L^2w^2R^2/n)$ . This result is tight up to a single factor of $L$ , representing the statistical floor for any estimator on this class. Notably, this rate is indexed by architectural parameters $(L, w, R)$ rather than target smoothness exponents.
Exponential NTK Sub-Optimality:
The authors prove that the NTK estimator sits exponentially above the minimax floor whenever the target's Fourier complexity and architectural complexity decouple. Specifically, for a target with dominant frequency $k^*$ , the NTK requires $\Omega((k^*)^2)$ samples, while the architecture class requires only polynomial resources in its structural parameters.
- The Witness: The depth- $L$ iterated sawtooth function (Telgarsky 2016) serves as the analytical witness. It can be constructed by a width-2, depth- $L$ network with $O(L)$ weights (low architectural complexity) but oscillates $2^{L-1}$ times (exponential Fourier complexity).
- The Gap: For the sawtooth, the NTK requires $\Omega(4^L)$ samples, whereas the minimax floor is polynomial in $L$ (between $L^3$ and $L^4$ ). This yields an exponential separation in sample complexity.
Empirical Validation:
Numerical experiments confirm the theoretical claims across three fronts:
- NTK Spectrum: The eigenvalue decay of the NTK on $S^1$ follows the predicted $k^{-2}$ decay, confirming the "deep equals shallow" phenomenon where depth does not alter the spectral decay rate.
- Smooth Targets: On bandlimited (smooth) targets, the NTK is competitive with or better than wide networks, showing no exponential gap.
- Compositional Targets: On the sparse parity model over the hypercube (a different domain where SGD is known to succeed), a standard two-layer network beats the NTK by four to six orders of magnitude in test error, realizing the predicted separation end-to-end.

Results and Significance
The paper concludes that the performance gap between NTK and trained networks is not a generic "kernel-versus-network" phenomenon but a specific function-space property. The gap arises from a mismatch between the kernel's inherent smoothness bias (favoring low-frequency functions) and the target's compositional structure (which can generate high-frequency oscillations with low architectural cost).

Theoretical Insight: The work provides a precise mechanism for why depth helps: it allows networks to represent high-frequency, oscillatory functions cheaply via composition, a capability the NTK (which behaves like a fixed Sobolev kernel) lacks.
Minimax Floor: The derivation of the minimax rate for the deep variation space is presented as a standalone contribution, offering a direct, kernel-free estimate of sample complexity for compositional problems based on architectural parameters.
Scope: The authors clarify that the gap is not universal; it disappears for smooth, bandlimited targets where Fourier and architectural complexities are aligned. Furthermore, they distinguish between statistical limits and algorithmic feasibility, noting that while the sawtooth is statistically learnable by the architecture class, it is notoriously difficult for gradient descent to optimize, whereas the sparse parity is both statistically and algorithmically learnable.

In summary, the paper argues that the NTK is near-optimal for $H^1$ -smooth targets but exponentially sub-optimal for targets where compositional structure allows for "cheap" high-frequency representations, a regime where rich-regime training is statistically necessary.