# Provably Auditing Ordinary Least Squares in Low Dimensions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 57 references that are in the map.
- First posted on arXiv 28 May 2022.

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

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Least Squares Generative Adversarial Networks](https://mlsanity.com/paper/1611.04076/) (2016)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [On the Accuracy of Influence Functions for Measuring Group Effects](https://mlsanity.com/paper/1905.13289/) (2019)
- [Why Is My Classifier Discriminatory?](https://mlsanity.com/paper/1805.12002/) (2018)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Understanding the Origins of Bias in Word Embeddings](https://mlsanity.com/paper/1810.03611/) (2018)
- [Robust Validation: Confident Predictions Even When Distributions Shift](https://mlsanity.com/paper/2008.04267/) (2020)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [A Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1806.00550/) (2018)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Contamination Attacks and Mitigation in Multi-Party Machine Learning](https://mlsanity.com/paper/1901.02402/) (2019)
- [The s-value: evaluating stability with respect to distributional shifts](https://mlsanity.com/paper/2105.03067/) (2021)

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

- [Most Influential Subset Selection: Challenges, Promises, and Beyond](https://mlsanity.com/paper/2409.18153/) (2024)
- [Dropping Just a Handful of Preferences Can Change Top Large Language Model Rankings](https://mlsanity.com/paper/2508.11847/) (2025)
- [Towards Practical Robustness Auditing for Linear Regression](https://mlsanity.com/paper/2307.16315/) (2023)
- [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)

Measuring the stability of conclusions derived from Ordinary Least Squares linear regression is critically important, but most metrics either only measure local stability (i.e. against infinitesimal changes in the data), or are only interpretable under statistical assumptions. Recent work proposes a simple, global, finite-sample stability metric: the minimum number of samples that need to be removed so that rerunning the analysis overturns the conclusion, specifically meaning that the sign of a particular coefficient of the estimated regressor changes. However, besides the trivial exponential-time algorithm, the only approach for computing this metric is a greedy heuristic that lacks provable guarantees under reasonable, verifiable assumptions; the heuristic provides a loose upper bound on the stability and also cannot certify lower bounds on it. We show that in the low-dimensional regime where the number of covariates is a constant but the number of samples is large, there are efficient algorithms for provably estimating (a fractional version of) this metric. Applying our algorithms to the Boston Housing dataset, we exhibit regression analyses where we can estimate the stability up to a factor of 3 better than the greedy heuristic, and analyses where we can certify stability to dropping even a majority of the samples.