# Surprises in adversarially-trained linear regression

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 47 references that are in the map.
- First posted on arXiv 25 May 2022.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [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)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Adversarial Examples Are Not Bugs, They Are Features](https://mlsanity.com/paper/1905.02175/) (2019)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Adversarial Examples: Attacks and Defenses for Deep Learning](https://mlsanity.com/paper/1712.07107/) (2017)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Recent Advances in Adversarial Training for Adversarial Robustness](https://mlsanity.com/paper/2102.01356/) (2021)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Adversarial Attacks and Defences Competition](https://mlsanity.com/paper/1804.00097/) (2018)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [Analysis of classifiers' robustness to adversarial perturbations](https://mlsanity.com/paper/1502.02590/) (2015)
- [Sparse DNNs with Improved Adversarial Robustness](https://mlsanity.com/paper/1810.09619/) (2018)
- [Learning with a Strong Adversary](https://mlsanity.com/paper/1511.03034/) (2015)
- [Precise Statistical Analysis of Classification Accuracies for Adversarial Training](https://mlsanity.com/paper/2010.11213/) (2020)
- [The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression](https://mlsanity.com/paper/2201.05149/) (2022)
- [The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization](https://mlsanity.com/paper/2002.11080/) (2020)
- [Foolish Crowds Support Benign Overfitting](https://mlsanity.com/paper/2110.02914/) (2021)
- [On the Generalization Properties of Adversarial Training](https://mlsanity.com/paper/2008.06631/) (2020)
- [Adversarially Robust Estimate and Risk Analysis in Linear Regression](https://mlsanity.com/paper/2012.10278/) (2020)
- [Overparameterized Linear Regression under Adversarial Attacks](https://mlsanity.com/paper/2204.06274/) (2022)
- [Tight bounds for minimum l1-norm interpolation of noisy data](https://mlsanity.com/paper/2111.05987/) (2021)
- [Asymptotic Behavior of Adversarial Training in Binary Classification](https://mlsanity.com/paper/2010.13275/) (2020)
- [Combating Adversarial Attacks Using Sparse Representations](https://mlsanity.com/paper/1803.03880/) (2018)

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

- [Adversarial robustness of amortized Bayesian inference](https://mlsanity.com/paper/2305.14984/) (2023)
- [Asymptotic Behavior of Adversarial Training Estimator under ℓ_∞-Perturbation](https://mlsanity.com/paper/2401.15262/) (2024)

## Abstract (arXiv)

State-of-the-art machine learning models can be vulnerable to very small input perturbations that are adversarially constructed. Adversarial training is an effective approach to defend against such examples. It is formulated as a min-max problem, searching for the best solution when the training data was corrupted by the worst-case attacks. For linear regression problems, adversarial training can be formulated as a convex problem. We use this reformulation to make two technical contributions: First, we formulate the training problem as an instance of robust regression to reveal its connection to parameter-shrinking methods, specifically that ℓ_∞-adversarial training produces sparse solutions. Secondly, we study adversarial training in the overparameterized regime, i.e. when there are more parameters than data. We prove that adversarial training with small disturbances gives the solution with the minimum-norm that interpolates the training data. Ridge regression and lasso approximate such interpolating solutions as their regularization parameter vanishes. By contrast, for adversarial training, the transition into the interpolation regime is abrupt and for non-zero values of disturbance. This result is proved and illustrated with numerical examples.