🔀 Shuffled Linear Regression, the LS estimator is inconsistent in every dimension

In shuffled linear regression you observe features $x$ and labels $y$, but an unknown permutation $\pi_0$ scrambles which label goes with which row: $$y = \pi_0\,(x\,w_0) + e,\qquad x_i\sim\mathcal N(\mu_X,\Sigma_X),\quad e\sim\mathcal N(0,\sigma_E^2).$$

The natural least-squares estimator $\hat w_{\mathrm{LS}}=\arg\min_w\min_\pi\|\pi x w-y\|^2$ is not consistent. As $n\to\infty$ it converges to the moment-matching set $$\{\,w:\ w^\top\mu_X=w_0^\top\mu_X,\quad w^\top\Sigma_X w=w_0^\top\Sigma_X w_0+\sigma_E^2\,\},$$ so the feature-covariance norm of the estimate is inflated by exactly $\sigma_E^2$, independent of the dimension $d$. (For $d=1$ this is the closed form of Abid–Poon–Zou 2017, Theorem 1, Eq. 4.)

Generate fresh data below and watch the amplification fail to vanish as $n$ grows.

The left panel is the key result: a consistent estimator would drive the curve to 0 (grey dotted), but the shuffled-LS estimate settles on $\sigma_E^2$ (red dashed) in every dimension. The right panel shows the estimate instead converges to the two-moment-matching set the theory predicts.