Adversarial Training with Complementary Labels: On the Benefit of Gradually Informative Attacks
Authors: Jianan Zhou
Jianing Zhu
Jingfeng Zhang
Tongliang Liu
Gang Niu
Bo Han
Masashi Sugiyama
Venue: NeurIPS 2022 Accept (2022)
Keywords: adversarial training
weakly supervised learning
complementary label

Abstract: Adversarial training (AT) with imperfect supervision is significant but receives limited attention. To push AT towards more practical scenarios, we explore a brand new yet challenging setting, i.e., AT with complementary labels (CLs), which specify a class that a data sample does not belong to. However, the direct combination of AT with existing methods for CLs results in consistent failure, but not on a simple baseline of two-stage training. In this paper, we further explore the phenomenon and identify the underlying challenges of AT with CLs as intractable adversarial optimization and low-quality adversarial examples. To address the above problems, we propose a new learning strategy using gradually informative attacks, which consists of two critical components: 1) Warm-up Attack (Warm-up) gently raises the adversarial perturbation budgets to ease the adversarial optimization with CLs; 2) Pseudo-Label Attack (PLA) incorporates the progressively informative model predictions into a corrected complementary loss. Extensive experiments are conducted to demonstrate the effectiveness of our method on a range of benchmarked datasets. The code is publicly available at: https://github.com/RoyalSkye/ATCL.

Adversarial Training with Complementary Labels: On the Benefit of Gradually Informative Attacks
Jianan Zhou
Jianing Zhu
Jingfeng Zhang?
Tongliang Liu
Gang Niu Bo Han
Masashi Sugiyama 2.4
Hong Kong Baptist University 2RIKEN Center for Advanced Intelligence Project
TML Lab, The University Sydney "The University of Tokyo
[csjnzhou, esjnzhu, bhanml] @ @wwmp.cobbua....m hem.p.hkbu.dd...k
tongliang. liu @ wydney..ddylleeeeeee edu.
gang.niu.ml gmail.com sugi @ k.u.tokyo.ac.
Abstract
Adversarial training (AT) with imperfect supervision significant but receives limited attention. To push AT towards more practical scenarios, explore brand new yet challenging setting, i.c. AT with complementary labels (CLs), which spec- ify class that data sample does not belong to. However, the direct combination of AT with existing methods for CLs results in consistent failure, but not on a simple baseline of two-stage training. In this paper, we further explore the phenomenon and identify the underlying challenges of AT with CLs as intractable adversarial optimization and low-quality adversarial examples. To address the above problems, we propose a new learning strategy using gradually informative attacks, which con- sists of two critical components: 1) Warm-up Attack (Warm-up) gently raises the ad adversarial perturbation budgets to case the adversarial optimization with CLs; 2) Pseudo-Label Attack (PLA) incorporates the progressively informative model pre- dictions into a corrected complementary loss. Extensive experiments are conducted demonstrate the effectiveness of our method on range of benchmarked datasets. The code is publicly available at: https: //gi thub. com /et///RolyyyyyyOOO/
Introduction
Deep neural networks vulnerable adversarial examples [15]. which motivates the development
of various defensive methods 30 21 24 2 to mitigate the arisen security issue. As one of the most effective and practical defensive methods, adversarial training (AT) [24] has been widely studied [1] [T]] Specifically, it formulates the problem as min-max optimization, which generates adversarial data during training and minimizes the training loss of the generated adversarial variants. In this way, the models are equipped with adversarial robustness against numan-imperceptible perturbations within the neighborhood of imputs. Although AT with perfect supervision (e.g., ordinary labels) has been thoroughly studied by previous works 25
43 [Л] the more common learning scenarios with imperfect supervision 45 has only received limited attention.
33
Complementary labels (CLs) [7], which convey partial label information by identifying a class that of those practical and promising imperfect supervision in 38 [4] recently focused on learning
data sample does not belong to, weakly supervised learning 3 27]. Several works 39 18 13
with CLs, where the model trained only with CLs through their designed losses (i.e., complementary loss f) is expected to predict ordinary labels accurately during inference. Their success illustrates the
"quual contribution.
Corresponding authors: Bo Han (bhanml wwwpecom..c..cc.cccc.. www.oopwwb...........o and Gang Niu (gang .uu. ml @ (emmail.com).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Duck 100
PORMAND
100 sep
40
25
SCLAL
30
LDS
20
0
20
60
100
40 60
80
100
40
60
100
spoch
<pach
(a) Failure of direct combination
(b) Trials of Complementary Losses
(c) Trials of Training Tricks
Figure 1: (a) in contrast to a simple two-stage baseline, the direct combination of AT with CLs (LOG (33 results the worse performance with the failed training curve. The two-stage baseline consists of complementary learning in the first 50 epochs and AT with predicted labels in the last 50 epochs; (b) we try various complementary loss functions while all of them result in consistent experimental failure in AT with CLs; (c) several training alternatives (e.g., optimizer) are tried with no success. We report mean with standard errors for PGD20 test accuracy on Kuzushiji within multiple random trials. The training on the direct combination of AT with CLs is significantly unstable.
possibility of training ordinary classifiers even when all the labels given for training are wrong (except that the data and labels are statistically independent). Due to the low acquisition cost and privacy preservability, it has been applied to online learning [9] and medical image segmentation BT.
To push AT towards more practical scenarios, explore brand new yet challenging setting, i.e., AT with CLs. In this paper, our interest how to equip machine learning models with adversarial robustness when all given labels in dataset are wrong (i.e., CLs), which is of scientific interests to both research areas of weakly supervised learning and adversarial learning. To conduct AT with CLs, straightforward attempt is regard & as the training objective of the min-max optimization
[5] 24
13 for learning with simple baseline of two-stage training (as shown in Figure D. To be specific, we mainly consider the single complementary label (SCL) with the uniform CL with the same probability. In complementary learning, the complementary losses i are obtained by certain correction techniques T 39) which guarantee the training with E on complementary datasets achieves similar performance to the training with the ordinary loss E on ordinary datasets. In contrast, when conducting AT with CLs, most experiments (as shown in Figure 1 with different and optimizers) consistently show failed training curves except for a simple two-stage baseline, which consists of a natural complementary learning phase and AT phase using the predicted labels of the first-stage model.
However, the direct combination of AT with existing methods
39
CLs results in consistent failure, but not
assumption 17
[8 7 where labels other than the true label are chosen
The above fact motivated us to further investigate AT with CLs, and we identified its unique challenges as intractable adversarial optimization and low-quality adversarial examples (as verified in Figure 2 Specifically, we first theoretically prove that conducting AT with the complementary risk statistically consistent to that with the ordinary risk when training with the general backward corrected loss [18 Although the guarantee holds with sufficient data, it is not preserved any more with limited number of CLs given practice 7 (see Eq. in Section 4.1). Empirically, of AT with CLS (e.g., gradient directions and norms), and observe that adversarial optimization with CL.s through & suffers from large gradient variance, with the gradient vanishing issue at the early stage of training. Moreover, we also find that the complementary loss as the objective of adversarial optimization fails generate high-quality adversarial examples due the less informative nature [77 of CLs and the implicit way of attacking ordinary labels (i.c., attacking Ejt9 Pe(j (j) x)) instead).
analyze the training dynamics
To mitigate the problems, we propose a new learning strategy using gradually informative attacks (in Algorithm M for AT with CLs, which consists of two critical components, i.e., Warm-up Altack ( (Warm- up) and Exeudo-Label Attack (PLA). We introduce the Warm-up to ease the intractable optimization with CLs. which is gradually transferred from natural training to AT by controlling the adversarial budget. We design the PLA to improve the low-quality adversarial generation, which incorporates the informative predictions from the progressively discriminative model itself. Overall, propose unified framework using a flexible scheduler to adjust two critical components during training.

---

Our contributions are summarized as follows. 1) Setting level: we study AT with CLs, which is practical yet thus far unexplored setting. 2) Challenge level: we discover the substantial experimental failures in the direct combination of AT with existing methods for learning with CL.s (in Figure I and provide the underlying insights of the observed phenomenon from both theoretical and empirical perspectives (in Sections I and adversarial optimization and low-quality adversarial examples. 3) Methodology level: we accordingly propose a unified framework, using Warm-up and PLA with a controllable scheduler to mitigate the problems (in Sections 1.3). 4) Experimental level: we conduct extensive experiments to verify the effectiveness of our method, and to understand the benefits of two critical components (in Section 5
Specifically, we identify two challenges as intractable
2 Related Work
Complementary Learning. Learning with CLs was introduced by [7], where the SCL with the uniform assumption was firstly considered. An unbiased risk estimator (URE) was derived by modifying a specific loss function (e.g., one-versus-all or pairwise comparison) that satisfies symmetric condition. Continuing with this work, [18] derived general URE for arbitrary loss functions and models, and further proposed non-negative correction and gradient ascent methods to cope with the overfitting issue of URE in practice. Although URE has good statistical properties, it has inferior empirical performance due to huge gradient variance. 7 mitigated this problem by proposing a surrogate complementary loss framework, which is biased risk estimator trading zero bias with reduced variance. Other than the uniform assumption,
39] considered the biased CLs, where labels other than the true label are chosen as a CL with different probabilities due to the annotator's 's bias. In addition to the SCL setting, [ derived an URE of the ordinary risk for multiple complementary labels, and further improved by minimizing properly chosen upper bounds. Moreover, there are also several works less related to the loss correction in complementary learning, such as introducing regularization
38 or reweighting [1] during the training process.
Adversarial Training. As one of the most effective defensive methods, AT has been widely studied 37
to improve the robustness of deep learning models [11
26 35 6). The standard AT [24] formulated the problem as min-max optimization. 4 proposed CAT to mitigate the catastrophic
36
forgetting and the generalization issues of AT. [4]] decomposed the prediction error into the natural and boundary errors, and proposed TRADES to balance the classification performance between the natural and adversarial examples. 4 resolved the trade off between robustness and accuracy via reweighting adversarial data by their geometrical information to the decision boundary. In contrast to previous works, only limited effort has been made to explore AT with imperfect supervision [27] 451 explored the interaction of AT with noisy labels (NLs), and found that AT itself is NLs correction since the number of PGD steps could be used to improve sample selection quality. 42] investigated the effects of NLs injection on the adversarial optimization, and proposed Nn mitigate the
robust overfitting issue based on the empirical observation that NLs are not always detrimental.
3 Preliminaries
In this section, we provide preliminaries for ordinary learning, complementary learning and AT. For complementary learning, we consider the SCL setting with the uniform assumption 17 [8 7 For AT, we focus on the standard method proposed in 24
3.1 Ordinary Learning
Let X C IRd be the input space, and y E [K] := (1, KJKK > 2) be the label space. The data (x H:) is sampled independently and identically from the joint distribution D with density p(X, Y), which could be further decomposed into p( pY( We define a class ctobs-probabilitt function n (x) p(Y = i| = 2). The decision and loss functions
defined as g X R and L: y x R + Rt, respectively. The goal of ordinary learning is to train a classifier f(x) : X y,
which is expected predict the correct label by arg max; g(x).. The ordinary risk is defined as
R(g; C) E(ax) Illy (())))()))
3

---

3.2 Complementary Learning
In complementary learning, the label space transformed into y, where each ordinary label y is flipped into E Y with a class-dependent probability p(ylv). Then, the data is sampled from different joint distribution D with density p( (X, Y). We assume the transition matrix Q E && is invertible, where Qij = p(Y = = i). With the uniform assumption, it takes 0 on diagonals and
K-1 on non-diagonals. The class-probabillty function is then written as
(((x) = PV = i = x) Σ p( = iY j)p(Y j = x) (g(n((.) 1#1
j#i
The complementary risk is defined as R(y; () E(V (z))], where E is a complementary loss function. Typically, it can be derived by the loss correction, which is technique that ensures risk or classifier consistency in the weakly supervised setting 2 17. The backward correction a risk consistent algorithm that ensures R is statistically consistent risk estimator of the ordinary risk R. while the forward correction is a classifier consistent algorithm that guarantees the classifier learned from D using l converges to the optimal one learned from D using L. In complementary learning, [7 18 3 focused on the backward correction that multiplies the loss by Q-1, while [3] proposed forward correction method via multiplying the model prediction by Q. Other methods (e.g.. bounded loss) can also be used to derive complementary losses loss functions are provided in Table 2 of Appendix
The detailed complementary
General Backward Correction. Among this line of research, a notable work D8 derived an URE of the ordinary risk, without any restriction on the used loss and model. Given the notations borrowed from [8 7 (((()) = [e(1, gzx)), {(2, g(z))..... ...,,(K, (((,g(()))) and e, is the one-hot column vector with one on the 4th entry. the URE derived as follows:
Proposition 1.
The ordinary risk can be expressed in terms of CLs as follows,
Ríg; e) (( (onni//!((y.. ((,, s(x))) = ((. R(g: E)
(3)
when É is rewrillen as
(
(4)
With the uniform assumption, E can be further rewrilten as
E(T.g(x)) -(K--))g,pl + Σ ((.g(()))
(5)
With this expression, we can obtain an URE of the ordinary risk only from CLs.
3.3 Adversarial Training
AT has been a commonly used defensive technique that equips deep learning models with adversarial robustness against imperceptible perturbations within small neighborhood of input. Here, consider conducting AT with ordinary labels (e.g., is the cross-entropy loss). Generally, it can be formulated into min-max max optimization problem:
min ((t)))(((((gg)))))) (f))), with F arg max
Ju] [n ((,))),,
(6)
where B, [x] {a: | ह I c} is the closed ball centered at input x with radius e > 0 under n,-norm threat models, and J. is the adversarial data found within B, (z).. Empirically, the solution of inner maximization approximated by projected gradient descent (PGD) as follows:
(1+1) IT. [o] (z asign V.1 ((
where is the step size, II is the projection operator that projects the adversarial data back to the epsilon ball, (1) is the adversarial data found at step I, and (0) is initialized by natural data or natural data with a small Gaussian or uniformly random perturbation. The adversarial data updated iteratively in the direction of loss maximization until stop criterion is satisfied.

---

4 Adversarial Training with Complementary Labels
In this section, we first provide some theoretical insights for AT with CLs. Then, we empirically analyze the experimental failure and identify the critical challenges as intractable adversarial opti- mization and low-que -uw-qulliy adversarial examples when conducting AT with corrected complementary losses. Accordingly, we propose new learning strategy with gradually informative attacks.
4.1 Theoretical Analysis
Without loss of generality, below we analyze the general backward correction |B| theoretically, and other popular complementary loss functions on the SCL setting.
For the general backward correction, conducting AT on the complementary risk is equivalent to that on the ordinary risk. However, this is not the case on their empirical risks:
Proposition 2.
min Exxp(X) #EB.(u]
Eysptr|x== (Ky. [())] min Exxp(X), SEB,(2]
max (e.
(8)
min Σ
[Ky (a:))) # min
max 2.EB.(m
[T. g(;)))]
The detailed proof is provided in Appendix A.2 In brief, when considering the general backward corrected loss, the maximization induced by AT keeps the statistical properties of the complementary risk, and it still yields consistent risk estimator. In theory, the adversarial optimization of the complementary risk with the general backward corrected loss is statistically consistent to that of the ordinary risk with the ordinary loss. But in practice, can only obtain limited CLs (e.g.. the sample size of E (P)x)() is one on the SCL setting), which causes the inconsistency between their empirical risks (i.e., the solutions to their inner maximization are different), and hence leads to difficult adversarial optimization (as verified in Appendix D.2). The solution to inner maximization of the complementary risk is equivalent to that of the ordinary risk if and only if maximizing the weighted loss over all candidate CLs, that is E F=)>(()X==>(((0 (+))
From the perspective of AT, expect to find the adversarial examples ă within the neighborhood of input æ that make the model predictions on the ordinary label ps (y|ā) (ī) as low as possible. When we have ordinary labels, it is quite straightforward to achieve this objective by maximizing the cross- entropy f = log pe (z) However, if we further consider recent proposed methods in addition to the general backward correction in complementary learning, most of i mathematically try to maximize Σjey (0) Po (or equivalently minimize po (ū ()) as shown in Table 2
Maximizing E leads to the minimization of Ejer(to) Po(jlă) which cannot guarantee the minimization of po ()) In such case, the inner maximization may serve random attacker without prior knowledge. Hence, corrected complementary losses fail to achieve the objective of AT, and low-quality adversarial examples may be generated, which is detailedly discussed in the following part.
4.2 Empirical Analysis
We conduct the experiment on Kuzushiji to justify the previous theoretical insights. For the upper panels of Figure 2
we focus on the issue of intractable adversarial optimization by adversarially training the model using several loss functions separately, with three random trials. For the lower panels of Figure 2
we focus on the issue of low-quality adversarial examples by measuring the different adversarial examples generated by various loss functions, given the same optimization model (i.e., the oracle model, which is trained using AT with ordinary labels). We show the average results over different seeds and training samples, respectively, Without loss of generality, here we only show the results of one complementary loss (i.e., LOG [3), and our proposed method (i.e., Warm-up+ PLA in Section 4.3). The detailed experiment settings and more comprehensive empirical results with other complementary losses and datasets are provided in Appendix C
Intractable Adversarial Optimization. In the outer minimization of AT, we first collect the gradient direction (with respect to the model parameters) of each data in one mini-batch (i.c., 256), and then compute the trace sum their covariance matrix (the average result for each epoch is shown
5

---

0.9
0.9
Loc
0.8
UPC
250
0.8
0.7
225
0.6
0.6
200
0.5
0.5
0.4
0.3
130
0.3
0.2
100
125
Onsei
20
40
60
80
100
02
0.0
0.1
20
60
80
100
0.3
0.0
20
40
60
80
100
epoch
epoch
(a) Gradient Direction Variance
(b) (Last Layer) Gradient L/- 2-rorm (c) (First Layer) Gradient No-No
LOC
0.8
100
0.20
Warn-g-PAAA
0.4
0.10
0.05
100
Mare-up-- ULA
60
60
100
epoch
epoch
upech
(d) Cosine Similarity
(e) I-Distance
(1) Po po(l
Po
Figure 2: [Intractable Adversarial Optimization] (a) the trace sum of covariance matrix of gradient directions w.r.t. the parameters of the first layer; (b) the 12-norm of stochastic gradients of the last layer, (c) the 12-norm of stochastic gradients of the first layer; [Low-quality Adversarial Examples] (d) the cosine similarity of gradient directions (i.c., sign (Vz((z, ÿ; 8))) with the oracle in the inner maximization; (e) the 1 -ddisttncce of the constructed adversarial examples with the oracle; (f) the difference of model predictions of natural data and adversarial data on the ordinary label.
the upper-left panel of Figure 2 A larger value reflects a group of gradient directions with a bigger variance. Note that the result of LOG nearly reaches the maximum trace sum of covariance matrix of the gradient directions, which results in its consistent failure at the early stage training. We also compute the average 12-norm of stochastic gradients of the last and first layer shown in the upper-middle and upper-right panels of Figure 2 respectively. Although some gradient signals exist for LOG in the last layer, the gradients paok-propagated the first layer is small that gradient vanishing problem occurs at the early stage of training. This phenomenon similar to that observed in the standard AT, which is conjectured the prevalence of dead neurons caused by large radius of epsilon ball 23 Moreover, considering AT with CLs, it is expected that the gradient norm tends be small since the observed variance of gradient directions one mini-batch is extremely large. The above observations indicate the adversarial optimization with CLs is difficult, and it is rational to use the method (i.e., our Warm-up+PLA) ease the optimization.
Low-quality Adversarial Examples. In the inner maximization of AT, given the same optimization model, we measure the quality generated adversarial examples by computing the cosine similarity of gradient directions (with respect to the same data) and the Ii-distance of constructed adversarial examples, with the oracle examples generated by ordinary label (in the lower-left and powermiidle panels of Figure D A larger cosine similarity and lower 1 -dittance indicate a stronger resemblance to the oracle, but not necessarily a stronger attack (or high-quality adversarial examples). Hence, we further compute the difference of model predictions of natural data and adversarial data on the ordinary label during training (in the lower-right panel of Figure D. A bigger difference explicitly demonstrates stronger attack. The results show that the complementary loss as the objective of AT with CLs fails to generate high-quality adversarial examples as our analysis Section
4.3 Methodology
To address the previous problems, we accordingly propose new strategy using gradually informative attacks to ease the intractable adversarial optimization and improve the quality of adversarial examples, respectively. Our algorithm is concretely presented in Algorithm [] Specifically, it consists of Warm-

---

Algorithm AT with CLs Using Gradually Informative Attacks
number of epochs: E, number of batches: B, number of class: K, radius of epsilon hall: number of attack steps: &., step size: a. hyperparameter for exponential moving average of cashed model predictions: 8 hyperparameter for label weights: 7,
Input:
Output: robust model On:
1: Pe K-1 (1 eg)" for all data
2: for ..... E do
3: 8,7 6 Update hyperparameters
4:
te, ke + Adversarial budget scheduler
Warm-up Attack
5:
for b- I,.... B do
6:
f Sample batch of data
7:
po(x)) t- Softmax (()x)) p=( <- Spo(w) (1 -3)pp (o(()a)) +-
8:
1 < arg maxişs Pc (i]zz)
9:
I & Approximate the solutions of max 6(2; 5; 0) (Eq. 10 by PGD( Ole, ke)
10:
L - (K log(r En Po (jlz) +1
Pseudo-Labe Attack
11: 0 + SGD(O, VoC)
12: end for
13: Evalunte(e, a, a.,)
14:
end for
up Attack and Pseudo-Label Attack, whose dynamics are controlled by flexible scheduler:
2 (1 - (cos(min( E
ES 1). xx) Warm-up Attack,
T(a, e, Ea) =
(9)
a (1 min( 1))
Pseudo-Label Attack,
where a is the maximum value of the scheduled variable (i.e., Emax = in Warm-up Attack and Tmmx = 1 in Pseudo-Label Attack), e is the epoch index, and Eg is the duration of the scheduler. Both the proposed attacks can be controlled by a flexible scheduler with the increasing and decreasing trends respectively (e.g., see the example in Figure 3) Below, we describe each component in detail.
Warm-up Attack. Adversarial optimization is harder compared with ordinary optimization and CLs further strengthen the degree of hardness as observed in our empirical analysis. The major difference of AT with CLs from the standard AT is the labels used in the adversarial generation. As shown in Figure 2 training with the adversarial examples generated by different labels results in the different gradient variance. Since the adversarial generation on CLs induces large gradient variance which causes the difficult adversarial optimization, we can adjust the adversarial generation to control the variance introduced into the optimization. To be specific, we adopt a dynamic adversarial budget to gradually enhance the degree of adversarial generation. Typically, adversarial budgets consist of radius of epsilon ball e, number of attack steps k; and step size a. Here, we mainly focus on the dynamics of in Eq. ( The radius of the epsilon ball is increased from 0 to within Eg epochs, and is kept constant until the end of adversarial optimization. The number of attack steps is constant (ke k), and the step size is increased proportionally to (a, f=a). In this way, the gradually increased adversarial budget can ease the difficulty of adversarial optimization.
Pseudo-Label Attack. Due to the existence of an adversarial budget scheduler, at the early stage of optimization, simple patterns may be prevalent in adversarial data found within an extremely small epsilon ball, which is helpful for the self- cel--evolvement of a discriminative model. The model tends to assign high confidence to the potential ordinary label, while low confidence to others. This informative model prediction is strong supplementary information that is promising for improving the quality of the adversarial generation. Therefore, we propose to optimize the objective consisting of the convex combination outputs of partial labels (labels other than CLs) and predicted ordinary label. This transforms the whole process into an optimization that starts with learning with CLs using certain correction techniques, and gradually moves to learning with predicted labels regarding them as ordinary labels. The loss function can be defined as follows:
É(z, 0) - -KK log(> Σ po(ilz) (1 7)pp (0pe000 [)), arg max maxpe (ilx,)) jデリ
(10)
379
where 7 E [0, 1] a hyperparameter that controls the transition of learning. Recent studies found that adversarial training can degrade the generalization, and a trade-off between natural accuracy
7

---

245
149
20
26
42
100
330
32
25
(a) Dynamics Ea and 7
(b) Ablation Study Kuzushiji
(c) Ablation Study CIFARIO
(d) Ablation Study on
Figure 3: (a) example of the dynamics of c. and adopted on MNIST/Kuzushiji, where the warmup period is 10 epochs, and E, 50: (b) ablation study of the two components on Kuzushiji: (c) ablation study of the two components on CIFARIO; (d) PGD20 test accuracy on Kuzushiji w.r.t. the Es.
and adversarial robustness exists optimization (e.g., a drastic shift of model predictions may occur due to the increasing adversarial budget), we use a simple exponential moving average to collect the dynamics model predictions, and choose the label with the maximum probability predicted ordinary label. Specifically, given the model predictions pa (2) of the current epoch, the cashed model predictions po(x) is updated as Pe(x) = (pp(a) + (1 - ())) where Pe(z) initialized with (I-eu!"
32
To avoid the effect of such degradation and stabilize the
K (P((y]z) 0, and B 0.9.
Experiments
In this section, we empirically verify the effectiveness of our method on MNIST 22 Kuzushiji (
CIFARIO (20) and SVHN (28) datasets, and conduct ablation studies to understand the two attacks. More detailed information and the conducted experiments are presented in Appendix D
Setups. 1) General Setups: for MNIST and Kuzushiji, we train small convolutional neural network, as used in A1. for 100 epoch with batch size of 256. For CIFAR-10 10 and SVHN, ResNet- 18 is trained for 120 epochs with batch size of 128. The training sets of CIFAR-10 10 and SVHN augmented with random cropping and horizontal flipping. 2) Adversarial Training Setups: we focus on the Lee threat model. For MNIST and Kuzushiji, stochastic gradient descent (SGD) is used with learning rate of 0.01 and momentum of 0.9. PGD is used as the approximation method of solving inner maximization, with
0.3, a 0.01 and & 40. For CIFARIO and SVHN, SGD is used with weight decay of 5e-4 and momentum of 0.9. The initial learning rate is 0.01, and decayed by 10 Epoch 30 and 60 of adversarial optimization. For the I threat model, c = 8/255, a 2/255 and k = 10. 3) Complementary Learning Setups: following the settings in 18 |33) for MNIST and Kuzushiji, Adam optimizer is used with learning rate of le-3 and weight decay of le-4. For CIFARI0 and SVHN, SGD is used with weight decay of 5e-4 and momentum of 0.9. The learning rate is linearly increased to 0.01 within the first epochs. More details are provided in Appendix D.I
Baseline. 1). Two-stage method: it first trains model for 50 epochs with the methods of comple- mentary learning (i.e., LOG, which shows better performance and stability compared to others (3)). Then we re-label the complementary training set using the checkpoint with the best validation per- formance, and adversarialyy train another model using the re-labeled training set afterwards. 2). Conducting adversarial training directly with complementary losses, including FORWARD (9)] FREE, NN [8]. SCL_NL_ SCL EXP 77) EXP and LOG [3.. We evaluate the adversarial robustness using PGD20, CW30 and AutoAttack (AA) g and report the results of checkpoint with the best PGD20 test accuracy. All experiments are conducted with multiple random seeds (i.e., 1-3).
5.1 Performance Evaluation
The detailed results are reported in Table ! where Oracle refers to the standard AT with ordinary labels, and is just given for measuring the performance gap between AT with CL.s and ordinary labels. For easy datasets (e.g., MNIST), the complementary losses are possible to obtain satisfying results, while most of them fail on complicated datasets. We would like to mention that the performance of
Note that AT is nearly 10-40 times 24 40 slower than the natural training due to the adversarial generation.
Here train 100 epochs which kept the same as the most literature in AT 24 41 2g

---

Table 1: Means (standard deviations) of natural and adversarial test accuracy.
Dataset
Method
Natural
PGD
AA
Oracle
99.46(++0.04)
98.14(+:0004)
97.45(+0.088
92.53(+:0.23)
Two-stage
99.07(+
97.44(=:0.23)
96.22(+00211)
92.06(+:::45)
FORWARD
97.22(=11.13)
93.76(1:2.38)
92.13(12.87)
85.41(#3..9)
FREE
48.94(::26.04)
38.02(+:22.11))
32.81(#19.63)
13.69(+11391)
MNIST
18
68.48(2240440)
66.80(++33.22)
66.25(
60.65(238.04)
SCL NL
93.09(++.335)
87.07(++1.40)
84.5((+14.51)
75.98(+11.29)
SCI__XXP EXP
(4.99
(4.34(
13.58(
10.47(#
EXP IR
10.59(=0.50)
10.90(
10.99(=0.50)
10.99(
LOG
13
97.16(##0.64)
1..38(+1.255)
91.67(#1..9)
84.88
Warm-up+PIAA
99.22(10.002)
0.073(10006)
97.11(L0.07)
92.37(11.11)
Oracle
95.94(+:0115)
90.01(+-::33)
88.06(+-0.96)
70.63(+-0:48)
Two-stage
89.75()00442
82.91(#1.01)
10.21(#1.277)
64.57(
FORWARD
35.48(#+:77.6)
29.84(+225.55)
28.09(++2.37)
22.01(#18.98)
FREE
1.777
12.01(#0.55)
9.33(
1.0((1160))
Kuzushiji
NN
10.00(=00.00)
10.00(
10.00(
8.87(
SCL
40.83(+:24.03))
32.82(++2.888)
29.93(#22.53)
20.86(+19.74)
SCL
10.00(=00.00)
10.000
10.000
8.21(=2.54)
EXP
10.00(=1.000)
10.00(
10.00
10.00
LOG
32.66(++2.500)
26.87(#22.66)
24.90(#21.20)
18.78(#
Warm-up+PLA
91.60(100:99)
85.88(10.48)
83.74(L0.35)
68.75(10068)
Oracle
78.10(+0..36)
47.35(+
45.66(+0.222)
43.47(+L0.2))
Twa-stage
64.98 2.700)
02.99
39.60(
(0.46)
FORWARD
15.41(=-0.85)
13.56(
13.03(+-0.4)
12.94(
FREE
11.60(
10.54(
10.45(=0.20)
10.32(
CIFARIO
NN
11.79(=0061)
11.13(#0.56)
11.14
11.10(
SCL_ NL
14.45(+
13.13(
12.84(
12.79(
SCL SCL_EXP
1.76)
1.35
12.45(#1.355
12.38(
EXP
10.17(+
10.66(+00.00)
10.38(--0.36)
10.37(+-0.4))
LOG
11.70(
(1.04
10.49(
10.44(
Warm-up+PLA
65.88(+1..51)
03.79(1
41.30(+
40.28(1
Oracle
91.95(10011)
53.89(
50.59(
47.05(+O..2))
Two-stage
90.62(:10.27)
53.92(+
50.86(
47.31(+O.11))
FORWARD
10000)
10.00)
19.00)
19.00(
FREE
09.00
09.00
19.00
19.60
SVHN
NN
19.00
19.00
19.00)
19.68(
SCI_
(0.00)
00.00)
(0.00)
19.67(
SCL_EXP
(0.00))
(0.00
(9.00
19.00
EXP
19.60(+00.01)
09.00)
19.06(
19.65(+0.004)
LOG
19.09(
19.60(10.022
19.59(10.00)
19.08(
Warm-up+PLA
90.50(++0.16)
54.58(+..110)
51.04(L0.04)
47.47(10.13)
the two-stage and methods slightly outperform that of the oracle on SVHN. We assume it may be attributed to the recent observation that noisy datasets (with a small portion of noisy labels) are not always detrimental to AT, and can even further boost the adversarial robustness 42
5.2 Ablation Study
In this part, conduct the ablation study demonstrate the importance of the two components, i.e., Warm-up Attack and Pseudo-Label Attack in our method with the critical hyperparameter.
Two Critical Components. We investigate the roles of two components in our method by removing them separately. We report the results within three trials on Kuzushiji and CIFAR 10 datasets as shown in the left-middle and hight-middll panels of Figure 3 In summary, warm-up attack could stabilize

---

the optimization especially when the model capacity are not sufficient large, and pseudo-label label attack erucial for the achieving high adversarial robustness. Specifically, the warm-up attack achieves quite good performance on Kuzushiji, while limited improvements on CIFARIO. 10. This is expected due to the difficulty of CIFARIO without further informative attacks. Pseudo-label attack solves this problem by incorporating the informative model predictions, and hence achieves quite good performance on CIFARIO. However, it has an unstable result on Kusushiji, which is attributed to the limited model capacity. It is of great importance to achieve adversarial robustness given limited model capacity. Therefore, warm-up attack is still a crucial component for stabilizing the optimization.
Hyperparameter. We investigate the performance sensitivity to the key hyperparameter E., which controls the growing speed of informative attacks. We report the results within three trials on Kuzushiji as shown in the right panels of Figure 5 The result shows similar performance across a wide range of Egg, which demonstrates that our method is not sensitive to the tuning of key hyperparameter.
Conclusion
To the best of our knowledge, this is the first work to study adversarial training (AT) with complemen- tary labels (CLs), and to analyze its challenges from both theoretical and empirical perspectives. To solve them, we proposed a new learning strategy using gradually informative attacks, narrowing the performance gap between AT with CLs and ordinary labels. Our work shed light on the applications of AT to a more practical scenario (e.g., with imperfect supervision). In this paper, we focused on the standard AT algorithm, which formulates the problem as min-max optimization. We leave more advanced algorithms (e.g.. TRADES) and other complementary settings (e.g.. multiple CLs) to the future work. Moreover, CLs can be viewed as an extreme case of noisy labels with 100% noise rate, or partial labels where the labels other than the CL the candidate set of labels. Hence, we hope work could provide new insights for AT with various imperfect supervision in the ML community.
Acknowledgments and Disclosure of Funding
JNZ and BH were supported by NSFC Young Scientists Fund No. 62006202, Guangdong Basic and Applicd Basic Research Foundation No. 2022A1515011652, and RIKEN Collaborative Research Fund. BH also supported by RGC Early Career Scheme No. 22200720, RGC Research Matching Grant Scheme No. RMGS2022_1 11__11111111 11_0211111111111111111 and No. RMGS2022_I1 06, and HKBU CSD Departmental Incentive Grant. JFZ was supported by JSPS KAKENHI Grant Number 22K17955 and JST ACT-X Grant Number JPMJAX21AF, Japan. TLL was partially supported by Australian Research Council Projects DP180103424, DE- EEE-19000443,, IC-190100033 DP 22122010,, and FT-220100318. GN and MS were supported by JST AIP Acceleration Research Grant Number JPMJCR20U3, Japan. MS was also supported by the Institute for Al and Beyond, UTokyo. We would also like to thank the anonymous reviewers of NeurlPS 2022 for their constructive comments and recommendations.
References
[1] lean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang. Alhussein Fawzi, Robert Stanforth, and Pushmeet Kohli. Are labels required for improving adversarial robustness? In NeurlPS, 2019.
[2] Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adver- sarial training. In NeurlPS, 2020.
[3] Dana Angluin and Philip Laird. Learning from noisy examples. In Machine Learning, 1988.
[4] Qi-Zhi Cai, Chang Liu, and Dawn Song. Curriculum adversarial training. In IJCAI, 2018.
[5] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C. Duchi. Unlabeled data improves adversarial robustness. In NeurlPS, 2019.
[6] Tianlong Chen, Zhenyu Zhang. Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In ICLR, 2021.
[7] Yu-Ting Chou, Gang Niu, Hsuan-Tien Lin, and Masashi Sugiyama. Unbiased risk estimators can mislead: A case study of learning with complementary labels. In ICML, 2020.
10

---

[8] Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. In arXiv, 2018.
[9] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter- free attacks. In ICML, 2020.
[10] Zhun Deng, Linjun Zhang, Kailas Vodrahalli, Kenji Kawaguchi, and James Y Zou. Adversarial training helps transfer learning via better representations. NeurIPS, 2021.
[11] Yinpeng Dong, Ke Xu, Xiao Yang. Tianyu Pang, Zhijie Deng. Hang Su, and Jun Zhu. Exploring memorization in adversarial training. In ICLR, 2022.
[12] Farzan Farnia, Jesse M. Zhang, and David Tse. Generalizable adversarial training via spectral normalization. ICLR, 2019.
[13] Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple complementary labels. In ICML, 2020.
[14] Yi Gao and Min-Ling Zhang. Discriminative complementary-label learning with weighted loss. In ICML, 2021.
[15] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In ICLR, 2015.
[16] Akhilesh Gotmare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. closer look at deep learning heuristies: Learning rate restarts, warmup and distillation. In ICLR, 2018.
[17] Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. In NeurlPS, 2017.
[18] Takashi Ishida, Gang Niu, Aditya Menon, and Masashi Sugiyama. Complementary-late learning for arbitrary losses and models. In ICML, 2019.
[19] Takuo Kaneko, Issei Sato, and Masashi Sugiyama. Online multiclass classification based prediction margin for partial feedback. In arXiv, 2019.
[20] Alex Krizhevsky. Learning multiple layers of features from tiny images. In arXivv, 2009.
[21] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In ICLR, 2016.
[22] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. baadient-based learning applicd to document recognition. Proceedings of the IEEE, 1998.
[23] Chen Liu, Mathieu Salzmann, Tao Lin, Ryota Tomioka, and Sabine Süsstrunk. On the loss landscape of adversarial training: Identifying challenges and how to overcome them. In NeurIPS. 2020.
[24] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[25] Pratyush Maini, Eric Wong, and Zico Kolter. Adversarial robustness against the union of multiple perturbation models. In ICML, 2020.
[26] Amir Najafi, Shin-ichi Maeda, Masanori Koyama, and Takeru Miyato. Robustness to adversarial perturbations in learning from incomplete data. In NeurIPS, 2019.
[27] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. NeurIPS, 2013.
[28] Yuval Netzer, Tao Wang. Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. In NewrIPS Workshop Deep Learning and Unsupervised Feature Learning, 2011.
[29] Tianyu Pang, Xiao Yang, Yinpeng Dong, Hang Su, and Jun Zhu. Bag of tricks for adversarial training. In ICLR, 2020.

---

[30] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense adversarial perturbations against deep neural networks. In Symposium on Security and Privacy (SP), 2016.
[31] Mina Rezaei, Haojin Yang, and Christoph Meinel, Recurrent generative adversarial network for learning imbalanced medical image semantic segmentation. In Multimedia Tools and Applications. 2020.
[32] Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarialyy robust deep learning. In ICML, 2020.
[33] Amartya Sanyal, Puneet K Dokania, Varun Kanade, and Philip H. S. Torr. How benign is benign overfitting? In ICLR, 2021.
[34] Ali Shafahi, Parsa Saadatpanah, Chen Zhu, Amin Ghiasi, Christoph Studer, David Jacobs, and Tom Goldstein. Adversarially robust transfer learning, In ICIR, 2020.
[35] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In ICLR, 2018.
[36] Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple perturbations.
In NeurIPS, 2019.
[37] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick D. McDaniel. Ensemble adversarial training; Attacks and defenses. In ICLR, 2018.
[38] Deng-Bao Wang, Lei Feng, and Min-Ling Zhang. Learning from complementary labels via partial-output consistency regularization. I/CAI, 2021.
[39] Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complemen- tary labels. In ECCV, 2018.
[40] Gaoyuan Zhang, Songtao Lu, Yihua Zhang, Xiangyi Chen, Pin- Yu Chen, Quanfu Fan, Lee Martie, Lior Horesh, Mingyi Hong, and Sijia Liu. Distributed adversarial training to robustify deep neural networks at scale. In UAI, 2022.
[41] Hongyang Zhang, Yaodong Yu, Jiantao Jíao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, 2019.
[42] Jingfeng Zhang, Xilie Xu, Bo Han, Tongliang Liu, Lizhen Cui, Gang Niu, and Masashi Sugiyama. Noilin: Improving adversarial training and correcting stereotype of noisy labels. Transactions on Machine Learning Research, 2022.
[43] Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry-aware instance-reweighted adversarial training. ICLR, 2021.
[44] Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In ICMI., 2022.
[45] Jianing Zhu, Jingfeng Zhang, Bo Han, Tongliang Liu, Gang Niu, Hongxia Yang. Mohan Kankanhalli, and Masashi Sugiyama. Understanding the interaction of adversarial training with noisy labels. In arXiv, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] Yes.
(b) Did you describe the limitations of your work? [Yes] See Appendix
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix E
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Yes.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
2 and Section 4
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes] See Section
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 5 and Section D.1
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Table
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section D.I
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets... (a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "q4E_h-xfUUc", "reviewer": "Reviewer_Jbnu", "summary": "This paper aims to propose an effective adversarial training (AT) method for the scenario where the imperfect supervision is available. More specifically, the paper shows that when the complementary label (CL) (i.e. label for non-groundtruth class) are available, a direct combination of AT and CL will fail. To address this limitation, two attack approaches, warm-up attack and pseudo-label attack, are proposed. The former gradually increases the attack budget over the training epoch and the latter uses the pseudo-label of the model prediction to generate the adversarial example. Experiments demonstrate the effectiveness of the proposed attack methods under the imperfect supervision scenario.", "questions": "The author is suggested to address the concern in the weakness section, especially the novelty of this work (e.g. the proposed 2 attacks).", "limitations": "Yes, the author has provided the checklist and the discuss the broader impact in the supplemental material. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n1.\tThis work first proposed adversarial training together with complementary labels. From my best understanding, this is the first work to study this problem.\n\n2.\tThe motivation of studying adversarial training in imperfect data scenario is strong and practical. \n\n3.\tAlgorithm 1 is clear and simple to follow.\n\nWeakness\n\n1.\tIn L24, the author mentioned that the adversarial training (AT) with imperfect supervision has received less attention. While this work mainly studies the use of complementary labels, there are papers like [a], which studies AT with noisy label. The author is suggested to compare the proposed method with [a], which both study the AT in imperfect data regime.\n\n2.\tThe novelty of the proposed method is a concern of this work. The warm-up technique has been widely used in deep learning. For example, [b] studies the warm-up technique used to adjust the learning rate.  [c] is somewhat similar to the proposed Warm-up Attack, where the attack budget gradually increases (See section 5 of [c]). On the other hand, the pseudo-label attack mainly stabilizes the adversarial example generation by using the pseudo-label from model prediction. This has been widely used, for example, when applying adversarial training under semi-supervised learning [d] (See Meta-Algorithm 1 in section 4 of [d]). Since both proposed attack methods appear in the literature, the author is suggested to highlight the novelty of the proposed methods.\n\n3.\tFigure 3 only conducts ablation on the LOG method, does the improvement of adding Warm-up Attack and Pseudo-label Attack applied to other complementary learning baselines?\n\n\n\n[a] Understanding the Interaction of Adversarial Training with Noisy Labels\n[b] A closer look at deep learning heuristics: Learning rate restarts, warmup and distillation\n[c] On the Loss Landscape of Adversarial Training: Identifying Challenges and How to Overcome Them\n[d] Unlabeled Data Improves Adversarial Robustness\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SYs7QX0VnU-", "reviewer": "Reviewer_GzvY", "summary": "The authors explore a brand new yet challenging setting that studies adversarial training (AT) with complementary labels (CL). Generally, it is significant to involve CL in AT since imperfect supervision can be common in real AT scenarios. However, the direct combination of AT and CL consistently leads to failure according to extensive empirical observations.\n\nTo explore this issue, the authors provide theoretical evidence that there exists inconsistency between complementary risk and ordinary risk of adversarial optimization with limited CLs. Together with the empirical studies of gradients, they identify two key challenges including intractable adversarial optimization and low-quality adversarial examples.\n\nBased on the analysis, a new attack strategy is introduced. A warm-up is adopted to ease the difficulty of adversarial optimization. With the model prediction as supplementary information, the adversarial training gradually involves the pseudo label predicted by the model. The authors conduct extensive experiments on different datasets and compare proposed algorithm with various baselines to demonstrate its effectiveness.", "questions": "1.Please provide empirical evaluation of pseudo labels.\n2.Please include more ablation studies of warm-up strategies of attacks.", "limitations": "Yes, the authors have discussed the limitations and potential negative societal impacts in Appendix E.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n* In general, this paper is well-written and easy to follow. The motivation is clear. The studied setting is both significant and challenging.\n* Both the theoretical analysis of the inconsistency between empirical risks with the assumption of limited CLs and the empirical analysis of the difficulty of adversarial optimization as well as adversarial example generation are intriguing.\n* The proposed techniques including warm-up and pseudo-label are proposed based on the theoretical and empirical analysis, which are simple yet natural.\n* The authors provide sufficient evaluation of proposed algorithm. The evaluation is conducted on MNIST, Kuzushiji, CIFAR-10 and SVHN, and includes various SOTA complementary losses for comparison. The proposed algorithm consistently achieves better adversarial robustness as well as stability.\n\nCons:\n\n* In Section 4.3, the authors propose to use model prediction as a strong supplementary information since the model tends to assign high confidence to ordinary label when the epsilon ball is small enough. However, it is difficult to find empirical evidence of it in experimental section. It would be better for the authors to report the accuracy of pseudo labels in some scenarios.\n* The author introduces a warm-up attack which controls the radius of epsilon ball. However, the number of attack steps is fixed during warm-up. It would be better for the authors to conduct more ablation studies of it.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D92bm06NeyQ", "reviewer": "Reviewer_u259", "summary": "This paper proposes to address a new problem: adversarial training with Complementary Labels (CLs). A naive combination of Adversarial training and CLs fails to yield good performance. The authors identified the problem of this naive combination and propose to use Warm-up Attack and Pseudo Label Attack to address these problems. The proposed method yields a performance improvement above the naive combination and simple two-stage method.", "questions": "My main concern is the novelty of the proposed method. It would be good if the author can further explain on this.", "limitations": "No  negative societal impact is found.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The writing is good and easy to follow\n2. Thorough theoretical analysis is provided\n3. The target problem has never been explored before\n4. Unique challenge of this problem is identified and solved\n\n\nWeakness:\n1. Limited novelty in the proposed method. The proposed Pseudo-Label Attack is very similar to the simple two-stage baseline. Also, the warm-up attack has also been explored in the previous work [1]. Meanwhile, the performance improvement above the simple two-stage baseline is not significant.\n\n[1] Liu, Chen, et al. \"On the loss landscape of adversarial training: Identifying challenges and how to overcome them.\" Advances in Neural Information Processing Systems 33 (2020): 21476-21487.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "C8dUB90z2or", "reviewer": "Reviewer_gLqj", "summary": "This paper focuses on how to make adversarial training(AT) applicable in a new setting where complementary labels (CL) instead of ground-truth labels are given for AT. The authors claim that the main obstacles for CL-based AT are intractable adversarial optimization and low-quality adversarial examples. Based on this, the authors propose to solve the problems with warm-up attack and pseudo-label attack. Experiment results show that  the proposed method successfully build robust models in CL setting while many baselines fail to get a robust model.\n\n", "questions": "I am still not understand why it is necessary to introduce CL into AT to increase the difficulty of AT. As discussed above, why a nosied dataset for AT is not considered? I would be really appreciate if the authors can explain more why use CL to make the supervision imperfect. What is the advantage of robust model trained from CL-based AT since it performs worse than models trained with normal AT?", "limitations": "The authors have addressed the limitations and potential negative societal impacts.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: the proposed method is neat and reasonable. The authors first analyze the reasons why AT fails in CL setting and then design corresponding solutions to mitigate the problems. \n\nWeakness: \n\n1. I am not quite agree with the setting proposed by the authors. The AT with complementary labels considers if there is no perfect supervision data for training a robust model. However, the authors did not make it clear and reasonable that why we should consider AT in such a setting. I admit that exploring the performance of AT in noised data might be necessary and practical, but exploring the performance of AT in CL setting seems to make it unnecessarily harder for adversarial training. It can be more reasonable if the authors can demonstrate their CL-based AT performs better than vanilla AT when the training data is noised, instead of first using CL to make the supervision imperfect and then try to conduct AT under imperfect supervision.\n2. Consequently, the robustness trained under CL setting does no lead to better robustness mostly because of the imperfect supervision as shown in the experiments. For most cases vanilla AT under standard setting outperforms the proposed methods in CL setting in Table 1. Though such unfair setting provides vanilla AT advantage, I still think the proposed setting is not reasonable. To better demonstrate the effectiveness, a noised dataset for AT may be considered and the authors can compare the performance on such a dataset between vanilla AT and their CL-based AT method.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept