On efficient robust regression with subquadratic samples

Abstract

We revisit the problem of robust linear regression under Gaussian covariates with an unknown covariance matrix of condition number $\hat{I}º$. For this fundamental problem, significant gaps remain in our understanding of the trade-offs among sample complexity, condition number, runtime, and prediction error for efficient algorithms. Our first result is a near-linear-time algorithm that uses $\tilde{O}(d/\hat{I}{\mu }^4)$ samples, where $d$ is the dimension and $\hat{I}\mu$ is the corruption rate, and achieves prediction error $O(\sqrt{\hat{I}\mu \hat{I}º})$ under the condition $\hat{I}\mu \hat{I}º\lesssim 1$, improving over all prior works. We complement this result with a Statistical Query (SQ) lower bound showing that efficient SQ algorithms achieving error $o(\sqrt{\hat{I}\mu \hat{I}º})$ when $\hat{I}\mu \hat{I}º\lesssim 1$ require queries that take $\hat{I}\text{c◯}(d^2)$ samples to simulate. Finally, we prove a low-degree polynomial lower bound that gives fine-grained evidence that, without assumptions such as $\hat{I}\mu \hat{I}º\lesssim 1$, efficient algorithms may require $\tilde{\hat{I}}\text{c◯}\left(\min \{d\hat{I}{\mu }^2\hat{I}{º}^2,\hat{I}{\mu }^2{d}^2\}\right)$ samples to significantly outperform the trivial estimator that always guesses $0$.

Accepted at COLT 2026