Michał Dereziński, Feynman Liang and Michael W. Mahoney (2019), NeurIPS 2020 — ARXIV-1912.04533
Key takeaways
- Exact, finite-sample double descent for X⁺y (Theorem 1). Under homoscedastic noise and general position, the surrogate-design MSE is given in closed form in each regime, with λn fixed by n = tr(Σμ(Σμ + λnI)⁻¹), αn = det(Σμ(Σμ + λnI)⁻¹) and βn = e^{d−n}. It peaks at n = d. With fast eigenvalue decay of Σ, the curve has a local optimum below the threshold, where the estimator beats the null estimator (Figure 1a).
- Implicit regularization made exact (Theorem 2). For n < d, E[X̄⁺ȳ] = (Σμ + λnI)⁻¹vμ,y, the global ridge solution on the population. The amount of implicit ℓ₂ regularization is the one for which the ridge effective degrees of freedom equal the sample size. This holds for any response, not only a linear model.
- The surrogate is faithful (Theorem 3). For rows zᵀΣ^{1/2} with sub-Gaussian z and well-conditioned Σ, the i.i.d.-design MSE minus the surrogate formula goes to 0 almost surely as n/d → c̄ ≠ 1. Experiments on four spectral decays show the discrepancy falling as O(1/d) (Figure 4, Conjecture 1).
- Spectral decay changes the curve. Varying d at fixed n (Figure 2), the covariance decay lets the estimator generalize below the threshold even at signal-to-noise 1, contrary to what the isotropic analysis of Hastie et al. suggests.
- The tool. A random matrix is determinant preserving when E[det A_{I,J}] = det E[A_{I,J}] for all square submatrices. The class is closed under independent sums and products (Lemma 4) and includes AᵀB for a Poisson number of i.i.d. rows (Lemma 5), which gives E[det(ABᵀ)] = e^{−E[K]} det(I + E[BᵀA]) (Lemma 6).
Standing in the record
Filed on 2026-10-03 with the owner’s batch (ADR-027), as its second exact account of double descent, beside Liao, Couillet and Mahoney (LIT-679). That paper is asymptotic and covers random Fourier features; this one is non-asymptotic and covers linear regression with arbitrary covariance. Liao is thanked here for pointing out the connection to random-matrix resolvents. Both reduce an implicit regularization to a self-consistent trace equation. Neither compares itself with the other, so no relation is declared. Yang et al. (LIT-663) cite both for the reading of double descent as a transition between phases. This paper uses “phase transition” only as the name of the phenomenon, in its abstract and introduction, and treats the threshold n = d analytically, with no statistical-mechanics argument.
Against the evidence framework. λn is defined by n = tr(Σ(Σ + λnI)⁻¹) = Σ σi/(σi + λn), over the eigenvalues σi of Σ. That sum has the same form as MacKay’s number of well-determined parameters, γ = Σ λa/(λa + α) (LIT-623). So the implicit ridge of the minimum-norm interpolant is the prior precision at which the effective number of parameters, counted MacKay’s way on the population covariance, equals the number of samples. The paper calls the quantity the “effective dimension” of ridge regression and does not cite MacKay. The identification is mine. It is worth a THEORY if a reading confirms it beyond the formal match (see the NOTE).
Against the information-geometry line. The quantity that sets the implicit regularization is a regularized trace of the population second-moment matrix, the Fisher of linear-Gaussian regression. The spectra line (Papyan, LIT-613, LIT-617, LIT-619) measures how such spectra look in trained classifiers; a fast decay is the regime where this paper predicts generalization below the threshold.
Anthology. The double-descent curve is held there (Belkin et al.,
ANTH-LIT-297), and it is cited here as Belkin et al. (2019a, c). ML theory,
so anthology-candidate.