# Robustness Auditing for Linear Regression: To Singularity and Beyond

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 10 Oct 2024.

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

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference?](https://mlsanity.com/paper/2011.14999/) (2020)
- [How Hard Is Robust Mean Estimation?](https://mlsanity.com/paper/1903.07870/) (2019)
- [Provably Auditing Ordinary Least Squares in Low Dimensions](https://mlsanity.com/paper/2205.14284/) (2022)
- [Towards Practical Robustness Auditing for Linear Regression](https://mlsanity.com/paper/2307.16315/) (2023)

## Built on by (most cited first, 6 of 6)

- [What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization](https://mlsanity.com/paper/2505.21692/) (2025)
- [Dropping Just a Handful of Preferences Can Change Top Large Language Model Rankings](https://mlsanity.com/paper/2508.11847/) (2025)
- [Rescaled Influence Functions: Accurate Data Attribution in High Dimension](https://mlsanity.com/paper/2506.06656/) (2025)
- [Testing Most Influential Sets](https://mlsanity.com/paper/2510.20372/) (2025)
- [On the Accuracy of Newton Step and Influence Function Data Attributions](https://mlsanity.com/paper/2512.12572/) (2025)
- [Finding Most Influential Sets](https://mlsanity.com/paper/2606.05919/) (2026)

## Abstract (arXiv)

It has recently been discovered that the conclusions of many highly influential econometrics studies can be overturned by removing a very small fraction of their samples (often less than 0.5%). These conclusions are typically based on the results of one or more Ordinary Least Squares (OLS) regressions, raising the question: given a dataset, can we certify the robustness of an OLS fit on this dataset to the removal of a given number of samples? Brute-force techniques quickly break down even on small datasets. Existing approaches which go beyond brute force either can only find candidate small subsets to remove (but cannot certify their non-existence) [BGM20, KZC21], are computationally intractable beyond low dimensional settings [MR22], or require very strong assumptions on the data distribution and too many samples to give reasonable bounds in practice [BP21, FH23]. We present an efficient algorithm for certifying the robustness of linear regressions to removals of samples. We implement our algorithm and run it on several landmark econometrics datasets with hundreds of dimensions and tens of thousands of samples, giving the first non-trivial certificates of robustness to sample removal for datasets of dimension 4 or greater. We prove that under distributional assumptions on a dataset, the bounds produced by our algorithm are tight up to a 1 + o(1) multiplicative factor.