On efficient robust regression with subquadratic samples

We revisit the problem of robust linear regression under Gaussian covariates with an unknown covariance matrix of condition number kappa. 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 widetildeO(d/ε4) samples, where d is the dimension and ε is the corruption rate, and achieves prediction error O(√εkappa) under the condition εkappa 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(√εkappa) when ε kappa lesssim 1 require queries that take Omega(d2) samples to simulate. Finally, we prove a low-degree polynomial lower bound that gives fine-grained evidence that, without assumptions such as ε kappa lesssim 1, efficient algorithms may require tildeOmegaleft(mindε2kappa2, ε2d2right) samples to significantly outperform the trivial estimator that always guesses 0.