Adversarial Attack Generation Empowered by Min-Max Optimization
Authors: Jingkang Wang
Tianyun Zhang
Sijia Liu
Pin-Yu Chen
Jiacen Xu
Makan Fardad
Bo Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: Min-max optimization
Ensemble attack
Universal perturbation

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 notion of min-max optimization over multiple domains can be leveraged to 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 against multiple perturbation types. Furthermore, we find that the self-adjusted domain weights learned from min-max optimization can provide a holistic tool to explain the difficulty level of attack across domains.

Adversarial Attack Generation Empowered by Min-Max Optimization
Jingkang Wang .2-
Tianyun Zhang Sijia Liu
Pin-Ye Yu Chen Jiacen Xu Makan Fardad Li
University of Toronto', Vector Institute², Cleveland State University Michigan State University*. MIT-IBM Watson AI Lab, IBM Research University of California, Irvine Syracuse University? University of Illinois at Urbana- Urbana-Champan Champaign
Abstract
The worst-case training principle that minimizes the maximal adversarial loss, also known as adversarial training (AT), has shown to state-of-the-ar approach for enhancing adversarial robustness. Nevertheless, min-max optimization beyond the purpose AT not been rigorously explored 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 set of risk sources, minimizing the worst-case attack loss can be reformulated as min-max problem by introducing domain weights that 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 approach leads to substantial attack improvement over the existing heuristic strategies as well as robustness improvement over state-of-the-art defense methods trained 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 explain the difficulty level of attack across domains. Code is available at https: h/ap:s///// gi thub. com/ com/wang] ks tu/ minmmxx-dat
Introduction
Training a machine learning model that capable of assuring its worst-case performance against possible adversaries given 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 specific form of min-man 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 alternative training fashion. In practice, AT has achieved the state-of-the defense performance against lp nornomm-bee 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 reseurch 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 (NcurIPS 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 one- step 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 O(1/T') convergence rate, where 7 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 e--norm perturbations are generated, and achieve superior performance as well as intepretability.
1.1 Related work
Recent studies have identified that DNNs are highly vulnerable to adversarial manipulations in various
applications [64, 12, 33, 33,26, 26, 14, 77, 20, 15,31] thus leading to arms race between adversarial at- tacks [13, 3, 28,4,,444444 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 pertur- bations 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]. known Expectation Over Transformation (EOT), is to train the attack under different data transformation (c.g., different view angles and distances). However, current approaches suffer from significant performance loss for resting the uniform averaging strategy or heuristic weighting schemes [34, 56]. We will compare these works with our min-max method in Sec. 4. As natural extension following min-mas attack, study the generalized AT under multiple perturbations [65, 2, 28, 17]. Finally, our min-max framework is adapted and inspired by previous literature 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. Specifi- cally, [7] considered the non-interactive blackbox adversary setting and proposed a framework that models the crafting of adversarial examples as min-max game between generator of attacks and classifier. [57] introduced a min-max based adaptive attacker's objective to craft perturbation so that it simultancously 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 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.
2 Min-Max Across Domains
Consider K loss functions (v) (each of which defined on learning domain), the problem of robust learning over K domains can be formulated as [50, 51, 38]
minimize maximize WEP
Σ FvF.(v)
vEV
where v and w are optimization variables, a constraint set, and P denotes the probability simplex P = {w 1'w== w 1, E [0, 1],vi,, Vij. Since the inner maximization problem in (1) is linear function

---

of w over the probabilistic simplex, problem (1) is thus equivalent to
minimize maximize Fv(v),
vEV
VE[K]
where [K] denotes the integer set (1,2,..., K}
Benefit and Challenge from (1), Compared to multi-task learning in finite-sum formulation which minimizes K losses on average, problem (1) provides consistently robust worst-case perfor- mance across all domains. This can be explained from the epigraph form of (2),
minimize t, subject to (v) S t E [K],
(3)
vEV,
where is epigraph variable [8] that provides the t-level robustness each domain.
In computation, the inner maximization problem of (1) always returns the one-hot value of w, namely, e, where e, is the ith standard basis vector, and arg max; (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 maximize Σ wvFi(v) 3/ ||w 1/K
(4)
vEV WEP
where y > 0 is regularization parameter. y O, problem (4) is equivalent to (l), By contrast, becomes the finite-sum problem when 7 - oo since w 1/K. In this sense, the trainable w provides 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.
3 Min-Max Power in Attack Design
To the best of our knowledge, few work has studied the power min-max in attack generation. In this section, 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 craft robust perturbations against multiple domains.
3.1 A Unified Framework for Robust Adversarial Attacks
The general goal of adversarial attack is to craft an adversarial example x' = xo + E IR to mislead the prediction of machine learning (ML) deep learning (DL) systems, where X, denotes the natural example with the true label fo, and 5 is known as adversarial perturbation, commonly subject to fy-norm (p f0, 1,2, )0)) constraint X' := {5 ||0] S c, Xo E [0, 1]d} for given small number c. Here the f,p norm enforces the similarity between x' and Xn, and the input space of ML/DL systems is normalized to 1]d.
Ensemble Attack over Multiple Models. Consider K ML/DL models (M,). the goal is to this case, the notion
find robust adversarial examples that can fool all models simultaneously. of 'domain' in (4) is specified as 'model", and the objective function F; in (4) signifies the attack loss fō; Xy. you M2) given the natural input (Xp, yo) and the model M,. Thus, problem (4) becomes
minimize maximize WEP
ΣK w;f(6; X yo. M,) | - 1/K
dEx
where w encodes the difficulty level of attacking each model.
Universal Perturbation over Multiple Examples. Consider K natural examples ((x; ys ))) K ==1
and 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 maximize ΣK wof M) www 1/K SEX
(6)
WEP
where different from (5), encodes the difficulty level of attacking each example.
3

---

Adversarial Attack over Data Transformations. Consider K categories of data transformation {p:}. e.g,, rotation, lightening, and translation, our goal is to find the adversarial attack that robust to data transformations. Such an attack setting is commonly applied to generate physical adversarial examples [5, 20J. Here the notion of "domain' in (4) is specified as 'data transformer', and problem (4) becomes
minimize maximize Σ Wi [/(( + 5); yo. M)] - 3/ll - 1/K1 WEP
6EX
where Ex-p, [ .)] denotes the attack loss under the distribution of data transformation ps, and encodes the difficulty level of attacking each type of transformed example Xo- 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 enviromment that an ad 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 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 assess the model robustness when facing different types of adversary. We refer readers to Figure Ic and Figure for more details.
domain weights. Even by carefully tuning the
3.2 Min-Max Algorithm for Adversarial Attack Generation
We propose the alternating projected gradient descent-ascent (APGDA) method (Algorithm 1) to solve problem (4). For ease of presentation, we
Algorithm 1 APGDA to solve problem (4)
1: Input: given (0)) and (())
write problems (5), (6), (7) into the general form minimize maximize ΣK wi; (:(): - 3 ||w 1/K 1B,
2: for ( = 1,2, ..... T do
3: outer min.: fixing w = w(--1), call
SEX
PGD (8) to update 8(t)
where F. 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.
4: inner max.: fixing 5 = 810, update (())
with projected gradient ascent (9)
5: end for
Outer Minimization Considering w w) and F(ő) -E w ((("")) in (4), we per- form one-step PGD to update â at iteration f, (t) projx - (VF(((())))
(8)
where proj(-) denotes the Euclidean projection operator, i.e., p = arg minxex ||x al at
the point a, a > 0 is a given learning rate, and Vs denotes the first-order gradient w.r.t. 5. If p = oc. then the projection function becomes the clip function. In Proposition 1, we derive the solution of pr (a) under different Ep norms for p E (0, 1,
Proposition 1. Given a point E Rdd and constraint set X = {81101|, < ē < 8 < c}. the Euclidean projection 8* = projæ (a) has a closed-form solution when E {0, 1,2]. where the specific form is given by Appendix A.
Inner Maximization By fixing 5 = 5(t) and letting (b()) == Σx w; wF((((())) 3|[ - 1/K in problem (4), we then perform one-step PGD (w.rt. -1) to update w,
w = projp
w (t-1) + BV w (w (1(1)))) = (b p1)
(9)
where 3 > 0 is given learning rate, (w) = (t()) 7(w 1/K), and (()) = (F)))())) "..,", F....,,.xx(()))) (x In (9), the second equality holds due to the closed-form of projec-
tion operation onto the probabilistic simplex P [49], where (x)+ max (0, x). and μ is the
root of the equation 1 (b- =1)+ = 1. Since 1 1b min: + 1/K)+ 2 1'1/K
1,
and (b max; (b.) )1 + 1/K)+ < 1"1/K = 1, the root l exists within the interval [min 1/ K, max, (b,) - 1/K] and can be found via the bisection method [8].

---

1.0
Attack success rate
1.0
Attack success
0.8
0.8
0.6
0.6
MLP
0.6
B: Ali-CMNs
0.4
0.4
0.4
0.2
D: LeNerV2
0.2
0.0
0.0
iterations
Number iterations
(a) average case
(b) min max
(c) weight {w:
Figure 1: Ensemble attack against four DNN models on MNIST. (a) & (b): Attack success rate of
adversarial examples generated by average PGD min-max (APGDA) attack method. (c): Boxplot of weight w in min-max adversarial loss. Here we adopt the same foc -attack as Table 1.
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) ()) has L-Lipschitz continuous gradients, and is a convex compact set. Given learning rates a S Y and B t. then the sequence 18(1) w(0) Ji=1 generated by Algorithm 1 converges first-order stationary poinf in rate O (+))
Proof: Note that the objective function of problem (4) is strongly concave w.r.t. w with parameter 7, and has 7-Liischitz continuous gradients. Moreover, we have ||w||2 S due to w E P. Using these facts and Theorem 1 in [37] [39] completes the proof.
4 Experiments on Adversarial Exploration
In this section, we first evaluate the proposed min-max optimization strategy three attack tasks. We show that our approach leads substantial improvement compared with state-of-the-an attack meth- ods such as average ensemble PGD [34] and EOT [3, 10, 5J. We also demonstrate the effectiveness of learnable domain weights in guiding the adversary's exploration over multiple domains.
4.1 Experimental setup
We thoroughly evaluate our algorithm on MNIST and CIFAR-10. set of diverse image classi- fiers (denoted from Model A to Model H) 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 Ap- pendix 1. Note that problem formulations (5)-(7) are applicable to both untargeted and targeted attack. Here we focus on the former setting and C& W loss function [13, 40] with confidence parameter x = 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 hyperparumeters (a, 3, 7). Apart from absolute attack success rate (ASR), we also report the relative improvement or degradationon the worse-case performance in experiments: Lift(f). The details of crafting adversarial examples are available in Appendix D.2.
4.2 Ensemble Attack over Multiple Models
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, w; = 1/K in problem (5). Throughout this task, measure the attack performance via ASR 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 fn-norm constraints on MNIST and 100 respectively. In what follows, we provide more detailed results and analysis.
In Table I and Table 3, we show that AMGDA significantly outperforms average PGD in ASRail- Taking -atackk MNIST example, our min-max attack leads to 90.16% ASRall, which Thhe stationarity is measured the &2 norm of gradient of the objective in (4) w.r.t (8, w).
5

---

Table 1: Comparison of average and min-max (APGDA) ensemble attack on MNIST.
Table 2: Comparison to heuristic weighting
schemes on MNİST (fx- -attack, = 0.2).
Box contrains
Ogi.
Acea
Aocy
Aeeg
Accp
ASR,a
Oge.
A
Acdy
Ace.
Accy,
A5R,.
ASR.
(t)
(t 300
wwg.
3.65
11.27
4,99
2.48
3.11
84.03
91.97
Mead
aup.
60.37
1,05
19.55
0.87
15.10
41.10
35.03
1.87
75.78
80.59
29.32
48.17
-39.135
6
www.
21.48
5:11
6.70
89.16
69.31
28.64%
Masied
0.46
21.57
25.36
13.84
84.69
53.30
10.84%
fy 3.00
6.88
1.51
26.26
3.50
14.50
2,06
95.31
09.12
37.8%%
Maaiy [56]
0.66
1.57
0,03
0.24
23.45
17.67
13:23
13.74
91.70
90.66
74.34
71.54
54.33%
48.52%
Fx (c- 0.23
ong. I0tn BEAX
2.47
1.08
0.39
0.00
41.10
7.39
35.05
5.81
48.17
90.16
87.17%
tuin maxt
Weenti
10.58
0.39
9.28
7.39
10.05
5.81
92.43
22.84
87.17%
61 11.59%
Table 3: Comparison of average and min-max (APGDA) ensemble attack on CIFAR-10.
Table 4: Comparison to heuristic weighting schemes on CIFAR-10 (lec--attatee -attack, E 0.05).
Bos constmint
Oje
Aue
Asni
Asto
Aupp
ASR.
(7)
Opt.
|Ace
| Accp
Avcp
Acen
ASR...
ASR,
Lift (t)
fo tr 500
min max
27.85
18,74
3.15
K.66
9.64
5.16
6.17
9.70
65.15
71.44
944%
Mbased
org.
42.12
19.59
1,63
1.55
5.61
5.93
1.12
4.26
92.22
75.78
73.29
51.63
-29 55%
f 1s 30)
asg. mick
32.92
12:45
3.24
2,07
5.55
5.62
5.86
6.36
59.74
78.05
31.65%
Museeed
13.35
5241
4.83
84.69
56.89
-22,38%
6y 2.0)
18t0 max
aang
3,03
4.65
4.20
5.14
69.55
83.05
20.70%
Nalpp [56]
Mprieer
11.13
19.72
3.75
2.30
4.38
4.29
91.70
77.82
73.45
0.22%
fe
aing
4.74
561
15.10%
zaia max
7.21
7.36
4.48
2,68
4.74
5.03
6.70
4.59
95.20
92.43
84.36
81.04
15.10%
10. 577
largely outperforms 48.17%. The reason 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, BJ. The choices of a, 8, y for all experiments and more results on CIFAR- 10 are provided in Appendix D.2 and Appendix E.
Effectiveness of learnable domain weights: Figure depicts the ASR of four models under average/min-max attacks as well as the distribu- tion of domain weights during attack generation. For average PGD (Figure la), 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 w; as shown in Figure Ic. 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 w;; converges after small number of iterations. Figure Ic also shows w. wa > W. > w/- indicating a decrease in model robustness for C, D, A and B, which is exactly verified by Accc > Accp > Acc A > Acep in the last row of Table I -oomm)r 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).
1.0
0.8
mimmax
auccesss
0.0
9.6
0.5
0.4
0.4
0.2
AV3
0.0
0.0
0.1
0.2
0.3
0.22
0.04
0.05
0.05
0.10
Figure 2: ASR of average and min-max foo en- semble attack versus maximum perturbation mag- nitude E. Left (MNIST), Right (CIFAR-IO).
Comparison with stronger heuristic baselines Apart from average strategy, we compare min- max framework with stronger heuristic weighting scheme in Table 2 (MNIST) and Table 4 (CIFAR- 10). Specifically, with the prior knowledge of robustness of given models (C > D > A > B), we devised several heuristic baselines including:
(a) We+d: average PGD on models C and D only; (b) Watctd: average PGD on models A, C and D only; (c) Walip: 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 = [,. WB, Wc, dp = 00.2. 0. 0.4, 0.3]; (c) Wstatic: the con- verged mean weights of min-max (APGDA) ensemble attack. For E2 (e = 3.0) and lxx (e = 0.2) at- tacks, Wstatic = W, Wp, WCC wp) are [0.209, 0.046, 0.495, 0. 0.250) and |0.080, 0.076, 0.541, 0.303). respectively. Table 2 shows that our approach achieve substantial improvement over baselines consis- tently. Moreover, we highlight that the use of learnable w avoids supervised manual adjustment on

---

Table 5: Comparison of average and minmax optimization on universal perturbation over multiple input examples. K represents the number of images each group. ASRavg and ASRau mean attack success rate (%) of all images and success rate of attacking all the images in each group, respectively. The adversarial examples are generated by 20-step &x APGDA with a 6. B
50 and y 4.
Setting
K
K=4
K 5
K 10
Dataset
Model
Opt.
[ASRas
ASR,a Lift ("JAS
ASR.i Lin (1)
AASRag
ASRar
Lift (1)
JASR, ASRai Lift (t)
All-CNNs
aug-.
91.09
83.08
85.66
54.72
82.76
40.20
71.22
4.50
min max
92.22
85.98
3.49%
87.63
65,80
20.25%
85.02
85.74
38.66%
63.64
11.80
162.2%
LeNetV2
93.26
86,90
90.04
66 12
88.28
55.00
72.02
8.90
CIFAR-10 10
min max
93.34
87.08
0.21 %
91.91
71.64
8.35%
91.21
63.55
15.55%
82.85
25.10
182.0%
VGGI6
aug.
90.76
82.56
89.36
63.92
88.74
55.20
85.86
22.40
unin muxx
92.40
85.92
4.07% %
90.04
70.40
10.14%
88.97
63.30
14.67% %
79.07
30,80
37.50%
GoogLeNel
avg-
72.48
75.20
32.68
59,01
0.40
mii max:
87.08
77.82
7.37% %
77.05
46.20
41.37%
71.20
33.70
71.94%
45.46
2.40
600.0%
Table 6: Interpretability of domain weight we for universal perturbation to multiple inputs on MNIST
(Digit 0, 2, 4). Domain weight w for different images under e--norm (p 0, 0,1,2,00)
2
2
2
2
2
4 4
4
4
/
Image
Fo
1.000
0.
0.909
0.
0.091
Weight
f1
0.
0.
1,000
0.
0.
0,843
0.
0.157
0.018
0.
0,567
0.416
f2
0.
0.788
0.
0.112
0.595
Exe
0.
0.
0.
0.
1.000
0.
0.
0,850
0.
0.150
0.
0.
0.651
0.
0.349
Metric
CC& [2]
1.839
1.954
1.347
1.698
3.041
1.928
1.439
2.312
1.521
2.356
1.558
1.229
1.939
0.297
1.303
(%x
0.113
0,167
0.073
0.121
0.199
0.082
0.106
0.176
0.072
0.171
0.084
0.088
0.122
0.060
0.094
the hcuristic weights or the choice of clipping threshold. Also, we show that even adopting converged min-max weights statically leads to huge performance drop attacking model ensembles, which again verifies the power of dynamically optimizing domain weights during attack generation process.
4.3 Multi-Image Universal Perturbation
We evaluate APGDA in universal perturbation on MNIST and CIFAR-10. 10, where 10,000 test images randomly divided into equal-size groups (K images per group) for universal perturbation. We measure two types of ASR (%), ASRavg and ASRau 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 ASRai for different values of K. When K = 5, our approach achieves 42.63% and 35.2 55.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 werage-based PGD attack fails) by self-adjusting domain weights, and thus leads to higher ASR
Interpreting "image robustness" with domain weights w: The min-max universal perturbation also offers interpretability of "image robustness" by associating domain weights with image visual- ization. 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 W fz) denotes the the minimum distortion of successfully attacking images using C&W (62 attack; Emin (foo) denotes the minimum perturbation magnitude for PPD attack.
4.4 Robust Attack over Data Transformations
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 w; = 1/K (average case). For each input sample (ori), we transform the image under a series of functions, e.g.. flipping horizontally (fth) or vertically (ffv), adjusting brightness (brí), performing gamma correction
7

---

Table 7: Comparison of average and min-max optimization robust attack over multiple data transformations on CIFAR-I0. 10. Acc (%) represents the test accuracy classifiers on adversarial TOo and 7 = 10) under different
examples (20-step Lo -PPG (e 0.03) with 2 3 transformations.
Model|
Opt.
AcCori
yn Accyie flu AcCari Ace AcCorap
ASR,, Lift (1)
A
avg.
10.80
21.93
14.75
11.52
10.66
20.03
55.88
min max
12.14
18.05
13.61
13.52
11.99
16.78
60.03
7.43%
B
avg.
5.49
11.56
9.51
5.43
5.75
15.89
72.21
min max
6.22
8.61
9.74
6.35
6.42
11.99
77.43
7.23%
avg.
7.66
21.88
15.50
8.15
7.87
15.36
56.51
min max
8.51
14.75
13.88
9.16
8.58
13:35
63.58
12.51 %
D
avg.
8.00
20.47
13.46
7.73
8.52
15.90
61.13
min max
9.19
13.18
12.72
8.79
9.18
13.11
67.49
10.40%
(gam) and cropping (crop), and group each image with its transformed variants. Similar to universal perturbation, ASRau 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 ASR 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
5 Extension: Understanding Defense over Multiple Perturbation Domains
In this section, we show that the min-max principle can also be used to gain more insights in general- ized adversarial training (AT) from defender's perspective. Different from promoting robustness of adversarial examples against the worsi-case allacking environment (Sec. 3), the generalized AT promotes model's 's robustness against the worst-case defending environment, given by the existence of multiple lp attacks [65]. Our approach obtains better performance than prior works [65, 41] and interpretability by introducing the trainable domain weights.
5.1 Adversarial Training under Mixed Types of Adversarial Attacks
Conventional AT is restricted to single type of norm-bar ball constrained adversarial attack [40]. For example, AT under foo attack yields:
minimize (xxy)D maximize frr 8; [ loo St
(10)
where A E IRt denotes model parameters, 8 denotes e-tolerant lo attack, and Sty (0, 6; 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 use the finite-sum formulation in the inner maximization problem of (10), namely, maximize(6.E.x,
K Σ (0, 6,;x, x, y), where
8, E Xr is the ith type of adversarial perturbation defined on X,, e.g., different l, attacks.
Since 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 [xxyjE maximize maximize (Or 8,; x, x, 6.E.t
(11)
<E(K]
In Lemma 1, we show that problem (11) can be equivalently transformed into the min-max form. Lemma 1. Problem (11) is equivalent to:
K Σ
minimize E (X) maximize
we (0,6;;;;
(12)
WEP. (8,EX.
where KK represent domain weights, and P has been defined in (1).
8

---

MAX
AVG [3]
MSD
AMPGD
Clean Accuracy
98.6%
99.1%
98.34
98.3%
0.
Atcus (4) Attacial
0.6-
fx Attacks [66] (c 0.3)
51.0%
(a Attacks [65] 2.0)
61.9%
60.1%
67.99
700.2%
4 Attacka [65] 10)
$2,6%
39.2%
65.01
67.216
Air
All Amacks [65]
42.158
34.9%
58.4%
64.1%
0.4
2.01
MSD AMPCD
attacis) [18)
36.9%
55.9%
99.39
E, 0.31
1.16-0.3)
AA (all smacks) [15]
34.3%
54.8%
10 Epoch
10 Spoch
10
Epach
Table 8: Adversarial robustness MNIST.
Figure 3: Robust accuracy of MSD and AMPGD.
Lg-AI
AI-
[65]
AVG [66]
MSD [41]
AMPGD
Clean Accuracy
83.3%
90.2%
73.3%
81 0.00
84.6%
81.1%
81.5%
1.00
fw Attacks (r 0.03) [41]
50.7%
28.3%
0.2%
44.9%
42.5%
48.0%%
49.2%
22 Attacks (e 0.5) [41]
57.3%
61.6%
0.0%
61.7%
65.0%
64.3%
68.0%
0.75
f Attacks (r [2)
16.0%
46.6%
7.9%
39 19.4%
54.0%
53.0%
50.0%
$0.50
Attacks [41]
15.6%
27.5%
0.0%
34.9%
40.6%
47.0%
48.7%
AA (fx. c = 0,03) [18]
47.8%
22.7%
0.0%
39.2%
40.7%
44.4%%
46.9%
0.25
(fa. 0.5) [18]
57.5%
62.0%
65.55%
0.00
AA (fi. 12) [18]
13.7%
23. 6%
1.4%
36 36.0%
58.8%
52.4%
52.39
1.0
1.5
2.0
3.0
4.0
attacks) [18]
12.8%
18.4%
40.4%
44.1%
46.2%
/00)
Figure 4: Domain weights.
Table Summary of adversarial accuracy results for CIFAR-10.
The proof of Lemma is provided in Appendix B. Similar (4), strongly concave regularizer - 1/K1 can be added into the inner maximization problem of (12) for boosting the stability of the learning procedure and striking balance between the max and the average attack performance:
minimize E(xx))D maximize (O,0, w, {5.)) (.,.(
(13)
(0, w, (..)) Σ we for( 00,0,;,,,) | - 1/K
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 multi- ple perturbations covers prior work [65] as special cases (7 = 0 for max case and 7 = oc for average case).
Algorithm 2 AMPGD solve problem (13)
1: Input: given (0)) w 8()) and K > 0.
for t 1, ...,... do
3: given w ((-11) and ((t-1), perform SGD to update g(t)
given g(0) perform R-step PGD update
(t) and g(t)
5: end for
5.2 Generalized AT vs. Multiple lp Attacks
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] achieve simultaneous robustness loc, lz, and & 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 É, 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 E for (Eoo, E2, &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 l, PGD attacks, we also incorporate the state-of-the-ar AutoAttack [18] for a more comprehensive evaluation under mixed e, perturbations.
The adversarial accuracy results are reported (higher the better). As shown in Table 8 and 9, our approach outperforms the state-of-the-an defense MSD consistently (4~6% and 2% improvements on MNIST and CIFAR-10), Compared 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 eurves 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 partieular 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: lz and Loo. During the training, we fix the for foo attack during training as 0.2, and change the for l2 from 1.0 to 4.0, As shown Figure 4, the domain weight w increases when the 22-attack becomes stronger i.e., e(62) increases, which is consistent with min-max spirit defending the strongest attack.
5.3 Additional Discussions
More parameters to tune for min-max? Our min-max approaches (APGDA and AMPGD) in- troduce two more hyperparameters / and 7, However, our proposal performs reasonably well by choosing the learning rate same standard PGD and using a large range of regularization coefficient 7 E [o, 10]; see Fig. AS in Appendix. For the learning rate 3 to update domain weights, we found 1/T is usually very good practice, where T is the total number of attack iterations.
Time complexity of inner maximization? Our proposal achieves significant improvements at low cost of extra computation. Specifically, (1) our APGDA attack 1.31 slower than the average PGD; (2) our AMPGD defense is 1.15x slower than average or max AT [65].
How efficient is the APGDA (Algorithm 1) for solving problem (4)? We remark that the min- max attack generation setup obeys the nonconvex strongly concave optimization form. Our proposed APGDA a single-loop algorithm, which is known to achieve a nearly optimal convergence rate for nonconvex-strongh concave min-max optimization [32, Table 1]. Furthermore, our solution gives a natural extension from the commonly-used PGD attack algorithm by incorporating the inner maximization step (9), it is easy implement based on existing frameworks.
Clarification on contributions: Our contribution is not to propose a new or more efficient opti- mization 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 multiple attack tasks.
6 Conclusion
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 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 -tate-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 a beneficial supplement to building trustworthy Al systems, in particular for criticlciitical 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.
10

---

Acknowledgement
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 prepar- ing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.
References
[1] M. Andriushchenko, F. Croce, N. Flammarion, and M. Hein. Square attack: A query-efficient black-box adversarial attack via random search. ECCV (23), volume 12368 of Lecture Notes in Computer Science, pages 484-501. Springer, 2020.
[2] A. Araujo, R. Pinot, B. Negrevergne, L.. Meunier, Y. Chevaleyre, F. Yger, and J. Atif. Robust neural networks using randomized adversarial training. arXiv preprint arXiv:1903.1022 2019.
[3] A. Athalye, N. Carlini, and D. Wagner. Obfuscated gradients give a false sense of security: Cireumventing defenses adversarial examples. arXiv preprint arXiv: arXiv: 1802.00420, 2018.
[4] A. Athalye, L. Engstrom, A. Ilyas, and K. Kwok. Synthesizing robust adversarial examples. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 284-293. PMLR, 2018.
[5] A. Athalye, L. Engstrom, A. Ilyas, and K. Kwok. Synthesizing robust adversarial examples. In
J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 284-293, 10-15 Jul 2018.
[6] A. Athalye and I. Sutskever. Synthesizing robust adversarial examples. ICML, 2018.
[7] A. J. Bose, G. Gidel, H. Berard, A. Cianflone, P. Vincent, S. Lacoste-Julien, and W. L. Hamilton. Adversarial example games. In NeurIPS, 2020.
[8] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[9] W. Brendel, J. Rauber, and M. Bethge. Decision- adversarial attacks: Reliable attacks
against black-box machine learning models. arXiv preprint arXiv: 2017.
[10] T. B. Brown, D. Mané, A. Roy, M. Abadi, and J. Gilmer. Adversarial patch. CoRR, abs/1712.09665, 2017.
[11] N. Carlini, A. Athalye, N. Papernot, W. Brendel, J. Rauber, D. Tsipras, I. J. Goodfellow, A. Madry, and A. Kurakin. On evaluating adversarial robustness. CoRR, abs/1902.067055, 2019.
[12] N. Carlini, P. Mishra, T. Vaidya. Y. Zhang, M. Sherr, C. Shields, D. Wagner. and W. Zhou. Hidden voice commands. In USENIX Security Symposium, pages 513-530, 2016.
[13] N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. Security and Privacy (SP), 2017 IEEE Symposium on, pages 39-57. IEEE, 2017.
[14] N. Carlini and D. A. Wagner. Audio adversarial examples: Targeted attacks speech-to-text. In IEEE Symposium on Security and Privacy Workshops, pages 1-7, IEEE Computer Society, 2018.
[15] H. Chen, H. Zhang, P.-Y. Chen, J. Yi, and C.-J. Hsieh. Attacking visual language grounding with adversarial examples: A case study on neural image captioning. Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics, volume 1, pages 2587-2597, 2018.
[16] M. Cohen, Rosenfeld, and J. Kolter. Certified adversarial robustness via randomized smoothing. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 1310- 1320. PMLR, 2019.
[17] Croce and M. Hein. Provable robustness against adversarial by-perturbations for p 2 arXiv preprint arXiv:1955.11213. 2019.

---

[18] F. Croce and M. Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter- free attacks. In JCML, volume 119 of Proceedings of Machine Learning Research, pages 2206-220 2216. PMLR, 2020.
[19] Y. Dong, F. Liao, T. Pang, H. Su, J. Zhu, X. Hu, and J. Li. Boosting adversarial attacks with momentum. In CVPR, pages 9185-9193 IEEE Computer Society, 2018.
[20] K. Eykholt, I. Evtimov, E. Fernandes, B. Li, A. Rahmati, C. Xiao, A. Prakash, T. Kohno, and D. Song. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1625-1634, 2018.
[21] K. Eykholt, I. Evtimov, E. Fernandes, B. Li, A. Rahmati, C. Xiao, A. Prakash, T. Kohno, and D. Song. Robust physical-world attacks on deep learning visual classification. CVPR, pages 1625-1634. IEEE Computer Society, 2018.
[22] I. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. 2015 ICLR, arXiv preprint arXiv:1412.65777 2015.
[23] J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 14l..6522..2... 2014.
[24] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[25] M. Hein and M. Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In Advances in Neural Information Processing Systems, pages 2266- 2276, 2017.
[26] S. Huang, N. Papernot, J. Goodfellow, Y. Duan, and P. Abbeel. Adversarial attacks on neural network policies. In ICLR (Workshop). OpenReview.net, 2017.
[27] R. Jia and P. Liang. Adversarial examples for evaluating reading comprehension systems. In EMNLP, pages 2021-2031. Association for Computational Linguistics, 2017.
[28] D. Kang, Y. Sun, D. Hendrycks, T. Brown, and Steinhardt. Testing robustness against unforeseen adversaries. arXiv preprint arXiv: /908. 000.08 2019.
[29] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the -ojysk--ojaiiwiizz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-811 Springer, 2016.
[30] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(1 96(11):2278-23) Nov 1998.
[31] Q. Lei, L. Wu, P.-Y. Chen, A. G. Dimakis, I. S. Dhillon, and M. Witbrock. Discrete adversarial attacks and submodular optimization with applications to text classification. SysMI, 2019.
[32] T. Lin, Jin, and M. I. Jordan. On gradient descent ascent for nonconvex-coneat minimax problems. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 6083- 6093. PMLR, 2020.
[33] Y. Lin, Z. Hong, Y. Liao, M. Shih, M. Liu, and M. Sun. Tactics of adversarial attack on deep reinforcement learning agents. In IJCAI, pages 3766- ijcai.org, 2017.
[34] J. Liu, W. Zhang, and N. Yu. CAAD 2018: 10//1811.03466.... 2018.
Iterative ensemble adversarial attack. CoRR,
[35] S. Liu, Lu, X. Chen, Y. Feng, K. Xu, A. Al-Dujaili, M. Hong, and U. Obelilly. Min-max optimization without gradients: Convergence and applications to adversarial ML. CoRR, abs/1909.13806 2019.
[36] Y. Liu, X. Chen, C. Liu, and D. Song. Delving into transferable adversarial examples and black-box box attacks. In ICLR. OpenReview.net, 2017.
12

---

[37] S. Lu, R. Singh, X. Chen, Y. Chen, and M. Hong. Understand the dynamics of GANs via primal-dual optimization, 2019.
[38] S. Lu, I. Tsaknakis, and M. Hong. Block alternating optimization for non-convex min-max problems: Algorithms and applications in signal processing and communications, 2018.
[39] S. Lu, I. Tsaknakis, and M. Hong. Block alternating optimization for non-convex min-max problems: algorithms and applications in signal processing and communications. In Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019.
[40] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083, 2017.
[41] P. Maini, E. Wong, and J. 7. Kolter. Adversarial robustness against the union of multiple perturbation models. In ICML, volume 119 of Proceedings of Machine Learning Research, pages
PMLR, 2020.
[42] D. Meng and H. Chen. Magnet: a two-pronged defense against adversarial examples. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 135-147. ACM, 2017.
[43] J. H. Metzen, M. C. Kumar, T. Brox, and V. Fischer. Universal adversarial perturbations against semantic image segmentation. In ICCV, pages 2774-2783, IEEE Computer Society, 2017.
[44] S.-M. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard. Universal adversarial perturba- tions. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 86-94 -4,9, 2017.
[45] M. Moosavi Dezfooli, A. Fawzi, and P. Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In Proceedings of 2016 IEEE Conference Computer Vision and Puttern Recognition (CVPR), number 1PFL- 2016.
[46] M. Nouiehed, M. Sanjabi, J. D. Lee, and M. Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. arXiv preprint
2019.
[47] N. Papernot, P. McDaniel, I. Goodfellow, S. Jha, Z. B. Celik, and A. Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pages 506-519. ACM, 2017.
[48] N. Papernot, P. McDaniel, Jha, M. Fredrikson, Z. B. Celik, and A. Swami. The limitations of deep learning in adversarial settings. In Security and Privacy (EuroS&P), 2016 IEEE European Symposium on, pages 372-387. IEEE, 2016.
[49] N. Parikh, S. Boyd, et al. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127-23,, 2014.
[50] Q. Qian, S. Zhu, J. Tang, R. Jin, B. Sun, and H. Li. Robust optimization over multiple domains. CoRR, ttbb//885,0758,, 2018.
[51] H. Rafique. M. Liu, Q. Lin, and T. Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint 180.0000, 2018.
[52] J. Rauber, W. Brendel, and M. Bethge. Foolbox v0.8.0: A python toolbox to benchmark the robustness of machine learning models. CoRR, abs//107... 701104431, 2017.
[53] L. Rice, E. Wong, and Z. Kolter. Overfitting in adversarially robust deep learning. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 8093-8100 8104. PMLR, 2020.
[54] Rony, L. G. Hafemann, S. Oliveira, I. B. Ayed, R. Sabourin, and E. Granger. Decoupling direction and norm for efficient gradient- L2 adversarial attacks and defenses. In CVPR, pages 4322-4330. Computer Vision Foundation IEEE, 2019.
[55] I.. Schott, J. Rauber, M. Bethge, and W. Brendel. Towards the first adversarially robust neural network model on MNIST. In ICLR (Poster). OpenReview.net, 2019.
13

---

[56] A. Shafahi, M. Najibi, Z. J. Dickerson, L. S. Davis, and T. Goldstein. Universal adversarial training. CoRR, abs/1811. 1104, 2018.
[57] F. Sheikholeslami, A. Lotfi, and J. Z. Kolter. Provably robust classification of adversarial examples with detection. In ICLR. OpenReview.net, 2021.
[58] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
[59] A. Sinha, H. Namkoong, and Duchi. Certifying some distributional robustness with principled adversarial training. 2018.
[60] L. N. Smith. disciplined approach to neural network hyper-parameters: Part 1- learning rate, batch size, momentum, and weight decay. CoRR, Abs/1883.099 2018.
[61] J. T. Springenberg. A. Dosovitskiy, T. Brox, and M. A. Riedmiller. Striving for simplicity: The all convolutional net. In ICLR (Workshop), 2015.
[62] D. Su, H. Zhang, H. Chen, J. Yi, P.-Y. Chen, and Y. Gao. Is robustness the cost of accuracy?-a comprehensive study on the robustness of 18 deep image classification models. In Proceedings of the European Conference on Computer Vision (ECCV), pages 631-648, 2018.
[63] C. Szegedy, W. Liu, Y. Jia, Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, Going deeper with convolutions. In CVPR, pages 1-9. IEEE Computer Society, 2015.
[64] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
[65] F. Tramèr and D). Boneh. Adversarial training and robustness for multiple perturbations. arXiv preprint arXiv: 1 13000, 2019.
[66] Tramèr, A. Kurakin, N. Papemot, I. Goodfellow, D. Boneh, and P. McDaniel. Ensemble adversarial training: Attacks and defenses. 2018 ICLR, arXiv preprint arXiv:1705.07200 2018.
[67] Tramèr, N. Papernot, Goodfellow, D. Bonch, and P. McDaniel. The space of transferable adversarial examples. arXiv preprint arXiv:1704.034433 2017.
[68] E. Wong, L. Rice, and J. Z. Kolter. Fast is better than free: Revisiting adversarial training. In ICLR. OpenReview.net. net, 2020.
[69] C. Xiao, B. Li, J. Zhu, W. He, M. Liu, and D. Song. Generating adversarial examples with adversarial networks. arXiv preprint arXiv:1801 086.0.2110,.......11011111001111 2018.
[70] C. Xiao, J.-Y. Zhu, B. Li, W. He, M. Liu, and D. Song. Spatially transformed adversarial examples. In International Conference on Learning Representations, 2018
[71] C. Xie, J. Wang. Z. Zhang, Z. Ren, and A. Yuille. Mitigating adversarial effects through randomization. arXiv preprint arXiv: 1rXiv:1111.01991 2017.
[72] K. Xu, S. Liu, Zhao, P.-Y. Chen, H. Zhang, Q. Fan, D. Erdogmus, Y. Wang, and X. Lin. Structured adversarial attack: Towards general implementation and better interpretability. In International Conference on Learning Representations, 2019.
[73) K. Xu, G. Zhang, S. Liu, Q. Fan, M. Sun, H. Chen, P. Chen, Y. Wang, and X. Lin. Adversarial t-shirt! evading person detectors in physical world. In ECCV (5), volume 12350 of Lecture Notes in Computer Science, pages 665-688 681. Springer, 2020.
[74] W. Xu, D. Evans, and Y. Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. In NDSS. The Internet Society, 2018.
[75] S. Zagoruyko and N. Komodakis. Wide residual networks. In BMVC. BMVA Press, 2016.
[76] H. Zhang, Y. Yu, J. Jiao, E. P. Xing, L. E. Ghaoui, and M. Jordan. Theoretically principled trade-off between robustness and accuracy. arXiv preprint
2019.
[77] 7. Zhao, D. Dua, and Singh. Generating natural adversarial examples. In ICLR, OpenRe- view.net, 2018.
14


Reviews:
[{"review_id": "xsKu-yiV5tv", "reviewer": "Reviewer_cLBV", "summary": "The paper studies a min-max formulation for adversarial attacks over multiple domains, which covers attacking ensembling attacks, multiple threat models, and universal perturbations. They propose a regularized formulation and show improvements performance on these tasks. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed regularized formulation of adversarial attack appears to improveme the attack performance in all three settings. Empirically, the paper seems sufficient. However, the paper suffers greatly with issues in clarity. The paper as a whole could be improved greatly, and two parts that stand out are: \n\n1. The paper introduces their formulation as a problem of robust learning. This is somewhat misleading, as the \"robust learning\" in this paper is referring to a robust formulation of the adversarial attack, and not for updating the model parameters (i.e. \"learning\"). The latter is what I see most commonly in the literature for robust learning, and it is not clear to me that this is a formulation for adversarial attacks until Section 3. \n\n2. The results are not clear and require a lot of parsing. For example, the text refers to ensemble baselines, but it is unclear what in the table this refers to (I assumed it was the ones with \"avg\" under \"opt\", since the table captions refer to both attacks as ensemble attacks). There is a column in the table that is labeled \"Lift\" which seems to suggest an amount of improvement, however it is not clear to me what number or metric this is supposed to be improving and I could not find any explanatory text in either the caption or the text. \n\nOverall, the proposed formulation and the corresponding results seem alright. I do like how the authors studied a simple, generalized regularized formulation and evaluated it in multiple attack settings. However this was only after struggling to parse and understand the paper, the presentation of which was not very clear to me. \n\nOther minor questions/comments: \n\nThe convergence analysis (Theorem 1) appears to make very strong assumptions on the problem. Specifically, it is assumed that the problem has L-Lipschitz continuous gradients. Is this really a reasonable assumption for the setting considered in this paper (i.e. classification in deep networks)? \n\nThere are some recent works that improved upon the multi-perturbation robustness setting (over MSD) that would be nice to compare to, i.e. \"Learning to generate noise for multi-attack robustness\" (this is recent work, and so I did not hold this against the authors, but it would be nice to include in the final version). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not find a discussion of the limitations of their work. It would be nice if the authors described some possible properties of their approach that may not be a strict improvement over the compared baselines. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "pStzwC3P7tL", "reviewer": "Reviewer_6whq", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality:**\n\n**Are the tasks or methods new? Is the work a novel combination of well-known techniques?** \n\nIt doesn't differ much from previous work (Universal Adversarial Training, Shafahi et al., 2018). \n\n**Is it clear how this work differs from previous contributions? Is related work adequately cited?**\n\nYes.  \n\n\n**Quality:**\n\n**Is the submission technically sound? Are claims well supported (e.g., by theoretical analysis or experimental results)? Are the methods used appropriate?**\n\nPartly, claims are mainly supported by experiments. \n\n**Is this a complete piece of work or work in progress? Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?**\n\nYes.\n\n\n**Clarity:**\n\n**Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.)** \n\nMostly clear. \n\n**Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)**\n\nYes.\n\n\n**Significance:**\n\n**Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work?**\n\nNot sure. \n\n**Does it advance the state of the art in a demonstrable way? Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?**\n\nN/A", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The authors perform many experiments on MNIST, but MNIST is known to be a poor dataset to study adversarial examples, especially in this experiment-based article.\n\n2. As the authors have trained models on MNIST and CIFAR-10, why not demonstrate Table 2 on CIFAR-10? According to Table 1 and Appendix E, their method performs better on MNIST, I suspect it will perform worse on large datasets(e.g., ImageNet).  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "lLZrtV5CRsa", "reviewer": "Reviewer_xJB1", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- The proposed method is general in generating attacks when multiple domain losses are needed to be optimized together. The insights behind the method in smoothifying and balancing weights are very interesting for the adversarial attack with multiple domains.\n- The paper is well written and easy to follow.\n- Comprehensive experiments illustrate the strength of the proposed methods over general attack methods. The ablation study and the following analysis are insightful in improving the studied three tasks.\n\nWeakness and comments:\n- The method is not that novel as it simply applies non-convex min-max optimization for adversarial attacks. The proposed min-max optimization and concave regularizer are mostly proposed in existing works like [45]. \n- More importantly, a very similar idea for ensemble attack via universal perturbation is explored in [G] (e.g., equation 13 in [G]) even though it is more for black-box attack setting. Comparisons for ensemble model evasions and universal perturbations settings against [G] are very important and discussions about the differences in related work are at least needed.\n- The proposed methods are not well compared with state-of-the-art attacks for the universal adversarial attacks. Generating universal adversarial perturbations (UAPs) has been extensively studied in both targeted [A,B,C] and non-targeted scenarios [D, E, F]. The authors should at least compare against one or two recent methods to demonstrate the effectiveness of the proposed methods.\n\n[A] Double targeted universal adversarial perturbations, ACCV 2020\n\n[B] Understanding adversarial examples from the mutual influence of images and perturbations, CVPR 2020\n\n[D] Ask, acquire, and attack: Data-free UAP generation using class impressions, ECCV 2018\n\n[E] Cross-domain transferability of adversarial perturbations, NeurIPS 2019\n\n[F] Regional homogeneity: Towards learning transferable universal adversarial perturbations against defenses, ECCV 2020\n\n[G] Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML, ICML 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitations and societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "gbCq0Oo_K6D", "reviewer": "Reviewer_YmFH", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**:\nThis paper adapts and existing min-max problem that was proposed for multi-domain robust optimization [45] to the problem of generating adversarial attacks. This work clearly explains its contributions and put them into context of existing work. However, the author mention that some paper have explored min-max formulation in the context of adversarial attacks but don't cite them, for example one work related to problem eq. 5 that also uses a min-max formulation is (Bose et al. 2020).\n\n**Quality**:\nThe claims of the paper are overall well supported. However It would be nice to have confidence intervals for the experimental results.\nI really enjoyed the experimental section, I found Table 2 and Figure 1 quite interesting, showing the importance of having adaptive weights and how the weights acts like an attention mechanism to focus more on the hardest task. Table 4 is also quite informative.\nThe author address the time complexity and additional parameters in section 5.3.\n\n**Clarity**:\nThe paper is well written and very clear.\n\n**Significance**:\nThe idea of training against the worst-case scenario is very interesting, this could lead to much more universal attacker.\n\n**Minor comments**:\n- Typo L298: $\\gamma=\\infty$ for averaging case\n\n\n**Additional references**:\n- Bose et al. \"Adversarial Example Games.\" (NeurIPS 2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "XEP-A3nUWI3", "reviewer": "Reviewer_CtyL", "summary": "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.  ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major Concerns:\n- While the effectiveness of the proposed min-max framework for solving several problems over the regular empirical risk minimization is shown through the experiments, the novelty of such formulations is not clear for the reviewer. There are many papers in the literature using the same min-max formulation for solving such problems, especially for attack generation (see [1]). \n\n- Moreover, almost all formulations, lemmas, and theorems in the paper use the basic idea that the max of finite terms can be written as the maximization of a convex combination of the terms over a simplex. Mathematically speaking: \nMax (x_1, x_2, …, x_n) = max_{w} w_1 x_1 + w_2 x_2 + … w_n x_n        s.t \\sum_{i=1}^n w_n x_n = 1, x_i >= 0 for all I. \n\nIt seems the common element among different investigated problems is the min-max formulation (which is not novel) and the mentioned trick. Thus, it cannot be considered a framework in the reviewer's opinion. \n\n- From an optimization perspective, the contribution of the paper is limited. The provided algorithms are basically different variations of the projected gradient descent ascent algorithm. \n\nStrengths:\n- The experiments show that the robust formulation (min-max) of the attack generation problem works far better than the average case. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors provide ample justification for the potential benefits of their work in safety-critical AI applications.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "-HeNopxss5U", "reviewer": "Reviewer_ynwW", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "$\\textbf{Cons:}$\n\n(1) According to Table 1,  it is clear that the proposed APGDA outperforms the compared methods in ${ASR}_{all}$ metric (for ensemble attack task). \nHowever, I found that in the $ACC_B$ metric, the proposed method performs worse than the comparisons under each setting, indicating the possibility of error due to the model selection and causing my great concern. The same problem appears in Table A3 and Table A4. \n\n(2)In addition, I think the experiments are not conducted fully. For example, the author conducted experiments (ensemble attacks) on MNIST with model ABCD but forgot to test EFH as tested on CIFAR-10. In Table A4's caption, all of the learning rate and regularization factors are the same as those in Table A3, but why did you change the parameter $\\epsilon$ (0.05, 0.03 in $l_{\\inf}$, and 2.0, 1.5 in $l_2$)?\n\n(3)The proof of Theorem 1 seems not finished?\n\n(4) When it comes to universal attack, I am confused that the PGD attack is not designed for \"universal attack\". Thus, comparing with PGD can not demonstrate the performance of the proposed APGDA.\n\n(5)I am scared that the same concern as I mentioned in issue(1) occurs again according to Table 5.\n\n(6) The noise size of the attacking methods has not been fully considered. I think the corresponding results will make this work more solid.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "about 4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This review results for this paper are borderline. While the reviewers appreciate some of the positive aspects of the paper (such as the formulation and the comprehensive numerical experiments), they have reservations about the novelty and the presentation of parts of the paper. However, regarding the contribution of the paper, the authors' argument about the novelty of 1909.13806 (published) w.r.t. 1906.03563 (unpublished) is reasonable and may justify the contribution.
Decision: Accept (Poster)