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 ,
$$

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

$$
\hat w_{\mathrm{LS}} \;=\; \arg\min_{w \in \mathbb{R}^d}\; \min_{\pi}\; \lVert \pi\, x\, w - y \rVert_2^2 ,
\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^\top \mu_X, \qquad
\sigma_S(w) \;:=\; \sqrt{w^\top \Sigma_X\, w},
$$

and the **label mean and standard deviation**

$$
\mu_Y \;:=\; w_0^\top \mu_X, \qquad
\sigma_Y \;:=\; \sqrt{\,w_0^\top \Sigma_X\, w_0 + \sigma_E^2\,}.
$$

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
$$
\bigl[(y_i^\uparrow - s'_j)^2 + (y_j^\uparrow - s'_i)^2\bigr] - \bigl[(y_i^\uparrow - s'_i)^2 + (y_j^\uparrow - s'_j)^2\bigr]
= -2\,(y_j^\uparrow - y_i^\uparrow)\,(s'_i - s'_j) \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
$$
\int_0^1 \hat F_U^{-1}(t)\,\hat F_V^{-1}(t)\, dt
= \sum_{i=1}^n \int_{(i-1)/n}^{i/n} u_{(i)} v_{(i)}\, dt
= \frac1n \sum_{i=1}^n u_{(i)} v_{(i)} ,
\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 \bigl(\hat F_U^{-1}\bigr)^2 dt = \frac1n\sum_i u_i^2 \xrightarrow{\text{a.s.}} \mathbb{E}[U^2] = \int_0^1 \bigl(F_U^{-1}\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
$$
\Bigl| \int \hat F_U^{-1}\hat F_V^{-1} - \int F_U^{-1} F_V^{-1} \Bigr|
\le \lVert \hat F_U^{-1}\rVert_2\,\lVert \hat F_V^{-1} - F_V^{-1}\rVert_2 + \lVert \hat F_U^{-1} - F_U^{-1}\rVert_2\,\lVert F_V^{-1}\rVert_2 \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$,
$$
\int_0^1 F_U^{-1}F_V^{-1}\,dt = \mu_U\mu_V + \sigma_U\sigma_V .
\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) = \frac1n\lVert s^\uparrow - y^\uparrow\rVert_2^2
= \underbrace{\frac1n\sum_i s_{(i)}^2}_{(A)} - 2\underbrace{\frac1n\sum_i s_{(i)} y_{(i)}}_{(B)} + \underbrace{\frac1n\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) \xrightarrow{\text{a.s.}} \bigl[\mu_S^2 + \sigma_S^2\bigr] - 2\bigl[\mu_S\mu_Y + \sigma_S\sigma_Y\bigr] + \bigl[\mu_Y^2 + \sigma_Y^2\bigr]
= (\mu_S - \mu_Y)^2 + (\sigma_S - \sigma_Y)^2 = \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
$$
|g_n(w) - g_n(w')| \;\le\; \sqrt{\tfrac1n\textstyle\sum_i y_{(i)}^2}\;\cdot\; \sqrt{\tfrac1n\lVert x(w-w')\rVert_2^2}
\;\le\; \sqrt{\tfrac1n\textstyle\sum_i y_i^2}\;\bigl\lVert\tfrac1n x^\top x\bigr\rVert^{1/2}\,\lVert w-w'\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)
$$
\ell(w) = \mu_X^2(w - w_0)^2 + (\sigma_X w - \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/w_0^2}}{\mu_X^2 + \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.