# Robust Linear Regression: Phase-Transitions and Precise Tradeoffs for General Norms

arXiv: https://arxiv.org/abs/2308.00556 · HTML: https://mlsanity.com/paper/2308.00556/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 39 references that are in the map.
- First posted on arXiv 1 Aug 2023.

## Builds on (most cited first, 23 of 23)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize](https://mlsanity.com/paper/2203.06176/) (2022)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Precise Statistical Analysis of Classification Accuracies for Adversarial Training](https://mlsanity.com/paper/2010.11213/) (2020)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression](https://mlsanity.com/paper/2201.05149/) (2022)
- [Provable tradeoffs in adversarially robust classification](https://mlsanity.com/paper/2006.05161/) (2020)
- [Adversarially Robust Estimate and Risk Analysis in Linear Regression](https://mlsanity.com/paper/2012.10278/) (2020)
- [Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes](https://mlsanity.com/paper/2106.02630/) (2021)
- [Adversarial robustness for latent models: Revisiting the robust-standard accuracies tradeoff](https://mlsanity.com/paper/2110.11950/) (2021)
- [Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond](https://mlsanity.com/paper/2301.13486/) (2023)

## Built on by (most cited first, 2 of 2)

- [On the Existence of Consistent Adversarial Attacks in High-Dimensional Linear Classification](https://mlsanity.com/paper/2506.12454/) (2025)
- [The Fourth Quadrant: A Stylized View of Benign Misfitting](https://mlsanity.com/paper/2608.01032/) (2026)

## Abstract (arXiv)

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.