SOAR: Second-Order Adversarial Regularization

Adversarial training (Szegedy et al., 2013) is the standard approach for improving the robustness of deep neural networks (DNN), or any other model, against adversarial examples. It is a data augmentation method that adds adversarial examples to the training set and updates the network with newly added data points. Intuitively, this procedure encourages the DNN not to make the same mistakes against an adversary. By adding sufficiently enough adversarial examples, the network gradually becomes robust to the attack it was trained on. One of the challenges with such a data augmentation approach is the tremendous amount of additional data required for learning a robust model. Schmidt et al. (2018) show that under a Gaussian data model, the sample complexity of robust generalization is $\sqrt{d}$ times larger than that of standard generalization. They further suggest that current datasets (e.g., CIFAR-10) may not be large enough to attain higher adversarial accuracy. A data augmentation procedure, however, is an indirect way to improve the robustness of a DNN. Our proposed alternative is to define a regularizer that penalizes DNN parameters prone to attacks. Minimizing the regularized loss function leads to estimators robust to adversarial examples.

Adversarial training and our proposal can both be formulated in terms of robust optimization framework for adversarial robustness (Ben-Tal et al., 2009; Madry et al., 2018; Wong and Kolter, 2018; Shaham et al., 2018; Sinha et al., 2018). In this formulation, one is seeking to improve the worst-case performance of the model, where the performance is measured by a particular loss function $\ell$. Adversarial training can be understood as approximating such a worst-case loss by finding the corresponding worst-case data point, i.e., $x+\delta$ with some specific attack techniques. Our proposed method is more direct. It is based on approximating the loss function $\ell(x+\delta)$ using its second-order Taylor series expansion, i.e.,

and then upper bounding the worst-case loss using the expansion terms. By considering both gradient and Hessian of the loss function with respect to (w.r.t.) the input, we can provide a more accurate approximation to the worst-case loss. In our derivations, we consider both $\ell_{2}$ and $\ell_{\infty}$ attacks. In our derivations, the second-order expansion incorporates both the gradient and Hessian of the loss function with respect to (w.r.t.) the input. We call the method Second-Order Adversarial Regularizer (SOAR) (not to be confused with the Soar cognitive architecture Laird 2012). In the course of development of SOAR, we make the following contributions:

• •

  We show that an over-parameterized linear regression model can be severely affected by an adversary, even though its population loss is zero. We robustify it with a regularizer that exactly mimics the adversarial training. This suggests that regularization can be used instead of adversarial training (Section 2).

• •

  Inspired by such a possibility, we develop a regularizer which upper bounds the worst-case effect of an adversary under an approximation of the loss. In particular, we derive SOAR, which approximates the inner maximization of the robust optimization formulation based on the second-order Taylor series expansion of the loss function (Section 4).

• •

  We study SOAR in the logistic regression setting and reveal challenges with regularization using Hessian w.r.t. the input. We develop a simple initialization method to circumvent the issue (Section 4.1).

• •

  We empirically show that SOAR significantly improves the adversarial robustness of the network against $\ell_{\infty}$ attacks and $\ell_{2}$ attacks generated based on cross-entropy-based PGD (Madry et al., 2018) on CIFAR-10 and SVHN (Sections 5.1 and 5.2).

• •

  Our result on state-of-the-art attack method AutoAttack (Croce and Hein, 2020) reveals SOAR’s vulnerability. We include a thorough empirical study by investigating how SOAR regularized models behave under different strengths of AutoAttacks (different $\varepsilon$), as well as they react to different parts of the AutoAttack algorithm. Based on the results, we discuss several hypotheses on SOAR’s vulnerability (Section 5.3).

This section shows that for over-parameterized linear models, gradient descent (GD) finds a solution that has zero population loss, but is prone to attacks. It also shows that one can avoid this problem with defining an appropriate regularizer. Hence, we do not need adversarial training to robustify such a model. This simple illustration motivates the development of our method in next sections. We only briefly report the main results here, and defer the derivations to Appendix A.

Consider a linear model $f_{w}(x)=\left\langle\,w\,,\,x\,\right\rangle$ with $x,w\in\mathbb{R}^{d}$. Suppose that $w^{*}=(1,0,\dotsc,0)^{\top}$ and the distribution of $x\sim p$ is such that it is confined on a $1$-dimensional subspace $\left\{\,(x_{1},0,0,\dotsc,0)\,:\,x_{1}\in\mathbb{R}\,\right\}$. This setup can be thought of as using an over-parameterized model that has many irrelevant dimensions with data that is only covering the relevant dimension of the input space. This is a simplified model of the situation when the data manifold has a dimension lower than the input space. We consider the squared error pointwise loss $l(x;w)=\frac{1}{2}\left|\left\langle\,x\,,\,w\,\right\rangle-\left\langle\,x\,,\,w^{*}\,\right\rangle\right|^{2}$. Denote the residual by $r(x;w)=\left\langle\,x\,,\,w-w^{*}\,\right\rangle$, and the population loss by $\mathcal{L}(w)={\mathbb{E}}\left[l(X;w)\right]$.

Suppose that we initialize the weights as $w(0)=W\sim N(0,\sigma^{2}\mathbf{I}_{d\times d})$, and use GD on the population loss, i.e., $w(t+1)\leftarrow w(t)-\beta\nabla_{w}\mathcal{L}(w)$. It is easy to see that the partial derivatives w.r.t. $w_{2,\dotsc,d}$ are all zero, i.e., no weight adaptation happens. With a proper choice of learning rate $\beta$, we get that the asymptotic solution is $\bar{w}\triangleq\lim_{r\rightarrow\infty}w(t)=(w^{*}_{1},w_{2}(0),w_{3}(0),\dotsc,w_{d}(0))^{\top}$. That is, the initial random weights on dimensions $2,\dotsc,d$ do not change.

We make two observations. The first is that $\mathcal{L}(\bar{w})=0$, i.e., the population loss is zero. So from the perspective of training under the original loss, we are finding the optimal solution. The second observation is that this model is vulnerable to adversarial examples. An FGSM-like attack that perturbs $x$ by $\Delta x=(0,\Delta x_{2},\Delta x_{3},\dotsc,\Delta x_{d})^{\top}$ with $\Delta x_{i}=\varepsilon\operatorname{\mathrm{sign}}(w_{i}(0))$ (for $i=2,\dotsc,d$) has the population loss of ${\mathbb{E}}_{X,W}\left[l(X+\Delta x);\bar{w})\right]\approx O(\varepsilon^{2}d^{2}\sigma^{2})$ under the adversary at the asymptotic solution $\bar{w}$. When the dimension is large, this loss is quite significant. The culprit is obviously that GD is not forcing the initial weights to go to zero when there is no data from irrelevant and unused dimensions. This simple problem illustrates how the optimizer and an over-parameterized model might interact and lead to a solution that is prone to attacks.

An effective solution is to regularize the loss such that the weights of irrelevant dimensions to go to zero. Generic regularizers such as ridge and Lasso regression lead to a biased estimate of $w_{1}^{*}$, and thus, one is motivated to define a regularizer that is specially-designed for improving adversarial robustness. Bishop (1995) showed the close connection between training with random perturbation and Tikhonov Regularization. Inspired by this idea, we develop a regularizer that mimics the adversary itself. For this FGSM-like adversary, the population loss at the perturbed point is

Minimizing $\mathcal{L}_{\text{robustified}}(w)$ is equivalent to minimizing the model at the point $x^{\prime}=x+\Delta x$. The regularizer $\varepsilon{\mathbb{E}}\left[r(X;w)\right]\left\|w_{2:d}\right\|_{1}+\frac{\varepsilon^{2}}{2}\left\|w_{2:d}\right\|_{1}^{2}$ incorporates the effect of adversary in exact form.

Nonetheless, there are two limitations of this approach. The first is that it is designed for a particular choice of attack, an FGSM-like one. We would like a regularizer that is robust to a larger class of attacks. The second is that this regularizer is designed for a linear model and the squared error loss. How can we design a regularizer for more complicated models, such as DNNs? We address these questions by formulating the problem of adversarial robustness within the robust optimization framework (Section 3), and propose an approach to approximately solve it (Section 4).

Designing an adversarial robust estimator can be formulated as a robust optimization problem (Huang et al., 2015; Madry et al., 2018; Wong and Kolter, 2018; Shaham et al., 2018). To describe it, let us introduce our notations first. Consider an input space ${\mathcal{X}}\subset\mathbb{R}^{d}$, an output space ${\mathcal{Y}}$, and a parameter (or hypothesis) space ${\mathcal{W}}$, parameterizing a model $f:{\mathcal{X}}\times{\mathcal{W}}\rightarrow{\mathcal{Y}}$. In the supervised learning scenario, we are given a data distribution ${\mathcal{D}}$ over pairs of examples $\{(X_{i},Y_{i})\}_{i=1}^{n}$. Given the prediction of $f(x;w)$ and a target value $y$, the pointwise loss function of the model is denoted by $\ell(x,y;w)\triangleq\ell(f(x;w),y)$. Given the distribution of data, one can define the population loss as $\mathcal{L}(w)={\mathbb{E}}\left[\ell(X,Y;w)\right]$. The goal of the standard supervised learning problem is to find a $w\in{\mathcal{W}}$ that minimizes the population loss. A generic approach to do this is through empirical risk minimization (ERM). Explicit or implicit regularization is often used to control the complexity of the hypothesis to avoid over- or under-fitting (Hastie et al., 2009).

As shown in the previous section, it is possible to find a parameter $w$ that minimizes the loss through ERM, but leads to a model that is vulnerable to adversarial examples. To incorporate the robustness notion in the model, it requires defenders to reconsider the training objective. It is also important to formalize and constrain the power of the adversary, so we understand the strength of the attack to which the model is resistant. This can be specified by limiting that the adversary can only modify any input $x$ to $x+\delta$ with $\delta\in\Delta\subset{\mathcal{X}}$. Commonly used constraints are $\varepsilon$-balls w.r.t. the $\ell_{p}$-norms, though other constraint sets have been used too (Wong et al., 2019b). This goal can be formulated as a robust optimization problem where the objective is to minimize the adversarial population loss given some perturbation constraint $\Delta$:

We have an interplay between two goals: 1) the inner-max term looks for the worst-case loss around the input, while 2) the outer-min term optimizes the hypothesis by minimizing such a loss.

Note that solving the inner-max problem is often computationally difficult, so one may approximate it with a surrogate loss obtained from a particular attack. Adversarial training and its variants (Szegedy et al., 2013; Goodfellow et al., 2014; Kurakin et al., 2016; Madry et al., 2018; Wong et al., 2019a) can be intuitively understood as an approximation of this min-max problem via different $\delta(x)$.

As shown in Section 2, one can design a regularizer that provides the exact value of the loss function at the attacked point for a particular choice of model, loss function, and adversary, cf. (1). Under the robust optimization framework, the regularizer and adversarial training are two realizations of the inner-max objective in (2), but using such a regularizer relieved us from using a separate inner optimization procedure, as is done in adversarial training. Motivated by that example and the robust optimization framework discussed here, we develop a regularizer that can be understood as an upper-bound on the worst-case value of the loss at an attacked point under a second-order approximation of the loss function.

The main idea of SOAR is to approximate the loss function using the second-order Taylor series expansion around an input $x$ and then solve the inner maximization term of the robust optimization formulation (2) using the approximated form. We show this for both $\ell_{2}$ and $\ell_{\infty}$ attacks; the same idea can be applied to other $\ell_{p}$ norms. We describe crucial steps of the derivation in this section, and defer details to Appendix B .

Assuming that the loss is twice-differentiable, we can approximate the loss function around input $x$ by the second-order Taylor expansion

For brevity, we drop $w$, $y$ and use $\nabla$ to denote $\nabla_{x}$. Let us focus on the $\ell_{p}$ attacks, where the constraint set in (2) is $\Delta=\{\delta:\left\|\delta\right\|_{p}\leq\varepsilon\}$ for some $\varepsilon>0$ and $p\geq 1$. We focus on the $\ell_{\infty}$ attack because of its popularity, but we also derive the formulation for the $\ell_{2}$ attacks.

As a warm-up, let us solve the inner optimization problem by considering the first-order Taylor series expansion. We have

The term $\varepsilon\left\|\nabla\ell(x)\right\|_{1}$ defines the First-Order Adversarial Regularizer (FOAR). This is similar to the regularizer introduced by Simon-Gabriel et al. (2019) with the choice of $\ell_{\infty}$ perturbation set. For a general $\ell_{p}$-attach with $1\leq p\leq\infty$, we have $\left\|\nabla\ell(x)\right\|_{q}$ with $q$ satisfying $p^{-1}+q^{-1}=1$. We shall empirically evaluate FOAR-based approach (for the $\ell_{\infty}$ attack), but our focus is going to be on solving the inner maximization problem based on the second-order Taylor expansion:

for $p=2,\infty$. The second-order expansion in (3) can be rewritten as

where $\delta^{\prime}=[\delta;1]$. This allows us to derive an upper bound on the expansion terms using the characteristics of a single Hessian term $\mathbf{H}$. Note that $\delta^{\prime}$ is a $d+1$-dimensional vector and $\mathbf{H}$ is a $(d+1)\times(d+1)$ matrix. We need to find an upper bound on $\delta^{\prime\top}\mathbf{H}\delta^{\prime}$ under the attack constraint.

For the $\ell_{\infty}$ attack, solving this maximizing problem is not as easy as in (4) since the Boolean quadratic programming problem in formulation (5) is NP-hard. But we can relax the constraint set and find an upper bound for the maximizer. Note that with $\delta\in\mathbb{R}^{d}$, an $\ell_{\infty}$-ball of size $\varepsilon$ is enclosed by an $\ell_{2}$-ball of size $\sqrt{d}\varepsilon$ with the same centre. Therefore, we can upper bound the inner maximization by

which after substituting the second-order Taylor series expansion leads to an $\ell_{2}$-constrained quadratic optimization problem

with $\delta^{\prime}=[\delta;1]$ as before. The $\ell_{2}$ version of SOAR does not require this extra step, and we have $\varepsilon$ instead of $\sqrt{d}\varepsilon$ in (8). A more detailed discussion on the above relaxation procedure is included in Appendix B.2 .

This result upper bounds the maximum of the second-order approximation $\tilde{\ell}_{\text{2nd}}$ over an $\ell_{\infty}$ ball with radius $\varepsilon$, and relates it to an expectation of a Hessian-vector product. Note that there is a simple correspondence between (1) and regularized loss in (9). The latter can be understood as an upper bound on the worst-case damage of an adversary under a second-order approximation of the loss. For the $\ell_{2}$ attack, the same line of argument leads to $\varepsilon^{2}+1$ instead of $d\varepsilon^{2}+1$.

Let us take a closer look at $\mathbf{H}z$. By decomposing $z=\left[z_{d},z_{1}\right]^{\top}$, we get

The term $\nabla^{2}\ell(x)z_{d}$ can be computed using Finite Difference (FD) approximation. Note that ${\mathbb{E}}\left[\left\|z_{d}\right\|_{2}\right]=\sqrt{d}$ for our Normally distributed $z$. To ensure that the approximation direction has the same magnitude, we use the normalized $\tilde{z}_{d}=\frac{z_{d}}{\left\|z_{d}\right\|_{2}}$ instead, and use the approximation below

To summarize, SOAR regularizer evaluated at $x$, with a direction $z$, and FD step size $h>0$ is

The expectation in (9) can then be approximated by taking multiple samples of $z$ drawn from $z\sim\mathcal{N}(0,\mathbf{I}_{(d+1)\times(d+1)})$. These samples would be concentrated around its expectation. One can show that ${\mathbb{P}}\left\{\left\|Hz\right\|-{\mathbb{E}}\left[\left\|Hz\right\|\right]>t\right\}\leq 2\exp(-\frac{ct^{2}}{\left\|H\right\|_{2}})$, where $c$ is a constant and $\left\|H\right\|_{2}$ is the $\ell_{2}$-induced norm (see Theorem 6.3.2 of Vershynin 2018). In practice, we observed that taking more than one sample of $z$ do not provide significant improvement for increasing adversarial robustness, and we include an empirical study on the the effect of sample sizes in Appendix E.4 .

Before we discuss the remaining details, recall that we fully robustify the model with an appropriate regularizer in Section 2. Note the maximizer of the loss based on formulation (2) is exactly the FGSM direction, and (1) shows the population loss with our FGSM-like choice of $\Delta x$. To further motivate a second-order approach, note that we can obtain the first two terms in (1) with a first-order regularizer such as FOAR; and we recover the exact form with a second-order formulation in (5).

Next, we study SOAR in the simple logistic regression setting, which shows potential failure of the regularizer and reveals why we might observe gradient masking. Based on that insight, we provide the remaining details of the method afterwards in Section 4.1.

In this section, we verify the effectiveness of the proposed regularization method against $\ell_{\infty}$ PGD attacks on CIFAR10. Our experiments show that training with SOAR leads to significant improvements in adversarial robustness against PGD attacks based on the cross-entropy loss under bothe the black-box and white-box settings. We discover that SOAR regularized model is more vulnerable under the state-of-the-art AutoAttack(Croce and Hein, 2020). We focus on $\ell_{\infty}$ in this section and defer evaluations on $\ell_{2}$ in Appendix E.5. Additionally, we provide a detailed discussion and evaluations on the SVHN dataset in Appendix E.6.

We train ResNet-10 (He et al., 2016) on the CIFAR-10 dataset. The baseline methods consist of: (1) Standard: training with no adversarially perturbed data; (2) ADV: training with 10-step PGD adversarial examples; (3) TRADES; (4) MART and (5) MMA. Empirical studies in Madry et al. (2018) and Wang et al. (2020) reveal that their approaches benefit from increasing model capacity to achieve higher adversarial robustness, as such, we include WideResNet (Zagoruyko and Komodakis, 2016) for all baseline methods. We were not able to reproduce the results of two closely related works, CURE and LLR, which we discuss further in Appendix E.1. In Appendix E.13, we compare SOAR and FOAR with different initializations. FOAR achieves the best adversarial robustness using PGD1 initialization, so we only present this variation of FOAR in this section.

The optimization procedure is described in detail in Appendix E.2. Note that all methods in this section are trained to defend against $\ell_{\infty}$ norm attacks with $\varepsilon=8/255$, as this is a popular choice of $\varepsilon$ in the literature. The PGD adversaries discussed in Sections 5.1 and 5.2 are generated with $\varepsilon=8/255$ and a step size of $2/255$ (pixel values are normalized to $[0,1]$). PGD20-50 denotes 20-step PGD attacks with 50 restarts. In Section 5.3, we compare SOAR with baseline methods on $\ell_{\infty}$ AutoAttack (Croce and Hein, 2020) adversaries with a varying $\varepsilon$. Additionally, results of all methods on ResNet10 are obtained by averaging over 3 independently initialized and trained models, where the standard deviations are reported in Appendix E.10. We use the provided pretrained WideResNet model provided in the public repository of each method. Lastly, discussions on challenges (i.e., difficult to train from scratch, catastrophic overfitting, BatchNorm, etc.) we encountered while implementing SOAR and our solutions (i.e., using pretrained model, clipping regularizer gradient, early stopping, etc.) are included in Appendix E.7.

This work proposed SOAR, a regularizer that improves the robustness of DNN to adversarial examples. SOAR was obtained using the second-order Taylor series approximation of the loss function w.r.t. the input, and approximately solving the inner maximization of the robust optimization formulation. We showed that training with SOAR leads to significant improvement in adversarial robustness under $\ell_{\infty}$ and $\ell_{2}$ attacks. This is only one step in designing better regularizers to improve the adversarial robustness. Several directions deserve further study, with the prominent one being SOAR’s vulnerabilities to AutoAttack. Another future direction is to understand the loss surface of DNN better in order to select a good point around which an accurate Taylor approximation can be made. This is important for designing regularizers that are not affected by gradient masking.