A Sublinear Adversarial Training Algorithm
This work addresses the efficiency problem in adversarial training for machine learning practitioners, offering a sublinear-time algorithm that is incremental over existing methods.
The paper tackles the high computational cost of adversarial training by showing that only a sublinear number of neurons are activated per input in a two-layer neural network, and develops an algorithm that reduces the time cost per iteration to o(m n d).
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 $Ω(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.