Provably Auditing Ordinary Least Squares in Low Dimensions

Ankur Moitra, Dhruv Rohatgi

Introduction

In high-stakes fields like econometrics and causal inference, linear regression is a foundational tool for determining the positive or negative effects of variables, such as policy changes. However, these models can be surprisingly "unstable." Sometimes, removing less than 1% of the training data can completely flip the sign of a regression coefficient, entirely reversing a study's conclusion.

While researchers often use "greedy" heuristics to find these influential data points—typically by removing points with the highest individual influence scores—these methods have a critical flaw: they cannot certify stability. If a greedy search fails to flip the sign, it does not guarantee a flip is impossible; it merely means the heuristic failed to find the right subset. This paper introduces the first polynomial-time algorithms to provably "audit" the stability of Ordinary Least Squares (OLS) regression in low dimensions, providing rigorous lower bounds to guarantee that no subset of a certain size can overturn the result.

Methods: Fractional Relaxation

The authors move away from the "integral" problem of removing whole data points, which is combinatorially explosive, to a fractional relaxation. By defining "finite-sample stability" to allow the removal of fractions of data points, they transform the challenge into a continuous optimization task.

They propose three main algorithmic approaches:

  1. Exact Algorithm: Utilizing advanced tools from algebraic geometry, they show the problem is solvable in $n^{O(d^3)}$ time. While theoretically significant, this remains too slow for practical application.
  2. PARTITIONANDAPPROX: This algorithm partitions the space of possible regression solutions into regions where the complex, non-convex stability problem can be approximated by a simpler Linear Program (LP).
  3. NETAPPROX: A simpler approach that builds a "net" (a representative sample of points) over the space of possible residuals. If the data satisfies certain "anti-concentration" properties, this provides a very tight approximation.

The authors also provide a hardness result, proving that under the Exponential Time Hypothesis, any algorithm for exact stability must scale exponentially with the number of dimensions ($d$).

Key Insights

  • The Failure of "Local" Influence: Traditional influence scores evaluate points individually. However, points can be "jointly influential." Removing a group of points might change the covariance of the remaining data, making other points more influential—a "covariance shift" that greedy heuristics often miss.
  • Low Dimensions are High Stakes: While modern machine learning often focuses on thousands of features, critical policy decisions frequently rely on regressions with only 2 to 5 covariates. In these regimes, $n$ is large but $d$ is small, making polynomial-time algorithms in $n$ highly practical.
  • Fractional is "Close Enough": The authors demonstrate that in low dimensions, the fractional version of stability is a very close proxy for the discrete version (within $d+1$ points), justifying the continuous optimization approach.

Key Results

The paper evaluates these algorithms using synthetic heterogeneous data (designed to trick greedy heuristics), isotropic Gaussian data (to test noise levels), and the real-world Boston Housing dataset.

Comparison of stability bounds on synthetic data
  • Outperforming Heuristics: On synthetic "tricky" data designed with sub-populations that are jointly influential but individually quiet, the authors' upper bound found sign-flipping subsets significantly smaller than those found by the greedy baseline. As shown in the evaluations, the proposed methods (like the Net upper bound and LP lower bound) successfully identify much smaller subsets required to overturn the model compared to the greedy approach.
Effect of noise level on sample weight removed
  • Certification: On the Boston Housing dataset, the authors certifiably bounded stability within a factor of two for most feature pairs. They successfully certified that some conclusions were stable even if up to 50% of the data were dropped.
  • Identifying Fragility: Conversely, they found regressions where the greedy heuristic claimed the model was stable, but their algorithm proved that removing just 8% of the data would nullify the result.

Limitations and Future Work

The primary limitation of this approach is the curse of dimensionality. Because the algorithms scale exponentially with the number of covariates ($d$), they are currently only feasible for "low-dimensional" regimes (typically $d \leq 3$ or $4$ in practice).

Future work could involve developing more efficient heuristics that still provide one-sided provable guarantees for higher-dimensional models, extending these auditing tools to more complex models like Random Forests or Neural Networks, and exploring different "anti-concentration" assumptions that might allow for faster approximation algorithms.

Summary updated

Abstract

Auditing the stability of a machine learning model to small changes in the training procedure is critical for engendering trust in practical applications. For example, a model should not be overly sensitive to removing a small fraction of its training data. However, algorithmically validating this property seems computationally challenging, even for the simplest of models: Ordinary Least Squares (OLS) linear regression. Concretely, recent work defines the stability of a regression as the minimum number of samples that need to be removed so that rerunning the analysis overturns the conclusion (Broderick et al., 2020), specifically meaning that the sign of a particular coefficient of the OLS regressor changes. But the only known approach for estimating this metric, besides the obvious exponential-time algorithm, is a greedy heuristic that may produce severe overestimates and therefore cannot certify stability. We show that stability can be efficiently certified in the low-dimensional regime: when the number of covariates is a constant but the number of samples is large, there are polynomial-time algorithms for estimating (a fractional version of) stability, with provable approximation guarantees. Applying our algorithms to the Boston Housing dataset, we exhibit regression analyses where our estimator outperforms the greedy heuristic, and can successfully certify stability even in the regime where a constant fraction of the samples are dropped.
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