PROOF.md

Generalizing Theorem 1 to $d$ Dimensions

Inconsistency and bias of the least-squares estimator for shuffled linear regression

This note generalizes Theorem 1 of Linear Regression with Shuffled Labels (Abid, Poon, Zou, 2017) from the one-dimensional case ($d=1$) to arbitrary dimension $d \ge 1$ and to an arbitrary Gaussian covariance $\Sigma_X$ (the paper assumed independent feature columns, i.e. diagonal $\Sigma_X$). The simulations in experiments.py confirm every quantitative prediction made below.

---

1. Setup

We observe features $x \in \mathbb{R}^{n \times d}$ and shuffled labels $y \in \mathbb{R}^n$ generated by

$$y={\pi }_{0}x{w}_0+e,y\; \backslash ;=\backslash ;\; \backslash pi\_0\backslash ,\; x\backslash ,\; w\_0\; \backslash ;+\backslash ;\; e\; ,$$

where:

• the rows $x_1,\dots,x_n \in \mathbb{R}^d$ are i.i.d. $\mathcal{N}(\mu_X, \Sigma_X)$, with mean vector $\mu_X \in \mathbb{R}^d$ and covariance $\Sigma_X \succ 0$;
• $w_0 \in \mathbb{R}^d$ is the unknown true weight vector;
• $\pi_0$ is an unknown $n \times n$ permutation matrix, drawn uniformly at random;
• $e \in \mathbb{R}^n$ has i.i.d. entries $\mathcal{N}(0,\sigma_E^2)$, independent of $x$ and $\pi_0$.

The shuffled least-squares (LS) estimator is

$$\begin{array}{cccc}& {\widehat{w}}_{\mathrm{L}\mathrm{S}}=\arg \underset{w\in {\mathbb{R}}^d}{\min }\underset{\pi }{\min }\parallel \pi xw-y{\parallel }_2^2,& & \text{(LS)}\end{array}\backslash hat\; w\_\{\backslash mathrm\{LS\}\}\; \backslash ;=\backslash ;\; \backslash arg\backslash min\_\{w\; \backslash in\; \backslash mathbb\{R\}^d\}\backslash ;\; \backslash min\_\{\backslash pi\}\backslash ;\; \backslash lVert\; \backslash pi\backslash ,\; x\backslash ,\; w\; -\; y\; \backslash rVert\_2^2\; ,\; \backslash tag\{LS\}$$

where the inner minimum is over all $n\times n$ permutation matrices.

Throughout, for a vector $v\in\mathbb{R}^n$ we write $v^{\uparrow}$ for its entries sorted in ascending order, and $v_{(i)}$ for the $i$-th smallest entry (order statistics). We write $\xrightarrow{\text{a.s.}}$ for almost-sure convergence as $n\to\infty$.

Two scalar functionals of $w$

Define the projection mean and standard deviation induced by a weight vector $w$,

$${\mu }_S(w):=w^{\mathrm{\top }}{\mu }_X,{\sigma }_S(w):=\sqrt{w^{\mathrm{\top }}{\mathrm{\Sigma }}_{X}w},\backslash mu\_S(w)\; \backslash ;:=\backslash ;\; w^\backslash top\; \backslash mu\_X,\; \backslash qquad\; \backslash sigma\_S(w)\; \backslash ;:=\backslash ;\; \backslash sqrt\{w^\backslash top\; \backslash Sigma\_X\backslash ,\; w\},$$

and the label mean and standard deviation

$${\mu }_Y:=w_0^{\mathrm{\top }}{\mu }_X,{\sigma }_Y:=\sqrt{w_0^{\mathrm{\top }}{\mathrm{\Sigma }}_X{w}_0+{\sigma }_E^2}\mathrm{.}\backslash mu\_Y\; \backslash ;:=\backslash ;\; w\_0^\backslash top\; \backslash mu\_X,\; \backslash qquad\; \backslash sigma\_Y\; \backslash ;:=\backslash ;\; \backslash sqrt\{\backslash ,w\_0^\backslash top\; \backslash Sigma\_X\backslash ,\; w\_0\; +\; \backslash sigma\_E^2\backslash ,\}.$$

These arise because $S := w^\top X \sim \mathcal{N}(\mu_S(w), \sigma_S(w)^2)$ is the (scalar) projection of a feature vector onto $w$, and each label is marginally $Y \sim \mathcal{N}(\mu_Y, \sigma_Y^2)$.

---

2. Main result

Theorem 1$'$ (generalized). Under the setup of §1, let $L_n(w) := \tfrac1n \min_\pi \lVert \pi x w - y\rVert_2^2$. Then $L_n$ converges almost surely and uniformly on compact sets to the population loss $$ \boxed{;\ell(w) ;=; \bigl(\mu_S(w) - \mu_Y\bigr)^2 ;+; \bigl(\sigma_S(w) - \sigma_Y\bigr)^2;} \tag{1} $$ Consequently the LS estimator $\hat w_{\mathrm{LS}}$ converges (in the set sense of §6) to the moment-matching set $$ \mathcal{W}^\star ;=; \Bigl{, w \in \mathbb{R}^d ;:; w^\top \mu_X = w_0^\top\mu_X ;\text{ and }; w^\top\Sigma_X w = w_0^\top\Sigma_X w_0 + \sigma_E^2 ,\Bigr}. \tag{2} $$ In particular:

1. (Inconsistency.) Whenever $\sigma_E \neq 0$, the true weight $w_0 \notin \mathcal{W}^\star$, so $\hat w_{\mathrm{LS}} \not\to w_0$.
2. (Norm amplification.) Every limit point $w^\star \in \mathcal{W}^\star$ satisfies $$ \lVert w^\star \rVert_{\Sigma_X}^2 ;=; \lVert w_0 \rVert_{\Sigma_X}^2 + \sigma_E^2 ;>; \lVert w_0\rVert_{\Sigma_X}^2 , \qquad \lVert v\rVert_{\Sigma_X}^2 := v^\top\Sigma_X v, $$ i.e. the $\Sigma_X$-norm of the estimate is strictly inflated by exactly the noise variance.
3. ($d=1$ reduction.) When $d=1$ the set $\mathcal{W}^\star$ collapses to a single point and recovers Eq. (4) of the paper exactly: $$ \hat w_{\mathrm{LS}} \xrightarrow{\text{a.s.}} w_0,\frac{\mu_X^2 + \sigma_X\sqrt{\sigma_X^2 + \sigma_E^2/w_0^2}}{\mu_X^2 + \sigma_X^2}. $$

The geometry is transparent: $\mathcal{W}^\star$ is the intersection of an affine hyperplane ($w^\top\mu_X = \mu_Y$) with an ellipsoid ($w^\top\Sigma_X w = \sigma_Y^2$). Since $w_0$ lies on the hyperplane but strictly inside the ellipsoid (its $\Sigma_X$-norm is short by $\sigma_E^2$), the hyperplane meets the ellipsoid in a $(d-2)$-dimensional set for $d\ge 2$ — so the minimizer is not unique in higher dimensions, and "the bias" is properly described by the two scalar invariants in (2) rather than a single limiting vector.

---

3. Lemma 1 — reduction to sorting (any $d$)

Lemma 1. For every fixed $w$, $\displaystyle \min_\pi \lVert \pi x w - y\rVert_2^2 = \lVert (xw)^{\uparrow} - y^{\uparrow}\rVert_2^2.$ Hence $$ L_n(w) = \tfrac1n \lVert (xw)^{\uparrow} - y^{\uparrow}\rVert_2^2. $$

Proof. Fix $w$ and write $s := xw \in \mathbb{R}^n$, a scalar vector. We must show that among all pairings of the entries of $s$ with the entries of $y$, the squared error $\sum_i (s_{\sigma(i)} - y_i)^2$ is minimized by the pairing that sorts both in the same order. Expanding, $\sum_i (s_{\sigma(i)} - y_i)^2 = \sum_i s_i^2 + \sum_i y_i^2 - 2\sum_i s_{\sigma(i)} y_i$; the first two sums are permutation-invariant, so minimizing the squared error is equivalent to maximizing $\sum_i s_{\sigma(i)} y_i$. By the rearrangement inequality, this inner product is maximized exactly when $s$ and $y$ are sorted in the same order, i.e. $\sum_i s_{(i)} y_{(i)}$.

A direct exchange argument (as in the paper) also proves it: if a minimizing pairing had indices $i<j$ with $y_i^\uparrow$ increasing but the matched $s$-values out of order, $s'_i > s'_j$, then swapping them changes the cost by $$[(y_i^{\uparrow }-s_j^{\mathrm{\prime }}{)}^2+(y_j^{\uparrow }-s_i^{\mathrm{\prime }}{)}^2]-[(y_i^{\uparrow }-s_i^{\mathrm{\prime }}{)}^2+(y_j^{\uparrow }-s_j^{\mathrm{\prime }}{)}^2]=-2(y_j^{\uparrow }-y_i^{\uparrow })(s_i^{\mathrm{\prime }}-s_j^{\mathrm{\prime }})\le 0,\backslash bigl[(y\_i^\backslash uparrow\; -\; s\text{'}\_j)^2\; +\; (y\_j^\backslash uparrow\; -\; s\text{'}\_i)^2\backslash bigr]\; -\; \backslash bigl[(y\_i^\backslash uparrow\; -\; s\text{'}\_i)^2\; +\; (y\_j^\backslash uparrow\; -\; s\text{'}\_j)^2\backslash bigr]\; =\; -2\backslash ,(y\_j^\backslash uparrow\; -\; y\_i^\backslash uparrow)\backslash ,(s\text{'}\_i\; -\; s\text{'}\_j)\; \backslash le\; 0,$$ a contradiction unless $s$ is already co-sorted with $y$. The argument never uses $d=1$: it only uses that $s=xw$ is a scalar vector, which holds in every dimension. $\qquad\blacksquare$

This is the linchpin of the generalization. The cost (LS) only ever "sees" $w$ through the scalar projection $xw$, which is why the limit will depend on $w$ only through the two functionals $\mu_S(w),\sigma_S(w)$.

---

4. Lemma 2 — the comonotone quantile limit (general form)

The paper's Lemma 2 computes $\tfrac1n\sum_i x_{(i)} y_{(i)}$ for two Gaussian samples by a hands-on concentration argument on order statistics (its Proposition 1). We replace it with a clean, fully rigorous statement that handles arbitrary cross-dependence between the two vectors — which is exactly what the multivariate case requires, since $s=xw$ and $y$ both depend on $x$.

Lemma 2 (comonotone limit). Let $(U_1,V_1),\dots,(U_n,V_n)$ be i.i.d. pairs with $\mathbb{E}[U_1^2],\mathbb{E}[V_1^2] < \infty$; the marginals may be arbitrarily dependent on one another. Let $F_U, F_V$ be the marginal CDFs and $F_U^{-1}, F_V^{-1}$ their quantile functions. Then $$ \frac1n \sum_{i=1}^n u_{(i)}, v_{(i)} ;\xrightarrow{\text{a.s.}}; \int_0^1 F_U^{-1}(t), F_V^{-1}(t), dt . \tag{3} $$

Proof. The sorted sum depends only on the two empirical quantile functions. Indeed, if $\hat F_U^{-1}(t) := u_{(\lceil nt\rceil)}$ denotes the empirical quantile function of $u$ (a left-continuous step function equal to $u_{(i)}$ on $(\tfrac{i-1}{n}, \tfrac in]$), then $$\begin{array}{cccc}& {\int }_0^1{\widehat{F}}_U^{-1}(t){\widehat{F}}_V^{-1}(t)dt=\sum _{i=1}^n{\int }_{(i-1)\mathrm{/}n}^{i\mathrm{/}n}{u}_{(i)}{v}_{(i)}dt=\frac{1}{n}\sum _{i=1}^n{u}_{(i)}{v}_{(i)},& & \text{(4)}\end{array}\backslash int\_0^1\; \backslash hat\; F\_U^\{-1\}(t)\backslash ,\backslash hat\; F\_V^\{-1\}(t)\backslash ,\; dt\; =\; \backslash sum\_\{i=1\}^n\; \backslash int\_\{(i-1)/n\}^\{i/n\}\; u\_\{(i)\}\; v\_\{(i)\}\backslash ,\; dt\; =\; \backslash frac1n\; \backslash sum\_\{i=1\}^n\; u\_\{(i)\}\; v\_\{(i)\}\; ,\; \backslash tag\{4\}$$ an exact identity — the left side is the integral of the product of the two sorted profiles. It does not reference the original pairing $(u_i, v_i)$, which is why the dependence between $U$ and $V$ is immaterial after sorting.

It remains to pass to the limit in (4). By the Glivenko–Cantelli theorem applied to each marginal, $\hat F_U^{-1} \to F_U^{-1}$ and $\hat F_V^{-1} \to F_V^{-1}$ almost everywhere on $(0,1)$ (a.s.). Moreover the second moments converge, $${\int }_0^1({\widehat{F}}_U^{-1}{)}^{2}dt=\frac{1}{n}\sum _i{u}_i^2\stackrel{\text{a.s.}}{\to }\mathbb{E}[U^2]={\int }_0^1(F_U^{-1}{)}^{2}dt,\backslash int\_0^1\; \backslash bigl(\backslash hat\; F\_U^\{-1\}\backslash bigr)^2\; dt\; =\; \backslash frac1n\backslash sum\_i\; u\_i^2\; \backslash xrightarrow\{\backslash text\{a.s.\}\}\; \backslash mathbb\{E\}[U^2]\; =\; \backslash int\_0^1\; \backslash bigl(F\_U^\{-1\}\backslash bigr)^2\; dt\; ,$$ by the strong law of large numbers (and likewise for $V$). A.e. convergence together with convergence of the $L^2(0,1)$ norms gives convergence in $L^2(0,1)$ (Riesz–Scheffé / the $L^p$ form of Vitali's theorem). Cauchy–Schwarz then yields $$\mid \int {\widehat{F}}_U^{-1}{\widehat{F}}_V^{-1}-\int F_U^{-1}{F}_V^{-1}\mid \le \parallel {\widehat{F}}_U^{-1}{\parallel }_2\parallel {\widehat{F}}_V^{-1}-F_V^{-1}{\parallel }_2+\parallel {\widehat{F}}_U^{-1}-F_U^{-1}{\parallel }_2\parallel F_V^{-1}{\parallel }_2\to 0,\backslash Bigl|\; \backslash int\; \backslash hat\; F\_U^\{-1\}\backslash hat\; F\_V^\{-1\}\; -\; \backslash int\; F\_U^\{-1\}\; F\_V^\{-1\}\; \backslash Bigr|\; \backslash le\; \backslash lVert\; \backslash hat\; F\_U^\{-1\}\backslash rVert\_2\backslash ,\backslash lVert\; \backslash hat\; F\_V^\{-1\}\; -\; F\_V^\{-1\}\backslash rVert\_2\; +\; \backslash lVert\; \backslash hat\; F\_U^\{-1\}\; -\; F\_U^\{-1\}\backslash rVert\_2\backslash ,\backslash lVert\; F\_V^\{-1\}\backslash rVert\_2\; \backslash to\; 0\; ,$$ which is (3). $\qquad\blacksquare$

(This $\int_0^1 F_U^{-1}F_V^{-1}$ is precisely the expected product under the comonotone / Hoeffding–Fréchet upper coupling — the maximal-covariance arrangement that co-sorting produces.)

Gaussian specialization. If $U\sim\mathcal{N}(\mu_U,\sigma_U^2)$ and $V\sim\mathcal{N}(\mu_V,\sigma_V^2)$, then $F_U^{-1}(t)=\mu_U+\sigma_U\Phi^{-1}(t)$ and likewise for $V$, so with $\int_0^1 \Phi^{-1}(t),dt = 0$ and $\int_0^1 \Phi^{-1}(t)^2,dt = \mathbb{E}[Z^2]=1$, $$\begin{array}{cccc}& {\int }_0^1{F}_U^{-1}{F}_V^{-1}dt={\mu }_U{\mu }_V+{\sigma }_U{\sigma }_V\mathrm{.}& & \text{(5)}\end{array}\backslash int\_0^1\; F\_U^\{-1\}F\_V^\{-1\}\backslash ,dt\; =\; \backslash mu\_U\backslash mu\_V\; +\; \backslash sigma\_U\backslash sigma\_V\; .\; \backslash tag\{5\}$$ This recovers the paper's $\tfrac1n\sum x_{(i)}y_{(i)} \to \mu_X\mu_Y + \sigma_X\sigma_Y$ as the special case $U=X,\ V=Y$.

---

5. Proof of the population loss formula (1)

Fix $w$ and set $s := xw$. By Lemma 1, $$L_n(w)=\frac{1}{n}\parallel s^{\uparrow }-y^{\uparrow }{\parallel }_2^2=\underset{(A)}{\underbrace{\frac{1}{n}\sum _i{s}_{(i)}^2}}-2\underset{(B)}{\underbrace{\frac{1}{n}\sum _i{s}_{(i)}{y}_{(i)}}}+\underset{(C)}{\underbrace{\frac{1}{n}\sum _i{y}_{(i)}^2}}\mathrm{.}L\_n(w)\; =\; \backslash frac1n\backslash lVert\; s^\backslash uparrow\; -\; y^\backslash uparrow\backslash rVert\_2^2\; =\; \backslash underbrace\{\backslash frac1n\backslash sum\_i\; s\_\{(i)\}^2\}\_\{(A)\}\; -\; 2\backslash underbrace\{\backslash frac1n\backslash sum\_i\; s\_\{(i)\}\; y\_\{(i)\}\}\_\{(B)\}\; +\; \backslash underbrace\{\backslash frac1n\backslash sum\_i\; y\_\{(i)\}^2\}\_\{(C)\}\; .$$

Each term has an almost-sure limit:

• (A) Sorting leaves the sum of squares unchanged: $\tfrac1n\sum_i s_{(i)}^2 = \tfrac1n\sum_i s_i^2 = w^\top\bigl(\tfrac1n x^\top x\bigr)w \xrightarrow{\text{a.s.}} w^\top \mathbb{E}[XX^\top] w = \mu_S(w)^2 + \sigma_S(w)^2.$
• (C) Likewise $\tfrac1n\sum_i y_{(i)}^2 = \tfrac1n\sum_i y_i^2 \xrightarrow{\text{a.s.}} \mathbb{E}[Y^2] = \mu_Y^2 + \sigma_Y^2.$
• (B) The entries $s_i=w^\top x_i$ are i.i.d. $\mathcal{N}(\mu_S(w),\sigma_S(w)^2)$ (rows of $x$ i.i.d.), and the entries $y_i = w_0^\top x_{\pi_0(i)} + e_i$ are i.i.d. $\mathcal{N}(\mu_Y,\sigma_Y^2)$ (a permutation of i.i.d. rows plus i.i.d. noise). They are mutually dependent through $x$, but Lemma 2 tolerates that. By (3) and the Gaussian formula (5), $\tfrac1n\sum_i s_{(i)} y_{(i)} \xrightarrow{\text{a.s.}} \mu_S(w)\mu_Y + \sigma_S(w)\sigma_Y.$

Combining, $$L_n(w)\stackrel{\text{a.s.}}{\to }[{\mu }_S^2+{\sigma }_S^2]-2[{\mu }_S{\mu }_Y+{\sigma }_S{\sigma }_Y]+[{\mu }_Y^2+{\sigma }_Y^2]=({\mu }_S-{\mu }_Y{)}^2+({\sigma }_S-{\sigma }_Y{)}^2=\mathrm{\ell }(w),L\_n(w)\; \backslash xrightarrow\{\backslash text\{a.s.\}\}\; \backslash bigl[\backslash mu\_S^2\; +\; \backslash sigma\_S^2\backslash bigr]\; -\; 2\backslash bigl[\backslash mu\_S\backslash mu\_Y\; +\; \backslash sigma\_S\backslash sigma\_Y\backslash bigr]\; +\; \backslash bigl[\backslash mu\_Y^2\; +\; \backslash sigma\_Y^2\backslash bigr]\; =\; (\backslash mu\_S\; -\; \backslash mu\_Y)^2\; +\; (\backslash sigma\_S\; -\; \backslash sigma\_Y)^2\; =\; \backslash ell(w),$$ which is (1). $\qquad\blacksquare$

Because $\ell$ depends on $w$ only through $\mu_S(w)=w^\top\mu_X$ and $\sigma_S(w)=\sqrt{w^\top\Sigma_X w}$, its minimum value is $0$ iff both targets are simultaneously attainable, and the minimizing set is exactly $\mathcal{W}^\star$ in (2).

---

6. From loss convergence to estimator convergence

Pointwise a.s. convergence $L_n \to \ell$ is upgraded to uniform convergence on compacts, which is what licenses $\arg\min L_n \to \arg\min \ell$.

Equi-Lipschitz bound. Terms (A) and (C) are, respectively, a quadratic form with matrix $\tfrac1n x^\top x \to \mathbb{E}[XX^\top]$ and a constant, so both converge uniformly on compacts. For the cross term $g_n(w):=\tfrac1n\sum_i s_{(i)} y_{(i)}$, use the standard fact that sorting is $1$-Lipschitz in $\ell_2$: $\sum_i\bigl((xw){(i)} - (xw'){(i)}\bigr)^2 \le \sum_i\bigl((xw)_i - (xw')_i\bigr)^2 = \lVert x(w-w')\rVert_2^2$. Hence by Cauchy–Schwarz $$\mathrm{\mid }{g}_n(w)-g_n(w^{\mathrm{\prime }})\mathrm{\mid }\le \sqrt{\frac{1}{n}{\sum }_i{y}_{(i)}^2}\cdot \sqrt{\frac{1}{n}\parallel x(w-w^{\mathrm{\prime }}){\parallel }_2^2}\le \sqrt{\frac{1}{n}{\sum }_i{y}_i^2}\parallel \frac{1}{n}{x}^{\mathrm{\top }}x{\parallel }^{1\mathrm{/}2}\parallel w-w^{\mathrm{\prime }}\parallel \mathrm{.}|g\_n(w)\; -\; g\_n(w\text{'})|\; \backslash ;\backslash le\backslash ;\; \backslash sqrt\{\backslash tfrac1n\backslash textstyle\backslash sum\_i\; y\_\{(i)\}^2\}\backslash ;\backslash cdot\backslash ;\; \backslash sqrt\{\backslash tfrac1n\backslash lVert\; x(w-w\text{'})\backslash rVert\_2^2\}\; \backslash ;\backslash le\backslash ;\; \backslash sqrt\{\backslash tfrac1n\backslash textstyle\backslash sum\_i\; y\_i^2\}\backslash ;\backslash bigl\backslash lVert\backslash tfrac1n\; x^\backslash top\; x\backslash bigr\backslash rVert^\{1/2\}\backslash ,\backslash lVert\; w-w\text{'}\backslash rVert\; .$$ Both prefactors converge a.s. to finite constants, so ${g_n}$ is asymptotically equi-Lipschitz on any compact set. Pointwise convergence plus equicontinuity gives uniform convergence on compacts (Arzelà–Ascoli). Therefore $L_n \to \ell$ uniformly on compacts, a.s.

Coercivity and consistency. As $\lVert w\rVert\to\infty$, $\sigma_S(w)=\sqrt{w^\top\Sigma_X w}\to\infty$ (since $\Sigma_X\succ0$), so $\ell(w)\to\infty$; the same holds for $L_n$ for large $n$ via term (A). Hence all minimizers eventually lie in a fixed compact set $K\supset\mathcal{W}^\star$. On $K$, uniform convergence of $L_n$ to the continuous $\ell$ implies (standard M-estimation / epi-convergence argument) that every sequence of minimizers $\hat w_{\mathrm{LS}}$ has all of its limit points in $\arg\min_K \ell = \mathcal{W}^\star$, and $\min_w L_n \to \min_w \ell$. This is the precise sense of "$\hat w_{\mathrm{LS}}\to\mathcal{W}^\star$." $\qquad\blacksquare$

The three conclusions of Theorem 1$'$ now follow:

1. Inconsistency. $w_0\in\mathcal{W}^\star \iff w_0^\top\Sigma_X w_0 = w_0^\top\Sigma_X w_0+\sigma_E^2 \iff \sigma_E=0$. So for any $\sigma_E\ne0$, $w_0\notin\mathcal W^\star$ and $\hat w_{\mathrm{LS}}\not\to w_0$.
2. Norm amplification. Directly from the second defining equation of $\mathcal{W}^\star$: $\lVert w^\star\rVert_{\Sigma_X}^2 = \lVert w_0\rVert_{\Sigma_X}^2 + \sigma_E^2$. The inflation is exactly the noise variance — note it is independent of $d$ and of $\mu_X$. This explains the paper's empirical observation that "the norm of estimated weights is larger than that of the true weights even for $d>1$."
3. $d=1$ reduction. See §7.

---

7. The $d=1$ case recovers Eq. (4) exactly

For $d=1$, write $\mu_X,\sigma_X$ for the scalar mean/sd, $\sigma_Y=\sqrt{w_0^2\sigma_X^2+\sigma_E^2}$, and minimize (taking $w>0$, as in Lemma 1) $$\mathrm{\ell }(w)={\mu }_X^2(w-w_0{)}^2+({\sigma }_{X}w-{\sigma }_Y{)}^2\mathrm{.}\backslash ell(w)\; =\; \backslash mu\_X^2(w\; -\; w\_0)^2\; +\; (\backslash sigma\_X\; w\; -\; \backslash sigma\_Y)^2\; .$$ Setting $\ell'(w)=0$: $;\mu_X^2(w-w_0) + \sigma_X(\sigma_X w - \sigma_Y) = 0$, hence $$w^{\star }=\frac{{\mu }_X^2{w}_0+{\sigma }_X{\sigma }_Y}{{\mu }_X^2+{\sigma }_X^2}=\frac{{\mu }_X^2{w}_0+{\sigma }_X\sqrt{w_0^2{\sigma }_X^2+{\sigma }_E^2}}{{\mu }_X^2+{\sigma }_X^2}=w_0\frac{{\mu }_X^2+{\sigma }_X\sqrt{{\sigma }_X^2+{\sigma }_E^2\mathrm{/}{w}_0^2}}{{\mu }_X^2+{\sigma }_X^2},w^\backslash star\; =\; \backslash frac\{\backslash mu\_X^2\; w\_0\; +\; \backslash sigma\_X\backslash sigma\_Y\}\{\backslash mu\_X^2\; +\; \backslash sigma\_X^2\}\; =\; \backslash frac\{\backslash mu\_X^2\; w\_0\; +\; \backslash sigma\_X\backslash sqrt\{w\_0^2\backslash sigma\_X^2\; +\; \backslash sigma\_E^2\}\}\{\backslash mu\_X^2\; +\; \backslash sigma\_X^2\}\; =\; w\_0\backslash ,\backslash frac\{\backslash mu\_X^2\; +\; \backslash sigma\_X\backslash sqrt\{\backslash sigma\_X^2\; +\; \backslash sigma\_E^2/w\_0^2\}\}\{\backslash mu\_X^2\; +\; \backslash sigma\_X^2\},$$ which is identical to Eq. (4) of the paper. (Equivalently: in $d=1$ the hyperplane $w\mu_X=\mu_Y$ is a single point that misses the ellipsoid, so $\ell$ cannot reach $0$ and the minimizer trades off the two terms — recovering the paper's amplification factor $>1$.) The amplification factor exceeds $1$ whenever $\sigma_X,\sigma_E\ne0$, matching the paper. $\qquad\blacksquare$

---

8. What the simulations confirm

experiments.py verifies each prediction empirically (figures saved to figures/):

Prediction	Check	Figure
$L_n(w)\to\ell(w)$ pointwise (§5)	empirical sorted loss vs. formula (1) over random $w$, growing $n$	fig1_loss_convergence.png
$d=1$ limit = Eq. (4) (§7)	$\hat w_{\mathrm{LS}}$ vs. closed form across $\sigma_E$ and $\mu_X$ sweeps	fig2_d1_formula.png
Mean-match invariant $w^{\star\top}\mu_X=w_0^\top\mu_X$ (§2)	empirical $\hat w^\top\mu_X$ vs. target, $d=2,3,5$	fig3_invariants.png
Variance amplification $w^{\star\top}\Sigma_X w^\star = w_0^\top\Sigma_X w_0+\sigma_E^2$ (§2)	empirical $\hat w^\top\Sigma_X\hat w$ vs. target, $d=2,3,5$	fig3_invariants.png
Norm-inflation $=\sigma_E^2$, $d$-independent (§6)	$\lVert\hat w\rVert_{\Sigma_X}^2 - \lVert w_0\rVert_{\Sigma_X}^2 \to \sigma_E^2$	fig4_amplification.png

All checks use general (non-diagonal) $\Sigma_X$ to exercise the strengthened result.