Zhenyu Liao, Romain Couillet and Michael W. Mahoney (2020), NeurIPS 2020; J. Stat. Mech. (2021) — ARXIV-2006.05013
Key takeaways
- The Gaussian kernel is the wrong limit. For fixed n and p the RFF Gram matrix converges entrywise to the Gaussian kernel as N → ∞ (Eqs. 1–2), but with n, p, N comparable it does not converge in spectral norm. So kernel-based predictions of training error miss badly when N/n < 1 (Figure 4).
- A deterministic equivalent replaces it (Theorem 1). E_W[Q] ≈ Q̄ = ((N/n)(Kcos/(1+δcos) + Ksin/(1+δsin)) + λIn)⁻¹, where [Kcos]ij = e^{−(‖xi‖²+‖xj‖²)/2} cosh(xiᵀxj), Ksin uses sinh, and (δcos, δsin) solve δσ = (1/n) tr(KσQ̄). As N/n → ∞ the δ go to 0 and Q̄ goes to (n/N)K⁻¹, the kernel answer (Remark 2).
- Exact training and test MSE (Theorems 2 and 3), each a first-order term plus a second-order correction through a 2×2 matrix Ω. Test data must be concentrated random vectors (Assumption 2), which covers Lipschitz maps of Gaussians and so GAN images, and they need not be independent of the training data.
- Two phases and a singular boundary. As λ → 0, for 2N < n the δ scale as 1/λ; for 2N > n they stay O(1) (Section 4.1, Figures 5–6, 8). Training MSE is continuous at 2N = n, but det(Ω⁻¹) scales as λ, so the test MSE diverges there whenever the test set is not close to the training set. That is the double-descent peak (Remark 9, Figure 7). If the test data are within σ² ≲ λ of the training data, the test error stays equal to the training error (Section 4.2, Figure 10).
- Over-parameterize and regularize. For fixed λ > 0 the minimum test error is always at 2N > n, and the global optimum is a heavily over-parameterized model with a non-vanishing λ (λopt ≈ 0.2 in Figure 7, which shows no peak).
Standing in the record
Filed on 2026-10-03 with the owner’s batch (ADR-027), as one of its two exact accounts of double descent. It is the record’s first random-matrix paper.
It extends Martin and Mahoney (LIT-672). That paper argued qualitatively that, in the limit where data and capacity grow together, learning has phases with sharp transitions. This paper works in the same proportional limit, cites the statistical mechanics of learning for it, and derives such a transition exactly for one model. Remark 9 says double descent is “a natural consequence of the phase transition between two qualitatively different phases of learning”, citing Martin and Mahoney.
Beside Dereziński, Liang and Mahoney (LIT-683). That paper derives exact non-asymptotic double descent for minimum-norm linear regression by changing the design distribution. Dereziński et al. thank Liao for pointing out the connection to random-matrix resolvents. In both papers an effective regularization is fixed by a self-consistent trace equation: δσ = (1/n) tr(KσQ̄) here, n = tr(Σ(Σ + λnI)⁻¹) there. Neither paper compares itself with the other, so no relation is declared.
Beside the kernel-regime holdings. The N/n → ∞ limit of this paper is kernel regression with the Gaussian kernel (Remark 7). The record’s NTK-regime readings work in that infinite-feature limit. Bietti and Bach (LIT-608) give the spherical-harmonic eigenstructure of ReLU kernels, Basri et al. (LIT-612) and Cao et al. (LIT-624) the eigenspace-by-eigenspace fitting rates (THEORY-086). This paper is the correction those analyses do not have when N is comparable to n.
Anthology. The double-descent curve itself is held there as Belkin et
al. (ANTH-LIT-297), which this paper cites as the empirical signature. It
is ML theory, with a practical conclusion about choosing N and λ, so
anthology-candidate.