Towards Practical Robustness Auditing for Linear Regression
Daniel Freund Samuel B. Hopkins
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.