paper_generalization.tex

\documentclass[11pt]{article}

% ---------- packages ----------
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}
\usepackage{bm}
\usepackage{graphicx}
\usepackage{booktabs}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{authblk}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage{cleveref}

% ---------- theorem environments ----------
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\theoremstyle{definition}
\newtheorem{remark}{Remark}

% ---------- macros ----------
\newcommand{\R}{\mathbb{R}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\X}{\bm{x}}
\newcommand{\wopt}{w_0}
\newcommand{\wls}{\hat{w}_{\mathrm{LS}}}
\newcommand{\SigX}{\Sigma_X}
\newcommand{\muX}{\mu_X}
\newcommand{\sigE}{\sigma_E}
\newcommand{\Wstar}{\mathcal{W}^\star}
\newcommand{\sort}[1]{#1^{\uparrow}}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand{\as}{\overset{\text{a.s.}}{\longrightarrow}}
\newcommand{\normSig}[1]{\lVert #1 \rVert_{\SigX}}

% ---------- title ----------
\title{\bfseries Inconsistency and Bias of the Least-Squares Estimator\\
in Higher-Dimensional Shuffled Linear Regression%
\footnote{All code, experiments, and results---including an interactive demo that
reproduces the inconsistency across dimensions---are available at
\url{https://huggingface.co/spaces/abidlabs/shuffled-linear-regression}.}}

\author[1]{Abubakar Abid}
\affil[1]{\small Department of Electrical Engineering, Stanford University}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
In \emph{shuffled linear regression} one observes input features and labels whose
mutual ordering has been scrambled by an unknown permutation. Prior work showed
that the natural analogue of the least-squares (LS) estimator is \emph{inconsistent}
and exhibits an \emph{amplification bias}, but the proof and the closed-form limit
were restricted to the one-dimensional ($d=1$) case, with independent feature
coordinates. We generalize this result to arbitrary dimension $d$ and to an
arbitrary Gaussian feature covariance $\SigX$. Our central observation is that the
shuffled LS loss converges almost surely and uniformly on compact sets to a
\emph{population loss that depends on the weight vector only through two scalar
functionals}---the mean and standard deviation of the induced linear projection.
Minimizing this population loss shows that the LS estimator converges to the set of
weights that \emph{match the first two self-moments} of the labels, namely
$\{w : w^\top\muX = \wopt^\top\muX,\; w^\top\SigX w = \wopt^\top\SigX\wopt + \sigE^2\}$.
Three consequences follow: (i) the estimator is inconsistent whenever the noise is
nonzero; (ii) the $\SigX$-norm of every limiting estimate is inflated by exactly the
noise variance $\sigE^2$, \emph{independently of the dimension}, which explains the
amplification bias observed empirically in higher dimensions; and (iii) the result
collapses to the previously known scalar formula when $d=1$. We confirm every
quantitative prediction with simulations across dimensions and covariance structures.
\end{abstract}

% ============================================================
\section{Introduction}
% ============================================================

Linear regression is classically performed on data in which each label is
individually associated with its input features. In \emph{shuffled linear
regression}, this correspondence is lost: all labels are observed, but the mutual
ordering between features and labels is unknown~\cite{abid2017shuffled}. Concretely,
one observes features $\X \in \R^{n\times d}$ and labels $y \in \R^n$ generated by
\begin{equation}\label{eq:model}
  y \;=\; \pi_0\, \X\, \wopt \;+\; e,
\end{equation}
where $\pi_0$ is an unknown $n\times n$ permutation matrix, $\wopt \in \R^d$ are the
unknown weights, and $e$ is additive noise. This model arises whenever a population of
objects is characterized by two separate measurement processes whose orderings cannot
be aligned---for example in flow cytometry, signaling with identical tokens, pose-and-
correspondence estimation, relational dating in archaeology, and data
de-anonymization~\cite{abid2017shuffled,pananjady2017denoising,unnikrishnan2018unlabeled}.

A natural estimator is the \emph{shuffled least-squares (LS) estimator}, which
searches jointly over weights and permutations,
\begin{equation}\label{eq:ls}
  \wls \;=\; \argmin_{w \in \R^d}\; \min_{\pi}\; \lVert \pi\,\X\,w - y \rVert_2^2,
\end{equation}
the minimum being over all $n\times n$ permutation matrices. Although the ordinary
least-squares estimator is consistent in the classical setting, the shuffled LS
estimator is not. Abid et al.~\cite{abid2017shuffled} proved (their Theorem~1) that in
one dimension, with $x_i \sim \N(\muX,\sigma_X^2)$ and zero-mean Gaussian noise of
variance $\sigE^2$, the estimator converges almost surely to
\begin{equation}\label{eq:thm1-d1}
  \wls \;\as\; \wopt\,
  \frac{\muX^2 + \sigma_X\sqrt{\sigma_X^2 + \sigE^2/\wopt^2}}{\muX^2 + \sigma_X^2},
\end{equation}
a limit strictly larger in magnitude than $\wopt$ whenever $\sigma_X,\sigE \neq 0$.
This \emph{amplification bias} means that, even with unbounded sample size, the
estimate is systematically inflated. The authors noted that empirically the bias
persists for $d>1$---the norm of the estimate exceeds that of the truth---but left the
multivariate case open: ``We have not extended the proof to higher dimensions''~\cite{abid2017shuffled}.

\paragraph{Contributions.} This paper closes that gap.
\begin{itemize}
  \item We prove that for any dimension $d$ and any positive-definite Gaussian
  covariance $\SigX$, the shuffled LS loss converges to a population loss that is a
  function of only two scalars---the projection mean $w^\top\muX$ and projection
  standard deviation $\sqrt{w^\top\SigX w}$ (\Cref{thm:main}, \Cref{eq:poploss}).
  \item Consequently $\wls$ converges to the \emph{moment-matching set} $\Wstar$
  (\Cref{eq:wstar}). We extract three scalar invariants of this set, which together
  characterize the bias: a mean-matching identity, a variance-amplification identity,
  and the resulting norm inflation.
  \item We show the estimator is inconsistent for any nonzero noise, that the
  $\SigX$-norm inflation equals exactly $\sigE^2$ regardless of $d$, and that the
  result recovers~\eqref{eq:thm1-d1} exactly when $d=1$.
  \item We confirm all predictions with simulations over $d \in \{1,2,3,4,5\}$ and
  non-diagonal $\SigX$.
\end{itemize}
Our argument also replaces the original order-statistic concentration bound with a
cleaner and more general lemma on the limit of products of sorted vectors
(\Cref{lem:comono})---a statement about the \emph{comonotone coupling} of two
empirical distributions that allows the two sorted vectors to be arbitrarily dependent.
This generality is precisely what the multivariate case demands.

% ============================================================
\section{Setup and notation}\label{sec:setup}
% ============================================================

We adopt the random-design setting of~\cite{abid2017shuffled}, generalized to an
arbitrary covariance. The rows $x_1,\dots,x_n \in \R^d$ of $\X$ are i.i.d.
$\N(\muX,\SigX)$ with mean vector $\muX \in \R^d$ and covariance $\SigX \succ 0$;
the weights $\wopt \in \R^d$ are fixed and unknown; $\pi_0$ is drawn uniformly from
the $n\times n$ permutation matrices; and the noise $e$ has i.i.d. entries
$\N(0,\sigE^2)$, independent of $\X$ and $\pi_0$. (The paper's setting of independent
feature columns is the special case $\SigX$ diagonal.)

For $v \in \R^n$ we write $\sort{v}$ for the vector of its entries sorted in ascending
order, and $v_{(i)}$ for the $i$-th order statistic. Convergence ``$\as$'' is almost
sure as $n\to\infty$. We write $\normSig{v}^2 := v^\top \SigX v$.

The estimator~\eqref{eq:ls} interacts with $w$ only through the scalar projection
$\X w$. It is therefore natural to summarize $w$ by the mean and standard deviation it
induces on a feature row,
\begin{equation}\label{eq:functionals}
  \mu_S(w) := w^\top \muX,
  \qquad
  \sigma_S(w) := \sqrt{w^\top \SigX\, w},
\end{equation}
so that $S := w^\top X \sim \N\!\big(\mu_S(w), \sigma_S(w)^2\big)$. Each label is
marginally $Y \sim \N(\mu_Y,\sigma_Y^2)$ with
\begin{equation}\label{eq:Ymoments}
  \mu_Y := \wopt^\top\muX,
  \qquad
  \sigma_Y := \sqrt{\,\wopt^\top\SigX\wopt + \sigE^2\,}.
\end{equation}

% ============================================================
\section{Main result}\label{sec:main}
% ============================================================

\begin{theorem}[Generalized Theorem~1]\label{thm:main}
Under the setup of \Cref{sec:setup}, 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
\begin{equation}\label{eq:poploss}
  \ell(w)
  \;=\;
  \big(\mu_S(w) - \mu_Y\big)^2
  \;+\;
  \big(\sigma_S(w) - \sigma_Y\big)^2 .
\end{equation}
Consequently the LS estimator converges (in the set sense of \Cref{sec:argmin})
to the \emph{moment-matching set}
\begin{equation}\label{eq:wstar}
  \Wstar \;=\; \Big\{ w \in \R^d :\;
    w^\top\muX = \wopt^\top\muX
    \;\text{ and }\;
    w^\top\SigX w = \wopt^\top\SigX\wopt + \sigE^2 \Big\}.
\end{equation}
\end{theorem}

The two defining equations of $\Wstar$ are exactly the constraints that the first
two \emph{self-moments} of the recovered signal $\X w$ match those of the labels $y$;
this is also the population analogue of the self-moments (SM) estimator
of~\cite{abid2017shuffled}. Geometrically, $\Wstar$ is the intersection of an affine
hyperplane (the mean constraint) with an ellipsoid (the variance constraint). The
truth $\wopt$ lies on the hyperplane but strictly \emph{inside} the ellipsoid---its
$\SigX$-norm falls short by exactly $\sigE^2$---so the hyperplane cuts through the
ellipsoid and the two constraints are jointly attainable for $d\ge 2$.

\begin{corollary}[Inconsistency]\label{cor:incons}
If $\sigE \neq 0$ then $\wopt \notin \Wstar$, and hence $\wls \not\to \wopt$. The
estimator is consistent only in the noiseless case.
\end{corollary}

\begin{corollary}[Dimension-independent norm amplification]\label{cor:amp}
Every limit point $w^\star \in \Wstar$ satisfies
\begin{equation}\label{eq:amp}
  \normSig{w^\star}^2 \;=\; \normSig{\wopt}^2 + \sigE^2 \;>\; \normSig{\wopt}^2 .
\end{equation}
The inflation of the $\SigX$-norm equals exactly the noise variance and does not
depend on $d$ or $\muX$. This explains the empirical observation
of~\cite{abid2017shuffled} that the norm of the estimate exceeds that of the truth
even for $d>1$.
\end{corollary}

\begin{corollary}[Reduction to $d=1$]\label{cor:d1}
When $d=1$ the set $\Wstar$ is a single point and \Cref{thm:main} reproduces the scalar
limit~\eqref{eq:thm1-d1} of~\cite{abid2017shuffled} exactly.
\end{corollary}

\begin{remark}[Non-uniqueness in higher dimensions]
For $d\ge 2$ the minimizer is generically a $(d-2)$-dimensional manifold rather than a
point, so ``the bias'' is most precisely described by the scalar invariants in
\eqref{eq:wstar} and \eqref{eq:amp}---which \emph{all} minimizers share---rather than
by a single limiting vector. The LS estimator can recover the noiseless signal energy
direction only up to this moment-matching ambiguity.
\end{remark}

% ============================================================
\section{Proof}\label{sec:proof}
% ============================================================

The proof rests on two lemmas: a rearrangement identity that reduces the
combinatorial minimization over permutations to sorting, and a limit law for products
of sorted vectors.

\subsection{Lemma 1: reduction to sorting in any dimension}

\begin{lemma}[Rearrangement]\label{lem:sort}
For every fixed $w$,
$\displaystyle \min_\pi \lVert \pi \X w - y \rVert_2^2
= \lVert \sort{(\X w)} - \sort{y}\rVert_2^2$, and therefore
$L_n(w) = \tfrac1n \lVert \sort{(\X w)} - \sort{y}\rVert_2^2$.
\end{lemma}

\begin{proof}
Fix $w$ and set $s := \X w \in \R^n$, a \emph{scalar} vector. Over pairings $\sigma$,
$\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$, which by the rearrangement
inequality occurs exactly when $s$ and $y$ are sorted in the same order. Equivalently,
by an exchange argument: if a minimizing pairing matched indices with $y^\uparrow_i \le
y^\uparrow_j$ but $s'_i > s'_j$, swapping them changes the cost by
$-2(y^\uparrow_j - y^\uparrow_i)(s'_i - s'_j) \le 0$, a contradiction unless $s$ is
co-sorted with $y$. The argument never uses $d=1$; it uses only that $s = \X w$ is a
scalar vector, which holds in every dimension.
\end{proof}

\Cref{lem:sort} is the linchpin of the generalization: the loss only ever sees $w$
through the scalar projection $\X w$, which is why its limit will depend on $w$ solely
through $\mu_S(w)$ and $\sigma_S(w)$. The minimization over $n!$ permutations is
replaced by a single sort, making~\eqref{eq:ls} computable in polynomial
time~\cite{abid2017shuffled}.

\subsection{Lemma 2: the comonotone limit of sorted products}

\begin{lemma}[Comonotone limit]\label{lem:comono}
Let $(U_1,V_1),\dots,(U_n,V_n)$ be i.i.d. pairs with finite second moments; the two
coordinates may be \emph{arbitrarily dependent}. Let $F_U,F_V$ be the marginal CDFs and
$F_U^{-1},F_V^{-1}$ the corresponding quantile functions. Then
\begin{equation}\label{eq:comono}
  \frac1n \sum_{i=1}^n u_{(i)}\, v_{(i)} \;\as\; \int_0^1 F_U^{-1}(t)\,F_V^{-1}(t)\,dt .
\end{equation}
\end{lemma}

\begin{proof}
The sorted sum depends only on the two empirical \emph{quantile functions}. Writing
$\widehat{F}_U^{-1}(t) := u_{(\lceil nt\rceil)}$ for the empirical quantile function
(equal to $u_{(i)}$ on $(\tfrac{i-1}{n},\tfrac{i}{n}]$), we have the exact identity
\begin{equation}\label{eq:exact}
  \int_0^1 \widehat{F}_U^{-1}(t)\,\widehat{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)} .
\end{equation}
Crucially, the left-hand side does not reference the original pairing $(u_i,v_i)$,
which is why dependence between $U$ and $V$ is immaterial after sorting. By the
Glivenko--Cantelli theorem, $\widehat{F}_U^{-1}\to F_U^{-1}$ and
$\widehat{F}_V^{-1}\to F_V^{-1}$ almost everywhere on $(0,1)$, a.s. Moreover the second
moments converge by the strong law,
$\int_0^1 (\widehat{F}_U^{-1})^2 = \tfrac1n\sum_i u_i^2 \as \E[U^2]
= \int_0^1 (F_U^{-1})^2$, and likewise for $V$. Almost-everywhere convergence together
with convergence of the $L^2(0,1)$ norms yields convergence in $L^2(0,1)$ (the $L^p$
form of Vitali's theorem / Riesz--Scheff\'e). Cauchy--Schwarz then gives
\eqref{eq:comono}.
\end{proof}

The limit $\int_0^1 F_U^{-1}F_V^{-1}$ is the expected product under the
\emph{comonotone} (Hoeffding--Fr\'echet upper) coupling, i.e. the maximal-covariance
arrangement produced by co-sorting~\cite{hoeffding1940,david2003order}. For two
Gaussians $U\sim\N(\mu_U,\sigma_U^2)$, $V\sim\N(\mu_V,\sigma_V^2)$ we have
$F_U^{-1}(t) = \mu_U + \sigma_U\,\Phi^{-1}(t)$, so with $\int_0^1\Phi^{-1}=0$ and
$\int_0^1 (\Phi^{-1})^2 = 1$,
\begin{equation}\label{eq:gaussprod}
  \int_0^1 F_U^{-1}F_V^{-1}\,dt = \mu_U\mu_V + \sigma_U\sigma_V .
\end{equation}
This recovers the corresponding step of~\cite{abid2017shuffled} as the special case
$U=X$, $V=Y$, but our derivation needs no bound on the variance of individual order
statistics and tolerates the dependence between $\X w$ and $y$.

\subsection{Convergence of the loss}

Fix $w$ and set $s := \X w$. By \Cref{lem:sort},
\[
  L_n(w)
  = \underbrace{\tfrac1n\textstyle\sum_i s_{(i)}^2}_{(A)}
  - 2\underbrace{\tfrac1n\textstyle\sum_i s_{(i)} y_{(i)}}_{(B)}
  + \underbrace{\tfrac1n\textstyle\sum_i y_{(i)}^2}_{(C)} .
\]
Each term converges almost surely.
\emph{(A)} Sorting preserves the sum of squares:
$\tfrac1n\sum_i s_{(i)}^2 = \tfrac1n\sum_i s_i^2 = w^\top\!\big(\tfrac1n \X^\top\X\big)w
\as w^\top \E[XX^\top] w = \mu_S(w)^2 + \sigma_S(w)^2$.
\emph{(C)} Likewise $\tfrac1n\sum_i y_{(i)}^2 \as \E[Y^2] = \mu_Y^2 + \sigma_Y^2$.
\emph{(B)} The entries $s_i = w^\top x_i$ are i.i.d. $\N(\mu_S(w),\sigma_S(w)^2)$ and the
entries $y_i$ are i.i.d. $\N(\mu_Y,\sigma_Y^2)$; they are dependent through $\X$, but
\Cref{lem:comono} permits this. By~\eqref{eq:comono} and~\eqref{eq:gaussprod},
$\tfrac1n\sum_i s_{(i)} y_{(i)} \as \mu_S(w)\mu_Y + \sigma_S(w)\sigma_Y$. Combining,
\[
  L_n(w) \as
  \big[\mu_S^2+\sigma_S^2\big] - 2\big[\mu_S\mu_Y+\sigma_S\sigma_Y\big]
  + \big[\mu_Y^2+\sigma_Y^2\big]
  = (\mu_S-\mu_Y)^2 + (\sigma_S-\sigma_Y)^2 = \ell(w),
\]
which is~\eqref{eq:poploss}. Since $\ell$ depends on $w$ only through $\mu_S(w)$ and
$\sigma_S(w)$, its minimum value is $0$ iff both targets are simultaneously attainable,
and its minimizing set is exactly $\Wstar$ in~\eqref{eq:wstar}.

\subsection{From loss convergence to estimator convergence}\label{sec:argmin}

We upgrade pointwise convergence to uniform convergence on compact sets, which
licenses passing from the minimizers of $L_n$ to those of $\ell$. Terms $(A)$ and
$(C)$ are, respectively, a
quadratic form with matrix $\tfrac1n\X^\top\X \to \E[XX^\top]$ and a constant, hence
uniformly convergent on compacts. For the cross term
$g_n(w):=\tfrac1n\sum_i s_{(i)} y_{(i)}$ we use that \emph{sorting is $1$-Lipschitz in
$\ell_2$}. Combining this with the Cauchy--Schwarz inequality gives
\[
  \sum_i\big((\X w)_{(i)} - (\X w')_{(i)}\big)^2 \le \lVert \X(w-w')\rVert_2^2 ,
  \qquad
  |g_n(w) - g_n(w')|
  \;\le\; \Big(\tfrac1n\textstyle\sum_i y_i^2\Big)^{1/2}
  \big\lVert \tfrac1n \X^\top\X \big\rVert^{1/2} \lVert w - w'\rVert ,
\]
with both prefactors in the latter bound converging a.s. to finite constants. Thus $\{g_n\}$ is
asymptotically equi-Lipschitz on any compact set; pointwise convergence plus
equicontinuity gives uniform convergence on compacts (Arzel\`a--Ascoli). Finally,
$\ell$ is coercive ($\sigma_S(w)\to\infty$ as $\lVert w\rVert\to\infty$ since
$\SigX\succ0$), and so is $L_n$ for large $n$ via term $(A)$; hence all minimizers
eventually lie in a fixed compact set. Uniform convergence of $L_n$ to the continuous
$\ell$ on that set implies, by the standard M-estimation/epi-convergence
argument~\cite{vandervaart1998}, that every sequence of minimizers has all its limit
points in $\Wstar$ and that $\min_w L_n \to \min_w \ell$. \Cref{cor:incons,cor:amp}
follow directly from the defining equations of $\Wstar$.

\subsection{The one-dimensional case}\label{sec:d1}

For $d=1$, write $\muX,\sigma_X$ for the scalar mean and standard deviation and
$\sigma_Y = \sqrt{\wopt^2\sigma_X^2 + \sigE^2}$. Taking $w>0$ as in \Cref{lem:sort},
$\ell(w) = \muX^2(w-\wopt)^2 + (\sigma_X w - \sigma_Y)^2$, and $\ell'(w)=0$ gives
\[
  w^\star = \frac{\muX^2\wopt + \sigma_X\sigma_Y}{\muX^2 + \sigma_X^2}
  = \wopt\,\frac{\muX^2 + \sigma_X\sqrt{\sigma_X^2 + \sigE^2/\wopt^2}}{\muX^2+\sigma_X^2},
\]
which is identical to~\eqref{eq:thm1-d1}, proving \Cref{cor:d1}. In one dimension the
hyperplane $w\muX=\mu_Y$ is a single point that misses the ellipsoid, so $\ell$ cannot
reach $0$ and the minimizer trades the two terms off, producing the amplification
factor strictly greater than $1$.

% ============================================================
\section{Experiments}\label{sec:exp}
% ============================================================

We verify each prediction by simulation. Throughout, features use a non-diagonal
covariance $\SigX$ to exercise the strengthened result, and the shuffled LS objective
is minimized by a structure-aware alternating ``sort-then-OLS'' procedure that exploits
\Cref{lem:sort} (each step co-sorts the projection with the labels, then performs an
ordinary least-squares update; the sorted loss is non-increasing). All code,
experiment scripts, and result figures, together with an interactive demo that
regenerates the inconsistency across dimensions, are publicly available
(\Cref{sec:availability}).

\paragraph{Convergence of the loss (\Cref{fig:loss}).}
For $d=4$ we evaluate the empirical sorted loss $L_n(w)$ at $200$ random probe weights
and compare it to the population formula~\eqref{eq:poploss}. The scatter collapses onto
the identity line as $n$ grows, with root-mean-square error falling from $1.43$ at
$n=200$ to $0.08$ at $n=5\times10^4$, confirming \Cref{thm:main}.

\paragraph{The $d=1$ formula (\Cref{fig:d1}).}
Sweeping the noise level $\sigE$ and the feature mean $\muX$, the empirical estimate
matches~\eqref{eq:thm1-d1} to within $0.003$. The bias grows with $\sigE$ and decays
toward $1$ as the signal mean dominates the noise, exactly as~\eqref{eq:thm1-d1}
predicts.

\paragraph{Moment-matching invariants for $d>1$ (\Cref{fig:inv}).}
For $d\in\{2,3,5\}$ we track the two invariant errors
$|\,\hat{w}^\top\muX - \wopt^\top\muX\,|$ and
$|\,\hat{w}^\top\SigX\hat{w} - (\wopt^\top\SigX\wopt+\sigE^2)\,|$. Both decay to zero
as $n\to\infty$, confirming that the recovered weights satisfy the defining equations
of $\Wstar$ in~\eqref{eq:wstar}.

\paragraph{Norm amplification (\Cref{fig:amp}).}
The $\SigX$-norm inflation $\normSig{\hat{w}}^2 - \normSig{\wopt}^2$ converges to
$\sigE^2$ for every dimension tested, confirming \Cref{cor:amp} and its prediction that
the amplification is exactly the noise variance, independent of $d$.

\begin{figure}[t]
  \centering
  \includegraphics[width=\textwidth]{figures/fig1_loss_convergence.png}
  \caption{Empirical sorted loss $L_n(w)$ versus the population loss $\ell(w)$
  of~\eqref{eq:poploss} over $200$ random probe weights ($d=4$, non-diagonal $\SigX$).
  The scatter collapses onto $y=x$ as $n$ grows (RMSE $1.43\to0.08$).}
  \label{fig:loss}
\end{figure}

\begin{figure}[t]
  \centering
  \includegraphics[width=\textwidth]{figures/fig2_d1_formula.png}
  \caption{$d=1$: the shuffled-LS estimate (points, with error bars over trials) tracks
  the closed-form limit~\eqref{eq:thm1-d1} (solid) across sweeps of the noise level
  $\sigE$ (left) and the feature mean $\muX$ (right). The dotted line marks the true
  weight $\wopt$.}
  \label{fig:d1}
\end{figure}

\begin{figure}[t]
  \centering
  \includegraphics[width=\textwidth]{figures/fig3_invariants.png}
  \caption{$d\in\{2,3,5\}$: absolute errors of the two moment-matching invariants---the
  mean-match identity (left) and the variance-amplification identity (right)---both
  decay to zero as $n\to\infty$, confirming $\wls \to \Wstar$.}
  \label{fig:inv}
\end{figure}

\begin{figure}[t]
  \centering
  \includegraphics[width=0.72\textwidth]{figures/fig4_amplification.png}
  \caption{The $\SigX$-norm inflation $\normSig{\hat{w}}^2 - \normSig{\wopt}^2$
  converges to the noise variance $\sigE^2$ (dashed) for every dimension, illustrating
  the dimension-independent amplification of \Cref{cor:amp}.}
  \label{fig:amp}
\end{figure}

% ============================================================
\section{Discussion}\label{sec:disc}
% ============================================================

The generalized result clarifies precisely \emph{what} information about $\wopt$ the
shuffled LS estimator retains and what it loses. After shuffling, the objective depends
on the weights only through the first two self-moments of the induced projection
(\Cref{thm:main}); the estimator therefore recovers $\wopt$ only up to the
$(d-2)$-dimensional ambiguity of matching those moments, and it systematically inflates
the signal energy by the noise variance (\Cref{cor:amp}). This is consistent with, and
explains, the empirical observations of~\cite{abid2017shuffled} in higher dimensions,
and it mirrors the failure mode in $d=1$, where the estimator cannot disentangle signal
variance from noise variance and so over-estimates the slope.

The same two-moment structure points to the remedy already proposed
in~\cite{abid2017shuffled}: a self-moments (SM) estimator that matches sample moments
of $\X w$ to those of $y$ is consistent precisely because it solves the population
constraints defining $\Wstar$ while accounting for the noise term, rather than
minimizing a squared error that conflates signal and noise. Two extensions are natural.
First, our \Cref{lem:comono} is distribution-free, so the population loss~\eqref{eq:poploss}
generalizes beyond the Gaussian design to
$\ell(w) = \E[(F_S^{-1}(U) - F_Y^{-1}(U))^2]$ for a uniform $U$; characterizing $\Wstar$
for heavy-tailed or asymmetric features is then a matter of computing the relevant
comonotone integrals. Second, the analysis extends to the replicated-experiment setting
of~\cite{abid2017shuffled}, where partial ordering information across independent shuffles
should shrink the ambiguity manifold $\Wstar$ toward a point.

% ============================================================
\section{Conclusion}
% ============================================================

We generalized the inconsistency-and-bias theorem for shuffled linear regression from
the scalar case to arbitrary dimension and arbitrary Gaussian covariance. The shuffled
least-squares loss converges to a population loss governed by two scalar functionals of
the weights, so the estimator converges to a moment-matching set on which the
feature-covariance norm is inflated by exactly the noise variance, independently of the
dimension. The result recovers the known one-dimensional formula as a special case and
is confirmed by simulation across dimensions.

% ============================================================
\section*{Code and data availability}\label{sec:availability}
\addcontentsline{toc}{section}{Code and data availability}
All code, experiment scripts, result figures, and the proof in machine-readable form
are publicly available as a Hugging Face Space at
\begin{center}
  \url{https://huggingface.co/spaces/abidlabs/shuffled-linear-regression}.
\end{center}
The Space hosts an interactive demo (built with Gradio) that draws fresh synthetic
data and shows, in real time and for any chosen dimension, noise level, feature mean,
and covariance structure, that the shuffled least-squares estimator is inconsistent:
the feature-covariance norm of the estimate is amplified by exactly $\sigE^2$ rather
than converging to the truth. The repository also contains the standalone estimator
library, the scripts that generate every figure in this paper, and the source of the
paper itself, so that all reported results can be reproduced end to end.

% ============================================================
\begin{thebibliography}{9}

\bibitem{abid2017shuffled}
A.~Abid, A.~Poon, and J.~Zou.
\newblock Linear regression with shuffled labels.
\newblock \emph{arXiv preprint arXiv:1705.01342}, 2017.

\bibitem{pananjady2017denoising}
A.~Pananjady, M.~J. Wainwright, and T.~A. Courtade.
\newblock Linear regression with shuffled data: Statistical and computational
limits of permutation recovery.
\newblock \emph{IEEE Transactions on Information Theory}, 64(5):3286--3300, 2018.

\bibitem{unnikrishnan2018unlabeled}
J.~Unnikrishnan, S.~Haghighatshoar, and M.~Vetterli.
\newblock Unlabeled sensing with random linear measurements.
\newblock \emph{IEEE Transactions on Information Theory}, 64(5):3237--3253, 2018.

\bibitem{hoeffding1940}
W.~Hoeffding.
\newblock Masstabinvariante Korrelationstheorie.
\newblock \emph{Schriften des Mathematischen Instituts der Universit\"at Berlin},
5:179--233, 1940.

\bibitem{david2003order}
H.~A. David and H.~N. Nagaraja.
\newblock \emph{Order Statistics}.
\newblock Wiley, 3rd edition, 2003.

\bibitem{vandervaart1998}
A.~W. van~der Vaart.
\newblock \emph{Asymptotic Statistics}.
\newblock Cambridge University Press, 1998.

\end{thebibliography}

\end{document}