  Adversarial training is a widely used strategy for making neural networks
resistant to adversarial perturbations. For a neural network of width $m$, $n$
input training data in $d$ dimension, it takes $\Omega(mnd)$ time cost per
training iteration for the forward and backward computation. In this paper we
analyze the convergence guarantee of adversarial training procedure on a
two-layer neural network with shifted ReLU activation, and shows that only
$o(m)$ neurons will be activated for each input data per iteration.
Furthermore, we develop an algorithm for adversarial training with time cost
$o(m n d)$ per iteration by applying half-space reporting data structure.
