Double Descente en Moindres Carrés — Analyse Asymptotique Exacte

1. Modèle statistique

Soient \(n \in \mathbb{N}^*\) et \(p \in \mathbb{N}^*\). On observe \(n\) couples \((X_i, y_i)_{1 \le i \le n}\) tels que :

$$ X_i \sim \mathcal{N}(0, I_p), \qquad y_i = X_i^\top w^\star + \varepsilon_i, \qquad \varepsilon_i \overset{\text{i.i.d.}}{\sim} \mathcal{N}(0, \sigma^2) $$

où \(w^\star \in \mathbb{R}^p\) est un vecteur fixe (inconnu) et \(\sigma > 0\) est fixé.

On adopte la notation matricielle suivante :

$$ X = \begin{pmatrix} X_1^\top \\ \vdots \\ X_n^\top \end{pmatrix} \in \mathbb{R}^{n \times p}, \qquad y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix} \in \mathbb{R}^n. $$

2. Estimateur considéré

On considère l'estimateur des moindres carrés de norme euclidienne minimale :

$$ \hat{w}_n = \arg\min_{w \in \mathbb{R}^p} \|Xw - y\|_2^2 $$

Cet estimateur s'exprime explicitement selon le rang de la matrice \(X\) :

  • Si \(\operatorname{rank}(X) = p\) (cas sous-paramétré \(p \le n\), rang plein), c'est l'unique solution des moindres carrés.
  • Si \(p > n\), c'est la solution de norme minimale donnée par la pseudo-inverse de Moore-Penrose :
    $$ \hat{w}_n = X^+ y = X^\top (XX^\top)^+ y. $$

3. Quantité d’intérêt : Erreur de prédiction hors échantillon

Soit \(x \sim \mathcal{N}(0, I_p)\) un vecteur de test indépendant de l'échantillon d'entraînement. On étudie l'espérance de l'erreur quadratique de prédiction (le risque) :

$$ R_n = \mathbb{E}\Bigl[ (x^\top \hat{w}_n - x^\top w^\star)^2 \Bigr]. $$

On s'intéresse au comportement asymptotique du risque normalisé \(R_n / \sigma^2\) lorsque \(n, p \to \infty\) avec un ratio fixe :

$$ \frac{p}{n} \longrightarrow \gamma \in (0, \infty). $$

4. Résultat principal (Asymptotique en grande dimension)

Théorème. Sous les hypothèses précédentes, lorsque \(n, p \to \infty\) avec \(p/n \to \gamma\), on a la convergence en probabilité suivante :

$$ \frac{R_n}{\sigma^2} \ \xrightarrow[\quad]{} \ L(\gamma) $$

avec la fonction limite \(L(\gamma)\) définie par :

$$ \boxed{ L(\gamma) = \begin{cases} \dfrac{\gamma}{1 - \gamma} & \text{si } 0 < \gamma < 1 \\[2.5ex] +\infty & \text{si } \gamma = 1 \\[2.5ex] \dfrac{\gamma}{\gamma - 1} & \text{si } \gamma > 1 \end{cases} } $$

5. Esquisse de preuve (Analyse des trois régimes)

Cas 1 : Régime sous-paramétré (\(\gamma < 1\))

Dans ce cas, la matrice de covariance empirique \(X^\top X\) est inversible avec une probabilité tendant vers 1. L'estimateur s'écrit :

$$ \hat{w}_n = (X^\top X)^{-1} X^\top y. $$

On décompose l'erreur d'estimation :

$$ \hat{w}_n - w^\star = (X^\top X)^{-1} X^\top \varepsilon. $$

En utilisant la concentration des matrices de Wishart inverse et le lemme de Woodbury–Sherman–Morrison dans le régime de grande dimension, le calcul de la trace de la covariance de l'erreur donne :

$$ \mathbb{E}\bigl[ \|x^\top (\hat{w}_n - w^\star)\|^2 \bigr] \ \sim \ \sigma^2 \, \frac{\gamma}{1 - \gamma}. $$

Cas 2 : Point critique (\(\gamma = 1\))

Lorsque \(p \approx n\), la plus petite valeur propre de la matrice \(X^\top X / n\) tend vers 0 (bord gauche de la loi de Marchenko-Pastur). La norme de l'opérateur inverse explose, entraînant une divergence de la variance de l'estimateur :

$$ \mathbb{E}[\|\hat{w}_n\|^2] \ \gtrsim \ \frac{\sigma^2 n}{\lambda_{\min}(XX^\top / n)} \ \to \ +\infty. $$

L'erreur de prédiction présente donc un pic vertical (singularité) en \(\gamma = 1\).

Cas 3 : Régime sur-paramétré (\(\gamma > 1\))

On utilise ici la pseudo-inverse :

$$ \hat{w}_n = X^\top (XX^\top)^+ y. $$

L'erreur de prédiction pour un nouveau point \(x\) s'écrit :

$$ x^\top \hat{w}_n = x^\top X^\top (XX^\top)^+ y = (X x)^\top (XX^\top)^+ y. $$

Posons \(z = Xx \in \mathbb{R}^n\). Puisque \(x\) est indépendant de \(X\) et \(x \sim \mathcal{N}(0, I_p)\), conditionnellement à \(X\), \(z\) se comporte comme un vecteur gaussien. L'analyse repose sur la théorie des matrices aléatoires (RMT). Le risque peut être relié à la transformée de Stieltjes \(m(z)\) de la distribution spectrale limite de \(XX^\top / n\).

La densité spectrale suit la loi de Marchenko–Pastur \(\rho_\gamma(\lambda)\), définie sur le support \([\lambda_-, \lambda_+]\) avec \(\lambda_\pm = (1 \pm \sqrt{\gamma})^2\) :

$$ \rho_\gamma(\lambda) = \frac{\sqrt{(\lambda_+ - \lambda)(\lambda - \lambda_-)}}{2\pi \gamma \lambda} \mathbf{1}_{[\lambda_-, \lambda_+]}(\lambda). $$

Le calcul de l'espérance via l'intégration de cette densité permet d'établir le résultat pour le régime sur-paramétré :

$$ \lim_{n,p \to \infty} \frac{R_n}{\sigma^2} = \frac{\gamma}{\gamma - 1}. $$