Linear Regression Under Misalignment: Algorithms and Theoretical Results

Performing regression is challenging in applications where training data is no longer aligned, arising due to anonymization, data fragmentation, or multi-source aggregation. Motivated by such scenarios, we study two related yet computationally distinct problems that arise when the correspondence between $d$-dimensional feature vectors and responses in linear regression is unknown. The first problem, referred to as the \emph{Shuffled Linear Regression} (SLR) problem, originally proposed in the machine learning community, considers the setting where feature vectors arrive as internally consistent $d$-dimensional units but their correspondence to response values is unknown. Prior work established an efficient exact solution only for the one-dimensional case. For higher dimensions ($d \geq 2$), the best known result is a $(1+\varepsilon)$ approximation scheme with running time $\mathcal{O}((n/\varepsilon)^d)$, where $n$ is the number of data points, leaving open the fundamental question of whether an exact polynomial-time algorithm exists for any fixed dimension $d$. \emph{Despite the extensive study in prior literature and established NP-hardness results for unbounded dimensions, the exact computational complexity of this problem for bounded $d$ has remained unresolved.} We resolve this open problem by providing the first exact polynomial-time algorithm via a geometric insight: the parameter space can be partitioned by $\binom{n}{2}$ separator hyperplanes into $O(n^{2d-2})$ regions, within each of which the optimal pairing remains unchanged. This reduces the exponential search over permutations to a polynomial search over regions, yielding the first exact polynomial-time algorithm for SLR with runtime $O(n^{2d-1}(d^2 + \log n))$, without any distributional assumptions. We initiate the study of the second problem, referred to as the \emph{\furlong} (\fur) problem, which considers a more challenging setting where neither the feature vectors themselves nor their correspondence to the response variable are internally aligned. For the \fur\ problem, we provide the first rigorous complexity and algorithmic results, proving that it is NP-hard even at $d = 2$. This establishes a qualitative gap : \fur\ is intractable even in low dimensions, whereas SLR admits an exact polynomial-time solution for fixed $d$.