Adversarial Robustness is at Odds with Lazy Training

Recent works show that adversarial examples exist for random neural networks [Daniely and Shacham, 2020] and that these examples can be found using a single step of gradient ascent [Bubeck et al., 2021] . In this work, we extend this line of work to "lazy training" of neural networks -a dominant model in deep learning theory in which neural networks are provably efficiently learnable. We show that over-parametrized neural networks that are guaranteed to generalize well and enjoy strong computational guarantees remain vulnerable to attacks generated using a single step of gradient ascent. 2 ball centered at u of radius R. the 2,∞ ball centered at U of radius R. For any function f : R d → R, ∇f denotes the gradient vector. We define the standard normal distribution as N (0, 1), and the standard multivariate normal distribution as N (0, I d ). We use S d-1 to denote the unit sphere in d dimensions. We use the standard O-notation (O and Ω). Problem Setup Let X ⊆ R d and Y denote the input space and the label space, respectively. In this paper, we focus on the binary classification setting where Y = -1, +1. We assume that the data (x, y) is drawn from an unknown joint distribution D on X × Y. For a function f w : X → Y parameterized by w in