summaries: The paper studies adversarial examples in random depth-2 ReLU networks.  They consider depth-2 networks, where the first layer is drawn from a normal distribution such that the norms of the weights vectors are roughly 1, and the second layer is drawn from the uniform distribution on {-1/\sqrt{k},1/\sqrt{k}} where k is the width of the network. They assume that k is at most sub-exponential in the input dimension, and is bounded below by some polylogarithmic expression. For an input x on the sphere of radius \sqrt{d} the output of the network is w.h.p. O(1) (the input x is fixed, and the probability is over the choice of the network). The authors show that there is w.h.p. \delta with ||\delta||=O(1) such that sign(f(x)) \neq sign(f(x+\delta)). Moreover, such \delta can be found with a single gradient step. Thus, although the inputs are of size \sqrt{d}, there is w.h.p. a perturbation of size O(1) that changes the sign of the output. They prove the result for both smooth and ReLU activations. Finally, they validate the results empirically, and also demonstrate that ש similar phenomenon occurs in deeper networks.  Daniely and Schacham [2020] showed that such a property holds in ReLU networks where the sizes d_1,…,d_t  of the layers (where d_1 is the input dimension) are such that for every j we have d_{j+1} = o(d_j) and d_t = \omega(1). For the special case of depth-2 networks it required width k=o(d). Thus, the improvement here w.r.t. k is exponential.  The proofs roughly follow the following steps. First, they show an O(1) upper bound on f(x) and an \Omega(1) lower bound on ||\nabla f(x)||. Then, they bound the variation of the gradient near x. Finally, they use standard arguments to bound f(x-\eta \nabla f(x)) for an appropriate \eta. The proofs of these steps for the case of the ReLU activation is different from the case of smooth activations, and the proofs for the ReLU activation with small k is different from the case of large k.  The paper studies the phenomenon of adversarial examples for random two-layer networks with ReLU or smooth activations. It is shown that one step of gradient descent yields adversarial examples (i.e., a switching of the sign of the network output) with high probability, under a much milder condition on the number of neurons compared to previous work, i.e. sub-exponential in the dimension instead of sub-linear for Daniely and Schacham [2020]. The proof is based on characterizing the landscape of the network function at different scales, showing that at relatively small "mesoscopic" scale of perturbations (o(sqrt(d)),  but still O(1)), the gradient is close to constant while being Omega(1), making it easy to find an adversarial example with a single gradient step. Some experiments are provided to illustrate the theory, and to illustrate how the phenomenon extends to multiple layers. The authors consider the existence of adversarial examples in neural networks trained by gradient descent.  They demonstrate that for two layer networks, one gradient update following random initialization can find adversarial examples.  Their results extend previous work by Daniely and Schacham to more general settings (for two layer networks) and rely upon a different suite of techniques.  The authors prove that two-layer neural networks can be perturbed adversarially at a fixed data point and at random initialization (with high probability), i.e.\ for a neural network $f$ with randomly initialized parameters and a data point $x$, there exists a small perturbation $\delta = O(1)$ such that $|f(x)| = \Omega(1)$, but $f(x+\delta)\cdot f(x) < 0$. The result holds for a wide range of widths and activation functions. They present numerical evidence for their theoretical claims.
abstractText: Daniely and Schacham [2020] recently showed that gradient descent finds adversarial examples on random undercomplete two-layers ReLU neural networks. The term “undercomplete” refers to the fact that their proof only holds when the number of neurons is a vanishing fraction of the ambient dimension. We extend their result to the overcomplete case, where the number of neurons is larger than the dimension (yet also subexponential in the dimension). In fact we prove that a single step of gradient descent suffices. We also show this result for any subexponential width random neural network with smooth activation function.
authors.name: Sébastien Bubeck
authors.name: Yeshwanth Cherapanamjeri
authors.name: Gauthier Gidel
references.authors: Zeyuan Allen-Zhu Yuanzhi Li
references.title: Feature purification: How adversarial training performs robust deep learning
references.venue: arXiv preprint arXiv:2005.10190,
references.authors: Anish Athalye Nicholas Carlini David Wagner
references.title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples
references.venue: In International Conference on Machine Learning,
references.authors: Gérard Ben Arous Eliran Subag Ofer Zeitouni
references.title: Geometry and temperature chaos in mixed spherical spin glasses at low temperature: the perturbative regime
references.venue: Communications on Pure and Applied Mathematics,
references.authors: Stéphane Boucheron Gábor Lugosi Pascal Massart
references.title: Concentration inequalities: A nonasymptotic theory of independence
references.venue: Oxford university press,
references.authors: Ronen Eldan Dan Mikulincer Tselil Schramm
references.title: Non-asymptotic approximations of neural networks by gaussian processes
references.venue: arXiv preprint arXiv:2102.08668,
references.authors: Ian Goodfellow Jonathon Shlens Christian Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: In International Conference on Learning Representations,
references.authors: Aleksander Madry Aleksandar Makelov Ludwig Schmidt Dimitris Tsipras Adrian Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: In International Conference on Learning Representations,
references.authors: Michael Mitzenmacher Eli Upfal
references.title: Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis
references.authors: Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi Omar Fawzi Pascal Frossard
references.title: Universal adversarial perturbations
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi Jonathan Uesato Pascal Frossard
references.title: Robustness via curvature regularization, and vice versa
references.venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition
references.authors: Nicolas Papernot Patrick McDaniel Ian Goodfellow Somesh Jha Z Berkay Celik Ananthram Swami
references.title: Practical black-box attacks against machine learning
references.venue: In Proceedings of the 2017 ACM on Asia conference on computer and communications security,
references.authors: Chongli Qin James Martens Sven Gowal Dilip Krishnan Krishnamurthy Dvijotham Alhussein Fawzi Soham De Robert Stanforth Pushmeet Kohli
references.title: Adversarial robustness through local linearization
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Adi Shamir Itay Safran Eyal Ronen Orr Dunkelman
references.title: A simple explanation for the existence of adversarial examples with small hamming distance
references.authors: Christian Szegedy Wojciech Zaremba Ilya Sutskever Joan Bruna Dumitru Erhan Ian Goodfellow Rob Fergus
references.title: Intriguing properties of neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Roman Vershynin
references.title: Introduction to the non-asymptotic analysis of random matrices
references.venue: In Compressed Sensing: Theory and Practice. Cambridge University Prteess,
references.authors: Roman Vershynin
references.title: High-dimensional probability. Cambridge Series in Statistical and Probabilistic Mathematics
references.authors: Martin J Wainwright
references.title: High-dimensional statistics: A non-asymptotic viewpoint
sections.heading: 1 Introduction
sections.text: We study the random two-layers neural network model, f : Rd ! R defined by
  f(x) = 1p k
  kX
  `=1
  a` (w` · x) , (1)
  where : R ! R is a fixed non-linearity, the weight vectors w` 2 Rd are i.i.d. from a Gaussian N 0, 1
  d Id (so they are roughly unit norm vectors), and the coefficients a` 2 R are independent from the weight vectors and i.i.d. uniformly distributed in { 1,+1}. With this parametrization, the central limit theorem says that, for x 2 p d · Sd 1 (so that w` · x ⇠ N (0, 1)) and large width k, the distribution of f(x) is approximately a centered Gaussian with variance EX⇠N (0,1)[ (X)2].
  Our goal is to study the concept of adversarial examples in this random model. We say that 2 Rd is an adversarial perturbation at x 2 Rd if k k ⌧ kxk and sign(f(x)) 6= sign(f(x + )). In this case, we call x+ an adversarial example. Our main result is that, while |f(x)| = O(1) with high probability, a single gradient step on f (i.e., a perturbation of the form = ⌘rf(x) for some ⌘ 2 R) suffices to find such adversarial examples, with roughly k k ' kxkp
  d = 1. Note, here that gradients
  are taken with respect to the input to the network as opposed to the weights of the network. We prove this statement for networks of subexponential width (e.g., k ⌧ exp(o(d))) with both smooth and ReLU activation functions. We first state our result for smooth activation functions in the following theorem. Theorem 1. Let 2 (0, 1) and be non-constant, Lipschitz and with Lipschitz derivative. There exists constants C1, C2, C3, C4 depending on such that the following holds true. Assume k
  ⇤Canada CIFAR AI Chair
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
sections.heading: C1 log
sections.text: 3(1/ ) and d C2 log(k/ ) log(1/ ), and let ⌘ 2 R such that |⌘| = C3
  p log(1/ ) krf(x)k2 and
  sign(⌘) = sign(f(x)). Then, with probability at least 1 , one has:
  sign(f(x)) 6= sign(f(x+ ⌘rf(x))) .
  Moreover we have k⌘rf(x)k  C4 p log(1/ ).
  Note that our proof of Theorem 1 in Section 2 easily gives explicit values for C1, C2, C3, C4. Also note that by re-arranging the constraint on d in Theorem 1 and setting = 1/poly(d), the subexponential width condition is of the form k ⌧ exp(o(d)). Our second main result establishes similar behavior for the non-smooth ReLU activation unit. Theorem 2. Let 2 (0, 1) and (t) = max(0, t). There exist constants C1, C2, C3, C4, C5 such that the following holds true. Assume
  C1 log 6(d) log(1/ )  k, C2 log3(d) log(1/ )  d, C3 log4(k) log(1/ ) 
  d
  log(d)
  and let ⌘ 2 R such that |⌘| = C4 p log(1/ )
  krf(x)k2 and sign(⌘) = sign(f(x)). Then, with probability at least 1 , one has: sign(f(x)) 6= sign(f(x+ ⌘rf(x))) . Moreover, we have k⌘rf(x)k  C5 p log(1/ ).
  As before, note that the subexponential condition on the width in the above Theorem is of the form k ⌧ exp(d0.24). In fact by modifying a bit the proof we can get a condition of the form k ⌧ exp(d⇢) for any ⇢ < 1/2, but for the sake of clarity we only prove the weaker version stated above. The proof for the ReLU activation is broken into two separate cases focusing on the overlapping regimes:
  Case 1: k & d log2(d) and Case 2: log6(d) log(1/ ) . k . d log3 d, as the proofs for the two settings use distinct arguments. The proof for the first regime is similar to the proof for Theorem 1 while the second uses a refinement of an argument by Daniely and Schacham [2020]. These arguments are carried out in Section 3. We would like to note that our results and corresponding proofs are extendible to the setting where a` are drawn from a normal distribution with minor modifications. We include the simpler setting with Bernoulli activations in the last layer for the sake of conceptual clarity. Intuitively, the strong concentration (and anti-concentration) properties of the normal distribution coupled with a conditioning argument on the magnitudes of the weights in the final layer yield similar results for gaussian setting as well. Additionally, due to the scale invariance of the ReLU activation function, our results also hold true for any distribution over x as long as P {x = 0} = 0 and for smooth activations when P n kxk = ⇥( p d) o = 1. Finally, our results also
  hold when a bias unit is introduced; in this setting, we simply project our perturbation onto the ((d 1)-dimensional) subspace of perturbations which leave the bias unit unchanged.
sections.heading: 1.1 Related works
sections.text: The existence of adversarial examples in neural network architectures was first evidenced in the seminal paper of Szegedy et al. [2014], where the authors found adversarial examples by using the L-BFGS optimization procedure. Shortly after this work, it was hypothesized in Goodfellow et al. [2015] that the existence of adversarial examples stems from an excessive “linearity” of neural network models. This hypothesis was experimentally confirmed by showing that a single step of gradient descent suffices to find adversarial perturbations (the so-called fast gradient sign method -FGSM). Our theorems can be thought of as a theoretical confirmation of the hypothesis in Goodfellow et al. [2015]. In fact, as explained in Section 1.2, our proofs proceed exactly by showing that “most” two-layers neural networks behave “mostly” linearly over “vast” regions of input space.
  We note that not all networks are susceptible to one-step gradient attacks to find adversarial examples. Indeed, in Goodfellow et al. [2015], it was shown that adversarial training can be used to build networks that are somewhat robust to one-step gradient attacks. Interestingly, Madry et al. [2018] showed that such models remain susceptible to multi-steps gradient attacks, and empirically demonstrated that better robustness can be achieved with adversarial training using multi-steps gradient
  attacks. Understanding this phenomenon theoretically remains a challenge, see for example AllenZhu and Li [2020] for a proposed approach, and Moosavi-Dezfooli et al. [2019], Qin et al. [2019] for discussion/algorithmic consequences of the relation with the phenomenon of gradient obfuscation (Papernot et al. [2017], Athalye et al. [2018]).
  Our work is a direct follow-up of Daniely and Schacham [2020] (which itself follows Shamir et al. [2019]). Daniely and Schacham prove that multi-steps gradient descent finds adversarial examples for ReLU random networks of the form (1), as long as the number of neurons is much smaller than the dimension (i.e., k = o(d)). They explicitly conjecture that this condition is not necessary, and indeed we exponentially improve it in Theorem 2 (see below for a discussion of k exponential in the dimension). We note that Daniely and Schacham went beyond two-layers neural networks, and conjectured (and proved for shrinking layers) that gradient descent finds adversarial examples on random multi-layers neural networks. We give some experimental confirmation of this multi-layer conjecture in Section 4.
  The ultra-wide case k = exp(⌦(d)) remains open. This exponential size case seems of a different nature than the polynomial size we tackle here, at least for the ReLU activation function. In particular, it is likely that the behavior with exponential width would be closely tied to the actual limit case k = +1, where the random model (1) yields a Gaussian process. Namely, for k = +1, f is a Gaussian process indexed by the sphere (say if we restrict to inputs x 2 p d · Sd 1), with f(x) ⇠ N (0,EX⇠N (0,1)[ (X)]) and E[f(x)f(y)] = EX,Y⇠N (0,1):E[XY ]=x·y[ (X) (Y )]. For example if the activation function is a Hermite polynomial of degree p, then f would be a spherical p-spin glass model. This polynomial case is particularly well-understood, and in fact the landscape we describe below in Section 1.2 was already described in this case by Ben Arous et al. [2020] (in particular Corollary 59) indicating that adversarial examples would likely continue to persist in the ultra-wide setting. It would be interesting to see if the p-spin glass landscape literature can be extended to non-polynomial activation functions, and to a finite (but possibly exponential in d) k. A step in this latter direction was recently taken in Eldan et al. [2021], where convergence rates to the Gaussian process limit where given both for polynomial activations and for the ReLU. Finally we note that for a smooth activation it might be that there is a more direct argument to remove the subexponential width condition in Theorem 1 (in technical terms, the proof of Proposition 2 could leverage a better argument than our naive upper bound on Lip( )).
  Finally, we note that, in practice, it has been found that there exists “universal” adversarial perturbations that generalize across both inputs and neural networks, Moosavi-Dezfooli et al. [2017]. For the case of ReLU activation (Theorem 2), we could in fact prove our result by replacing the gradient step with a step in the direction P k
  `=1 a`w`, which is indeed a direction independent of the input x, thus proving the existence of “universal” perturbations (generalizing across inputs) for our model.
sections.heading: 1.2 The landscape of random two-layers neural networks
sections.text: For a smooth non-linearity , we have
  rf(x) = 1p k
  kX
  `=1
  a`w` 0(w` · x) and r2f(x) = 1p k
  kX
  `=1
  a`w`w > ` 00(w` · x) .
  We already claimed in the introduction that, with high probability the value of f(x) was bounded:
  Upper-Bounded Value : |f(x)| = O(1) . (2) We alluded to the CLT for this claim, but it is also easy to guess it intuitively by noting that:
  E[f(x)2] = E
  2
  41 k
  kX
  `,`0=1
  a`a`0 (w` · x) (w`0 · x)
  3
  5 = EX⇠N (0,1)[ (X)2] ,
  as E[a`a`0 ] = 1{` = `0}. The formal proof of (2) (and all other claims we make here) will eventually be a simple application of the classical Bernstein concentration inequality. Similarly, it is easy to see that (noticing that E[krf(x)k2] = EX⇠N (0,1)[ 0(X)2]), with high probability, the norm of the gradient of f(x) is bounded below (note that we can also show that it is bounded above).
  Lower-Bounded Gradient : krf(x)k = ⌦(1) . (3)
  A slightly more difficult calculation, although classical too, is that
  Upper-Bounded Hessian : kr2f(x)kop = eO ✓
  1p d
  ◆ . (4)
  Indeed one can simply note that, for any u 2 Sd 1, u>r2f(x)u = 1p k
  P k
  `=1 a`(w` · u)2 00(w` · x) is approximately distributed as a centered Gaussian with variance (through a heuristic application of the asymptotic central limit theorem):
  EW,Z⇠N (0,1):E[WZ]= x·up d "✓ Wp d ◆4 00 (Z)2 # ,
  so that with probability at least 1 one can expect u>r2f(x)u to be of order p log(1/ )
  d , and thus
  by taking a union bound over a discretization of the sphere Sd 1, one can show inequality (4). In fact, interestingly, one can even hope that (4) holds true for an entire ball around x: with appropriate smoothness over (say C2,1 smoothness), this could be obtained by another union bound over a second discretization of a d-dimensional ball. In other words, we can expect with high probability:
  8x 2 Rd : kxk = poly(d), one has kr2f(x)kop = eO ✓
  1p d
  ◆ . (5)
  Equations (2), (3), and (5) paint a rather clear geometric picture. There are essentially two scales around a fixed x 2 p d · Sd 1: The macroscopic scale, where one considers a perturbation x + with k k = ⌦( p d), and the mesoscopic scale where k k = o( p d) (we use this term because for the ReLU network there will also be a microscopic scale, with k k = o(1)). At the macroscopic scale the landscape of f might be very complicated, but our crucial observation is that the picture at the mesoscopic scale is dramatically simpler. Namely, at the mesoscopic scale, the function f is essentially linear, since one has (thanks to (3) and (5))
  Approximate Linearity : krf(x) rf(x+ )k = o(krf(x)k), 8 : k k = o( p d) . (6)
  Moreover, since the height of the function is at most a constant (by (2)) and the norm of the gradient is constant, it suffices to step at a constant distance in the direction of the gradient (or negative gradient) to change the sign of f . Assuming without any loss of generality that f(x) > 0, we combine (2), (3), and (6) using a standard descent lemma (Lemma 3):
  f(x ⌘rf(x))  f(x)|{z} O(1) by (2) ⌘ krf(x)k| {z } ⌦(1) by (3) ⇣ krf(x)k| {z } ⌦(1) by (3)
  sup k k krf(x)k⌘ krf(x) rf(x+ )k | {z } o(1) by (4) or (6)
  ⌘ (7)
   C1 C2⌘ < 0 (for C1/C2 < ⌘ < C3 p d) (8)
  where C1, C2 and C3 are constants that do not depend on k and d. In words: a single step of gradient descent (or ascent) with a O(1) step-size suffices to find an adversarial example, and moreover the adversarial perturbation satisfies k k = O(1) = O(kxk/ p d).
sections.heading: 1.3 Proof strategy
sections.text: The starting point of the proof for both the smooth and ReLU case is to show (2) and (3), which we essentially do below in Section 1.4. In the smooth case, one could then prove formally (4) and conclude as indicated in the last paragraph of Section 1.2. Of course, (4) is simply ill-defined for the ReLU case, so one has to take a different route. Instead, we propose to directly prove (6), that is we study the difference of gradients at the mesoscopic scale. Using that khk = supv2Sd 1 v · h, we thus need to control (for some R = o( p d)):
  sup 2Rd:k kR krf(x) rf(x+ )k = sup v2Sd 1,
  2Rd:k kR
  1p k
  kX
  `=1
  a`(w` ·v)( 0(w` ·x) 0(w` · (x+ ))) .
  (9)
  We execute this strategy first for the smooth case in Section 2. We then prove the ReLU case in Section 3, where we face an extraneous difficulty since the gradient is not Lipschitz at very small scale, which introduces a third scale (the microscopic scale) that has to be dealt with differently. Technically, this issue appears when we try to move from the discretization over v and in (9) to the whole space (a so-called "-net argument).
sections.heading: 1.4 Scaling of value and gradient
sections.text: Here we show how to prove (2) and (3) (in fact, for our purpose, we only need the one-sided inequality krf(x)k = ⌦(1)) under very mild conditions on which will be satisfied for both ReLU and smooth activations. We will repeatedly use Bernstein’s inequality which we restate here for convenience (see e.g., Theorem 2.10 in Boucheron et al. [2013]): Theorem 3 (Bernstein’s inequality). Let (X`) be i.i.d. centered random variables such that for all integers q 2, E[|X`|q]  q!2 2 c q 2 for fixed , c > 0. Then, with probability at least 1 :
  kX
  `=1
  X`  p 2 2k log(1/ ) + c log(1/ ) . (10)
  We will also use repeatedly that EX⇠N (0,1)[|X|q]  (q 1)!!  q!2 , as well as the following concentration of 2 random variables (see e.g., (2.19) in Wainwright [2019]): let X1, . . . , Xk be i.i.d. standard Gaussians, then with probability at least 1 , one has:
  kX
  `=1
  X 2 ` k
   4 p k log(2/ ) . (11)
  We can now proceed to our various results. Lemma 1 (Bounded Value). Assume that there exists , c > 0 such that for all integers q 2, EX⇠N (0,1)[| (X)|q]  q!2 2 c q 2 . Then with probability at least 1 one has
  |f(x)|  p 2 2 log(1/ ) +
  c log(1/ )p k .
  Proof sketch. Since 1p k
  P k
  `=1 a` (w` · x), we use Bernstein’s inequality on X` = a` (w` · x).
  Lemma 2 (Lower-Bounded Gradient). Let be differentiable almost everywhere, and assume that there exists 0 , c
  0 > 0 such that for all integers q 2, EX⇠N (0,1)[| 0(X)|2q]  q!2 02 c 0q 2 . Then
  with probability at least 1 ,
  krf(x)k EX⇠N (0,1)[| 0(X)|2]
  r 2 02 log(2/ )
  k +
  c 0 log(2/ )
  k
  !!1/2 1 5 r log(4/ )
  d
  ! .
  Proof sketch. Let P = Id xx > d be the projection on the orthogonal complement of the span of x. We have krf(x)k kPrf(x)k = k 1p k P k `=1 Pa`w` 0(w` · x)k where a`Pw` is independent of w` · x and is distributed as N 0, 1
  d Id 1 ). We conclude by conditioning on the values (w` · x)`2[k]
  and using the concentration results (10) and (11).
sections.heading: 2 Smooth Non-Linearity (Theorem 1)
sections.text: In this section, we consider a 1-Lipschitz and L-smooth activation function, that is for all s, t 2 R,
  | (s) (t)|  |s t| and | 0(s) 0(t)|  L|s t| . (12)
  We also assume (0) = 0 and denote c2 = EX⇠N (0,1)[( 0(X))2] which we assume to be non-zero (that is is not a constant function).
  Proposition 1 (Upper-Bounded Value and Lower-Bounded Gradient). Under the above assumptions, one has with probability at least 1 ,
  |f(x)| 
  s
  2 log
  ✓ 1
  ◆ 0
  BB@1 +
  vuut log ⇣ 2 ⌘
  k
  1
  CCA
  and krf(x)k
  0
  BB@c 2
  vuut2 log ⇣ 4 ⌘
  k
  0
  BB@1 +
  vuut log ⇣ 4 ⌘
  k
  1
  CCA
  1
  CCA
  1/20
  BB@1 5
  vuut log ⇣ 8 ⌘
  d
  1
  CCA .
  Particularly, there exists C > 0 such that for k C log(2/ ) and d C log(8/ ) we have
  |f(x)|  2 p log(1/ ) and krf(x)k c /2 . (13)
  Proof. With (12) we have | (X)|  |X| and thus in Lemma 1 we can take = c = 1 which yields the first claimed equation. For the second equation we use that | 0(X)|  1 (since is 1-Lipschitz) and thus, in Lemma 2, we can also take 0 = c0 = 1 yielding the second claimed equation.
  Next, we need to control (9) where we use crucially the smoothness of the activation function. Proposition 2 (Bounded Variations). Let R 1. With probability at least 1 one has
  sup 2Rd : k kR
  krf(x) rf(x+ )k  20RL r log(Rk/ )
  d + log(1/ )p k
  ! .
  Particularly, for any c > 0, there exists C1, C2 such that if k C1R2log2(1/ ) and d C2R
  2 log(Rk/ ) then sup
  2Rd : k kR krf(x) rf(x+ )k  c . (14)
  Proof sketch. Our plan is to use the fact that khk = supv2Sd 1 v · h . Thus, we first show, by using Bernstein’s inequality on X` = a`L (w` · v)(
  0(w` · x) 0(w` · (x+ )), that if we fix 2 Rd such that k k  R and v 2 Sd 1, then with probability at least 1 one has:
  (v, ) := hrf(x) rf(x+ ), vi = Lp k
  kX
  `=1
  Xl  4RL
  d
  p log(1/ ) 1 +
  r log(1/ )
  k
  ! .
  Let ⌦ := {(v, ) : kvk = 1, k k  R} and N" be an "-net over ⌦ with " = 1/k. By a union bound over N" (whose size is at most (10kR)2d [Vershynin, 2018, Corollary 4.2.13]), we obtain with probability at least 1 :
  sup (v, )2⌦ (v, )  sup (v, )2N" (v, ) + sup (v, ),(v0, 0)2⌦:kv v0k+k 0k"
  | (v, ) (v0, 0)|
   4RL d
  p 2d log(Rk) + log(1/ ) 1 +
  r 2d log(Rk) + log(1/ )
  k
  ! + Lip( )
  k .
  Then we show that the variations of can be upper-bounded by a RL times a 2 random variable and use (11) to show that with probability at least 1 ,
  Lip( )  RL p k + 4
  r log(1/ )
  d
  ! .
  Finally we can turn to the proof of Theorem 1. Let us first recall this theorem.
  Theorem 1. Let 2 (0, 1) and be non-constant, Lipschitz and with Lipschtiz derivative. There exists constants C1, C2, C3, C4 depending on such that the following holds true. Assume k C1 log3(1/ ) and d C2 log(k/ ) log(1/ ), and let ⌘ 2 R such that |⌘| = C3 p log(1/ )krf(x)k 2 and sign(⌘) = sign(f(x)). Then with probability at least 1 one
  has: sign(f(x)) 6= sign(f(x+ ⌘rf(x))) . Moreover we have k⌘rf(x)k  C4 p log(1/ ).
  Proof. We make the following claims which hold with probability at least 1 . Without any loss of generality we can assume that f(x) > 0, we will use a standard descent lemma (Lemma 3) and the previous propositions to get that,
  f(x ⌘rf(x))  f(x)|{z} O(1) by (13) ⌘ krf(x)k| {z } ⌦(1) by (13) ⇣ krf(x)k| {z } ⌦(1) by (13)
  sup k k krf(x)k⌘ krf(x) rf(x+ )k | {z } o(1) by (14)
  ⌘ . (15)
  Formally, let us set ⌘ = 32 c2 krf(x)k2
  p log(1/ ), R = 64
  c3
  p log(1/ ), k C1R2 log2(1/ ) and d
  C2R 2 log(Rk/ ) where C1 and C2 are large enough such that (13) and (14) are valid with c = c 4 . By Proposition 1 we have that krf(x)k c /2 and ⌘krf(x)k2 = 32c2 p log(1/ ) 16 c2 |f(x)|.
  Moreover, Proposition 2 shows that for all such that k k  |⌘|krf(x)k  64 c3
  p log(1/ ) = R, we
  thus have krf(x) rf(x+ )k  c := c 4 . Consequently,
  f(x ⌘rf(x))  f(x) ⌘krf(x)k ⇣ c
  2 c 4
  ⌘  f(x) ⌘ c 2
  8  f(x) . (16)
  Thus, with a single gradient step of size at most R = 64 c3
  p log(1/ ), we switched the sign of f .
sections.heading: 3 ReLU Non-Linearity (Theorem 2)
sections.text: In this section, we consider the ReLU non-linearity (t) = max(0, t). We start by showing that f(x) is upper bounded and that krf(x)k is lower-bounded. Proposition 3 (Upper-Bounded Value and Lower-Bounded Gradient). With probability at least 1 ,
  |f(x)|  p 2 log(2/ ) 1 +
  r log(2/ )
  k
  !
  and krf(x)k 1 2 r 2 log(4/ ) k 1 + r log(1/ ) k !!1/2 1 5 r log(4/ ) d ! .
  Particularly, there exists C > 0 such that for k C log(1/ ) and d C log(4/ ) we have
  |f(x)|  2 p log(2/ ) and krf(x)k 1
  4 . (17)
  Proof. In Lemma 1 and Lemma 2, we can take = c = 0 = c0 = 1 (since | (X)|  |X| and | 0(X)|  1), which concludes the proof.
  Now we split the control of the gradient variation into two cases: the large width case (Cd log2 d . k) and the small width case (log6(d) log(1/ ) . k . d log3 d). Proposition 4. (Bounded Variations – Large Width Case) Let 1  R  p d/2, p k 52 and
  d log(1/ ). Then, with probability at least 1 , one has
  sup 2Rd : k kR
  krf(x) rf(x+ )k  20 R log2(Rk)
  r log d
  d
  !1/4 + 40 r d
  k log(Rk) .
  Particularly, for any c > 0, there exists C1, C2 such that if C1d log 2(Rk)  k and C2 log4(Rk)R2 
  d
  log(d) , then we have,
  sup 2Rd : k kR
  krf(x) rf(x+ )k  c . (18)
  Proof sketch. In the smooth case (Proposition 2) we did so by using crucially the smoothness of the activation function. Here, instead of smoothness, we will use that only few activations can change when you make microscopic move (i.e., between x+ and x+ 0 with k 0k = o(1)). The key observation that for any such that k k  R,
  P(sign(w` · x) 6= sign(w` · (x+ )))  R r 2 log(d)
  d +
  1 d . (19)
  We can then use this result to bound the variation of rf(x) along a fixed direction. If we fix 2 Rd such that k k  R (with R 1) and v 2 Sd 1, then with probability at least 1 one has:
  (v, ) := hrf(x) rf(x+ ), vi = 1p k
  kX
  `=1
  Xl  2 q log( 1 )
  d
  ✓ 2R q
  log(d) d
  ◆ 1 4
  +
  q log( 1 )
  k
  ! .
  This inequality is proven via Bernstein’s inequality on X` := a`(w` ·v)( 0(w` ·x) 0(w` · (x+ ))) where we use (19) to prove
  E[|X`|q]  p E[|w` · v|2q]⇥ P(sign(w` · x) 6= sign(w` · (x+ )))  q!
  2 c q 2 ⇥ 2, (20)
  with = 2p d ⇥ ✓ 2R q log(d) d ◆1/4 and c = 2p d .
  Then, similarly as in the proof of Proposition 2, we use a covering argument (but this time with an "-Net of size " = R 4/3k 4) to show that,
  sup (v, )2⌦ (v, )  sup (v, )2N" (v, ) + sup (v, ),(v0, 0)2⌦:kv v0k+k 0k"
  | (v, ) (v0, 0)|
   2 r 10d log(Rk) + log(2/ )
  d
  0
  @ 2R
  r log(d)
  d
  !1/4 + r 10d log(Rk) + log(2/ )
  k
  1
  A
  + sup (v, ),(v0, 0)2⌦:kv v0k+k 0k"
  | (v, ) (v0, 0)| . (21)
  By using 2 concentration, it is easy to see that with probability at least 1 :
  | ( , v) ( , v0)|  kv v0k
  s
  k + 4k
  r log(k/ )
  d . (22)
  By using (19) we are able to show that with probability 1 for any (v, ) 2 N" there is at most 4d different activated neurons between (v, ) and (v, 0) and thus by applying a concentration result of Lipschitz function of Gaussians we get,
  | ( , v) ( 0, v)|  18 r d
  k
  r log 4k + log 8/
  d . (23)
  Combining (21), (22), and (23), we get
  sup 2Rd : k kR
  krf(x) rf(x+ )k  20 R log2(Rk)
  r log d
  d
  !1/4 + 40 r d
  k log(Rk) .
  Proposition 5 (Bounded Variations – Small Width Case). Let 20 log3 d · log 1/  k  d log3 d and d 20 · log3 d · log 1/ . Then, with probability at least 1 , we have:
  sup 2Rd,k k p k
  log6 d
  krf(x) rf(x+ )k  60 log d .
  Proof sketch. In the small width regime we assume 20 log3 d · log 1/  k  d log3 d. The idea of the proof is to control the operator norm of W (where f(x) = 1p
  k a > (W>x)) as well as the
  number of neurons with a too small activation. With high probability, we show that we have,
  kWk  3 · 1 +
  r 10(k + log 1/ )
  d
  ! , # ⇢ i : |hwi, xi|  1
  log3 d
   2 · k
  log3 d .
  Thus, uniformly on n y : kx yk  p k
  log6 d
  o the cardinal of Ty := {i : sgnhwi, xi 6= sgnhwi, yi} is
  uppper-bounded: |Ty|  300k/ log3 d := B . (24) We can conclude the proof by using an union bound and a concentration inequality on Gaussians.
  krf(x) rf(y)k = 1p k
  X
  `2T a`w`  supA⇢[k] |A|B
  1p k
  X
  `2T a`w`
   r B
  k
  0
  @1 +
  s B log k + log 4
  d
  1
  A .
  We can now prove our final result. Theorem 2. Let 2 (0, 1) and (t) = max(0, t). There exist constants C1, C2, C3, C4, C5 such that the following holds true. Assume
  C1 log 6(d) log(1/ )  k, C2 log3(d) log(1/ )  d, C3 log4(k) log(1/ ) 
  d
  log(d) ,
  and let ⌘ 2 R such that |⌘| = C4 p log(1/ )
  krf(x)k2 and sign(⌘) = sign(f(x)). Then with probability at least 1 one has: sign(f(x)) 6= sign(f(x+ ⌘rf(x))) . Moreover we have k⌘rf(x)k  C5 p log(1/ ).
  Proof. The proof is the same as for Theorem 1 using Proposition 3 instead of Proposition 1 and Proposition 4 or Proposition 5 replacing Proposition 2.
sections.heading: 4 Experiments
sections.text: Setting. To verify our theoretical findings, we run some experiments to measure empirically the probability of finding an adversarial example in the direction rf(x). More precisely, we take a random point x of norm p d and initialize a network using the procedure described in Section 12. We then find the smallest ⌘ such that a gradient step ⌘rf(x) changes the sign of the function. ⌘ is of the opposite sign of f(x) and we limit our search to |⌘| < 20. We explore various values of d and k, as well as deeper networks with L = 1 through L = 6 hidden layers. All hidden layers are of width k. For our experiments, we used ReLU activation units and the standard deviations reported in Figure 1 are computed over 100 random network initializations for each choice of architecture and 100 random input points for each such initialization.
  Results. Figure 2a shows the average of the smallest ⌘ required to switch the sign of the function. We note that the average only includes cases where an ⌘ was indeed found. Figure 2b shows the gradient norm in x (all cases included). As we see, both the smallest ⌘ and the gradient norm are approximately constant both in d and in k. This finding also holds for deeper networks (see Appendix D). In Figure 1, we show the fraction of examples (out of 10, 000 samples) whose sign is switched. We see that with L = 1 and values of d and k larger than 50, 100% of samples are switched. This confirms our theoretical results. Once again, we observe the same statement holds for deeper networks. The values of d and k at which 100% switching is reached appears to grow with L
  3. Additionally, we track the value of the smallest ⌘ required to switch the sign of the function, and the gradient norm w.r.t x. Both are approximately constant in d and in k. This finding also holds for deeper networks (see Appendix D for the curves).
  2We also conducted experiments with a gaussian initialization for the last layer in place of the Bernoulli initialization from Section 1 and obtained qualitatively similar results.
  3Due to GPU memory limitations, k could not reach 1,000,000 for deeper networks.
sections.heading: Acknowledgment
sections.text: We thank Mark Sellke for pointing out to us the reference Ben Arous et al. [2020], and Peter Bartlett for several discussions on this problem.
sections.heading: 5 Disclosure of Funding and Competing Interests
sections.text: GG research is supported by the Canada CIFAR AI Chair Program and an IVADO grant. YC gratefully acknowledges the support of the NSF through grants DMS-2023505 and DMS-2031883, the Simons Foundation through award #814639, and Microsoft through the BAIR Open Research Commons. We declare no competing interests.
title: A single gradient step finds adversarial examples on random two-layers neural networks