# Linear regression with partially mismatched data: local search with theoretical guarantees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 3 Jun 2021.

## Builds on (most cited first, 12 of 12)

- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Denoising Linear Models with Permuted Data](https://mlsanity.com/paper/1704.07461/) (2017)
- [Linear Regression with Shuffled Labels](https://mlsanity.com/paper/1705.01342/) (2017)
- [Linear Regression without Correspondences via Concave Minimization](https://mlsanity.com/paper/2003.07706/) (2020)
- [Signal Recovery from Unlabeled Samples](https://mlsanity.com/paper/1701.08701/) (2017)
- [A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Data](https://mlsanity.com/paper/1910.01623/) (2019)
- [Spherical Regression under Mismatch Corruption with Application to Automated Knowledge Translation](https://mlsanity.com/paper/1810.05679/) (2018)
- [Permutations Unlabeled beyond Sampling Unknown](https://mlsanity.com/paper/1812.00498/) (2018)
- [Stochastic EM for Shuffled Linear Regression](https://mlsanity.com/paper/1804.00681/) (2018)

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

- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)
- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

Linear regression is a fundamental modeling tool in statistics and related fields. In this paper, we study an important variant of linear regression in which the predictor-response pairs are partially mismatched. We use an optimization formulation to simultaneously learn the underlying regression coefficients and the permutation corresponding to the mismatches. The combinatorial structure of the problem leads to computational challenges. We propose and study a simple greedy local search algorithm for this optimization problem that enjoys strong theoretical guarantees and appealing computational performance. We prove that under a suitable scaling of the number of mismatched pairs compared to the number of samples and features, and certain assumptions on problem data; our local search algorithm converges to a nearly-optimal solution at a linear rate. In particular, in the noiseless case, our algorithm converges to the global optimal solution with a linear convergence rate. Based on this result, we prove an upper bound for the estimation error of the parameter. We also propose an approximate local search step that allows us to scale our approach to much larger instances. We conduct numerical experiments to gather further insights into our theoretical results, and show promising performance gains compared to existing approaches.