# Efficient Algorithms for Outlier-Robust Regression

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

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2018.

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

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Robust Imitation Learning from Corrupted Demonstrations](https://mlsanity.com/paper/2201.12594/) (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)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [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)
- [Reducing Certified Regression to Certified Classification for General Poisoning Attacks](https://mlsanity.com/paper/2208.13904/) (2022)

## Abstract (arXiv)

We give the first polynomial-time algorithm for performing linear or polynomial regression resilient to adversarial corruptions in both examples and labels. Given a sufficiently large (polynomial-size) training set drawn i.i.d. from distribution D and subsequently corrupted on some fraction of points, our algorithm outputs a linear function whose squared error is close to the squared error of the best-fitting linear function with respect to D, assuming that the marginal distribution of D over the input space is certifiably hypercontractive. This natural property is satisfied by many well-studied distributions such as Gaussian, strongly log-concave distributions and, uniform distribution on the hypercube among others. We also give a simple statistical lower bound showing that some distributional assumption is necessary to succeed in this setting. These results are the first of their kind and were not known to be even information-theoretically possible prior to our work. Our approach is based on the sum-of-squares (SoS) method and is inspired by the recent applications of the method for parameter recovery problems in unsupervised learning. Our algorithm can be seen as a natural convex relaxation of the following conceptually simple non-convex optimization problem: find a linear function and a large subset of the input corrupted sample such that the least squares loss of the function over the subset is minimized over all possible large subsets.