# Adversarial Training with Complementary Labels: On the Benefit of Gradually Informative Attacks

arXiv: https://arxiv.org/abs/2211.00269 · HTML: https://mlsanity.com/paper/2211.00269/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 45 references that are in the map.
- First posted on arXiv 1 Nov 2022.

## Builds on (most cited first, 30 of 36)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Overfitting in adversarially robust deep learning](https://mlsanity.com/paper/2002.11569/) (2020)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Unlabeled Data Improves Adversarial Robustness](https://mlsanity.com/paper/1905.13736/) (2019)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Understanding and Improving Fast Adversarial Training](https://mlsanity.com/paper/2007.02617/) (2020)
- [Bag of Tricks for Adversarial Training](https://mlsanity.com/paper/2010.00467/) (2020)
- [Geometry-aware Instance-reweighted Adversarial Training](https://mlsanity.com/paper/2010.01736/) (2020)
- [Adversarial Training and Robustness for Multiple Perturbations](https://mlsanity.com/paper/1904.13000/) (2019)
- [Are Labels Required for Improving Adversarial Robustness?](https://mlsanity.com/paper/1905.13725/) (2019)
- [A Closer Look at Deep Learning Heuristics: Learning rate restarts, Warmup and Distillation](https://mlsanity.com/paper/1810.13243/) (2018)
- [Learning with Biased Complementary Labels](https://mlsanity.com/paper/1711.09535/) (2017)
- [Curriculum Adversarial Training](https://mlsanity.com/paper/1805.04807/) (2018)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Adversarial Robustness Against the Union of Multiple Perturbation Models](https://mlsanity.com/paper/1909.04068/) (2019)
- [Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization](https://mlsanity.com/paper/2112.12376/) (2021)
- [Generalizable Adversarial Training via Spectral Normalization](https://mlsanity.com/paper/1811.07457/) (2018)
- [Adversarially robust transfer learning](https://mlsanity.com/paper/1905.08232/) (2019)
- [On the Loss Landscape of Adversarial Training: Identifying Challenges and How to Overcome Them](https://mlsanity.com/paper/2006.08403/) (2020)
- [Complementary-Label Learning for Arbitrary Losses and Models](https://mlsanity.com/paper/1810.04327/) (2018)
- [Exploring Memorization in Adversarial Training](https://mlsanity.com/paper/2106.01606/) (2021)
- [Learning with Multiple Complementary Labels](https://mlsanity.com/paper/1912.12927/) (2019)
- [Robustness to Adversarial Perturbations in Learning from Incomplete Data](https://mlsanity.com/paper/1905.13021/) (2019)
- [How benign is benign overfitting?](https://mlsanity.com/paper/2007.04028/) (2020)

## Built on by (most cited first, 4 of 4)

- [Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical](https://mlsanity.com/paper/2311.15502/) (2023)
- [Boosting Single Positive Multi-label Classification with Generalized Robust Loss](https://mlsanity.com/paper/2405.03501/) (2024)
- [Improving Adversarial Robustness via Phase and Amplitude-aware Prompting](https://mlsanity.com/paper/2502.03758/) (2025)
- [Recent advances in weakly supervised learning: New supervision paradigms, assumption relaxations, and practical solutions](https://mlsanity.com/paper/2608.06896/) (2026)

## Abstract (arXiv)

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.