Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.

To 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.

Based 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.
strengths_and_weaknesses: Pros:

* In general, this paper is well-written and easy to follow. The motivation is clear. The studied setting is both significant and challenging.
* 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.
* The proposed techniques including warm-up and pseudo-label are proposed based on the theoretical and empirical analysis, which are simple yet natural.
* 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.

Cons:

* 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.
* 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.
questions: 1.Please provide empirical evaluation of pseudo labels.
2.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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.


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. 

Weakness: 

1. 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.
2. 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.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. The writing is good and easy to follow
2. Thorough theoretical analysis is provided
3. The target problem has never been explored before
4. Unique challenge of this problem is identified and solved


Weakness:
1. 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.

[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.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength

1.	This work first proposed adversarial training together with complementary labels. From my best understanding, this is the first work to study this problem.

2.	The motivation of studying adversarial training in imperfect data scenario is strong and practical. 

3.	Algorithm 1 is clear and simple to follow.

Weakness

1.	In 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.

2.	The 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.

3.	Figure 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?



[a] Understanding the Interaction of Adversarial Training with Noisy Labels
[b] A closer look at deep learning heuristics: Learning rate restarts, warmup and distillation
[c] On the Loss Landscape of Adversarial Training: Identifying Challenges and How to Overcome Them
[d] Unlabeled Data Improves Adversarial Robustness

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.
review_title: null

Meta-review: metareview: This paper focuses on a significant and challenging problem: adversarial training (AT)  with complementary labels. A naive combination of AT with existing complementary learning techniques fails to achieve good performance. The authors conduct both theoretical and empirical analyses of this phenomenon and identified two key challenges including intractable adversarial optimization and low-quality adversarial examples. Furthermore, two attack approaches are proposed accordingly: a warm-up attack to ease the adversarial optimization and a pseudo-label attack to improve the adversarial example quality. All reviewers recognize the effectiveness of the proposed method through experimental evaluations.  During the discussion, the authors also successfully addressed the reviewers' questions on the problem settings, the novelty of the pseudo-label attack, warm-up strategies, etc.  Based on the positive reviews and thorough discussions, we recommend the acceptance of the paper.

confidence: Certain
Decision: Accept