In recent years several adversarial attacks and defenses have been proposed. Often seemingly robust models turn out to be non-robust when more sophisticated attacks are used. One way out of this dilemma are provable robustness guarantees. While provably robust models for specific $l_p$-perturbation models have been developed, we show that they do not come with any guarantee against other $l_q$-perturbations. We propose a new regularization scheme, MMR-Universal, for ReLU networks which enforces robustness wrt $l_1$- \textit{and} $l_\infty$-perturbations and show how that leads to the first provably robust models wrt any $l_p$-norm for $p\geq 1$. The vulnerability of neural networks against adversarial manipulations (Szegedy et al., 2014; Goodfellow et al., 2015) is a problem for their deployment in safety critical systems such as autonomous driving and medical applications. In fact, small perturbations of the input which appear irrelevant or are even imperceivable to humans change the decisions of neural networks. This questions their reliability and makes them a target of adversarial attacks. To mitigate the non-robustness of neural networks many empirical defenses have been proposed, e.g. by Gu & Rigazio (2015) ; Zheng et al. (2016) ; Papernot et al. (2016) ; Huang et al. (2016) ; Bastani et al. (2016) ; Madry et al. (2018) , but at the same time more sophisticated attacks have proven these defenses to be ineffective (Carlini & Wagner, 2017; Athalye et al., 2018; Mosbach et al., 2018) , with the exception of the adversarial training of Madry et al. (2018) . However, even these l ∞ -adversarially trained models are not more robust than normal ones when attacked with perturbations of small l p -norms with p = ∞ (Sharma & Chen, 2019; Schott et al., 2019; Croce et al., 2019b; Kang et al., 2019) . The situation becomes even more complicated if one extends the attack models beyond l p -balls to other sets of perturbations (Brown et al., 2017; Engstrom et al., 2017; Hendrycks & Dietterich, 2019; Geirhos et al., 2019) . Another approach, which fixes the problem of overestimating the robustness of a model, is provable guarantees, which means that one certifies that the decision of the network does not change in a certain l p -ball around the target point. Along this line, current state-of-theart methods compute either the norm of the minimal perturbation changing the decision at a point (e.g. Katz et al. (2017) ; Tjeng et al. (2019) ) or lower bounds on it (Hein & Andriushchenko, 2017; Raghunathan et al., 2018; Wong & Kolter, 2018) . Several new training schemes like (Hein & Andriushchenko, 2017; Raghunathan et al., 2018; Wong & Kolter, 2018; Mirman et al., 2018; Croce et al., 2019a; Xiao et al., 2019; Gowal et al., 2018) aim at both enhancing the robustness of networks and producing models more amenable to verification techniques. However, all of them are only able to prove robustness against a single kind of perturbations, typically either l 2 -or l ∞ -bounded, and not wrt all the l p -norms simultaneously, as shown in Section 5. Some are also designed to work for a specific p (Mirman et al., 2018; Gowal et al., 2018) , and it is not clear if they can be extended to other norms. The only two papers which have shown, with some limitations, non-trivial empirical robustness against multiple types of adversarial examples are Schott et al. (2019) and Tramèr & Boneh In this paper we aim at robustness against all the l p -bounded attacks for p ≥ 1. We study the non-trivial case where none of the l p -balls is contained in another. If p is the radius of the l p -ball for which we want to be provably robust, this requires: q > p > q for p < q and d being the input dimension. We show that, for normally trained models, for the l 1 -and l ∞ -balls we use in the experiments none of the adversarial examples constrained to be in the l 1 -ball (i.e. results of an l 1 -attack) belongs to the l ∞ -ball, and vice versa. This shows that certifying the union of such balls is significantly more complicated than getting robust in only one of them, as in the case of the union the attackers have a much larger variety of manipulations available to fool the classifier. We propose a technique which allows to train piecewise affine models (like ReLU networks) which are simultaneously provably robust to all the l p -norms with p ∈ [1, ∞]. First, we show that having guarantees on the l 1 -and l ∞ -distance to the decision boundary and region boundaries (the borders of the polytopes where the classifier is affine) is sufficient to derive meaningful certificates on the robustness wrt all l p -norms for p ∈ (1, ∞). In particular, our guarantees are independent of the dimension of the input space and thus go beyond a naive approach where one just exploits that all l p -metrics can be upper-and lower-bounded wrt any other l q -metric. Then, we extend the regularizer introduced in Croce et al. (2019a) so that we can directly maximize these bounds at training time. Finally, we show the effectiveness of our technique with experiments on four datasets, where the networks trained with our method are the first ones having non-trivial provable robustness wrt l 1 -, l 2 -and l ∞ -perturbations. We have presented the first method providing provable robustness guarantees for the union of multiple l p -balls beyond the trivial case of the union being equal to the largest one, establishing a baseline for future works. Without loss of generality after a potential permutation of the coordinates it holds |x d | = x ∞ . Then we get , which finishes the proof.
We introduce a method to train models with provable robustness wrt all the $l_p$-norms for $p\geq 1$ simultaneously.
{"src": "scitldr-AIC_train", "paper_id": "rklk_ySYPB"}