Bordelon et al. (2020) — ARXIV-2002.02561
Key takeaways
Derives exact learning curves for kernel regression and NTK-equivalent wide neural networks as a function of the eigenvalue spectrum of the data covariance (or kernel matrix). Shows that when the eigenvalue spectrum decays as a power law λ_k ∝ k^{-β}, the generalization error follows ε(n) ∝ n^{-β/(1+β)} exactly in the large-n limit. Two-layer ReLU networks in the NTK regime have polynomial eigenvalue decay, giving power-law learning curves — not exponential. This is the theoretical justification for why empirical neural network learning curves follow power laws.
- Power-law learning curve from power-law spectrum. If the kernel eigenvalues satisfy λ_k ∝ k^{-β} and the target function has bounded RKHS norm, then: ε_gen(n) = C · n^{-β/(1+β)} + O(n^{-(β+ε)/(1+β)}) The exponent α = β/(1+β) ∈ (0, 1) is a strictly increasing function of β. The constant C depends on the RKHS norm of the target and the noise level. Holds when: β = eigenvalue decay exponent; α = β/(1+β)
- Two-layer ReLU NTK has power-law spectrum. The NTK of a two-layer ReLU network on S^{d-1} has eigenvalues λ_k ∝ k^{-(d+1)/d}. This gives α = (d+1)/(2d+1). For d=1: α = 2/3. For d → ∞: α → 1/2. Power law spectra → power law learning curves (not exponential). Holds when: d = input dimension; ReLU activation
- Bias-variance decomposition in power-law regime. Generalization error decomposes as: ε(n) = bias²(n) + variance(n) bias²(n) ∝ n^{-α} variance(n) ∝ n^{-α} (same exponent, different constant) Both terms decay at the same rate, so their ratio is asymptotically constant. The learning curve exponent is the same for both noise-free and noisy targets. Holds when: Optimal ridge regularization parameter
- Unrealizable case: irreducible floor. If the target function has components outside the RKHS (unrealizable), ε(n) → ε_∞ > 0 as n → ∞. The floor ε_∞ is the squared projection of the target onto the complement of the RKHS. In the realizable case ε_∞ = 0. Holds when: General RKHS setting
What the evidence does not cover
- NTK regime only (infinite width, lazy training); feature learning (Saad- Solla regime) requires different analysis.
- Asymptotic (n → ∞); finite-sample corrections may be large.
- Requires knowledge of kernel eigenspectrum; hard to measure for real datasets.
- Does not cover training dynamics explicitly — only generalization vs n, not vs steps t.
- Minibatch SGD introduces additional noise; exact results are for full- batch ridge regression.
Standing in the anthology
Read — the reading is NOTE-094. Arrived in the imported batch, which brought in the scaling-law line.