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

Abstract

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.

arXiv comment32 pages, 10 figures

References in corpus (22)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Adversarially Robust Generalization Requires More Data
• Underspecification Presents Challenges for Credibility in Modern Machine Learning
• Adversarial Examples Are Not Bugs, They Are Features
• On Lazy Training in Differentiable Programming
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Adversarial Examples Are a Natural Consequence of Test Error in Noise
• The jamming transition as a paradigm to understand the loss landscape of deep neural networks
• Robustness of classifiers: from adversarial to random noise
• To understand deep learning we need to understand kernel learning
• Adversarial Robustness May Be at Odds With Simplicity
• When Do Neural Networks Outperform Kernel Methods?
• Understanding and Mitigating the Tradeoff Between Robustness and Accuracy
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• More Data Can Hurt for Linear Regression: Sample-wise Double Descent
• Understanding overfitting peaks in generalization error: Analytical risk curves for $l_2$ and $l_1$ penalized interpolation
• Failures of model-dependent generalization bounds for least-norm interpolation
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• A law of robustness for two-layers neural networks
• Properties of the After Kernel