Sample Complexity of Linear Regression under Random-Location Coordinate Corruptions

We study Gaussian linear regression under coordinate-wise corruptions and missingness in high dimensions. A large body of work in statistics investigates estimation under different missingness and corruption mechanisms—ranging from missing completely at random to missing not at random—each leading to qualitatively different behaviors. Recent work on the problem considered a strong missing-not-at-random model, where an adversary can inspect the data and corrupt or erase an $\eta$-fraction of entries in each coordinate. A striking consequence of this model is an information-theoretic breakdown at $\eta = \Theta(1/\sqrt{d})$, beyond which non-trivial estimation is impossible even with infinite samples—an unusually small threshold compared to classical robust estimation settings. A natural question is whether this phenomenon is inherent or a consequence of adversarial control over corruption locations. To investigate this, we consider a more benign model in which corruption locations are chosen at random, and the adversary can affect the data only in a subset of these locations. We show that randomizing the locations fundamentally changes the answer. There is no sharp infinite-sample breakdown: non-trivial estimation is now possible for every $\eta < 1$. However, the price is sample complexity. We prove matching upper and lower bounds showing that the sample complexity for non-trivial estimation scales exponentially with $\eta^2 d$. Additionally, this sample complexity also includes a dependence on the signal-to-noise ratio $\sigma^2 / \|\beta\|^2$ which is another new phenomenon in this model.