Adversarial Attack Generation Empowered by Min-Max Optimization
Year: 2022

Abstract:
The worst-case training principle that minimizes the maximal adversarial loss, also known as adversarial training (AT), has shown to be a state-of-the-art approach for enhancing adversarial robustness. Nevertheless, min-max optimization beyond the purpose of AT has not been rigorously explored in the adversarial context. In this paper, we show how a general framework of min-max optimization over multiple domains can be leveraged to advance the design of different types of adversarial attacks. In particular, given a set of risk sources, minimizing the worst-case attack loss can be reformulated as a min-max problem by introducing domain weights that are maximized over the probability simplex of the domain set. We showcase this unified framework in three attack generation problems – attacking model ensembles, devising universal perturbation under multiple inputs, and crafting attacks resilient to data transformations. Extensive experiments demonstrate that our approach leads to substantial attack improvement over the existing heuristic strategies as well as robustness improvement over state-of-the-art defense methods trained to be robust against multiple perturbation types. Furthermore, we find that the self-adjusted domain weights learned from our min-max framework can provide a holistic tool to explain the difficulty level of attack across domains. Code is available at https://github.com/wangjksjtu/minmax-adv.

heading: 1 Introduction
text: Training a machine learning model that is capable of assuring its worst-case performance against possible adversaries given a specified threat model is a fundamental and challenging problem, especially for deep neural networks (DNNs) [64, 22, 13, 69, 70]. A common practice to train an adversarially robust model is based on a specific form of min-max training, known as adversarial training (AT) [22, 40], where the minimization step learns model weights under the adversarial loss constructed at the maximization step in an alternative training fashion. In practice, AT has achieved the state-of-the-art defense performance against `p-norm-ball input perturbations [3].
Although the min-max principle is widely used in AT and its variants [40, 59, 76, 65], few work has studied its power in attack generation. Thus, we ask: Beyond AT, can other types of min-max formulation and optimization techniques advance the research in adversarial attack generation? In this paper, we give an affirmative answer corroborated by the substantial performance gain and the ability of self-learned risk interpretation using our proposed min-max framework on several tasks for adversarial attack.
⇤Equal contributions.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We demonstrate the utility of a general formulation for minimizing the maximal loss induced from a set of risk sources (domains). Our considered min-max formulation is fundamentally different from AT, as our maximization step is taken over the probability simplex of the set of domains. Moreover, we show that many problem setups in adversarial attacks can in fact be reformulated under this general min-max framework, including attacking model ensembles [66, 34], devising universal perturbation to input samples [44] and data transformations [6, 10]. However, current methods for solving these tasks often rely on simple heuristics (e.g., uniform averaging), resulting in significant performance drops when comparing to our proposed min-max optimization framework.
Contributions ¨ With the aid of min-max optimization, we propose a unified alternating onestep projected gradient descent-ascent (APGDA) attack method, which can readily be specified to generate model ensemble attack, universal attack over multiple images, and robust attack over data transformations. ≠ In theory, we show that APGDA has an O(1/T ) convergence rate, where T is the number of iterations. In practice, we show that APGDA obtains 17.48%, 35.21% and 9.39% improvement on average compared with conventional min-only PGD attack methods on CIFAR-10. Æ More importantly, we demonstrate that by tracking the learnable weighting factors associated with multiple domains, our method can provide tools for self-adjusted importance assessment on the mixed learning tasks. Ø Finally, we adapt the idea of the domain weights into a defense setting [65], where multiple `p-norm perturbations are generated, and achieve superior performance as well as intepretability.

heading: 1.1 Related work
text: Recent studies have identified that DNNs are highly vulnerable to adversarial manipulations in various applications [64, 12, 27, 33, 26, 14, 77, 20, 15, 31], thus leading to an arms race between adversarial attacks [13, 3, 23, 48, 45, 72, 1, 18] and defenses [40, 59, 76, 65, 42, 71, 74, 68, 53, 16]. One intriguing property of adversarial examples is the transferability across multiple domains [36, 67, 47, 62], which indicates a more challenging yet promising research direction – devising universal adversarial perturbations over model ensembles [66, 34], input samples [44, 43, 56] and data transformations [3, 6, 10].
Besides, many recent works started to produce physical realizable perturbations that expose real world threats. The most popular approach [4, 21], as known as Expectation Over Transformation (EOT), is to train the attack under different data transformation (e.g., different view angles and distances). However, current approaches suffer from a significant performance loss for resting on the uniform averaging strategy or heuristic weighting schemes [34, 56]. We will compare these works with our min-max method in Sec. 4. As a natural extension following min-max attack, we study the generalized AT under multiple perturbations [65, 2, 28, 17]. Finally, our min-max framework is adapted and inspired by previous literature on robust optimization over multiple domains [50, 51, 38, 37].
To our best knowledge, only few works leverage min-max principle for adversarial attack generation while the idea of producing the worst-case example across multiple domains is quite natural. Specifically, [7] considered the non-interactive blackbox adversary setting and proposed a framework that models the crafting of adversarial examples as a min-max game between a generator of attacks and a classifier. [57] introduced a min-max based adaptive attacker’s objective to craft perturbation so that it simultaneously evades detection and causes misclassification. Inspired by our work, the min-max formulation has also been extended to zero-order blackbox attacks [35] and physically realizable attacks [73, Adversarial T-shirt]. We hope our unified formulation can stimulate further research on applying min-max principle and interpretable domain weights in more attack generation tasks that involve in evading multiple systems.

heading: 2 Min-Max Across Domains
text: Consider K loss functions {Fi(v)} (each of which is defined on a learning domain), the problem of robust learning over K domains can be formulated as [50, 51, 38]
minimize v2V maximize w2P
P K
i=1 wiFi(v), (1)
where v and w are optimization variables, V is a constraint set, and P denotes the probability simplex P = {w |1Tw = 1, wi 2 [0, 1], 8i}. Since the inner maximization problem in (1) is a linear function
of w over the probabilistic simplex, problem (1) is thus equivalent to minimize
v2V maximize i2[K] Fi(v), (2)
where [K] denotes the integer set {1, 2, . . . ,K}.
Benefit and Challenge from (1). Compared to multi-task learning in a finite-sum formulation which minimizes K losses on average, problem (1) provides consistently robust worst-case performance across all domains. This can be explained from the epigraph form of (2),
minimize v2V,t t, subject to Fi(v)  t, i 2 [K], (3) where t is an epigraph variable [8] that provides the t-level robustness at each domain.
In computation, the inner maximization problem of (1) always returns the one-hot value of w, namely, w = ei, where ei is the ith standard basis vector, and i = argmaxi{Fi(v)}. However, this one-hot coding reduces the generalizability to other domains and induces instability of the learning procedure in practice. Such an issue is often mitigated by introducing a strongly concave regularizer in the inner maximization step to strike a balance between the average and the worst-case performance [38, 50].
Regularized Formulation. Following [50], we penalize the distance between the worst-case loss and the average loss over K domains. This yields
minimize v2V maximize w2P
P K
i=1 wiFi(v) 2 kw 1/Kk 2 2, (4)
where > 0 is a regularization parameter. As ! 0, problem (4) is equivalent to (1). By contrast, it becomes the finite-sum problem when ! 1 since w ! 1/K. In this sense, the trainable w provides an essential indicator on the importance level of each domain. The larger the weight is, the more important the domain is. We call w domain weights in this paper.

heading: 3 Min-Max Power in Attack Design
text: To the best of our knowledge, few work has studied the power of min-max in attack generation. In this section, we demonstrate how the unified min-max framework (4) fits into various attack settings. With the help of domain weights, our solution yields better empirical performance and explainability. Finally, we present the min-max algorithm with convergence analysis to craft robust perturbations against multiple domains.

heading: 3.1 A Unified Framework for Robust Adversarial Attacks
text: The general goal of adversarial attack is to craft an adversarial example x0 = x0 + 2 Rd to mislead the prediction of machine learning (ML) or deep learning (DL) systems, where x0 denotes the natural example with the true label t0, and is known as adversarial perturbation, commonly subject to `p-norm (p 2 {0, 1, 2,1}) constraint X := { | k kp  ✏, x0 + 2 [0, 1]d} for a given small number ✏. Here the `p norm enforces the similarity between x0 and x0, and the input space of ML/DL systems is normalized to [0, 1]d.
Ensemble Attack over Multiple Models. Consider K ML/DL models {Mi}Ki=1, the goal is to find robust adversarial examples that can fool all K models simultaneously. In this case, the notion of ‘domain’ in (4) is specified as ‘model’, and the objective function Fi in (4) signifies the attack loss f( ;x0, y0,Mi) given the natural input (x0, y0) and the model Mi. Thus, problem (4) becomes
minimize 2X maximize w2P
P K
i=1 wif( ;x0, y0,Mi) 2 kw 1/Kk 2 2, (5)
where w encodes the difficulty level of attacking each model.
Universal Perturbation over Multiple Examples. Consider K natural examples {(xi, yi)}Ki=1 and a single model M, our goal is to find the universal perturbation so that all the corrupted K examples can fool M. In this case, the notion of ‘domain’ in (4) is specified as ‘example’, and problem (4) becomes
minimize 2X maximize w2P
P K
i=1 wif( ;xi, yi,M) 2 kw 1/Kk 2 2, (6)
where different from (5), w encodes the difficulty level of attacking each example.
Adversarial Attack over Data Transformations. Consider K categories of data transformation {pi}, e.g., rotation, lightening, and translation, our goal is to find the adversarial attack that is robust to data transformations. Such an attack setting is commonly applied to generate physical adversarial examples [5, 20]. Here the notion of ‘domain’ in (4) is specified as ‘data transformer’, and problem (4) becomes
minimize 2X maximize w2P
P K
i=1 wiEt⇠pi [f(t(x0 + ); y0,M)] 2 kw 1/Kk 2 2, (7)
where Et⇠pi [f(t(x0+ ); y0,M)] denotes the attack loss under the distribution of data transformation pi, and w encodes the difficulty level of attacking each type of transformed example x0. We remark that if w = 1/K, then problem (7) reduces to the existing expectation of transformation (EOT) setup used for physical attack generation [5].
Benefits of Min-Max Attack Generation with Learnable Domain Weights w: We can interpret (5)-(7) as finding the robust adversarial attack against the worst-case environment that an adversary encounters, e.g., multiple victim models, data samples, and input transformations. The proposed min-max design of adversarial attacks leads to two main benefits. First, compared to the heuristic weighting strategy (e.g., clipping thresholds on the importance of individual attack losses [56]), our proposal is free of supervised manual adjustment on domain weights. Even by carefully tuning the heuristic weighting strategy, we find that our approach with self-adjusted w consistently outperforms the clipping strategy in [56] (see Table 2). Second, the learned domain weights can be used to assess the model robustness when facing different types of adversary. We refer readers to Figure 1c and
Figure 6 for more details.

heading: 3.2 Min-Max Algorithm for Adversarial Attack Generation
text: Algorithm 1 APGDA to solve problem (4) 1: Input: given w(0) and (0). 2: for t = 1, 2, . . . , T do 3: outer min.: fixing w = w(t 1), call
PGD (8) to update (t) 4: inner max.: fixing = (t), update w(t) with projected gradient ascent (9) 5: end for
We propose the alternating projected gradient descent-ascent (APGDA) method (Algorithm 1) to solve problem (4). For ease of presentation, we write problems (5), (6), (7) into the general form minimize
2X maximize w2P
PK i=1 wiFi( ) 2 kw 1/Kk 2 2,
where Fi denotes the ith individual attack loss. We show that at each iteration, APGDA takes only one-step PGD for outer minimization and one-step projected gradient ascent for inner maximization.
Outer Minimization Considering w = w(t 1) and F ( ) := P K
i=1 w (t 1) i
Fi( ) in (4), we perform one-step PGD to update at iteration t,
(t) = projX (t 1) ↵r F ( (t 1)) , (8)
where proj(·) denotes the Euclidean projection operator, i.e., projX (a) = argminx2X kx ak22 at the point a, ↵ > 0 is a given learning rate, and r denotes the first-order gradient w.r.t. . If p = 1, then the projection function becomes the clip function. In Proposition 1, we derive the solution of projX (a) under different `p norms for p 2 {0, 1, 2}. Proposition 1. Given a point a 2 Rd and a constraint set X = { |k kp  ✏, č   ĉ}, the Euclidean projection ⇤ = projX (a) has a closed-form solution when p 2 {0, 1, 2}, where the specific form is given by Appendix A.
Inner Maximization By fixing = (t) and letting (w) := P K
i=1 wiFi( (t)) 2 kw 1/Kk 2 2
in problem (4), we then perform one-step PGD (w.r.t. ) to update w,
w(t) = projP ⇣ w(t 1) + rw (w
(t 1))| {z } b
⌘ = (b µ1)+ , (9)
where > 0 is a given learning rate, rw (w) = (t) (w 1/K), and (t) := [F1( (t)), . . . , FK( (t))]T . In (9), the second equality holds due to the closed-form of projection operation onto the probabilistic simplex P [49], where (x)+ = max{0, x}, and µ is the root of the equation 1T (b µ1)+ = 1. Since 1T (b mini{bi}1 + 1/K)+ 1T1/K = 1, and 1T (b maxi{bi}1 + 1/K)+  1T1/K = 1, the root µ exists within the interval [mini{bi} 1/K,maxi{bi} 1/K] and can be found via the bisection method [8].
Convergence Analysis We remark that APGDA follows the gradient primal-dual optimization framework [37], and thus enjoys the same optimization guarantees. Theorem 1. Suppose that in problem (4) Fi( ) has L-Lipschitz continuous gradients, and X is a convex compact set. Given learning rates ↵ 
1 L and < 1 , then the sequence { (t),w(t)}T t=1
generated by Algorithm 1 converges to a first-order stationary point 2 in rate O 1 T .
Proof : Note that the objective function of problem (4) is strongly concave w.r.t. w with parameter , and has -Lipschitz continuous gradients. Moreover, we have kwk2  1 due to w 2 P . Using these facts and Theorem 1 in [37] or [39] completes the proof. ⇤

heading: 4 Experiments on Adversarial Exploration
text: In this section, we first evaluate the proposed min-max optimization strategy on three attack tasks. We show that our approach leads to substantial improvement compared with state-of-the-art attack methods such as average ensemble PGD [34] and EOT [3, 10, 5]. We also demonstrate the effectiveness of learnable domain weights in guiding the adversary’s exploration over multiple domains.

heading: 4.1 Experimental setup
text: We thoroughly evaluate our algorithm on MNIST and CIFAR-10. A set of diverse image classifiers (denoted from Model A to Model H) are trained, including multi-layer perceptron (MLP), All-CNNs [61], LeNet [30], LeNetV2, VGG16 [58], ResNet50 [24], Wide-ResNet [40, 75] and GoogLeNet [63]. The details about model architectures and training process are provided in Appendix D.1. Note that problem formulations (5)-(7) are applicable to both untargeted and targeted attack. Here we focus on the former setting and use C&W loss function [13, 40] with a confidence parameter  = 50. The adversarial examples are generated by 20-step PGD/APGDA unless otherwise stated (e.g., 50 steps for ensemble attacks). APGDA algorithm is relatively robust and will not be affected largely by the choices of hyperparameters (↵, , ). Apart from absolute attack success rate (ASR), we also report the relative improvement or degradationon the worse-case performance in experiments: Lift("). The details of crafting adversarial examples are available in Appendix D.2.

heading: 4.2 Ensemble Attack over Multiple Models
text: We craft adversarial examples against an ensemble of known classifiers. Recent work [34] proposed an average ensemble PGD attack, which assumed equal importance among different models, namely, wi = 1/K in problem (5). Throughout this task, we measure the attack performance via ASRall - the attack success rate (ASR) of fooling model ensembles simultaneously. Compared to the average PGD attack, our approach results in 40.79% and 17.48% ASRall improvement averaged over different `p-norm constraints on MNIST and CIFAR-10, respectively. In what follows, we provide more detailed results and analysis.
In Table 1 and Table 3, we show that AMGDA significantly outperforms average PGD in ASRall. Taking `1-attack on MNIST as an example, our min-max attack leads to a 90.16% ASRall, which
2The stationarity is measured by the `2 norm of gradient of the objective in (4) w.r.t. ( ,w).
largely outperforms 48.17%. The reason is that Model C, D are more difficult to attack, which can be observed from their higher test accuracy on adversarial examples. As a result, although the adversarial examples crafted by assigning equal weights over multiple models are able to attack {A, B} well, they achieve a much lower ASR in {C, D}. By contrast, APGDA automatically handles the worst case {C, D} by slightly sacrificing the performance on {A, B}: 31.47% averaged ASR improvement on {C, D} versus 0.86% degradation on {A, B}. The choices of ↵, , for all experiments and more results on CIFAR-10 are provided in Appendix D.2 and Appendix E.
Effectiveness of learnable domain weights:
Figure 1 depicts the ASR of four models under average/min-max attacks as well as the distribution of domain weights during attack generation. For average PGD (Figure 1a), Model C and D are attacked insufficiently, leading to relatively low ASR and thus weak ensemble performance. By contrast, APGDA (Figure 1b) will encode the difficulty level to attack different models based on the current attack loss. It dynamically adjusts the weight wi as shown in Figure 1c. For
instance, the weight for Model D is first raised to 0.45 because D is difficult to attack initially. Then it decreases to 0.3 once Model D encounters the sufficient attack power and the corresponding attack performance is no longer improved. It is worth noticing that APGDA is highly efficient because wi converges after a small number of iterations. Figure 1c also shows wc > wd > wa > wb – indicating a decrease in model robustness for C, D, A and B, which is exactly verified by AccC > AccD > AccA > AccB in the last row of Table 1 (`1-norm). As the perturbation radius ✏ varies, we also observe that the ASR of min-max strategy is consistently better or on part with the average strategy (see Figure 2).
Comparison with stronger heuristic baselines Apart from average strategy, we compare minmax framework with stronger heuristic weighting scheme in Table 2 (MNIST) and Table 4 (CIFAR10). Specifically, with the prior knowledge of robustness of given models (C > D > A > B), we devised several heuristic baselines including: (a) wc+d: average PGD on models C and D only; (b) wa+c+d: average PGD on models A, C and D only; (c) wclip: clipped version of C&W loss (threshold = 40) to balance model weights in optimization as suggested in [56]; (d) wprior: larger weights on the more robust models, wprior = [wA, wB , wC , wD] = [0.2, 0.1, 0.4, 0.3]; (e) wstatic: the converged mean weights of min-max (APGDA) ensemble attack. For `2 (✏ = 3.0) and `1 (✏ = 0.2) attacks, wstatic = [wA, wB , wC , wD] are [0.209, 0.046, 0.495, 0.250] and [0.080, 0.076, 0.541, 0.303], respectively. Table 2 shows that our approach achieve substantial improvement over baselines consistently. Moreover, we highlight that the use of learnable w avoids supervised manual adjustment on
the heuristic weights or the choice of clipping threshold. Also, we show that even adopting converged min-max weights statically leads to a huge performance drop on attacking model ensembles, which again verifies the power of dynamically optimizing domain weights during attack generation process.

heading: 4.3 Multi-Image Universal Perturbation
text: We evaluate APGDA in universal perturbation on MNIST and CIFAR-10, where 10,000 test images are randomly divided into equal-size groups (K images per group) for universal perturbation. We measure two types of ASR (%), ASRavg and ASRall. Here the former represents the ASR averaged over all images in all groups, and the latter signifies the ASR averaged over all groups but a successful attack is counted under a more restricted condition: images within each group must be successfully attacked simultaneously by universal perturbation. In Table 5, we compare the proposed min-max strategy with the averaging strategy on the attack performance of generated universal perturbations. APGDA always achieves higher ASRall for different values of K. When K = 5, our approach achieves 42.63% and 35.21% improvement over the averaging strategy under MNIST and CIFAR-10. The universal perturbation generated from APGDA can successfully attack ‘hard’ images (on which the average-based PGD attack fails) by self-adjusting domain weights, and thus leads to a higher ASRall.
Interpreting “image robustness” with domain weights w: The min-max universal perturbation also offers interpretability of “image robustness” by associating domain weights with image visualization. Figure 6 shows an example in which the large domain weight corresponds to the MNIST letter with clear appearance (e.g., bold letter). To empirically verify the robustness of image, we report two metrics to measure the difficulty of attacking single image: dist. (C&W `2) denotes the the minimum distortion of successfully attacking images using C&W (`2) attack; ✏min (`1) denotes the minimum perturbation magnitude for `1-PGD attack.

heading: 4.4 Robust Attack over Data Transformations
text: EOT [5] achieves state-of-the-art performance in producing adversarial examples robust to data transformations. From (7), we could derive EOT as a special case when the weights satisfy wi = 1/K (average case). For each input sample (ori), we transform the image under a series of functions, e.g., flipping horizontally (flh) or vertically (flv), adjusting brightness (bri), performing gamma correction
(gam) and cropping (crop), and group each image with its transformed variants. Similar to universal perturbation, ASRall is reported to measure the ASR over groups of transformed images (each group is successfully attacked signifies successfully attacking an example under all transformers). In Table 7, compared to EOT, our approach leads to 9.39% averaged lift in ASRall over given models on CIFAR-10 by optimizing the weights for various transformations. We leave the the results under randomness (e.g., flipping images randomly w.p. 0.8; randomly clipping the images at specific range) in Appendix E

heading: 5 Extension: Understanding Defense over Multiple Perturbation Domains
text: In this section, we show that the min-max principle can also be used to gain more insights in generalized adversarial training (AT) from a defender’s perspective. Different from promoting robustness of adversarial examples against the worst-case attacking environment (Sec. 3), the generalized AT promotes model’s robustness against the worst-case defending environment, given by the existence of multiple `p attacks [65]. Our approach obtains better performance than prior works [65, 41] and interpretability by introducing the trainable domain weights.

heading: 5.1 Adversarial Training under Mixed Types of Adversarial Attacks
text: Conventional AT is restricted to a single type of norm-ball constrained adversarial attack [40]. For example, AT under `1 attack yields:
minimize ✓ E(x,y)2D maximize k k1✏ ftr(✓, ;x, y), (10)
where ✓ 2 Rn denotes model parameters, denotes ✏-tolerant `1 attack, and ftr(✓, ;x, y) is the training loss under perturbed examples {(x+ , y)}. However, there possibly exist blind attacking spots across multiple types of adversarial attacks so that AT under one attack would not be strong enough against another attack [2]. Thus, an interesting question is how to generalize AT under multiple types of adversarial attacks [65]. One possible way is to use the finite-sum formulation in the inner maximization problem of (10), namely, maximize{ i2Xi} 1 K P K
i=1 ftr(✓, i;x, y), where i 2 Xi is the ith type of adversarial perturbation defined on Xi, e.g., different `p attacks.
Since we can map ‘attack type’ to ‘domain’ considered in (1), AT can be generalized against the strongest adversarial attack across K attack types in order to avoid blind attacking spots:
minimize ✓ E(x,y)2D maximize i2[K] maximize i2Xi ftr(✓, i;x, y). (11)
In Lemma 1, we show that problem (11) can be equivalently transformed into the min-max form. Lemma 1. Problem (11) is equivalent to:
minimize ✓ E(x,y)2D maximize w2P,{ i2Xi}
KX
i=1
wiftr(✓, i;x, y), (12)
where w 2 RK represent domain weights, and P has been defined in (1).
The proof of Lemma 1 is provided in Appendix B. Similar to (4), a strongly concave regularizer /2kw 1/Kk22 can be added into the inner maximization problem of (12) for boosting the stability of the learning procedure and striking a balance between the max and the average attack performance:
minimize ✓ E(x,y)2D maximize w2P,{ i2Xi} (✓,w, { i})
(✓,w, { i}) := P K i=1 wiftr(✓, i;x, y) 2 kw 1/Kk 2 2
(13)
Algorithm 2 AMPGD to solve problem (13) 1: Input: given ✓(0), w(0), (0) and K > 0. 2: for t = 1, 2, . . . , T do 3: given w(t 1) and (t 1), perform SGD to
update ✓(t)
4: given ✓(t), perform R-step PGD to update w(t) and (t) 5: end for We propose the alternating multi-step projected gradient descent (AMPGD) method (Algorithm 2) to solve problem (13). Since AMPGD also follows the min-max principles, we defer more details of this algorithm in Appendix C. We finally remark that our formulation of generalized AT under multiple perturbations covers prior work [65] as special cases ( = 0 for max case and = 1 for average case).

heading: 5.2 Generalized AT vs. Multiple `p Attacks
text: Compared to vanilla AT, we show the generalized AT scheme produces model robust to multiple types of perturbation, thus leads to stronger “overall robustness”. We present experimental results of generalized AT following [41] to achieve simultaneous robustness to `1, `2, and `1 perturbations on the MNIST and CIFAR-10 datasets. To the best of our knowledge, MSD proposed in [41] is the state-of-the-art defense against multiple types of `p attacks. Specifically, we adopted the same architectures as [41] four layer convolutional networks on MNIST and the pre-activation version of the ResNet18 [24]. The perturbation radius ✏ for (`1, `2, `1) balls is set as (0.3, 2.0, 10) and (0.03, 0.5, 12) on MNIST and CIFAR-10 following [41]. Apart from the evaluation `p PGD attacks, we also incorporate the state-of-the-art AutoAttack [18] for a more comprehensive evaluation under mixed `p perturbations.
The adversarial accuracy results are reported (higher the better). As shown in Table 8 and 9, our approach outperforms the state-of-the-art defense MSD consistently (4⇠6% and 2% improvements on MNIST and CIFAR-10). Compared to MSD that deploys an approximate arg max operation to select the steepest-descent (worst-case) universal perturbation, we leverage the domain weights to self-adjust the strengthens of diverse `p attacks. Thus, we believe that this helps gain supplementary robustness from individual attacks.
Effectiveness of Domain Weights: Figure 3 shows the robust accuracy curves of MSD and AMPGD on MNIST. As we can see, the proposed AMPGD can quickly adjust the defense strengths to focus on more difficult adversaries - the gap of robust accuracy between three attacks is much smaller. Therefore, it achieves better results by avoiding the trade-off that biases one particular perturbation model at the cost of the others. In Figure 4, we offer deeper insights on how the domain weights work as the strengths of adversary vary. Specifically, we consider two perturbation models on MNIST: `2 and `1. During the training, we fix the ✏ for `1 attack during training as 0.2, and change the ✏ for `2 from 1.0 to 4.0. As shown in Figure 4, the domain weight w increases when the `2-attack becomes stronger i.e., ✏(`2) increases, which is consistent with min-max spirit – defending the strongest attack.

heading: 5.3 Additional Discussions
text: More parameters to tune for min-max? Our min-max approaches (APGDA and AMPGD) introduce two more hyperparameters - and . However, our proposal performs reasonably well by choosing the learning rate ↵ same as standard PGD and using a large range of regularization coefficient 2 [0, 10]; see Fig. A5 in Appendix. For the learning rate to update domain weights, we found 1/T is usually a very good practice, where T is the total number of attack iterations.
Time complexity of inner maximization? Our proposal achieves significant improvements at a low cost of extra computation. Specifically, (1) our APGDA attack is 1.31⇥ slower than the average PGD; (2) our AMPGD defense is 1.15⇥ slower than average or max AT [65].
How efficient is the APGDA (Algorithm 1) for solving problem (4)? We remark that the minmax attack generation setup obeys the nonconvex + strongly concave optimization form. Our proposed APGDA is a single-loop algorithm, which is known to achieve a nearly optimal convergence rate for nonconvex-strongly concave min-max optimization [32, Table 1]. Furthermore, as our solution gives a natural extension from the commonly-used PGD attack algorithm by incorporating the inner maximization step (9), it is easy to implement based on existing frameworks.
Clarification on contributions: Our contribution is not to propose a new or more efficient optimization approach for solving min-max optimization problems. Instead, we focus on introducing this formulation to the attack design domain, which has not been studied systematically before. We believe this work is the first solid step to explore the power of min-max principle in the attack design and achieve superior performance on multiple attack tasks.

heading: 6 Conclusion
text: In this paper, we revisit the strength of min-max optimization in the context of adversarial attack generation. Beyond adversarial training (AT), we show that many attack generation problems can be re-formulated in our unified min-max framework, where the maximization is taken over the probability simplex of the set of domains. Experiments show our min-max attack leads to significant improvements on three tasks. Importantly, we demonstrate the self-adjusted domain weights not only stabilize the training procedure but also provides a holistic tool to interpret the risk of different domain sources. Our min-max principle also helps understand the generalized AT against multiple adversarial attacks. Our approach results in superior performance as well as intepretability.
Broader Impacts
Our work provides a unified framework in design of adversarial examples and robust defenses. The generated adversarial examples can be used to evaluate the robustness of state-of-the-art deep learning vision systems. In spite of different kinds of adversaries, the proposed defense solves one for all by taking into account adversaries’ diversity. Our work is a beneficial supplement to building trustworthy AI systems, in particular for safety-critical AI applications, such as autonomous vehicles and camera surveillance. We do not see negative impacts of our work on its ethical aspects and future societal consequences.

heading: Acknowledgement
text: We sincerely thank the anonymous reviewers for their insightful suggestions and feedback. This work is partially supported by the NSF grant No.1910100, NSF CNS 20-46726 CAR, NSF CAREER CMMI-1750531, NSF ECCS-1609916, and the Amazon Research Award. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.

Review summaries:
This paper proposes a unified alternating projected gradient descent-ascent (APGDA) attack by considering the min-max operation for adversarial attack settings. The proposed method can be applied in generating model ensemble attacks, universal adversarial attacks, and robust attacks over data transformations. Extensive results show that the proposed method can achieve better attack performances for these three applications.

This paper proposed a APGDA attack method, in which the model ensemble attack, universal attack, and robust attack are unified. The authors proved their APGDA's superiority in theory, ${i.e.}$, convergence rate and strong attacking ability. All of the mentioned tasks (ensemble attack, universal attack, robust attack) are investigated through experiments.

The paper provides a general min-max framework to formulate several popular problems in the literature including Ensemble attack over multiple models, Universal Perturbation over multiple examples, and adversarial attack over data transformations. For each case, a standard first-order approach converging to a stationary point of the problem is provided. The effectiveness of the min-max approach compared to the standard empirical risk minimization has been demonstrated by extensive experiments.  

This paper adapts the min-max problem proposed for multi-domain robust optimization [45] to the problem of generating adversarial attacks. They show how several adversarial attacks scenarios can be formulated using this min-max, for example they show that this min-max formulation can be used to find successful attacks against an ensemble of models. They also show how this min-max can also be used to train robust models against multiple $\ell_p$ attacks. They show experimentally that the approach outperforms several baseline in several setting.

The work proposes a min-max framework APGDA that can take in different models related to adversarial robustness. APGDA can generate model ensemble attack, universal attack over multiple images, and robust attack over data transformations. They perform experiments to evaluate their method.