Ronen Basri, David Jacobs, Yoni Kasten and Shira Kritchman (2019), NeurIPS 2019 — ARXIV-1906.00425
Key takeaways
- With uniform data on S^d, the expected Gram matrix H∞ of a wide two-layer ReLU network is a convolution on the sphere (Theorem 1). Its eigenvectors are therefore Fourier modes on S¹ and spherical harmonics on S^d (via Funk–Hecke, Theorem 3). Gradient descent’s residual decays along each eigenvector as (1 − ηλ_i)^t (Eq. 5, from Arora et al.), so the eigenvalue per frequency is the learning rate per frequency.
- Without a bias term, every odd frequency k ≥ 3 has eigenvalue exactly zero (Eq. 12 on S¹; Theorem 4 on S^d). Each unit’s output max(wᵀx, 0) has no odd harmonic above degree 1 (Theorem 2), so the bias-free network cannot even represent cos 3θ. On a finite sample those directions appear as the smallest eigenvalues of H∞ (Fig. 4), and fitting them means interpolating the sample with even frequencies that oscillate wildly between the points (Fig. 3). A zero-initialised bias gives the kernel (xᵀx′ + 1)(π − arccos xᵀx′)/4π, which passes every frequency: 1/(π²k²) on odd k ≥ 3 and (k²+1)/(π²(k²−1)²) on even k ≥ 2 (Eq. 13).
- The predicted convergence time is t_k ≳ −log(δ + ε)/(ηλ_k), quadratic in k on S¹, and measured exponents agree: k^1.93 with bias, k^1.94 for a 5-layer net, k^2.11 for a 10-layer residual net (Fig. 6). On S² the prediction is about k³, measured as k^2.87 and k^3.13 (Fig. 7). The generalisation bound for a band-limited target, √(2yᵀ(H̄∞)⁻¹y/n) ≈ √(2π Σ α_k²k²/n) (Eq. 14), grows linearly in frequency for a pure sine.
Standing in the record
Filed on 2026-10-03 at the owner’s request, with Cao et al.’s eigendirection convergence theorem (LIT-624) and Bietti and Bach’s general decay theorem for deep NTKs (LIT-608). The owner listed the three beside work on Fisher-spectrum block structure, Papyan’s spectra and model comparison by evidence, which are being filed in parallel.
It is the most concrete of the three: explicit eigenvalues, one frequency at a time, and an exact null space. Bietti and Bach (LIT-608) extend it. They derive its decays from a general theorem about endpoint regularity, take its zero-initialised bias as the standard way to remove the parity constraint, and show that depth does not change the exponent, which this paper observed only in its deep-network experiments. Cao et al. (LIT-624) independently state the same odd-degree null space as part of their Theorem 4.3.
Two things in it bear on the owner’s line of inquiry, and both are my reading, not the paper’s claims. First, the bias-free kernel’s odd frequencies are a structural zero block: an architectural choice deletes a whole family of eigendirections, and a sample-level spectrum shows them only as small, misleading eigenvalues. A threshold applied to the finite-sample spectrum would remove them for the right reason without knowing it. Second, the quadratic form yᵀ(H∞)⁻¹y that governs the bound in Eq. 14 is the same quadratic form that sets the data-fit term of a Gaussian-process log evidence under the kernel H∞. So the frequency weighting k² in Eq. 14 is the Occam weighting that kernel would apply in a Bayesian model comparison. NOTE-481 sets this out.
The discrete analogue is in the record as O’Donnell (LIT-346), where the operators natural to the hypercube are diagonal in the Fourier–Walsh basis with eigenvalues depending only on degree. The modular-arithmetic network of Nanda et al. (LIT-345), which learns a handful of Fourier frequencies, is a case where the frequencies a network ends up using are not the lowest ones, which is a reminder that this paper’s theory holds in the lazy regime and not beyond it.
It carries anthology-candidate because its subject is the training
dynamics of neural networks. The anthology holds the NTK (ANTH-LIT-360) and
Tancik et al. on Fourier features (ANTH-LIT-550), whose remedy for slow
high-frequency learning is exactly a reshaping of the spectrum this paper
computes. The paper’s suggestion that early stopping regularises by
selecting smooth functions is an observation, not an instruction, and is
not filed as one.