  Recent studies demonstrate that deep networks, even robustified by the
state-of-the-art adversarial training (AT), still suffer from large robust
generalization gaps, in addition to the much more expensive training costs than
standard training. In this paper, we investigate this intriguing problem from a
new perspective, i.e., injecting appropriate forms of sparsity during
adversarial training. We introduce two alternatives for sparse adversarial
training: (i) static sparsity, by leveraging recent results from the lottery
ticket hypothesis to identify critical sparse subnetworks arising from the
early training; (ii) dynamic sparsity, by allowing the sparse subnetwork to
adaptively adjust its connectivity pattern (while sticking to the same sparsity
ratio) throughout training. We find both static and dynamic sparse methods to
yield win-win: substantially shrinking the robust generalization gap and
alleviating the robust overfitting, meanwhile significantly saving training and
inference FLOPs. Extensive experiments validate our proposals with multiple
network architectures on diverse datasets, including CIFAR-10/100 and
Tiny-ImageNet. For example, our methods reduce robust generalization gap and
overfitting by 34.44% and 4.02%, with comparable robust/standard accuracy
boosts and 87.83%/87.82% training/inference FLOPs savings on CIFAR-100 with
ResNet-18. Besides, our approaches can be organically combined with existing
regularizers, establishing new state-of-the-art results in AT. Codes are
available in https://github.com/VITA-Group/Sparsity-Win-Robust-Generalization.
