  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.
