Two Heads are Better than One: Towards Better Adversarial Robustness by
  Combining Transduction and Rejection
Nils Palumbo Yang Guo Xi Wu Jiefeng Chen Yingyu Liang Somesh Jha
Both transduction and rejection have emerged as important techniques for
defending against adversarial perturbations. A recent work by Tram\`er showed
that, in the rejection-only case (no transduction), a strong rejection-solution
can be turned into a strong (but computationally inefficient) non-rejection
solution. This detector-to-classifier reduction has been mostly applied to give
evidence that certain claims of strong selective-model solutions are
susceptible, leaving the benefits of rejection unclear. On the other hand, a
recent work by Goldwasser et al. showed that rejection combined with
transduction can give provable guarantees (for certain problems) that cannot be
achieved otherwise. Nevertheless, under recent strong adversarial attacks
(GMSA, which has been shown to be much more effective than AutoAttack against
transduction), Goldwasser et al.'s work was shown to have low performance in a
practical deep-learning setting. In this paper, we take a step towards
realizing the promise of transduction+rejection in more realistic scenarios.
Theoretically, we show that a novel application of Tram\`er's
classifier-to-detector technique in the transductive setting can give
significantly improved sample-complexity for robust generalization. While our
theoretical construction is computationally inefficient, it guides us to
identify an efficient transductive algorithm to learn a selective model.
Extensive experiments using state of the art attacks (AutoAttack, GMSA) show
that our solutions provide significantly better robust accuracy.