# On efficient robust regression with subquadratic samples

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 67 references that are in the map.
- First posted on arXiv 18 May 2026.

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

- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [A spectral algorithm for robust regression with subgaussian rates](https://mlsanity.com/paper/2007.06072/) (2020)
- [A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise](https://mlsanity.com/paper/2209.02856/) (2022)

## Abstract (arXiv)

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.