# Efficient Algorithms and Lower Bounds for Robust Linear Regression

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2018.

## Built on by (most cited first, 30 of 76)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [Robust Nonparametric Regression under Poisoning Attack](https://mlsanity.com/paper/2305.16771/) (2023)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Understanding In-Context Learning of Linear Models in Transformers Through an Adversarial Lens](https://mlsanity.com/paper/2411.05189/) (2024)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (2022)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)

## Abstract (arXiv)

We study the problem of high-dimensional linear regression in a robust model where an ε-fraction of the samples can be adversarially corrupted. We focus on the fundamental setting where the covariates of the uncorrupted samples are drawn from a Gaussian distribution N(0, Sigma) on ℝd. We give nearly tight upper bounds and computational lower bounds for this problem. Specifically, our main contributions are as follows: For the case that the covariance matrix is known to be the identity, we give a sample near-optimal and computationally efficient algorithm that outputs a candidate hypothesis vector widehatβ which approximates the unknown regression vector β within ℓ2-norm O(ε log(1/ε) σ), where σ is the standard deviation of the random observation noise. An error of Omega (ε σ) is information-theoretically necessary, even with infinite sample size. Prior work gave an algorithm for this problem with sample complexity tildeOmega(d2/ε2) whose error guarantee scales with the ℓ2-norm of β. For the case of unknown covariance, we show that we can efficiently achieve the same error guarantee as in the known covariance case using an additional tildeO(d2/ε2) unlabeled examples. On the other hand, an error of O(ε σ) can be information-theoretically attained with O(d/ε2) samples. We prove a Statistical Query (SQ) lower bound providing evidence that this quadratic tradeoff in the sample size is inherent. More specifically, we show that any polynomial time SQ learning algorithm for robust linear regression (in Huber's contamination model) with estimation complexity O(d2-c), where c>0 is an arbitrarily small constant, must incur an error of Omega(√ε σ).