# Finite-Sample Inference for Sparsely Permuted Linear Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 36 references that are in the map.
- First posted on arXiv 21 Jan 2026.

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

- [Exact post-selection inference, with application to the lasso](https://mlsanity.com/paper/1311.6238/) (2013)
- [Optimal Inference After Model Selection](https://mlsanity.com/paper/1410.2597/) (2014)
- [Universal Inference](https://mlsanity.com/paper/1912.11436/) (2019)
- [More powerful post-selection inference, with application to the Lasso](https://mlsanity.com/paper/1801.09037/) (2018)
- [Ridge Regularization: an Essential Concept in Data Science](https://mlsanity.com/paper/2006.00371/) (2020)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Isotonic regression with unknown permutations: Statistics, computation, and adaptation](https://mlsanity.com/paper/2009.02609/) (2020)
- [Uncoupled isotonic regression via minimum Wasserstein deconvolution](https://mlsanity.com/paper/1806.10648/) (2018)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Optimal Permutation Recovery in Permuted Monotone Matrix Model](https://mlsanity.com/paper/1911.10604/) (2019)
- [A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Data](https://mlsanity.com/paper/1910.01623/) (2019)
- [Permuted and Unlinked Monotone Regression in ℝd: an approach based on mixture modeling and optimal transport](https://mlsanity.com/paper/2201.03528/) (2022)
- [Repro Samples Method for Finite- and Large-Sample Inferences](https://mlsanity.com/paper/2206.06421/) (2022)
- [Finite- and Large- Sample Inference for Model and Coefficients in High-dimensional Linear Regression with Repro Samples](https://mlsanity.com/paper/2209.09299/) (2022)
- [Linear Regression with an Unknown Permutation: Statistical and Computational Limits](https://mlsanity.com/paper/1608.02902/) (2016)
- [Linear regression with partially mismatched data: local search with theoretical guarantees](https://mlsanity.com/paper/2106.02175/) (2021)
- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)
- [Repro Samples Method for a Performance Guaranteed Inference in General and Irregular Inference Problems](https://mlsanity.com/paper/2402.15004/) (2024)
- [Shuffled Linear Regression via Spectral Matching](https://mlsanity.com/paper/2410.00078/) (2024)
- [Repro Samples Method for Model-Free Inference in High-Dimensional Binary Classification](https://mlsanity.com/paper/2510.01468/) (2025)

## Abstract (arXiv)

We study a linear observation model with an unknown permutation called textitpermuted/shuffled linear regression, where responses and covariates are mismatched and the permutation forms a discrete, factorial-size parameter. The permutation is a key component of the data-generating process, yet its statistical investigation remains challenging due to its discrete nature. We develop a general statistical inference framework on the permutation and regression coefficients. First, we introduce a localization step that reduces the permutation space to a small candidate set building on recent advances in the repro samples method, whose miscoverage decays polynomially with the number of Monte Carlo samples. Then, based on this localized set, we provide statistical inference procedures: a conditional Monte Carlo test of permutation structures with valid finite-sample Type-I error control. We also develop coefficient inference that remains valid under alignment uncertainty of permutations. For computational purposes, we develop a linear assignment problem computable in polynomial time and demonstrate that, with high probability, the solution is equivalent to that of the conventional least squares with large computational cost. Extensions to partially permuted designs and ridge regularization are further discussed. Extensive simulations and an application to air-quality data corroborate finite-sample validity, strong power to detect mismatches, and practical scalability.