# Linear Regression under Missing or Corrupted Coordinates

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 68 references that are in the map.
- First posted on arXiv 23 Sep 2025.

## Builds on (most cited first, 30 of 31)

- [Generalized Out-of-Distribution Detection: A Survey](https://mlsanity.com/paper/2110.11334/) (2021)
- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics](https://mlsanity.com/paper/2104.11315/) (2021)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [What's a good imputation to predict with missing values?](https://mlsanity.com/paper/2106.00311/) (2021)
- [Graphical Models for Processing Missing Data](https://mlsanity.com/paper/1801.03583/) (2018)
- [On the consistency of supervised learning with missing values](https://mlsanity.com/paper/1902.06931/) (2019)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019)
- [Linear predictor on linearly-generated data with missing values: non consistency and solutions](https://mlsanity.com/paper/2002.00658/) (2020)
- [Truncated Linear Regression in High Dimensions](https://mlsanity.com/paper/2007.14539/) (2020)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [Tuned Models of Peer Assessment in MOOCs](https://mlsanity.com/paper/1307.2579/) (2013)
- [Imputation for High-Dimensional Linear Regression](https://mlsanity.com/paper/2001.09180/) (2020)
- [Efficient Truncated Linear Regression with Unknown Noise Variance](https://mlsanity.com/paper/2208.12042/) (2022)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers](https://mlsanity.com/paper/2008.08071/) (2020)
- [On Robust Mean Estimation under Coordinate-level Corruption](https://mlsanity.com/paper/2002.04137/) (2020)
- [Nonparametric classification with missing data](https://mlsanity.com/paper/2305.11672/) (2023)
- [Collaboratively Learning Linear Models with Structured Missing Data](https://mlsanity.com/paper/2307.11947/) (2023)
- [Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise](https://mlsanity.com/paper/2411.06697/) (2024)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)

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

- [High-Dimensional Gaussian Mean Estimation under Realizable Contamination](https://mlsanity.com/paper/2603.16798/) (2026)

## Abstract (arXiv)

We study multivariate linear regression under Gaussian covariates in two settings, where data may be erased or corrupted by an adversary under a coordinate-wise budget. In the incomplete data setting, an adversary may inspect the dataset and delete entries in up to an η-fraction of samples per coordinate; a strong form of the Missing Not At Random model. In the corrupted data setting, the adversary instead replaces values arbitrarily, and the corruption locations are unknown to the learner. Despite substantial work on missing data, linear regression under such adversarial missingness remains poorly understood, even information-theoretically. Unlike the clean setting, where estimation error vanishes with more samples, here the optimal error remains a positive function of the problem parameters. Our main contribution is to characterize this error up to constant factors across essentially the entire parameter range. Specifically, we establish novel information-theoretic lower bounds on the achievable error that match the error of (computationally efficient) algorithms. A key implication is that, perhaps surprisingly, the optimal error in the missing data setting matches that in the corruption setting-so knowing the corruption locations offers no general advantage.