Non-asymptotic rate of the surrogate random design approximation for double descent, and closed-form i.i.d.-design expectations (pseudo-Wishart and MACG moments)

The surrogate random design of Dereziński, Liang and Mahoney (NeurIPS 2020) yields the first exact non-asymptotic formulas for the mean squared error of the minimum-norm least squares estimator, reproducing double descent and an exact implicit ridge-regularization identity, but only for a determinantal surrogate of the standard i.i.d. design; consistency with the i.i.d. design is known only asymptotically. The conjectured $O(1/d)$ relative-error rate between the i.i.d. and surrogate MSE for Gaussian features with constant condition number remains unproven and unrefuted, and the closed-form gaps it rests on — the Moore–Penrose-inverse trace moment of the pseudo-Wishart distribution and the second moment of the matrix angular central Gaussian distribution, both for arbitrary covariance — remain unfilled. The problem asks for rigorous non-asymptotic bounds settling that rate (or refuting it via a slower-decaying covariance construction), together with the closed-form i.i.d.-design expectations of which the rate discrepancy is composed.

Background

In the standard linear regression model, responses are generated as $y(\mathbf{x})=\mathbf{x}^{\top}\mathbf{w}^{*}+\xi$ with an unknown coefficient vector $\mathbf{w}^{*}\in\mathbb{R}^{d}$ and noise of mean zero and variance $\sigma^{2}$, and the learner observes $n$ training pairs with feature vectors drawn i.i.d. from a distribution $\mu$ having second-moment matrix $\boldsymbol{\Sigma}$. Given the resulting design matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$ and response vector $\mathbf{y}$, the Moore–Penrose estimator $\mathbf{X}^{\dagger}\mathbf{y}$ (where $\dagger$ denotes the Moore–Penrose pseudoinverse) is the least-squares fit when $n\geq d$ and, when $n<d$, the unique minimum-Euclidean-norm vector that interpolates the training data exactly. Double descent is the empirical phenomenon in which the generalization error of such unregularized interpolating models, viewed as a function of the aspect ratio between sample size $n$ and dimension $d$, rises to a peak near $n=d$ and then falls again as the model becomes over-parameterized.

Dereziński, Liang and Mahoney (NeurIPS 2020) obtained the first exact non-asymptotic (finite-sample) expressions for the mean squared error $\mathrm{MSE}[\mathbf{X}^{\dagger}\mathbf{y}]=\mathbb{E}[\|\mathbf{X}^{\dagger}\mathbf{y}-\mathbf{w}^{*}\|^{2}]$ of this estimator — but not under the standard i.i.d. design. Instead they replace the i.i.d. sample by a surrogate random design, a specially constructed determinantal point process (DPP; a distribution over point sets or rows under which the probability of a sample is proportional to the squared volume it spans, inducing negative dependence among the sampled points) built from $\mu$. For the surrogate design they prove: (Theorem 1) an exact closed-form MSE, denoted $\mathcal{M}(\boldsymbol{\Sigma},\mathbf{w}^{*},\sigma^{2},n)$, involving a parameter $\lambda_n$ pinned by the effective-dimension identity $n=\mathrm{tr}(\boldsymbol{\Sigma}(\boldsymbol{\Sigma}+\lambda_n\mathbf{I})^{-1})$, familiar from ridge regression; (Theorem 2) an exact implicit-regularization identity, namely that for $n<d$ the expected estimator equals the ridge-regularized ($\ell_2$-penalized) least squares solution on the population distribution with penalty $\lambda_n$; and (Theorem 3) that the surrogate MSE is asymptotically consistent with the i.i.d.-design MSE when the rows are sub-Gaussian (a tail condition satisfied by, but weaker than, Gaussian entries) with spectrum bounded above and below in the sense $c\mathbf{I}\preceq\boldsymbol{\Sigma}\preceq C\mathbf{I}$, as $d,n\to\infty$ with $n/d\to\bar c\in(0,\infty)\setminus\{1\}$. Their experiments show the relative error between the i.i.d. MSE and $\mathcal{M}$ decaying empirically like $1/d$ across covariance spectra of fixed condition number, and they conjecture this rate.

What blocks a direct finite-sample analysis under the i.i.d. Gaussian design is exactly a pair of matrix expectations. Writing $\mathbf{X}=\mathbf{Z}\boldsymbol{\Sigma}^{1/2}$ with $\mathbf{Z}$ having i.i.d. standard Gaussian entries, the variance term of the MSE is $\sigma^{2}\,\mathbb{E}[\mathrm{tr}((\mathbf{X}^{\top}\mathbf{X})^{\dagger})]$, where $\mathbf{X}^{\top}\mathbf{X}$ follows the pseudo-Wishart (singular Wishart) distribution $PW(\boldsymbol{\Sigma},n)$ — the Wishart distribution generalized to fewer degrees of freedom than dimension, giving a singular matrix. The bias term involves $\mathbb{E}[\mathbf{I}-\mathbf{X}^{\dagger}\mathbf{X}]=\mathbb{E}[\mathbf{I}-\mathbf{V}\mathbf{V}^{\top}]$, where $\mathbf{V}$ (a $d\times n$ matrix with orthonormal columns, i.e. an orthonormal $n$-frame, an element of the Stiefel manifold) is the orthogonal factor of $\mathbf{X}$ and has the matrix angular central Gaussian (MACG) distribution introduced by Chikuse — the distribution of the polar factor of a Gaussian matrix with row covariance $\boldsymbol{\Sigma}$. For identity covariance both expectations follow from rotational invariance, but for general $\boldsymbol{\Sigma}$ no closed forms are known: Cook and Forzani (2011), who computed moments of generalized inverses of the singular Wishart, state that for the Moore–Penrose inverse and arbitrary $\boldsymbol{\Sigma}$ the required quantities 'do not have tractable closed-form representation', and Imori and von Rosen (2020) could only derive bounds for arbitrary scale matrices. Asymptotically exact formulas for i.i.d. designs are available by a different route — the Marchenko–Pastur resolvent analysis of ridgeless least squares by Hastie, Montanari, Rosset and Tibshirani (Marchenko–Pastur theory is the classical random-matrix description of the limiting eigenvalue spectrum of large sample covariance matrices, and its resolvent formalism yields limiting risk formulas) — but these characterize the $d\to\infty$ limit, not finite samples, and do not yield a non-asymptotic rate for the surrogate-vs-i.i.d. discrepancy.

Problem Statement

The problem is the finite-sample gap left by the surrogate-design analysis of double descent, in the two linked forms stated by the source. The common objective is rigorous non-asymptotic (finite-sample) control of the minimum-norm risk under the standard i.i.d. Gaussian design; the two components below serve this single objective because the rate discrepancy of component (1) is exactly composed of the matrix expectations of component (2). The problem comprises both linked components.

(1) Rate of the surrogate approximation (Conjecture 1 of Dereziński–Liang–Mahoney). In the linear model $y(\mathbf{x})=\mathbf{x}^{\top}\mathbf{w}^{*}+\xi$ with homoscedastic zero-mean noise of variance $\sigma^{2}$, let $\mathbf{X}\in\mathbb{R}^{n\times d}$ have i.i.d. rows $\mathbf{x}_i^{\top}=\mathbf{z}_i^{\top}\boldsymbol{\Sigma}^{1/2}$ with standard Gaussian vectors $\mathbf{z}_i$, where the condition number of $\boldsymbol{\Sigma}$ (ratio of largest to smallest eigenvalue) is bounded by a constant independent of $d$. Let $\mathrm{MSE}[\mathbf{X}^{\dagger}\mathbf{y}]=\mathbb{E}[\|\mathbf{X}^{\dagger}\mathbf{y}-\mathbf{w}^{*}\|^{2}]$ be the i.i.d.-design MSE of the minimum-norm estimator and $\mathcal{M}(\boldsymbol{\Sigma},\mathbf{w}^{*},\sigma^{2},n)$ the exact surrogate expression of the source's Theorem 1. Establish a rigorous non-asymptotic bound that settles the conjecture: prove that, for fixed aspect ratio $n/d\in(0,\infty)\setminus\{1\}$,

$\left|\frac{\mathrm{MSE}[\mathbf{X}^{\dagger}\mathbf{y}]}{\mathcal{M}}-1\right|=O(1/d),$

or refute it by exhibiting an admissible covariance sequence (constant condition number, fixed aspect ratio) for which the relative discrepancy provably decays slower than $1/d$; either the aggregate bound or the refutation settles the conjecture. In the under-determined regime $n<d$ (where the standard bias-variance decomposition gives $\mathcal{M}=\sigma^{2}V(\boldsymbol{\Sigma},n)+\mathbf{w}^{*\top}B(\boldsymbol{\Sigma},n)\mathbf{w}^{*}$, so that a bound of $\epsilon$ on both relative discrepancies below implies $(1-2\epsilon)\leq\mathrm{MSE}[\mathbf{X}^{\dagger}\mathbf{y}]/\mathcal{M}\leq(1+2\epsilon)$), prove non-asymptotic bounds for the variance discrepancy $\left|\mathbb{E}[\mathrm{tr}((\mathbf{X}^{\top}\mathbf{X})^{\dagger})]/V(\boldsymbol{\Sigma},n)-1\right|$ and the bias discrepancy $\sup_{\mathbf{w}\neq\mathbf{0}}\left|\mathbf{w}^{\top}\mathbb{E}[\mathbf{I}-\mathbf{X}^{\dagger}\mathbf{X}]\mathbf{w}\,/\\,(\mathbf{w}^{\top}B(\boldsymbol{\Sigma},n)\mathbf{w})-1\right|$, where $V(\boldsymbol{\Sigma},n)=(1-\alpha_n)/\lambda_n$ with $\alpha_n=\det(\boldsymbol{\Sigma}(\boldsymbol{\Sigma}+\lambda_n\mathbf{I})^{-1})$ and $B(\boldsymbol{\Sigma},n)=\lambda_n(\boldsymbol{\Sigma}+\lambda_n\mathbf{I})^{-1}$ are the surrogate variance and bias terms of Theorem 1 and $\lambda_n\geq0$ satisfies $n=\mathrm{tr}(\boldsymbol{\Sigma}(\boldsymbol{\Sigma}+\lambda_n\mathbf{I})^{-1})$. These two finer bounds address the under-determined aspect ratios $n<d$; the over-determined aspect ratios $n>d$ are addressed by the aggregate bound or by a refutation.

(2) The closed-form expectation gaps that a direct i.i.d. finite-sample analysis must fill: derive closed-form expressions for (i) $\mathbb{E}[\mathrm{tr}(\mathbf{W}^{\dagger})]$ where $\mathbf{W}\sim PW(\boldsymbol{\Sigma},n)$ is a pseudo-Wishart matrix with $n<d$ and arbitrary covariance $\boldsymbol{\Sigma}$, and (ii) $\mathbb{E}[\mathbf{V}\mathbf{V}^{\top}]$ where $\mathbf{V}$ has the matrix angular central Gaussian distribution $\mathrm{MACG}(\boldsymbol{\Sigma})$ on the Stiefel manifold of orthonormal $n$-frames in $\mathbb{R}^{d}$, with arbitrary covariance $\boldsymbol{\Sigma}$ (the case $\boldsymbol{\Sigma}=c\mathbf{I}$ is already known by rotational invariance).

The source's further scope extensions — exact implicit-regularization identities for interpolating estimators other than the minimum-norm one, for other sampling designs, or for algorithmic regularizers such as SGD-induced bias, and the behavior of the surrogate formulas under heavy-tailed features or covariances with growing condition number — are not part of this problem.

References

1. Michał Dereziński, Feynman T. Liang, Michael W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. Advances in Neural Information Processing Systems 33 (2020), 5152–5164. arXiv:1912.04533, DOI: 10.48550/arXiv.1912.04533. https://arxiv.org/abs/1912.04533
2. Michał Dereziński, Feynman T. Liang, Zhenyu Liao, Michael W. Mahoney. Precise expressions for random projections: Low-rank approximation and randomized Newton. Advances in Neural Information Processing Systems 33 (2020). arXiv:2006.10653, DOI: 10.48550/arXiv.2006.10653. https://arxiv.org/abs/2006.10653
3. Daniel LeJeune, Pratik Patil, Hamid Javadi, Richard G. Baraniuk, Ryan J. Tibshirani. Asymptotics of the Sketched Pseudoinverse. SIAM Journal on Mathematics of Data Science 6 (2024), 199–225. DOI: 10.1137/22M1530264. arXiv:2211.03751. https://arxiv.org/abs/2211.03751
4. Adrien Kassel, Thierry Lévy. On the mean projection theorem for determinantal point processes. Latin American Journal of Probability and Mathematical Statistics (ALEA) 20 (2023), 497. DOI: 10.30757/ALEA.v20-17. arXiv:2203.04628. https://arxiv.org/abs/2203.04628
5. R. Dennis Cook, Liliana Forzani. On the mean and variance of the generalized inverse of a singular Wishart matrix. Electronic Journal of Statistics 5 (2011), 146–158. DOI: 10.1214/11-EJS602. https://doi.org/10.1214/11-EJS602
6. Shinpei Imori, Dietrich von Rosen. On the mean and dispersion of the Moore-Penrose generalized inverse of a Wishart matrix. Electronic Journal of Linear Algebra 36 (2020), 124–133. DOI: 10.13001/ela.2020.5091. https://doi.org/10.13001/ela.2020.5091
7. Taras Bodnar, Nestor Parolya. Reviving pseudo-inverses: Asymptotic properties of large dimensional Moore-Penrose and Ridge-type inverses with applications. The Annals of Statistics 54 (2026). arXiv:2403.15792, DOI: 10.1214/25-AOS2602. https://arxiv.org/abs/2403.15792
8. Justyna Wróblewska. A note on some extensions of the matrix angular central Gaussian distribution. Central European Journal of Economic Modelling and Econometrics (2025), 131–141. DOI: 10.24425/cejeme.2025.156674. arXiv:2010.03243. https://arxiv.org/abs/2010.03243
9. Yasuko Chikuse. The matrix angular central Gaussian distribution. Journal of Multivariate Analysis 33(2) (1990), 265–274. DOI: 10.1016/0047-259X(90)90050-R. https://doi.org/10.1016/0047-259X(90)90050-R
10. Michał Dereziński, Zhenyu Liao, Edgar Dobriban, Michael W. Mahoney. Sparse sketches with small inversion bias. Proceedings of the 34th Conference on Learning Theory (COLT 2021), PMLR 134. arXiv:2011.10695, DOI: 10.48550/arXiv.2011.10695. https://arxiv.org/abs/2011.10695
11. Chengmei Niu, Zhenyu Liao, Zenan Ling, Michael W. Mahoney. Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton. arXiv:2502.13583 (2025), DOI: 10.48550/arXiv.2502.13583. https://arxiv.org/abs/2502.13583
12. Michaël Fanuel, Joachim Schreurs, Johan A. K. Suykens. Determinantal Point Processes Implicitly Regularize Semiparametric Regression Problems. SIAM Journal on Mathematics of Data Science 4(3) (2022), 1171–1190. DOI: 10.1137/21M1403977. arXiv:2011.06964. https://arxiv.org/abs/2011.06964
13. Courtney Paquette, Elliot Paquette, Ben Adlam, Jeffrey Pennington. Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions. Advances in Neural Information Processing Systems 35 (2022). arXiv:2206.07252, DOI: 10.48550/arXiv.2206.07252. https://arxiv.org/abs/2206.07252
14. Liam Hodgkinson, Chris van der Heide, Robert Salomone, Fred Roosta, Michael W. Mahoney. The Interpolating Information Criterion for Overparameterized Models. arXiv:2307.07785 (2023), DOI: 10.48550/arXiv.2307.07785. https://arxiv.org/abs/2307.07785
15. Trevor Hastie, Andrea Montanari, Saharon Rosset, Ryan J. Tibshirani. Surprises in High-Dimensional Ridgeless Least Squares Interpolation. arXiv:1903.08560 (2019), DOI: 10.48550/arXiv.1903.08560. https://arxiv.org/abs/1903.08560