# Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 51 references that are in the map.
- First posted on arXiv 27 Sep 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [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)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (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)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Understanding and Mitigating the Tradeoff Between Robustness and Accuracy](https://mlsanity.com/paper/2002.10716/) (2020)
- [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)
- [Adversarial Examples Are a Natural Consequence of Test Error in Noise](https://mlsanity.com/paper/1901.10513/) (2019)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Robustness of classifiers: from adversarial to random noise](https://mlsanity.com/paper/1608.08967/) (2016)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Adversarial vulnerability for any classifier](https://mlsanity.com/paper/1802.08686/) (2018)
- [The jamming transition as a paradigm to understand the loss landscape of deep neural networks](https://mlsanity.com/paper/1809.09349/) (2018)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Precise Statistical Analysis of Classification Accuracies for Adversarial Training](https://mlsanity.com/paper/2010.11213/) (2020)
- [Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures](https://mlsanity.com/paper/2104.13628/) (2021)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)

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

- [The Fourth Quadrant: A Stylized View of Benign Misfitting](https://mlsanity.com/paper/2608.01032/) (2026)

## Abstract (arXiv)

State-of-the-art deep learning classifiers are heavily overparameterized with respect to the amount of training examples and observed to generalize well on "clean" data, but be highly susceptible to infinitesmal adversarial perturbations. In this paper, we identify an overparameterized linear ensemble, that uses the "lifted" Fourier feature map, that demonstrates both of these behaviors. The input is one-dimensional, and the adversary is only allowed to perturb these inputs and not the non-linear features directly. We find that the learned model is susceptible to adversaries in an intermediate regime where classification generalizes but regression does not. Notably, the susceptibility arises despite the absence of model mis-specification or label noise, which are commonly cited reasons for adversarial-susceptibility. These results are extended theoretically to a random-Fourier-sum setup that exhibits double-descent behavior. In both feature-setups, the adversarial vulnerability arises because of a phenomenon we term spatial localization: the predictions of the learned model are markedly more sensitive in the vicinity of training points than elsewhere. This sensitivity is a consequence of feature lifting and is reminiscent of Gibb's and Runge's phenomena from signal processing and functional analysis. Despite the adversarial susceptibility, we find that classification with these features can be easier than the more commonly studied "independent feature" models.