# Linear Regression with Shuffled Labels

arXiv: https://arxiv.org/abs/1705.01342 · HTML: https://mlsanity.com/paper/1705.01342/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2017.

## Built on by (most cited first, 11 of 11)

- [Low-rank Matrix Recovery With Unknown Correspondence](https://mlsanity.com/paper/2110.07959/) (2021)
- [Permuted and Unlinked Monotone Regression in ℝd: an approach based on mixture modeling and optimal transport](https://mlsanity.com/paper/2201.03528/) (2022)
- [Linear regression with partially mismatched data: local search with theoretical guarantees](https://mlsanity.com/paper/2106.02175/) (2021)
- [Shuffled linear regression through graduated convex relaxation](https://mlsanity.com/paper/2209.15608/) (2022)
- [Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group](https://mlsanity.com/paper/2111.01767/) (2021)
- [Smoothness and effective regularizations in learned embeddings for shape matching](https://mlsanity.com/paper/2112.07289/) (2021)
- [Shuffled Multi-Channel Sparse Signal Recovery](https://mlsanity.com/paper/2212.07368/) (2022)
- [Shuffled Linear Regression via Spectral Matching](https://mlsanity.com/paper/2410.00078/) (2024)
- [Optimal Estimator for Linear Regression with Shuffled Labels](https://mlsanity.com/paper/2310.01326/) (2023)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)
- [Cross-Channel Unlabeled Sensing over a Union of Signal Subspaces](https://mlsanity.com/paper/2506.09773/) (2025)

## Abstract (arXiv)

Is it possible to perform linear regression on datasets whose labels are shuffled with respect to the inputs? We explore this question by proposing several estimators that recover the weights of a noisy linear model from labels that are shuffled by an unknown permutation. We show that the analog of the classical least-squares estimator produces inconsistent estimates in this setting, and introduce an estimator based on the self-moments of the input features and labels. We study the regimes in which each estimator excels, and generalize the estimators to the setting where partial ordering information is available in the form of experiments replicated independently. The result is a framework that enables robust inference, as we demonstrate by experiments on both synthetic and standard datasets, where we are able to recover approximate weights using only shuffled labels. Our work demonstrates that linear regression in the absence of complete ordering information is possible and can be of practical interest, particularly in experiments that characterize populations of particles, such as flow cytometry.