Reducing Adversarial Training Cost with Gradient Approximation

First of all, we present the third-order Taylor series of a scalar function $f(x)$ with continuous third-order derivatives as follows:

where $\xi\in(x,x+\triangle x)$ and $\triangle x^{3}f^{(3)}(\xi)/6$ is the Lagrangian remainder. Because $f^{(3)}(\xi)/6$ is a constant, we can rewrite the remainder as $O(\triangle x^{3})=\triangle x^{3}f^{(3)}(\xi)/6$, which is a function of $\triangle x$. If $\triangle x$ is small enough, we can omit the remainder $O(\triangle x^{3})$, so we approximate $f(x+\triangle x)$ as follows:

In our setting, due to the small value of the imperceptible perturbation $\delta$, it is reasonable to approximate the adversarial loss¹¹1For the convenience of representation, we abbreviate adversarial loss $\ell(f_{\theta}(x+\delta),y)$ as $\ell(x+\delta)$. $\ell(x+\delta)$ in the matrix form by Formula (2):

where $J(x)=\nabla_{x}\ell(x)$ is the first-order derivative matrix, i.e., the Jacobian matrix; $H(x)=\nabla_{x}^{2}\ell(x)$ is the second-order derivative matrix, i.e., the Hessian matrix.

In order to evaluate the effectiveness of the approximation (3), we define the residual error between the true loss and the approximate loss as

where $|\cdot|$ computes the absolute value, and $||\delta||_{\infty}\leq\epsilon$. $H(x)$ is approximated by Equation (8).

We measure $R(x,\delta)$ of two ResNet models (ResNet-18 and ResNet-50) with RAT on the CIFAR-10 dataset, where the adversary generation is run with 1, 4, 10, 16 steps of PGD attack (1). $R(x,\delta)$ is computed throughout training on the training set of CIFAR-10. We used two residual networks with the depth of 18 and 50 as our models. The results are shown in Figure 1. At the initial epochs, $R(x,\delta)$ is relatively large, and as the training process goes on, $R(x,\delta)$ decreases. Besides, the more steps the PGD attack has, the larger $R(x,\delta)$ is, while it still converges to very small values, i.e., $7.9\times 10^{-4}$ for ResNet-18 and $5.4\times 10^{-4}$ for ResNet-50. However, when we train with more PGD steps to generate adversaries, $R(x,\delta)$ is not going to get any larger, e.g., $R(x,\delta)$ of 16-step PGD equals approximately to $R(x,\delta)$ of 10-step PGD.

Instead of computing the partial derivative with respect to $\delta$ of the true adversarial loss, we find the partial derivative of the approximate loss (3), so we obtain:

Furthermore, we replace the formula of Line 6 in Algorithm 1 with

In the $T$-step PGD adversarial training, the regular PGD method computes the partial derivative [$\nabla_{\delta}\ell(x+\delta)$] for $T$ times in a batch. However, except some very simple operations (like addition and multiplication), adversarial training with gradient approximation (5) only computes the Jacobian matrix and the Hessian matrix of $\ell(x)$ with respect to natural examples $x$ for one time.

In Equations (5) and (6), we can easily obtain the Jacobian matrix by backpropagation in adversarial training, while the Hessian matrix is usually difficult to calculate or requires a large amount of calculation. Therefore, we also use approximation method to simplify the calculation.

Use $J(x)$ to Approximate $H(x)$. Referring to the Gauss-Newton method, we use the Jacobian matrix to roughly approximate the Hessian matrix. Gauss-Newton method is a specialized method for minimizing the least squares cost. Given a point $x$, the Gauss-Newton method in our setting is based on the following objective function:

where we use the first-order Taylor series to approximate $\ell(x+\delta)$. So the gradient of (7) is $g=r\nabla_{x}\ell(x)$ (Here, we abbreviate $r(\delta)$ as $r$), and the Hessian matrix is $H(x)=\nabla_{x}\ell(x)^{T}\nabla_{x}\ell(x)+r\nabla_{\delta}(\nabla_{x}\ell(x))$. Omitting the second item of $H(x)$, we obtain:

Although the objective function (7) is different from the objective function in our task, we can still use (8) to roughly approximate the Hessian matrix in (5) and (6) for the purpose of simplifying the calculation.

Omit Partial Derivatives to Approximate $H(x)$. Given an image $x\in\mathbb{R}^{w\times h}$, the Hessian matrix can be written as²²2For convenience, we reshape the $w\times h$ image matrix as $wh\times 1$ vector.

where $i$ (or $j$) is the $i$th (or $j$th) element of the image vector and $1\leq i,j\leq wh$. When $i\neq j$, the partial derivatives $\partial^{2}\ell/\partial x_{i}\partial x_{j}$ are very difficult to calculate; however, when $i=j$, the second-order derivatives $\partial^{2}\ell/\partial x_{i}^{2}$ are easier to obtain. So another idea to approximate $H(x)$ is to omit the partial derivatives ($\partial^{2}\ell/\partial x_{i}\partial x_{j}$, $i\neq j$) and just set them to zero, and further we obtain the following diagonal matrix for approximating the Hessian matrix:

Before ending this section, we summarize adversarial training with gradient approximation (GAAT) in Algorithm 2 [using (8) to approximate $H(x)$].

For MNIST, we used the convolutional ReLU model mentioned in Wong and Kolter (2018), with two convolutional layers with 16 and 32 $4\times 4$ filters each, followed by a fully connected layer with 100 units, with a batch size of 512. For CIFAR-10, we used four popular models, VGGNet-16, ResNet-18, ResNet-50 and WideResNet-28x4 with a batch size of 128. For CIFAR-100, we use ResNet-18 and ResNet-50 models with a batch size of 128.

Generally, we used 200 epochs in total, SGD with momentum 0.9 and weight decay $2\times 10^{-4}$ as the optimizer, and an initial learning rate of 0.1, which was decayed by a factor of $0.2$ after epochs 60, 120 and 160. For adversarial training, the parameters are represented in a tuple: {$T$, $\alpha$, $\epsilon$}. The adversarial parameters were set to {10,$1/255$,$8/255$} for CIFAR-10 and CIFAR-100. For MNIST, the adversarial parameters were set to {100, 0.01, 0.1}. All adversarial examples were generated by adding an initial random perturbation $\delta^{0}$ with $||\delta^{0}||_{\infty}\leq\epsilon$.

Table 2 displays the training time and test accuracy to train all robust models on different datasets. Table 3 shows the elapsed time of different models to generate adversarial examples with RAT and GAAT on the CIFAR-10 dataset.

Training time. To assess how much training time the approximate gradient can reduce, we conducted experiments to record the elapsed time of generating 10-step adversarial examples with the true gradient and the approximate gradient. The results on the CIFAR-10 dataset with different models are shown in Table 3, where Line 5-8 in Algorithm 1 represent generating adversarial examples with RAT; Line 6-7 in Algorithm 1 denote one step PGD with RAT; Line 4-10 in Algorithm 2 represent generating adversarial examples with GAAT; Line 8-9 in Algorithm 2 denote one step PGD with GAAT; and Line 4-6 in Algorithm 2 denote computing the Hessian matrix. Evidently, our method greatly reduces the elapsed time of generating adversarial examples, and for larger and more complicated models, e.g., ResNet-50 and WideResNet-28x4, our method reduces the elapsed time by a larger margin. Besides, the time of computing the Hessian matrix (Line 4-6 in Algorithm 2) relates to the depth of models. However, it is negligible compared with the time of generating adversarial examples.

We also evaluated the total training time for RAT and GAAT with different models on different datasets. The results are displayed in Table 2, showing that the overhead are remarkably decreased when using our proposed method. For all models, we obtained significant reduction in time overhead. Note that the more complex the model is, the greater overhead reduction our method achieves. For instance, our method saves 60% of the time overhead when training a robust WideResNet-28x4 model.

Test accuracy. From Table 2, we find that the test accuracy of models trained with our method is very close to that of models trained with RAT. In fact, the natural accuracy (tested with natural examples) of models trained with our method is a little higher than that of models trained with RAT, while the adversarial accuracy (tested with adversarial examples) of models trained with our method is a little lower than that of models trained with RAT. The possible reason of these results is that we used an approximate gradient to replace the true gradient. Exactly, the approximate gradient is smaller than the true gradient because the approximate gradient omits the high-order items of the true gradient. Hence, in our method, we used weaker attacks than the attack in RAT to adversarially train a robust model. The little loss of the adversarial accuracy is acceptable, compared with the great time overhead saving.

Delayed adversarial training (DAT), which uses the natural training to replace the adversarial training for the initial epochs, reduces much time overhead and achieves comparable accuracy. In this subsection, we compare it with our method, and then combine it with our method to further improve adversarial training efficiency. Additionally, early stopping strategy Rice et al. (2020) is regarded as an effective way to avert adversarial overfitting; thus we also used this strategy to save training time and improve model robustness. Table 4 shows the training time and test accuracy of RAT, DAT, GAAT and DAT+GAAT methods. Here, we used the CIFAR-10 dataset and the ResNet-50 model. In DAT and DAT+GAAT, we switched natural training to adversarial training after epoch 100.

As shown in Table 4, GAAT and DAT both significantly reduce the time cost of establishing a robust model, while GAAT can save more time. More intriguingly, when combining DAT with GAAT, DAT+GAAT reduces the time overhead to a greater extent, saving about 70% of the training time compared with RAT (80% with early stopping). Besides, by using early stopping strategy, training efficiency and model robustness are both improved.

We assessed robustness of the four model in Table 4 against attacks of different strength which they were not trained to defend against. We varied the number of PGD steps and the value of $\epsilon$ to test attacks. Figure 2 shows the performances with RAT, DAT, GAAT and DAT+GAAT methods on the CIFAR-10 dataset. The models trained using three efficient methods, i.e., DAT, GAAT and DAT+GAAT, achieve comparable robustness against a wide range of PGD attacks and follows the same pattern as RAT.