# Overparameterized Linear Regression under Adversarial Attacks

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 63 references that are in the map.
- First posted on arXiv 13 Apr 2022.

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

- [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)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [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)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Adversarial Examples: Attacks and Defenses for Deep Learning](https://mlsanity.com/paper/1712.07107/) (2017)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Unsolved Problems in ML Safety](https://mlsanity.com/paper/2109.13916/) (2021)
- [High-dimensional dynamics of generalization error in neural networks](https://mlsanity.com/paper/1710.03667/) (2017)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization](https://mlsanity.com/paper/2008.06786/) (2020)
- [Adversarial Attacks and Defences Competition](https://mlsanity.com/paper/1804.00097/) (2018)
- [Scaling description of generalization with number of parameters in deep learning](https://mlsanity.com/paper/1901.01608/) (2019)

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

- [Deep networks for system identification: a Survey](https://mlsanity.com/paper/2301.12832/) (2023)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Regularization properties of adversarially-trained linear regression](https://mlsanity.com/paper/2310.10807/) (2023)
- [Robust Nonparametric Regression under Poisoning Attack](https://mlsanity.com/paper/2305.16771/) (2023)
- [Sup-Norm Convergence of Deep Neural Network Estimator for Nonparametric Regression by Adversarial Training](https://mlsanity.com/paper/2307.04042/) (2023)
- [Efficient Optimization Algorithms for Linear Adversarial Training](https://mlsanity.com/paper/2410.12677/) (2024)
- [Dense Hopfield Networks in the Teacher-Student Setting](https://mlsanity.com/paper/2401.04191/) (2024)
- [Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization](https://mlsanity.com/paper/2510.20883/) (2025)
- [Surprises in adversarially-trained linear regression](https://mlsanity.com/paper/2205.12695/) (2022)
- [Over-parameterization and Adversarial Robustness in Neural Networks: An Overview and Empirical Analysis](https://mlsanity.com/paper/2406.10090/) (2024)
- [Minimax rates of convergence for nonparametric regression under adversarial attacks](https://mlsanity.com/paper/2410.09402/) (2024)
- [Risk Analysis and Design Against Adversarial Actions](https://mlsanity.com/paper/2505.01130/) (2025)
- [On the Existence of Consistent Adversarial Attacks in High-Dimensional Linear Classification](https://mlsanity.com/paper/2506.12454/) (2025)
- [On the ISS Property of the Gradient Flow for Single Hidden-Layer Neural Networks with Linear Activations](https://mlsanity.com/paper/2305.09904/) (2023)
- [Asymptotic Behavior of Adversarial Training Estimator under ℓ_∞-Perturbation](https://mlsanity.com/paper/2401.15262/) (2024)
- [Adversarial Machine Learning Attacks on Financial Reporting via Maximum Violated Multi-Objective Attack](https://mlsanity.com/paper/2507.05441/) (2025)
- [An integrated perspective of robustness in regression through the lens of the bias-variance trade-off](https://mlsanity.com/paper/2407.10418/) (2024)
- [Analysis of the vulnerability of machine learning regression models to adversarial attacks using data from 5G wireless networks](https://mlsanity.com/paper/2505.00487/) (2025)
- [Adversarial generalization of unfolding (model-based) networks](https://mlsanity.com/paper/2509.15370/) (2025)
- [A Robust Optimization Approach to Sparse Principal Component Analysis](https://mlsanity.com/paper/2606.03553/) (2026)
- [Adversarial Training of Linear Models under Stealthy Attacks](https://mlsanity.com/paper/2608.25681/) (2026)

## Abstract (arXiv)

We study the error of linear regression in the face of adversarial attacks. In this framework, an adversary changes the input to the regression model in order to maximize the prediction error. We provide bounds on the prediction error in the presence of an adversary as a function of the parameter norm and the error in the absence of such an adversary. We show how these bounds make it possible to study the adversarial error using analysis from non-adversarial setups. The obtained results shed light on the robustness of overparameterized linear models to adversarial attacks. Adding features might be either a source of additional robustness or brittleness. On the one hand, we use asymptotic results to illustrate how double-descent curves can be obtained for the adversarial error. On the other hand, we derive conditions under which the adversarial error can grow to infinity as more features are added, while at the same time, the test error goes to zero. We show this behavior is caused by the fact that the norm of the parameter vector grows with the number of features. It is also established that ℓ_∞ and ℓ2-adversarial attacks might behave fundamentally differently due to how the ℓ1 and ℓ2-norms of random projections concentrate. We also show how our reformulation allows for solving adversarial training as a convex optimization problem. This fact is then exploited to establish similarities between adversarial training and parameter-shrinking methods and to study how the training might affect the robustness of the estimated models.