summaries: The paper studies the phenomenon of trade-off between robust and standard accuracies that is usually observed in adversarial training. Many existing studies try to understand this trade-off and show that it is unavoidable. In contrast, this work shows that under a sensible definition of adversarial risk, there is no trade-off between standard accuracy and sensible adversarial accuracy. It is shown that Bayes optimal classifier has optimal standard and sensible adversarial accuracies. The authors then go on to propose a new adversarial training algorithm which tries to minimize the sensible adversarial risk. Experimental results show that models learned through the proposed technique have high adversarial and standard accuracies.  Motivated from the so-called trade-off between robustness and standard accuracy in the existing adversarial learning, this paper has proposed a "sensible" adversarial example framework without losing  significantly  performance in natural accuracy. Some toy examples have been presented, showing its reasonableness of the model. The proposed algorithm looks very simple, but it appears that it could be effective through some experiments on two data sets. The paper proposes the notion of a "sensible" adversary that does not perturb data points on which the Bayes-optimal classifier is incorrect. The authors then provide theory showing that minimizing robust risk against such a sensible adversary yields the Bayes-optimal classifier, which addresses the question about standard vs. robust risk posed in prior work. On the experimental side, the authors then introduce a simple yet effective variation of adversarial training / robust optimization. Instead of maximizing the loss over the perturbation set, the proposed variant stops as soon as the loss exceeds a certain threshold. This can be seen as a variant of gradient clipping that reduces the influence of examples with a very high loss. The authors show that their modification yields an 8 - 9% improvement in robust accuracy on CIFAR-10, which gives state-of-the-art performance.
abstractText: The trade-off between robustness and standard accuracy has been consistently reported in the machine learning literature. Although the problem has been widely studied to understand and explain this trade-off, the problem seems to remain as an open problem. In this paper, motivated by the fact that the high dimensional distribution is poorly represented by limited data samples, we introduce sensible adversarial learning and demonstrate the synergistic effect between pursuits of natural accuracy and robustness. Specifically, we define a sensible adversary which is useful for learning a defense model and keeping a high natural accuracy simultaneously. We theoretically establish that the Bayes rule is the most robust multi-class classifier with the 0-1 loss under sensible adversarial learning. We propose a novel and efficient algorithm that trains a robust model with sensible adversarial examples, without a significant drop in natural accuracy. Our model on CIFAR10 yields state-of-the-art results against various attacks with perturbations restricted to `∞ with = 8/255, e.g., the robust accuracy 57.23% against PGD attacks as well as the natural accuracy 91.51%.
references.authors: Battista Biggio Igino Corona Davide Maiorca Blaine Nelson Nedim Šrndić Pavel Laskov Giorgio Giacinto Fabio Roli
references.title: Evasion attacks against machine learning at test time
references.venue: In Joint European conference on machine learning and knowledge discovery in databases,
references.authors: Sébastien Bubeck Eric Price Ilya Razenshteyn
references.title: Adversarial examples from computational constraints
references.venue: arXiv preprint arXiv:1805.10204,
references.authors: Gavin Weiguang Ding Kry Yik Chau Lui Xiaomeng Jin Luyu Wang Ruitong Huang
references.title: On the sensitivity of adversarial robustness to input data distributions
references.venue: arXiv preprint arXiv:1902.08336,
references.authors: Gavin Weiguang Ding Luyu Wang Xiaomeng Jin
references.title: AdverTorch v0.1: An adversarial robustness toolbox based on pytorch
references.venue: arXiv preprint arXiv:1902.07623,
references.authors: Yinpeng Dong Fangzhou Liao Tianyu Pang Hang Su Jun Zhu Xiaolin Hu Jianguo Li
references.title: Boosting adversarial attacks with momentum
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Ian J Goodfellow Jonathon Shlens Christian Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: arXiv preprint arXiv:1412.6572,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Alex Krizhevsky Geoffrey Hinton
references.title: Learning multiple layers of features from tiny images
references.venue: Technical report, Citeseer,
references.authors: Alexey Kurakin Ian Goodfellow Samy Bengio
references.title: Adversarial examples in the physical world
references.venue: arXiv preprint arXiv:1607.02533,
references.authors: Alexey Kurakin Ian Goodfellow Samy Bengio
references.title: Adversarial machine learning at scale
references.venue: arXiv preprint arXiv:1611.01236,
references.authors: Yann LeCun Corinna Cortes CJ Burges
references.title: Mnist handwritten digit database
references.venue: AT&T Labs [Online]. Available: http://yann. lecun. com/exdb/mnist,
references.authors: Aleksander Madry Aleksandar Makelov Ludwig Schmidt Dimitris Tsipras Adrian Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: arXiv preprint arXiv:1706.06083,
references.authors: Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi Pascal Frossard
references.title: Deepfool: a simple and accurate method to fool deep neural networks
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Maria-Irina Nicolae Mathieu Sinn Minh Ngoc Tran Ambrish Rawat Martin Wistuba Valentina Zantedeschi Nathalie Baracaldo Bryant Chen Heiko Ludwig Ian Molloy Ben Edwards
references.title: Adversarial robustness toolbox v0.8.0
references.venue: CoRR, 1807.01069,
references.authors: Nicolas Papernot Patrick McDaniel Somesh Jha Matt Fredrikson Z Berkay Celik Ananthram Swami
references.title: The limitations of deep learning in adversarial settings
references.venue: IEEE European Symposium on Security and Privacy (EuroS&P),
references.authors: Jonas Rauber Wieland Brendel Matthias Bethge
references.title: Foolbox v0.8.0: A python toolbox to benchmark the robustness of machine learning models
references.venue: CoRR, abs/1707.04131,
references.authors: Dale Schuurmans Ruitong Huang Bing Xu Csaba Szepesvari
references.title: Learning with a strong adversary
references.venue: arXiv preprint arXiv:1511.03034,
references.authors: Ludwig Schmidt Shibani Santurkar Dimitris Tsipras Kunal Talwar Aleksander Madry
references.title: Adversarially robust generalization requires more data
references.venue: In Advances in Neural Information Processing Systems,
references.authors: David Stutz Matthias Hein Bernt Schiele
references.title: Disentangling adversarial robustness and generalization
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Dong Su Huan Zhang Hongge Chen Jinfeng Yi Pin-Yu Chen Yupeng Gao
references.title: Is robustness the cost of accuracy?–a comprehensive study on the robustness of 18 deep image classification models
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV),
references.authors: Arun Sai Suggala Adarsh Prasad Vaishnavh Nagarajan Pradeep Ravikumar
references.title: Revisiting adversarial risk
references.venue: arXiv preprint arXiv:1806.02924,
references.authors: Christian Szegedy Wojciech Zaremba Ilya Sutskever Joan Bruna Dumitru Erhan Ian Goodfellow Rob Fergus
references.title: Intriguing properties of neural networks
references.venue: arXiv preprint arXiv:1312.6199,
references.authors: Pedro Tabacof Eduardo Valle
references.title: Exploring the space of adversarial images
references.venue: In 2016 International Joint Conference on Neural Networks (IJCNN),
references.authors: Dimitris Tsipras Shibani Santurkar Logan Engstrom Alexander Turner Aleksander Madry
references.title: Robustness may be at odds with accuracy
references.authors: Dong Yin Kannan Ramchandran Peter Bartlett
references.title: Rademacher complexity for adversarially robust generalization
references.venue: arXiv preprint arXiv:1810.11914,
references.authors: Hongyang Zhang Yaodong Yu Jiantao Jiao Eric P Xing Laurent El Ghaoui Michael I Jordan
references.title: Theoretically principled trade-off between robustness and accuracy
references.authors: Bubeck
references.title: 2018) in that a robust model exists, but we search for an efficient algorithm to estimate a robust model in a reasonable time. Su et al. (2018) compared various naturally trained models on ImageNet, and found that the trade-off varies among different model architectures. Also, they empirically discovered that more accurate models tend to be less robust when the models are trained with natural examples
references.venue: Stutz et al
references.authors: Su
references.title: 2018) that accurate models tend to be less robust when the models are trained with natural examples. On the other hand, although not displayed, the plots corresponding to c = 0.9 are essentially similar to the plots in the second low. This implies even for large c, our method is not like natural learning; The models trained with c = 0.9 still have larger natural and adversarial margins
references.authors: Zhang
references.title: 2019) investigate the Bayes decision boundary to resolve the trade-off problem
references.authors: Zhang
references.title: 2019) for MNIST and CIFAR10
references.venue: The results are in Table 6 and Table
references.authors: Zhang
references.title: We note that for each dataset, the TRADE and SENSE model share
sections.heading: 1 INTRODUCTION
sections.text: With many impressive successes of deep learning, there are a multitude of applications of deep neural networks (DNNs) that permeate in our everyday life. As DNNs are applied in securitycritical systems such as malware detection, face identification, and autonomous driving, robustness of DNNs against adversarial attacks, i.e., the intently perturbed inputs to fool the system, has become an important research topic (Szegedy et al., 2013; Papernot et al., 2016; Biggio et al., 2013).
  One of the most widely studied classes of adversarial perturbations is `p-norm constrained adversarial perturbations (Szegedy et al., 2013). Madry et al. (2017) formalize the adversarial learning against this class of perturbations as a minimization problem of adversarial risk defined in a following way. Let (X, y) ∈ X × Y be from some unknown distribution PX,Y . Given a loss function ` : Y × Y → R and a constraint constant > 0, the adversarial robust risk is
  Rrob(f) = EX,Y [
  max ‖δ‖p≤
  `(f(X + δ), y) ] . (1)
  Many adversarial learning methods can be interpreted as empirical minimization of (1) (Goodfellow et al., 2014; Kurakin et al., 2016b; Ruitong Huang & Szepesvari, 2015; Madry et al., 2017). For this optimization problem, Madry et al. (2017) propose to train a robust model with the augmented data generated by the projected gradient descent method (PGD). On this adversarial training, they make two important observations. First, it costs natural accuracy. A network trained with adversarial examples tends to have a lower natural accuracy than a naturally trained network. This trade-off is observed even with a small training . Second, the adversarial training requires a larger model capacity than the natural training does. If the model capacity is only sufficient for the natural learning, the adversarial training can converge to a constant function.
  For a large , the optimization problem of (1) itself may pose the trade-off. For instance, Tsipras et al. (2018) show an example of an inherent tension between pursuits of accuracy and robustness when is large enough to change the true class. For a smaller , however, the formulation in (1) does not explicitly pose any conflict between the pursuit of robustness and accuracy. Note that Rrob(f) is an upper bound of the standard risk of f . A perfectly robust model f with Rrob(f) = 0 is also perfectly accurate for natural learning. If the perfect classifier exists in a given model class, the trade-off may be caused by the large sample complexity of adversarially robust generalization
  (Schmidt et al., 2018; Yin et al., 2018; Stutz et al., 2019). Without sufficiently large amount of data, the empirical minimization of (1) may result in a large standard risk by converging to a model of a poor robust risk. On the other hand, if robust learning converges to a constant function, it cannot achieve natural accuracy. In this sense, to resolve the trade-off problem, we may need to deal with the increased requirement on the model capacity.
  In this paper, we propose a novel framework, called sensible adversary, in order to overcome the trade-off between natural accuracy and robustness. In particular, we restrict adversarial perturbations not to cross the Bayes decision boundary besides the -ball constraint, so that the perturbation ball is adaptively modified for every single data point. Our main contributions are:
  • Under the framework of sensible adversary, the pursuit of robustness and accuracy given an enough model capacity can align with each other, i.e., there is no trade-off. We theoretically establish the Bayes rule is most robust against the sensible adversary. If the Bayes decision boundary can be far from data manifolds at least by , our pursuit of sensible robustness does not cost any adversarial robust risk.
  • We propose an efficient algorithm for sensible adversarial training , which utilizes sensible adversaries in the absence of the true Bayes rule. This sensible adversarial training enjoys robustness without a significant drop of natural accuracy. Furthermore, the algorithm is not sensitive to the model capacity. When insufficient model capacity is given, our algorithm does not collapse to a constant function. Instead, it trains a model as robust as possible.
  • We experimentally demonstrate that sensible adversarial training enables to stably learn a robust and accurate model. In particular, on CIFAR10, we achieve 91.51% natural test accuracy and 57.23% robust test accuracy against `∞ PGD attacks constrained to = 8/255. To the best of our knowledge, there is no approaches known to achieve natural accuracy more than 90%, while achieving more than 55% of robust accuracy against PGD attacks of = 8/255. Moreover, no previous approaches pursuing robustness against this attack achieved the natural accuracy more than .
sections.heading: 1.1 RELATED WORK
sections.text: Madry et al. (2017) formalize adversarial learning as a mini-max problem given perturbation restriction, and theoretically and empirically established the feasibility of the optimization. Our sensible adversary redefines the set of perturbation in the inner maximization problem on which their theoretical result is directly applicable. Tsipras et al. (2018) investigate the possible source of robust trade-off. The key idea is that when there are features that are useful for natural classification but vulnerable to adversarial perturbations, a robust model would abandon these features because otherwise all of these features can adversarially move to promote incorrect prediction. Our work explores the possibility of learning a robust model while not allowing such collective adversarial migration. While a class change by adversarial examples typically has been prevented by using a small , Suggala et al. (2018) explicitly ignore an adversarial perturbation that crosses the decision boundary of a Bayes rule. Zhang et al. (2019) also investigate the Bayes decision boundary to resolve the trade-off problem. They search for a model f having a small weighted sum of the natural risk and a probability that an adversarial example can cross the decision boundary of f . Gilmer et al. (2018) show that in high dimensional setting, even small test error can imply the existence of adversarial examples for most of data points. Our effort to prioritize natural accuracy to find a robust model is consistent to the view in Gilmer et al. (2018). More related work will be presented in Appendix A.
sections.heading: 1.2 NOTATION
sections.text: Let F denote the class of functions represented by DNNs with a fixed architecture. An optimal robust model w.r.t. PX,Y is denoted by frob = arg minf∈F Rrob(f). Denote the standard risk w.r.t PX,Y by Rstd(f) = EX,Y [`(f(X), y)] and its optimal natural model by fstd = arg minf∈F Rstd(f). Let P̃X,Y = PX,Y |X̃×Y denote a restricted distribution of PX,Y on a subset X̃ × Y ⊂ X × Y . Likewise, denote the standard risk w.r.t P̃X,Y by R̃std(f) and the robust risk w.r.t P̃X,Y by R̃rob(f). For a set A, the -neighborhood in `p-norm is defined as B(A, ) = {y|‖y − x‖p ≤ , x ∈ A}, and the interior is denoted by int(A). Denote the -
  neighborhood of the decision boundary of f by DB(f, ) = {x ∣∣ ∃x′ ∈ B(x, ) s.t. f(x) 6= f(x′)}.
  Let p̂f,y(x) denote the predicted probability of the label of x being y by a model f .
sections.heading: 2 ADVERSARIAL LEARNING MAY HELP STANDARD LEARNING
sections.text: In this section, we use a toy example to investigate the synergistic effect between the pursuit of robustness and natural accuracy.
  Example: We can easily find an example of trade-off wherever an -ball attack can cross the manifold boundary between classes. For example, consider a two-dimensional random vector X = (X1, X2) on X = (0, 1) × (0, 1) with a binary class Y ∼ Ber(p), where p > 0.5. Let the conditional distribution be (X1, X2)|Y = 0 ∼ Unif((0, 12 ) × (0, 1)) and (X1, X2)|Y = 1 ∼ Unif(( 12 , 1)×(0, 1)). Then the Bayes Rule is f
  B(x) = sign(x1−0.5), and it is a perfect classifier, in thatRstd(fB) = 0 with ` as the 0-1 loss. If p > 0.5, the robust classifier against -ball attacks is frob(x) = sign(x1−(0.5− )). Its decision boundary is deviated by− from that of the Bayes rule, and this deviation costs natural accuracy byRstd(frob)−Rstd(f) = (1− p) . However, when the data points reside in a high-dimensional space, the samples are too sparse to represent the underlying true distribution. To take this phenomenon into account, consider a distribution P̃X,Y = PX,Y |X̃×Y on a subset X̃ × Y ⊂ X × Y . Assume that we only observe data generated from P̃X,Y , and the training and test sets do not provide any information on X̃ c × Y . Now by applying this support restriction to the example above, we demonstrate how adversarial learning dramatically changes from harming to benefiting natural accuracy.
  The Cheese hole distribution: For the above example, we restrict the support on X̃ = ∪3i=1 ∪3j=1 Hij ,whereHij = ((α2 , 3α 2 )+2α(i−1))×(( α 2 , 3α 2 )+2α(j−1)), α = 1 6 , and j = 1, 2, 3. Therefore the sampling support X̃ comprises of nine small squares equally spaced by α. This is illustrated in Figure 1 (a). Among all classifiers which predict the same as fB on X̃ , the worst one, denoted by f̃B∗, predicts exact opposite on x ∈ X̃ c as illustrated in Figure 1 (b). For this worst case, the true standard risk w.r.t PX,Y is 34 , although the standard risk w.r.t. P̃X,Y is zero.
  We argue that pursuing robustness can mitigate this discrepancy. Among minimizers of R̃rob, let f̃∗rob be the worst classifier in that it predicts incorrectly outside X̃ as depicted in Figure 1 (c). On B(X̃ , ), f̃∗rob should correctly classify, except on A = {(x1, x2)|0.5− ≤ x1 ≤ 0.5} ∩ B(X̃ , ). In this situation, the inaccuracy of f̃∗rob is compensated by its increased accuracy on B(X̃ , ) \ A . Moreover, the composition ofRrob(f̃B∗) is particularly interesting, and it is easy to show that
  Rrob(f̃B∗) = P ( f̃B∗(Y ) = X,X ∈ DB(f̃B∗, ) ) + 3/4,
  where 3/4 is from the standard inaccuracy on X̃ c. The major part of Rrob(f̃B∗) comes from the inaccuracy of f̃B∗ outside of the sampling support X̃ . Therefore by simply reducing this inaccuracy on X̃ c, we can lower the robust risk by 3/4. Another interesting observation is that B = {(x1, x2)|0.5 − < x1 < 0.5 + } is the only area where the Bayes rule fB has its robust risk. Note that Rrob(fB) = P(X ∈ B , fB(X) = Y ) = 2 which is greater than the optimal robust risk. The reason why fB is not most robust is simply because it is accurate on B . This prevents fB from being a robust function under the current adversarial robustness framework.
  These observations have two implications. First, the robust pursuit can help to increase natural accuracy outside of X̃ where the samples are poorly representative. Second, by accurately correcting the model outside of X̃ in a standard sense, the robust risk can be significantly decreased. This is where the pursuit of robustness and accuracy coincides.
  Toward respecting the original data structure: What if we regard the adversarial robust risk near the class border as reasonable gullibility? This corresponds to pursuit of robustness only against adversarial examples which do not cross between the class manifolds, i.e., as long as this does not harm the natural accuracy on X̃ . We call this robustness as sensible robustness, which respects the structure represented by data. In this example, the sensible robustness can increase both robustness and natural accuracy. Let f̃s∗rob denote the worst case sensibly robust classifier w.r.t P̃X,Y . The
  decision boundary of f̃s∗ should not deviate to the left on B(X̃ , ) no matter how large is, as depicted in Figure 1 (d). Note that when ≥ α/2, f̃∗rob is the unique minimizer of R̃rob(f) as B(X̃ , ) covers X .
sections.heading: 3 SENSIBLE ADVERSARIAL ROBUSTNESS
sections.text: In this section, we introduce a sensible adversary framework. Consider a general multi-class case with the 0-1 loss, where Y = [K]. Assume the model capacity is enough so that the Bayes rule fB ∈ F . We consider `p-norm constrained adversarial attacks, where p ∈ {0, 1, ...,∞}. Definition 1. (sensible adversarial example) For a classifier f , let Sx, (f) = {z ∈ X |‖z − x‖p ≤ , f(z) = y}. Then the sensible adversarial example of (x, y) w.r.t f is defined as
  x̃ = x, if f B(x) 6= y
  arg max z∈Sx, (fB)
  `(f(z), y), otherwise. (2)
  Definition 2. (sensible robustness) Let the sensible adversarial loss be `srob, (f, x, y) = `(f(x̃), y) where x̃ is a sensible adversarial example as defined above. Then the sensible robust risk of a model f is defined by
  Rsrob(f) = EPX,Y [ `srob, (f,X, Y ) ] = EPX,Y [ `(f(X̃), Y ) ] . (3)
  We call its minimizer as a sensibly robust model w.r.t PX,Y and denote by fsrob , i.e.,
  fsrob = arg min f∈F Rsrob(f).
  Remark 1. Intuitively, a sensible adversarial example is an adversarial example restricted not to cross the decision boundary of the Bayes rule. In addition, a sensible adversary does not perturb a data point that the Bayes rule incorrectly classifies. Therefore, it is natural to expect that pursuing sensible robustness would not cost natural accuracy, and the following theorem confirms it. Theorem 1. Let R∗std denote the minimum standard risk which is Rstd(fB). Then we have Rsrob(fB) = R∗std. Furthermore, fB is the unique minimizer ofRsrob(f) among f ∈ F . Theorem 2. Let SX, be an -ball centered at X . Then for any f ∈ F and for any set A ⊂ X \DB(fB , ),
  P ( ∃ x′ ∈ SX, s.t. fB(x′) 6= Y,X ∈ A ) ≤ P ( ∃ x′ ∈ SX, s.t. f(x′) 6= Y,X ∈ A ) .
  Remark 2. According to the Theorem 1, a sensibly robust model w.r.t PX,Y is the Bayes rule, i.e., fsrob = f B . This sensible robustness costs adversarial robustness since fB may have a larger
  Algorithm 1 Sensible adversarial training for `∞ norm restriction
  1: Input: Initialized f = fθ, c ∈ (0, 1), step number K, step sizes η1, η2, data X(0)adv = X 2: repeat 3: for i = 1, ...,m, s.t. f(x(0)i,adv) = yi 4: for k = 1, ...,K 5: x(k)i,adv ← ΠB(xi, )(η1sign(∇x`(f(x (k−1) i,adv ), yi)) +x (k−1) i,adv ), Π: the projection operator 6: if `(f, x(k)i,adv, yi) > log 1 c 7: (sensible reversion) x(K)i,adv = x (k−1) i,adv 8: break 9: θ ← θ − η2 ∑m i=1∇θ`(f, x (K) i,adv, yi)/m
  10: until training converged
  adversarial robust risk compared with frob, a direct minimizer of (1). However, Theorem 2 shows fB is equally or even more robust than frob except on a certain area. In particular, Theorem 2 shows that fB is the most robust model except on DB(fB , ). Therefore, fB is most robust almost everywhere if the decision boundary of fB can lie outside of B(X , ), so that X \DB(fB , ) = X . For example, this happens when each class has its own support apart from each other by at least 2 .
  The next theorem shows that even when we only have data from P̃X,Y restricted on X̃ × Y , we can find fsrob, the optimal function w.r.t. PX,Y .
  Theorem 3. Let A = { f ∈ F ∣∣ P̃(f(x) = fB(x), ∀x ∈ SX, (fB)) = 1} and R̃srob(f) = EP̃X,Y [` s rob, (f,X, Y )]. Then, for any > 0, R̃srob(f) is only minimized by any f ∈ A . Furthermore, if B(X̃ , ) ⊃ X , fB is the unique minimizer of R̃srob(f). Remark 3. It is interesting to compare our work with that of Suggala et al. (2018). We notice there are some critical differences between these two works. Given Y ∈ {−1, 1}, Suggala et al. (2018) define an adversarial risk as
  Radv(f) = E[ max g(x)=g(x+δ),‖δ‖≤ `(f(x+ δx), g(x))− `(f(x), g(x))].
  Unlike our definition of sensible adversary, if g is a Bayes rule fB , their adversary tries to increase the loss w.r.t. not y but a deterministic function of x. Therefore, for making fB being an optimal robust model, their objective should always have an additional term, e.g., Rnat(f) + λRadv(f) for 0 < λ < ∞ because an f s.t. f(x) 6= g(x) w.p. 1 can minimize Radv(f). Unlike their approach, our sensible adversarial risk (3) can alone be optimized making the Bayes rule as the optimal model.
sections.heading: 4 ALGORITHM
sections.text: A transition from theory to algorithm poses two main challenges. First, the 0-1 loss function in the theory is hard to optimize. Therefore, as a common practice, we use the cross-entropy loss. Second, fB on the entire space is practically unavailable. We note that a model that performs well on natural data can be a nice approximation of fB on the restricted support X̃ × Y . Therefore, we generalize sensible adversary in (2) to utilize a general loss function and a reference model that substitutes fB . Definition 3. (generalized sensible adversarial example) Consider a loss function `. For a classifier f and c ∈ (0, 1], let Sx, (f) = {z ∈ X |‖z− x‖p ≤ , `(f(z), y) ≤ log 1c} ∪ {x}. Then given a reference model fr, the sensible adversarial example of f for (x, y) is defined as
  x̃|fr = x, if fr(x) 6= yarg max z∈Sx, (fr) `(f(z), y), otherwise. (4)
  If ` is the cross-entropy loss, the condition `(fr(x), y) ≤ log 1c is equivalent to p̂fr,y(x) ≥ c. In binary case with c = 0.5, this requires the perturbed examples not to cross the decision boundary of fr, and for general c, not to reach to a vicinity of the boundary.
  In our algorithm we set fr as a naturally trained model or a current model. Given a fr, the implementation of sensible adversarial attacks is straightforward. For a correctly classified natural example by fr, we add perturbations in the similar way to the PGD method (Madry et al., 2017). The difference is that during the K-step of PGD iterations, once the loss of a currently generated example exceeds log 1c , we reverse it back to the previous step and break the iteration. This requires no additional forward- or backward-propagation, compared with the PGD method. The proposed algorithm is in Algorithm 1 for the `∞-norm and in Algorithm 2 in Appendix C for the other `p-norms.
  The definition of the sensible adversary in (4) divides the data into three subsets: Afr = {x|fr(x) 6= y or Sx, (fr) = {x}}, Bfr = {x|Sx, (fr) 6= Sx, , Sx, (fr) 6= {x}}, and Cfr = X \ (Af ∪ Bf ). Therefore, our algorithms generate a sensible adversarial example x̃s|fr=f in three different ways: (1) x̃s = x for x ∈ Af , (2) x̃s 6= x̃p for x ∈ Bf , and (3) x̃s = x̃p for x ∈ Cf , where x̃p is a full K-step PGD attack. Therefore, sensible adversarial training inherently involves a set selection mechanism. The sensible adversarial loss `s(f, x, y) can be written as
  `(f, x, y)1x∈Af + `(f, x̃ s, y)1x∈Bf + `(f, x̃ p, y)1x∈Cf
  =`(f, x, y)1`(f,x,y)>log 1c + `(f, x̃ s, y)1x̃p 6=x̃s, `(f,x,,y)≤log 1c + `(f, x̃ p, y)1`(f,x̃p,y)≤log 1c . (5)
  When c ≥ 0.5, this optimization problem has a strong motivation to increase |Cf |, i.e., the number of sensible adversarial attacks that are identical to full PGD attacks. BecauseAf = {x|`(f(x), y) > log 1c} for c ≥ 0.5, the loss on the natural stage Af is always greater than the loss of the sensibly reversed stage Bf and the full PGD stage Cf . Furthermore, the loss for x ∈ Bf is always approximately log 1c by adaptive sensible perturbations. Therefore, paradoxically, the smallest loss is only achievable by full PGD examples. In other words, sensible adversarial training penalizes when x 6∈ Cf . We note that the optimization problem has a smooth landscape; Although the data points may jump around between Af , Bf , and Cf , there is no obvious discontinuity in the loss. Therefore, during the training, `s(f, x, y) smoothly slides down, making both `(f, x, y) and `(f, x̃p, y) smaller than log 1c . This enables to learn a naturally and adversarially accurate model. More discussion on the stability of our algorithms are presented in Appendix D.
sections.heading: 5 EXPERIMENTS
sections.heading: 5.1 EXPERIMENT 1: ROBUSTNESS AGAINST -BALL ATTACKS
sections.text: CIFAR10 We train WideResNet-34-10 (He et al., 2016) with sensible adversarial examples of = 8/255 and c = 0.7 with the step number K = 10 and size η1 = /5. We attack our model with various white-box attacks with perturbations restricted to `∞ with = 8/255. We compare the performance with TRADE using the same architecture (Zhang et al., 2019), which is know to be robust and accurate. The result is in Table 1. Our model achieves 91.51% natural accuracy. This is 3.7% drop in natural accuracy from 95.2%, which is an accuracy that a naturally trained model can achieve (Madry et al., 2017). With this architecture, Madry et al. (2017) achieve 47.04% robust
  Table 3: MNIST: test results of our models on natural examples and `∞ based attacks ( = 0.3).
  Defence model Natural PGD500 C&W40
  SENSE 99.51 91.74 96.02
  TRADE 99.48 93.30 96.90
  Figure 2: The natural and robust accuracies of our models for the varying parameter c.
  accuracy against PGD20 attacks and 87.3% natural accuracy. As a black-box attack, we try transfer attacks between the TRADE and SENSE model by the `∞ based PGD and MIFGSM, which are known to be effective for transfer attack ( = 8/255). We obtain adversarial examples by applying PGD and MIFGSM on a generating model, and then use the examples to attack a defense model. The result is in Table 2. Overall we observe that our model outperforms both the TRADE and Madry model. In particular, sensible adversary achieves more than 55% of robust accuracy against PGD attacks of = 8/255. This performance is consistent to the test margin distribution in Figure 8, and this is discussed in detail in Appendix E. For PGD100, we conduct random 20 restarts and count only the worst case. The step number 100 and step size 2/255 of the PGD attacks are justified by the plot in Figure 11 in Appendix H.
  MNIST We consider a CNN model with three convolutional layers followed by a fully connected linear layer, which is the same architecture in (Zhang et al., 2019). We train an MNIST model with sensible adversarial examples of = 0.3 and c = 0.5 with the step number K = 10 and size η1 = 0.05. The robust test result in Table 3 shows the comparable performance of our model. The step size of the PGD500 attack is 0.01, and the serenity check on the PGD attack is in Appendix H. We conduct 100 random restarts and count only the worst case for each test example.
sections.heading: 5.2 EXPERIMENT 2: SENSITIVITY ANALYSIS
sections.text: MNIST: We perform the sensibility analysis to understand the effect of c and the model capacity for two reasons. First, the sensible training prevents full PGD perturbations on an example until the loss on it becomes less than log 1c , which could hardly happen for a model with a small capacity. Second, as Madry et al. (2017) point out, when the model capacity is insufficient for adversarial learning, the model collapses to a constant function. We are interested in a range of c that keeps sensible learning from collapsing. Therefore, we consider a sequence of CNNs of the increasing number of kernels similar to Madry et al. (2017), where we denote the capacity by q ∈ {1, 2, 3, 4, 5}. The details of the model architectures are presented in Appendix H. When we train them with natural examples, the networks of capacity 1 and 2 achieve about 95% and 97% accuracy, whereas the networks of the other capacities achieve more than 99%. When trained with regular PGD examples, the networks with capacity 1,2, and 3 collapse. Therefore, capacity 3 is enough only for natural learning, and capacities 1 and 2 are possibly insufficient even for natural learning.
  For each capacity q, we train the models with sensible adversarial examples on MNIST with the hyperparameters c ∈ {0, 0.1, · · · , 0.9, 1}. Note that sensible adversarial training is identical to natural training when c = 1, and to adversarial learning without any perturbations for incorrectly classified natural examples when c = 0. Figure 2 shows the natural and robust accuracy against PGD-40 attacks with varying c for each capacity. In general, the natural accuracy tends to increase as c increases while robustness decreases. For capacities 3, 4 and 5, the accuracies are almost insensitive to varying c. On the other hand, the tendency is most distinct in capacity 1. In this case, the network obtains best robustness when c = 0.5, which is the least loss bound among c ≥ 0.5, the range of c with stable learning property. Even for capacity 1, however, the sensible learning does not collapse except when c = 0. We also see that c = 0.5 is least sensitive to the model capacity.
  Note that capacities 2 and 3 do not collapse even with c = 0. When c = 0, the only difference of the sensible adversarial learning from the regular PGD training is that the sensible learning requires robustness only for the correctly classified natural examples. When c = 0, at the convergence of the models of capacities 1 and 2, about 5% of the data points are allowed to be free from the perturbation. By paying only the 5% of robust training accuracy, the sensible learning avoids collapsing and obtains about 80% of robust accuracy and 90% of natural accuracy.
  Intuitively, an insufficient model capacity or locally close class manifolds can make a virtual decision boundary that is inevitable to keep a nice natural performance. In the algorithm, the sensible reversion prevents adversarial examples from crossing this boundary. This effectively reduces the requirement of the model capacity posed by the regular adversarial learning. The sensible reversion also allows a robust model to have larger margins than the PGD trained model for the majority of the dataset as in Figure 3. The PGD trained model has majority adversarial margins as positive. Instead, it has much smaller natural margins than the naturally trained model. The SENSE model with c = 0.5 has comparably large adversarial and natural margins. Instead, the number of data points with negative adversarial margins is larger than that of the PGD trained model. As c increases to 0.9, this model has much smaller and more negative adversarial margins. On the other hand, its two types of margins are generally even larger. This phenomenon is consistent to the decreasing robustness in Figure 2 for capacity 5. In general, for a fixed capacity, increasing c increases the natural and adversarial margins of the majority of the data, while it also increases the portion of data of negative adversarial margins.
  The cost for this highly confident prediction is the robustness near the decision boundary at convergence, i.e., the portion of the data points in the natural and sensibly reversed stage. When we consider the margin on the training set, we find that there is a linear relationship between the portion of the data points having negative adversarial margins and the test accuracy. In practice, such a portion can be an indicator about the robustness of the model or the sufficiency of the model capacity, without directly testing the model.
  CIFAR: We train train WideResNet-34-10 with several different c values. Except that for c = 0.8 we stopped learning at 120 epoch, other models are trained for 300 epochs. We report the adversarial accuracy against and PGD100 attacks with a step size η1 = 2/255 for the first 2000 test examples, with random 20 restarts. The results are in Table 4.
  Interestingly, while the natural accuracy positively correlated to the c value, the robustness does not show clear negative correlation to c. Rather, as c become closer to 0.7, more robust result the model shows. As we see that c = 0.8 has better robustness than c ≤ 0.5, in CIFAR, the main reason of the observed trade-off could attribute to the influential adversarial perturbations.
  For the CIFAR dataset, we also try to train a robust model with a small capacity. We intentionally choose the CNNs model that is used in Experiment 1 for MNIST. This model can be not enough for adversarial training on CIFAR. We report the results in Table 5. Given the serious lack of model capacity, the decrease in natural accuracy of SENSE models compared with the naturally trained model is not serious, while achieving better robust accuracy numbers. Note that none of our models collapse, and therefore the possibility of sensible adversarial training is not sensitive to the choice of c even in the lack of model capacity.
sections.heading: 6 CONCLUDING REMARKS
sections.text: In this paper, we proposed a sensible adversary which is useful for learning a defense model, keeping a high natural accuracy simultaneously. We theoretically establish that the Bayes rule is most robust under the framework of sensible adversarial learning. Our learning algorithm is efficient and stable, and not sensitive to the choice of the main hyperparameter c. Also, c has a clear meaning as the lowest prediction-probability bound. Our empirical experiments yield state-of-the-art results of adversarial learning on the CIFAR10 and MNIST datasets. In addition, we showed that the sensible approach can effectively deal with the lack of model capacity. This is because by paying a robust accuracy on a certain area, the algorithm protects the model from being collapsed by influential adversarial examples. Furthermore, the sensible adversarial learning trains a model to have high prediction margins on both natural and adversarial examples.
  We now mention several future directions for research on sensible adversary. One remaining theoretical problem is to develop generalization error bounds for sensible adversary learning, so that we can theoretically justify our empirical performance. In fact, in this work, we did not tackle the lack of sample size. In particular, as our algorithm tends to produce a model with large natural and adversarial prediction margins, in the lack of sample size, it is not clear if this large margins are always beneficial. Therefore, there is much remaining work to be done to theoretically understand the high margin tendency of the models trained with sensible adversarial examples with relation to generalization.
sections.heading: A ADDITIONAL RELATED WORK
sections.text: Bubeck et al. (2018) conjecture that learning a robust model is information theoretically possible but computationally intractable. They introduce an example which is not robustly learnable in polynomial time. Our view is consistent with Bubeck et al. (2018) in that a robust model exists, but we search for an efficient algorithm to estimate a robust model in a reasonable time. Su et al. (2018) compared various naturally trained models on ImageNet, and found that the trade-off varies among different model architectures. Also, they empirically discovered that more accurate models tend to be less robust when the models are trained with natural examples. Stutz et al. (2019) demonstrate that given a large training set, adversarial training can produce a robust model that is as accurate as a naturally trained model. Our work to maximize the synergistic effect between natural and adversarial accuracy is consistent to their demonstration. Also, they show that most of PGD attacks are offmanifold of the original data, and by on-manifold adversarial training, the natural accuracy can be improved. If we see the restricted space X̃ as the data manifold, and X̃ c as off-manifold, our sensible framework aligns with their view, given the data manifolds of different classes are separated by at least 2 . Kurakin et al. (2016b) suggest adversarial learning that trains with data randomly divided into two parts, a natural and adversarial set. We divide data in a data adaptive way into three parts including a sensibly reversed adversarial set. The relationship between their approach and our algorithm is discussed more in Appendix F.
sections.heading: B PROOFS OF THEOREMS
sections.text: To save the space, we use η(k|x) to denote P(Y = k|X = x). Theorem 1. (Restated) Let R∗std denote the minimum standard risk which is Rstd(fB). Then we have Rsrob(fB) = R∗std. Furthermore, fB is the unique minimizer ofRsrob(f) among f ∈ F .
  Proof.
  Rsrob(fB) = P(fB(X̃) 6= Y )
  = P(fB(X) 6= Y ) + P(fB(X) = Y, and ∃x′ ∈ SX, (fB) s.t. fB(x′) 6= Y )
  = P(fB(X) 6= Y ) + 0, by the definition of SX, (fB)
  = Rstd(fB) = R∗std.
  It is obvious that fB is a minimizer ofRsrob(f) becauseR∗std is a lower bound ofRsrob(f) for any f ∈ F .
  Now we show fB is the unique minimizer ofRsrob(f).
  Rsrob(f) = P(fB(X) 6= Y, f(X) 6= Y ) + P(fB(X) = Y, ∃x′ ∈ SX, (fB) s.t. f(x′) 6= Y )
  = K∑ k=1 P(fB(X) 6= k, f(X) 6= k, Y = k) + P(fB(X) = k, ∃x′ ∈ SX, (fB) s.t. f(x′) 6= k, Y = k)
  = K∑ k=1 ∫ X P(fB(x) 6= k, f(x) 6= k, Y = k|X = x) + P(fB(x) = k, ∃x′ ∈ Sx, (fB) s.t. f(x′) 6= k, Y = k|X = x)dP(x)
  = K∑ k=1 ∫ X 1fB(x)6=k,f(x)6=kη(k|x) + 1fB(x)=k,∃x′∈Sx, (fB) s.t. f(x′)6=kη(k|x)dP(x) = Rstd(f) + K∑ k=1 ∫ X 1fB(x)=k(1∃x′∈Sx, (fB) s.t. f(x′)6=k − 1f(x)6=k)η(k|x)dP(x) (6)
  The last equality is by 1fB(x)6=k,f(x)6=k = (1− 1fB(x)=k)1f(x)6=k.
  The first termRstd(f) is uniquely minimized by the Bayes rule fB . The second term is always non-negative, and is zero when f = fB . Therefore,Rsrob(f) is uniquely minimized by fB .
  Theorem 2. (Restated) Let SX, be an -ball centered at X . Then for any f ∈ F and for any set A ⊂ X \DB(fB , ),
  P ( ∃ x′ ∈ SX, s.t. fB(x′) 6= Y,X ∈ A ) ≤ P ( ∃ x′ ∈ SX, s.t. f(x′) 6= Y,X ∈ A ) .
  Proof. For any setA ⊂ X\DB(fB , ), P(∃x′ ∈ SX, s.t. fB(x′) 6= Y,X ∈ A) = P(fB(X) 6= Y,X ∈ A). Note that on any subset B ⊂ X , the Bayes rule has the least error probability. Therefore, P(fB(X) 6= Y,X ∈ A) ≤ P(f(X) 6= Y,X ∈ A) ≤ P(∃x′ ∈ SX, s.t. f(x′) 6= Y,X ∈ A). The last inequality is trivial because if f(X) 6= Y ⇒ ∃x′ ∈ SX, s.t. f(x′) 6= Y . Theorem 3. (Restated) Let A = { f ∈ F
  ∣∣P̃(f(x) = fB(x), ∀x ∈ SX, (fB)) = 1} and R̃srob(f) = EP̃X,Y [` s rob, (f,X, Y )]. Then, for any > 0, R̃srob(f) is only minimized by any f ∈ A . Furthermore, if B(X̃ , ) ⊃ X , fB is the unique minimizer of R̃srob(f).
  Proof. The sensible risk of f w.r.t. the restricted distribution corresponding to (6) is
  R̃srob(f) = R̃std(f) + K∑ k=1 ∫ X̃ 1fB(x)=k(1∃x′∈Sx, (fB) s.t. f(x′)6=k − 1f(x)6=k)η(k|x)dP̃(x) (7)
  = R̃std(f) + ∫ X̃ K∑ k=1 1fB(x)=k(1∃x′∈Sx, (fB) s.t. f(x′)6=fB(x) − 1f(x) 6=fB(x))η(f B(x)|x)dP̃(x)
  = R̃std(f) + ∫ X̃ (1∃x′∈Sx, (fB) s.t. f(x′)6=fB(x) − 1f(x)6=fB(x))η(f B(x)|x)dP̃(x) (8)
  because P̃(Y = k|X = x) = P(Y = k|X = x) for x ∈ X̃ . The minimum of R̃srob(f) is achieved by fB with the minimum value R̃∗ = R̃std(fB) + 0. Therefore, any function f that R̃std(f) > R̃∗ cannot achieve the minimum of R̃srob(f) because the term (1∃x′∈Sx, (fB) s.t. f(x′)6=fB(x) − 1f(x)6=fB(x)) in (8) is always non-negative. Therefore, only functions in A = { f ∈ F|P̃ ( f(X) = fB(X) ) = 1 }
  need to be considered as possible minimizers of R̃srob(f).
  Note that A ⊂ A. By the definition, we know that f ∈ A \ A if and only if
  i)P̃ ( f(X) = fB(X) ) = 1
  ii)P̃ ( f(x) = fB(x), ∀x ∈ SX, (fB) ) < 1
  Therefore, for f ∈ A\A , ∃A ⊂ X̃ s.t. P̃ ( X ∈ A ) > 0 and ∃x′ ∈ Sx, (fB) for ∀x ∈ A s.t. f(x′) 6= fB(x′). For this f , the equation in (8) can be written as R̃srob(f) = R̃∗+α for some α ≥ 0. Now we show that α > 0.
  Note that by the definition of the Bayes rule, P(y = fB(x)|X = x) ≥ 1 K . Otherwise, 1 = ∑K k=1 P(y = k|X = x) ≤ KP(y = fB(x)|X = x) < 1, which is contradict. Then, for the f ∈ A \ A and A ⊂ X̃ that are described above,∫
  (1∃x′∈Sx, (fB) s.t. f(x′)6=fB(x) − 1f(x)6=fB(x))η(f B(x)|x)dP̃(x)
  ≥ 1 K ∫ X̃ (1∃x′∈Sx, (fB) s.t. f(x′)6=fB(x) − 1f(x)6=fB(x))dP̃(x)
  = 1
  K ∫ X̃ (1∃x′∈Sx, (fB) s.t. f(x′)6=fB(x))dP(x) by f ∈ A
  ≥ 1 K ∫ A (1∃x′∈Sx, (fB) s.t. f(x′)6=fB(x))dP(x) = P(A) K > 0.
  Therefore, α > 0. Note that for any f ∈ A , the second term in (8) is zero by the definition of A . Therefore, first result of the theorem is proved. Furthermore, for such that B(X̃ , ) ⊃ X ,A = {fB}. Therefore, when B(X̃ , ) ⊃ X , fB is the unique minimizer of R̃srob(f).
  Theorem 4. Let A = { f ∈ F|P̃ ( f(X) = fB(X) ) = 1 } , and take a reference function fr ∈ A. Consider extended sensible adversarial examples, with c < 1 and ` as the 0-1 loss. Then, for any > 0, R̃srob(f |fr) = EP̃X,Y [`(f(X̃|fr , Y )] is uniquely minimized by fr .
  Theorem 4 says that for fr ∈ A, which behaves as the Bayes rule fB on the restricted support, the corresponding sensible adversarial riskEP̃X,Y [`(f(X̃|fr , Y )] is minimized only by fr . This implies that if we do not have any information about the Bayes rule on X̃ c, the sensibly optimal model w.r.t. P̃X,Y can be arbitrary on X̃ c although this optimal model is the Bayes rule on X̃ . Our algorithm deals with this arbitrariness by searching for a better reference function in each iteration. As a current model is used as a reference function, i.e., the estimation of the defense model and the reference model is identical, the algorithm essentially pursues sensibleness on X̃ and robustness on X̃ c of the trained model. Note that on X̃ , sensibleness a sufficient condition for natural accuracy.
  Proof. By using the same way to derive (6) and (8) and noting that fr(x) = fB(x) on X̃ , we get
  R̃srob(f |fr) = R̃std(f) + K∑ k=1 ∫ X̃ 1fB(x)=k(1∃x′∈Sx, (fr) s.t. f(x′) 6=k − 1f(x)6=k)η(k|x)dP̃(x)
  = R̃std(f) + ∫ X̃ (1∃x′∈Sx, (fr) s.t. f(x′)6=fB(x) − 1f(x)6=fB(x))η(f B(x)|x)dP̃(x) (9)
  Because fr(x) = fB(x) on X̃ , R̃std(fr) = R̃std(fB). This implies fr minimizes R̃srob(f |fr) because R̃std(fB) is the minimum of R̃std(f) for all f ∈ F and the second term in (9) is non-negative. This implies any function f s.t. R̃std(f) > R̃std(fB) cannot achieve the minimum of R̃srob(f |fr). Therefore, as a minimizer of R̃srob(f |fr), we only need to consider f ∈ A. Note that 1f(x)6=fB(x) = 0 for f ∈ A on X̃ . Therefore, by letting R̃∗std be R̃std(fB), the equation in (9) can be written as
  R̃srob(f |fr) =R̃∗std + ∫ X̃ 1∃x′∈Sx, (fr) s.t. f(x′)6=fB(x)η(f B(x)|x)dP̃(x)
  =R̃∗std + ∫ X̃ 1∃x′∈Sx, (fr) s.t. f(x′) 6=fr(x)η(f B(x)|x)dP̃(x) (10)
  Note that η(fB(x)|x) is positive on X̃ . Therefore, for f ∈ A to minimize (10), it must satisfy that P̃ ( ∃x′ ∈ SX, (fr) s.t. f(x ′) 6= fr(x′) ) = 0. This essentially says f should be fr .
sections.heading: C ALGORITHM
sections.text: Algorithm 2 Sensible adversarial training for `p norm restriction
  Input: Initialized f = fθ, c ∈ (0, 1), step number and sizes K, η1, η2, data X(0)adv = X 2: repeat for i = 1, ...,m, s.t. f(x(0)i,adv) = yi 4: for k = 1, ...,K
  x (k) i,adv ← ΠBp(xi, )(η1
  ∇x`(f(x(k−1)i,adv ),yi)
  ‖∇x`(f(x(k−1)i,adv ),yi)‖p + x
  (k−1) i,adv ), Π: the projection operator
  6: if `(f, x(k)i,adv, yi) > log 1 c
  (sensible reversion) x(K)i,adv = x (k−1) i,adv
  8: break θ ← θ − η2 ∑m i=1∇θ`(f, x (K) i,adv, yi)/m
  10: until training converged
  Algorithm 2 is a straightforward extension of Algorithm 1 from `∞ norm to `p norm. In addition, we present another way to realize the sensible reversion. After stepping back when the loss exceeds the threshold, we can add a random noise as the next step instead of just breaking the iteration as in Algorithm 1 and 2. Considering the nature of (mini-) batch leaning, this random noise does not add much computational cost because until every loss exceeds the threshold, the for loop would keep calculating the forward and backward loop with fixed perturbation for the reversed examples. This algorithm for `∞ norm is presented in Algorithm 3, of which the objective function is also (5). Algorithm 3 also reverses the adversarial example when the loss is greater than log 1
  c . The only difference is that instead of breaking the iteration after the reversion, it considers a random noise as the next step. This can lead to more effective search for the local loss maximizer in the ball x, (f) in definition 4. The extension of Algorithm 3 to `p norm is straight forward, and thus omitted.
  Algorithm 3 Sensible adversarial training for `∞ norm restriction
  Input: Initialized f = fθ, c ∈ (0, 1), step number K, step sizes η1, η2, data X(0)adv = X repeat
  3: for i = 1, ...,m, s.t. f(x(0)i,adv) = yi for k = 1, ...,K x̃i ← ΠB(xi, )(step (k) i + x (k−1) i,adv ), Π: the projection operator 6: if `(f, x̃i, yi) ≤ log 1c x (k) i,adv = x̃i
  step (k+1) i = η1sign(∇x`(f(x (k) i,adv), yi))
  9: else x (k) i,adv = x (k−1) i,adv
  step (k+1) i = random noise 12: θ ← θ − η2 ∑m i=1∇θ`(f, x (K) i,adv, yi)/m
  until training converged
sections.heading: D THE LANDSCAPE FOR SENSIBLE ROBUST OPTIMIZATION
sections.text: Note that when the original examples are incorrectly classified, full PGD examples can be very influential in regular adversarial training. If we do not add any perturbations on these potentially influential examples and add full PGD perturbations on the other examples, the resultant examples are equivalent to the sensible adversarial examples when c = 0. Experiment 1 shows this small change keeps the models from collapsing, demonstrating how influential the PGD perturbations on the incorrectly classified natural examples. However, an adversarial training with the sensible adversarial examples with c = 0, the empirical loss can largely fluctuate during the training; Once an incorrectly classified natural example becomes correctly classified, its full PGD attack can pose a sudden large gradient for the model update. Then, when it is incorrectly classified again, the loss on it suddenly reduces to the natural loss that is distinctly smaller than the large loss value on its full PGD attack. Therefore, whenever an example changes its state between a correctly and incorrectly classified example, i.e., the full PGD and natural stage, the corresponding loss can fluctuate making the learning unstable.
  However, if we add sensible reversion step, particularly if c ≥ 0.5, this fluctuation does not occur. Between the two stages, the sensibly reversed stage provides a kind of cushion between the natural and full PGD stage, preventing the sudden change in the loss value as described. Until Sx, (f) = Sx, , the sensibly adversarial perturbation for x is adapted to make the loss of the current function approximately equal to log 1
  c . As the
  abstraction in Figure 4, it is like to have a virtually extended area at p̂f,y(x) = c on the loss function that is locally flat on {x̃s|Sx, (f) = Sx, }, i.e., on a set of x̃s that are in the sensibly reversed stage. However, in spite of the existence of such a flat loss area, the model still can learn with x̃s in sensibly reversed stage. This is obvious because the cross-entropy loss has its non-zero gradient when it is log 1
  c . Interestingly, when
  the model is updated in a way to decrease the loss of the previous x̃s, the new sensible perturbation is again adapted to have the loss approximately equal to log 1
  c . Therefore, the course of training directs the model to
  have sensible adversarial examples in the full PGD stage. Furthermore, as long as c > 0, even when x̃s is in a sensibly reversed stage, it still has perturbation in an adapted -ball. This helps to obtain a robustness although it is not on a full ball.
  Note that for c ≥ 0.5, the learning is very stable because only natural examples can overpower the training; The large loss values are only achievable by sensible attack in the natural stage. Any single full PGD attack cannot dominate the next update of the training because the loss function has relatively small gradients on the full PGD stage. Therefore, our algorithms not only effectively ignore any influential full PGD attacks that may overpower the next update but also train a model that allows as many sensible attacks to be full PGD attacks. In other words, our algorithms can stably learn a robust model.
sections.heading: E HIGH MARGIN PROPERTY OF SENSIBLE ADVERSARIAL TRAINING
sections.text: In sensible adversarial learning, the natural accuracy clearly takes priority over the adversarial accuracy. The perturbed example is not allowed to cross the decision boundary of the Bayes rule in (2) or to reach the vicinity of the decision boundary of a reference function in (4). As mentioned, when the cross-entropy loss is used, p̂f,y(x) ≥ c is a prerequisite for adding any adversarial perturbation on x. We note that this condition provides
  a lower bound of the following natural margin as
  M(f, x, y) = log p̂f,y(x)−max y′ 6=y
  log p̂f,y′(x) ≥ log p̂f,y(x) 1− p̂f,y(x) ≥ log c 1− c .
  Therefore, the priority of natural accuracy hints that the learning will prevent the natural margin from being sacrificed for the sake of adversarial robustness. We note that the natural margin of x is an upper bound of its adversarial margin. Therefore, if a model cannot confidently predict a natural example x, neither can the model confidently predict any adversarial examples of x.
  Experiment 1 We investigate the margins of the models trained in Experiment 2, to understand the effect of c. In Figure 5 we draw density plots of the margins on the test set for varying c for the fixed capacities. Overall, we see that a larger c results in a larger adversarial margins and natural margins. In Figure 6, we also draw the margins but for varying model capacity. In general, for a each c, a smaller capacity has more data points of negative margins. However, for naturally trained models, i.e., the models with c = 1.0, a larger model has smaller adversarial margins. This is consistent to the observation of Su et al. (2018) that accurate models tend to be less robust when the models are trained with natural examples. On the other hand, although not displayed, the plots corresponding to c = 0.9 are essentially similar to the plots in the second low. This implies even for large c, our method is not like natural learning; The models trained with c = 0.9 still have larger natural and adversarial margins.
  Note that in Figure 3, the regular PGD model of capacity 5 has only few negative adversarial margins. Instead, their natural margins significantly smaller than those of the natural models. In contrast, our model has negative adversarial margins for a few more data points. Note that the majority of both natural and adversarial margins of the our models are significantly larger than that of the regular PGD models. For capacity 1,2 and 3, the regular PGD models collapse having small ”mean” of adversarial losses. On the contrary, our models deal with the lack of model capacity by letting more portion of examples to have negative margins. As demonstrated by Figure 5, in our methods the mean adversarial loss can be arbitrarily large. Instead, it maintains a large portion of points having relatively large adversarial margins, i.e., being far from decision boundaries.
  The flip side of the advantage of high margin is the possibility of over fitting. For c ≥ 0.5 in Figure 7, the best robust accuracies are not achieved when capacity is 5 but when capacity is 3. On the contrary, the PGD method achieves better robustness as the capacity increases. Therefore, there is a possibility of over-fitting problem that arises form the high margin property of sensible adversarial learning.
  Experiment 2 In Figure 8, we draw the plot of natural and adversarial margins on the testset of CIFAR10. Compared with the distribution of the TRADE model, the natural margin of the SENSE model is large. For the adversarial margins, the SENSE model has two clearly separated clusters; one is of negative margins and the other is of positive margins. Instead, the positive margins are distributed on the larger values. We remark that this phenomenon is consistent to the sensible idea to allow to be fooled near the decision boundary of the Bayes rule. When the capacity is not enough, the concept of the decision boundary is not of the Bayes rule. Its is projected to an inevitable boundary of a model with nice natural performance, caused by the lack of model capacity. The portion of negative adversarial margin is a cost for sensibility and with this cost, the model can obtain robustness as much as possible given a model capacity. We see the portion of adversarial margins of the SENSE model in the negative area in Figure 8 is not small. This may imply the current model capacity and the sample size for SENSE are not enough.
sections.heading: F COMPARISON WITH OTHER METHODS
sections.text: The sensible selection and reversion in our approach distinguish sensible learning from other approaches that balance between the natural and adversarial accuracy. The objective function of our algorithm can be rewritten as follows. For f ∈ F ,
  L(f) = 1 n n∑ i=1 `s(f, xi, yi)
  = |Af | n R̂std(f |Af ) + |Bf | n R̂srob(f |Bf ) + |Cf | n R̂rob(f |Cf ), (11)
  where `s(f, x, y) is defined in (5).
  Kurakin et al. (2016b) suggest adversarial training that randomly divides data into two parts, a natural and adversarial set. The objective function can be written as the following. For random index sets A and C s.t. |A|+ |C| = n and A ∩ C = φ,
  L(f) = 1|A|+ λ|C| [∑ i∈A `(f(xi), yi) + λ ∑ i∈C `(f(x̃i), yi) ]
  = |A| |A|+ λ|C| R̂std(f |A) + λ |C| |A|+ λ|C| R̂rob(f |C), (12)
  where x̃i is an adversarial example of xi.
  Our approach is similar in that we also divide the data for different usage. However, we divide the data by not a random but an adaptive way, so that `s(f, xi, yi) ≥ `s(f, xj , yj) for xi ∈ Af and xj ∈ Cf . Also, we have an additional set other than a natural and fully adversarial set. This additional set, a sensibly reversed adversarial set, plays an important role in allowing a data point smoothly changes its identity between a natural example and a full adversarial example. Note that we do not have any weight controllers like λ in (12). The hyperparameter c itself controls the importance of the natural accuracy in comparison to the adversarial accuracy.
  Zhang et al. (2019) investigate the Bayes decision boundary to resolve the trade-off problem. They propose TRADE, of which the objective function is for β > 0,
  L(f) = E [ `(f(X), y) + β max
  X′∈B(X, ) `(f(X ′), f(X))
  ] . (13)
  This formulation shows several key differences between TRADE and SENSE. First, (13) uniformly restricts the perturbation norm to for all data points, whereas (11) selects the sets for Af , Bf and Cf and restricts
  the perturbation in different ways. Second, the main parameter β in (13) controls the importance of the natural accuracy in comparison to the smoothness of the model. However, the main parameter c in (11) directly controls the lower bound of the natural and adversarial loss of the individual data. This is the lower bound on the prediction probability c if ` is the cross entropy loss. Third, the term `(f(X ′), f(X)) in (13) leads the model to be smooth to all directions in the input space, but `s(f, x, y) in (11) leads to be close to one. Therefore, intuitively, TRADE achieves robustness by obtaining smoothness of the model, whereas SENSE achieves robustness by reformulating (1) in a way to promote high confidency of the robust prediction. This may provide an intuition on the plot of the margin density in Figure 8. By this intuition, we apply PGD attacks with larger perturbation of the training . We apply the attacks on our trained models and the TRADE model by Zhang et al. (2019) for MNIST and CIFAR10. The results are in Table 6 and Table 7.
sections.heading: G ADDITIONAL INFORMATION ABOUT CHEESE HOLE DISTRIBUTION
sections.text: Figure 9 (e) compares the worst-case standard risk Rstd(f̃∗rob) and Rstd(f̃B∗). Although Rstd(f̃∗rob) does not consistently decrease as increases, it is always much smaller than Rstd(f̃B∗). Therefore, pursuit of robustness leads to a more naturally accurate classifier. Figure 9 (e) shows that, as increases from = α/2 to 1, the standard risk of the robustly optimal model gradually increases whereas the sensibly robust model keeps zero risk. Figure 9 (f) demonstrates the robustness against -ball attacks of f̃B∗nat (black), f̃∗rob (blue), and f̃ s∗ rob (red). Although sensibly robust models have large adversarial robustness increasing to 1 as increases, this is because more and more adversarial examples can cross the border, while the model keeps its decision boundary consistent to the class border line. On the other hand, adversarially robust functions have constant robust risk for > 1/4. This is because the robust functions predict as y = 1 for every x ∈ X .
  The sketch of the proof on the standard and adversarial robust risks in (e) and (f) in Figure 9 We first calculate the three classes of functions which minimize natural, adversarial robust, and sensibly robust risk respectively, w.r.t P̃X,Y . Then for each class, we consider the worst case function from each class, in that the function maximizes the standard risk w.r.t PX,Y . The corresponding standard risks are in Figure 9 (e).
  Likewise, for each class, we consider the worst case function from each class, in that the function maximizes the adversarial robust risk w.r.t PX,Y . The corresponding adversarial robust risks are in Figure 1 (f).
  First, the minimizers of each risk w.r.t. P̃X,Y are as following.
  1) Let F̃B be a set of naturally optimal functions w.r.t P̃X,Y :
  F̃B = {f ∈ F|f(x) = sign(x1 − 0.5) for (x1, x2) ∈ X̃}
  2) Let F̃srob be a set of sensibly optimal functions w.r.t P̃X,Y :
  F̃srob = {f ∈ F|f(x) = sign(x1 − 0.5) for (x1, x2) ∈ B(X̃ , )}.
  3) Let F̃rob be a set of robustly optimal functions w.r.t P̃X,Y :
  F̃rob = {f ∈ F|f(x) = g(x) for (x1, x2) ∈ B(X̃ , )},
  where
  g(x) = { sign(x1 − 0.5 + ) if < α/2 or ≥ 3α/4 1(x1≥0.5− ) − 1(x1≤3α/2+ ) if α/2 ≤ < 3α/4
  (14)
  Second, we consider the worst case standard risk w.r.t. PX,Y for each class above.
  1) maxf∈F̃B Rstd(f): Although p 6= 0.5, due to the symmetry of the shape of X̃ , maxf∈F̃B Rstd(f) is the area on X \ X̃ , the area outside the small nine squares.
  2) maxf∈F̃s rob Rstd(f): For the same reason above, maxf∈F̃s rob Rstd(f) is the area on X \B(X̃ , ), the area outside the small nine squares extended by .
  3) maxf∈F̃rob Rstd(f): When < α/2 or ≥ 3α/4, we consider the deviated line on B(X̃ , ), and regard the model outside B(X̃ , ) as incorrect. The risk is calculated easily by using the fact that the risk of any f ∈ F̃rob on is B(X̃ , ) is 3×min(a+2 , 2a)× (1− p)×min(2 , 0.5)/0.5. When α/2 ≤ < 3α/4, since B(X̃ , ) covers X̃ , the worst case functions are in a form of f(x) = sign(x1 − 0.5 + c ) for some c on the entire X̃ . For each s.t. 3α/2 + < x1 < 0.5− , it is easy to find the corresponding c .
  Last, for the worst case adversarial robust risk w.r.t. PX,Y , we can calculate the risks in a similar way to above.
sections.heading: H ADDITIONAL INFORMATION ABOUT EXPERIMENTS
sections.text: H.1 EXPERIMENT 1
  We consider the MNIST and CIFAR-10 dataset (LeCun et al., 2010; Krizhevsky & Hinton, 2009).
  Training For each dataset, we initialize our model by a naturally trained model. Then, we train the initialized model with sensible adversarial examples with the specifications in Table 8.
  Testing with white-box attacks For white-box attacks, we consider PGD (Madry et al., 2017), C&W (Ding et al., 2019a), DeepFool (Moosavi-Dezfooli et al., 2016), FGSM (Kurakin et al., 2016a), LBFGS (Tabacof & Valle, 2016), and MIFGSM (Dong et al., 2018). In Experiment 1, we consider adversarial perturbations with `∞-norm less than , where = 0.3 for the MNIST dataset and = 8/255 for the CIFAR10 dataset.
  We attack our models with the white-box attacks. We use the attacks implemented in Foolbox (Rauber et al., 2017), Advertorch (Ding et al., 2019b), and Adversarial Robustness 360 Toolbox (ART) (Nicolae et al., 2018). The attack specifications are in Table 9. The options that are not listed in the table are kept as default of the attack generating functions.
  We set the step size for MIFGSM as slightly smaller than 8 255 × 1 40 in order to keep the adversarial example from having the perturbation norm greater than = 8/255. For the performance of TRADE on C&W40, we apply the C&W40 attack with the same specifications in Table 9. For the other results of TRADE in Table 1, we refer to Zhang et al. (2019). For PGD attacks, we draw accuracy and loss plots for increasing step numbers in Figure 10 and Figure 11. They show that for the chosen step sizes, the chosen step numbers are enough to generate proper local maximizer of the PGD objective function. Particularly, for CIFAR, we use the step size 2/255 rather than × 2/255 as it is more efficient.
  PGD attack serenity check We test with 100 random restarts, and for the step size 0.01, the step number 500 seem enough by Figure 10.
  Testing with black-box attacks We attack our models with PGD40 and MIFGSM swith the specifications in Table 9. As the Foolbox implementation for MIGSM only returns the successful attacks on the generating model, we only apply these attacks on the defense model. We note that the argument return early of MIFGSM is set to False as in Table 9. For TRADE, we use the models by Zhang et al. (2019) for both MNIST and CIFAR10.
  H.2 EXPERIMENT 2
  Model Architecture We conduct Experiment 2 on the MNIST dataset (LeCun et al., 2010). We consider a sequence of CNNs with the increasing number of kernels. A network of capacity q has two convolutional layers with 2(d−1) and 2d filters respectively, followed by a fully connected linear layer of 2(d+4) units. Each layer is activated by ReLU. Each convolutional layer is followed by 2× 2 a max-pooling layer. The size of all convolutional filters is 5× 5.
  With a similar sequence of CNNs, Madry et al. (2017) investigate the model behavior when the capacity increases. They have capacity scale 1,2,4,8 and 16. In their experiment, capacity scale 1 and 2 collapse. our capacities 2 and 3 are comparable to the capacity scale 1 and 2 by Madry et al. (2017). Likewise, our capacities 4 and 5 are comparable to their capacity scale 4 and 81. Therefore, our result, which shows the PGD models of capacity 1,2 and 3 collapse, is consistent to the result by Madry et al. (2017).
  Training We train the sequence of MNIST models with sensibly adversarial example with = 0.3, η1 = 0.05 and K = 10 for varying c ∈ {0.0, 0.1, · · · , 0.9}. The initial learning rate η2 is 0.01, and we train for 500 epochs. When training the PGD models, we use the same hyperparameters except c.
  Testing The MNIST models are tested with `∞ PGD attacks of = 0.3 with the step number K = 40 and step size η1 = 0.01. We generate the attacks by using a Python package Advertorch by Ding et al. (2019b).
  H.3 ADDITIONAL EXPERIMENT FOR TABLE 6 AND TABLE 7
  We conduct our additional experiment on the MNIST and CIFAR-10 dataset (LeCun et al., 2010; Krizhevsky & Hinton, 2009). For each dataset, we consider the SENSE model trained in Experiment 1 and the TRADE model by Zhang et al. (2019). We note that for each dataset, the TRADE and SENSE model share the same architecture. On theses models, we apply the PGD attacks with perturbations larger than the training . We generate the PGD attacks, using a Python package Advertorch by Ding et al. (2019b) with the following attack specifications.
  MNIST Let 0 = 0.3, which is the training for each model. For δ ∈ {1.1, 1.2, 1.3}, we generate the `∞ PGD attacks of = δ 0 with the step number K = 40× δ and step size η1 = 0.01.
  1Our models could be slightly smaller than the counterparts by Madry et al. (2017) because our max-pooling layers do not apply any padding.
  CIFAR-10 Let 0 = 8/255, which is the training for each model. For δ ∈ { 108 , 12 8 , 14 8 , 16 8 }, we generate the `∞ PGD attacks of = δ 0 with the step number K = 40× δ step size η1 = 0/20.