Understanding and Increasing Efficiency of Frank-Wolfe Adversarial
  Training
  Deep neural networks are easily fooled by small perturbations known as
adversarial attacks. Adversarial Training (AT) is a technique that
approximately solves a robust optimization problem to minimize the worst-case
loss and is widely regarded as the most effective defense. Due to the high
computation time for generating strong adversarial examples in the AT process,
single-step approaches have been proposed to reduce training time. However,
these methods suffer from catastrophic overfitting where adversarial accuracy
drops during training, and although improvements have been proposed, they
increase training time and robustness is far from that of multi-step AT. We
develop a theoretical framework for adversarial training with FW optimization
(FW-AT) that reveals a geometric connection between the loss landscape and the
$\ell_2$ distortion of $\ell_\infty$ FW attacks. We analytically show that high
distortion of FW attacks is equivalent to small gradient variation along the
attack path. It is then experimentally demonstrated on various deep neural
network architectures that $\ell_\infty$ attacks against robust models achieve
near maximal distortion, while standard networks have lower distortion. It is
experimentally shown that catastrophic overfitting is strongly correlated with
low distortion of FW attacks. This mathematical transparency differentiates FW
from Projected Gradient Descent (PGD) optimization. To demonstrate the utility
of our theoretical framework we develop FW-AT-Adapt, a novel adversarial
training algorithm which uses a simple distortion measure to adapt the number
of attack steps during training to increase efficiency without compromising
robustness. FW-AT-Adapt provides training time on par with single-step fast AT
methods and closes the gap between fast AT methods and multi-step PGD-AT with
minimal loss in adversarial accuracy in white-box and black-box settings.
