Robust Linear Regression: Phase-Transitions and Precise Tradeoffs for
  General Norms
Elvis Dohmatob Meyer Scetbon
In this paper, we investigate the impact of test-time adversarial attacks on
linear regression models and determine the optimal level of robustness that any
model can reach while maintaining a given level of standard predictive
performance (accuracy). Through quantitative estimates, we uncover fundamental
tradeoffs between adversarial robustness and accuracy in different regimes. We
obtain a precise characterization which distinguishes between regimes where
robustness is achievable without hurting standard accuracy and regimes where a
tradeoff might be unavoidable. Our findings are empirically confirmed with
simple experiments that represent a variety of settings. This work applies to
feature covariance matrices and attack norms of any nature, and extends beyond
previous works in this area.