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 κ. 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 O(d/ε^4) samples, where d is the dimension and ε is the corruption rate, and achieves prediction error O(√(εκ)) under the condition εκ≲ 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(√(εκ)) when εκ≲ 1 require queries that take Ω(d^2) samples to simulate. Finally, we prove a low-degree polynomial lower bound that gives fine-grained evidence that, without assumptions such as εκ≲ 1, efficient algorithms may require Ω̃(mindε^2κ^2, ε^2d^2) samples to significantly outperform the trivial estimator that always guesses 0.