# Towards Practical Robustness Auditing for Linear Regression

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 31 references that are in the map.
- First posted on arXiv 30 Jul 2023.

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

- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [How Many and Which Training Points Would Need to be Removed to Flip this Prediction?](https://mlsanity.com/paper/2302.02169/) (2023)
- [Provably Auditing Ordinary Least Squares in Low Dimensions](https://mlsanity.com/paper/2205.14284/) (2022)

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

- [Most Influential Subset Selection: Challenges, Promises, and Beyond](https://mlsanity.com/paper/2409.18153/) (2024)
- [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)
- [Robustness Auditing for Linear Regression: To Singularity and Beyond](https://mlsanity.com/paper/2410.07916/) (2024)
- [Testing Most Influential Sets](https://mlsanity.com/paper/2510.20372/) (2025)
- [Finding Most Influential Sets](https://mlsanity.com/paper/2606.05919/) (2026)

## Abstract (arXiv)

We investigate practical algorithms to find or disprove the existence of small subsets of a dataset which, when removed, reverse the sign of a coefficient in an ordinary least squares regression involving that dataset. We empirically study the performance of well-established algorithmic techniques for this task -- mixed integer quadratically constrained optimization for general linear regression problems and exact greedy methods for special cases. We show that these methods largely outperform the state of the art and provide a useful robustness check for regression problems in a few dimensions. However, significant computational bottlenecks remain, especially for the important task of disproving the existence of such small sets of influential samples for regression problems of dimension 3 or greater. We make some headway on this challenge via a spectral algorithm using ideas drawn from recent innovations in algorithmic robust statistics. We summarize the limitations of known techniques in several challenge datasets to encourage further algorithmic innovation.