Provably Auditing Ordinary Least Squares in Low Dimensions

Ankur Moitra, Dhruv Rohatgi

Abstract

Measuring the stability of conclusions derived from Ordinary Least Squares (OLS) 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.

Introduction

Ordinary Least Squares (OLS) is the foundational tool of the social and physical sciences, used to estimate the relationship between a "treatment" variable and a "response." However, the reliability of these estimates is often called into question during the ongoing "replication crisis." A central concern is that a statistically significant result might be driven by a tiny, idiosyncratic subset of the data rather than a robust underlying trend.

To address this, researchers have turned to finite-sample stability: a metric defined as the minimum number of data points that must be removed from a dataset to flip the sign of a specific regression coefficient. If a conclusion can be overturned by removing only a handful of points, it is considered fragile. Until now, the primary method for estimating this stability was a greedy heuristic that removes points based on individual influence. This paper provides the first efficient algorithms with provable guarantees to audit OLS stability, moving beyond heuristics to provide mathematical certification.

The Limitations of Greedy Auditing

The standard greedy approach calculates the "influence" of each data point individually and removes the most influential ones until the sign flips. While intuitive, this method has two major flaws:

  1. No Lower Bounds: It cannot certify that a conclusion is stable. It only provides an upper bound (i.e., "I found a way to flip the sign by removing $X$ points"), but it cannot prove that no smaller subset exists.
  2. Joint Influence: It fails to account for "jointly influential" points. A group of points might collectively exert massive pressure on the regression line even if no single point in that group appears suspicious on its own. In heterogeneous datasets, greedy heuristics can overestimate the number of points needed to flip a result by a factor of 30 or more.

Algorithmic Framework

The authors frame the auditing problem as a non-convex optimization challenge. While the problem is computationally hard in high dimensions, they demonstrate that it becomes tractable in the low-dimensional regime—where the number of covariates ($d$) is small relative to the number of samples ($n$).

Exact and Hardness Results

Using machinery from real algebraic geometry, specifically Renegar’s work on polynomial systems, the authors developed an exact algorithm that runs in $n^{O(d^3)}$ time. This establishes that for a fixed dimension, the problem is solvable in polynomial time. Conversely, they prove that under the Exponential Time Hypothesis (ETH), an exponential dependence on the dimension is likely unavoidable, as the problem cannot be solved in $n^{o(d)}$ time.

Practical Approximation Algorithms

To make auditing feasible for real-world applications, the paper introduces two approximation methods:

  • PartitionAndApprox: This algorithm divides the parameter space into regions where the complex, non-linear stability problem can be approximated by a simple Linear Program (LP).
  • NetApprox: This method uses a "net"—a finite set of representative points—over the parameter space to estimate stability with a bounded additive error.

These approximations rely on "anti-concentration" assumptions, which essentially ensure the data is not so pathologically clustered that infinitesimal shifts in the data lead to massive, unpredictable jumps in the regression output.

Empirical Validation: The Boston Housing Dataset

The authors applied their algorithms to the classic Boston Housing dataset, regressing house values against various feature pairs (156 combinations). The results highlight the practical utility of provable auditing:

  • Superior Estimation: On real-world data, the proposed algorithms estimated stability up to a factor of 3 better than the greedy heuristic, identifying much smaller subsets of points that could overturn conclusions.
  • Certification of Robustness: In several instances, the algorithms were able to mathematically certify that a conclusion remained valid even if a majority of the samples were removed. This level of assurance is impossible with heuristic methods.
  • Computational Efficiency: Despite the theoretical complexity, the approximation algorithms were implemented and successfully run on a standard laptop, processing the Boston dataset in under 30 hours.

Conclusion

This work represents a significant step forward in data auditing. By providing the first provable guarantees for OLS stability, the authors offer a path toward more transparent and reliable scientific reporting. While the "curse of dimensionality" currently limits these methods to models with a small number of features, the framework extends naturally to other techniques like Instrumental Variables (IV) regression. Future research will explore whether similar provable auditing is possible for more complex machine learning models, such as logistic regression.

Summary updated

Abstract

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.
BibTeX
@inproceedings{moitra2023provably,
  author = {Ankur Moitra and Dhruv Rohatgi},
  title = {{Provably Auditing Ordinary Least Squares in Low Dimensions}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=DlpCotqdTy},
}

Loading related content...

Figure