  Daniely and Schacham 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.
