--- title: "Robustra: Training Provable Robust Neural Networks over Reference Adversarial Space" authors: - "Linyi Li" - "Zexuan Zhong" - "Bo Li" - "Tao Xie" doi: "10.24963/ijcai.2019/654" url: "https://ijcai.org/proceedings/2019/654" pdf: "https://ijcai.org/proceedings/2019/0654.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "4711-4717" track: "Main track" keywords: - "Machine Learning: Adversarial Machine Learning" - "Multidisciplinary Topics and Applications: Security and Privacy" --- # Robustra: Training Provable Robust Neural Networks over Reference Adversarial Space Linyi Li, Zexuan Zhong, Bo Li, Tao Xie *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 4711-4717. DOI: [10.24963/ijcai.2019/654](https://doi.org/10.24963/ijcai.2019/654) ## Abstract Machine learning techniques, especially deep neural networks (DNNs), have been widely adopted in various applications. However, DNNs are recently found to be vulnerable against adversarial examples, i.e., maliciously perturbed inputs that can mislead the models to make arbitrary prediction errors. Empirical defenses have been studied, but many of them can be adaptively attacked again. Provable defenses provide provable error bound of DNNs, while such bound so far is far from satisfaction. To address this issue, in this paper, we present our approach named Robustra for effectively improving the provable error bound of DNNs. We leverage the adversarial space of a reference model as the feasible region to solve the min-max game between the attackers and defenders. We solve its dual problem by linearly approximating the attackers' best strategy and utilizing the monotonicity of the slack variables introduced by the reference model. The evaluation results show that our approach can provide significantly better provable adversarial error bounds on MNIST and CIFAR10 datasets, compared to the state-of-the-art results. In particular, bounded by L^infty, with epsilon = 0.1, on MNIST we reduce the error bound from 2.74% to 2.09%; with epsilon = 0.3, we reduce the error bound from 24.19% to 16.91%. ## Full text ## 1 Introduction In recent years, machine learning techniques, especially deep neural networks (DNNs), have been widely adopted in various applications, such as image classification and machine translation. However, DNNs are recently found to be vulnerable against adversarial examples, i.e., maliciously perturbed inputs that can mislead the models to make arbitrary prediction errors [Szegedy et al., 2014]. Such malicious perturbations are usually imperceptible to human eyes, but allow attackers to easily mislead the behavior of DNNs. The existence of adversarial examples impedes application of DNNs in domains where the safety is highly sensitive, such as autonomous driving and access control systems. Although a series of heuristic defenses [Papernot et al., 2016; Samangouei et al., 2018] have been proposed to defend against existing adversarial examples, many of these defenses can be adaptively attacked again [Carlini and Wagner, 2017b; Athalye et al., 2018]. How to train DNNs that are guaranteed to be robust to any attack serves as an open problem to the community. ∗Both authors contributed equally to this work. Recently, provable defenses [Wong and Kolter, 2018; Wong et al., 2018] have been proposed to train DNNs with low provable error bound, which refers to the fraction of test set inputs for which there is provably no adversarial example within allowed perturbations. However, provable error bounds of DNNs so far are far from satisfaction. For example, on CIFAR10, the state-of-the-art provable error bound is still as high as 46.11%, when bounded by ℓ∞, with ϵ = 2/255 [Tjeng et al., 2019]. To address the issue, in this paper, we present our approach named Robustra for effectively improving the provable error bound of ReLU-based DNNs. We formalize the target task as a min-max game between the attackers and defenders. Different from previous work [Wong and Kolter, 2018] that solves the min-max optimization over the whole normbounded space, we additionally leverage the adversarial space of a reference model as the feasible region. Specifically, given a reference model, our formalized problem seeks to train a model that is robust in the adversarial space of the reference model, i.e., the adversarial examples cannot transfer to the model that we train. Solving such a non-convex problem is non-trivial. We use linear approximation for ReLU activations in the DNNs, and solve its dual problem. The constraint related to the reference adversarial space introduces a family of slack variables in the dual problem, causing no existing approach to effectively solve it. To address the problem, by leveraging the monotonicity and boundedness of the slack variables' gradients, only querying the gradients once, our approach directly calculates out the solution for slack variables. Thus, we solve the problem in the same order of time as the previous work [Wong et al., 2018]. Furthermore, by using similar techniques introduced in the previous work [Wong et al., 2018], Robustra is scalable to be applied to large models such as ResNet. Moreover, we train a pair of models mutually, i.e., iteratively using one as training model and the other as reference, and thus we obtain a pair of robust models at the same time, without requiring external reference. We evaluate Robustra on the MNIST and CIFAR10 datasets. The evaluation results show that our approach can provide significantly better provable adversarial error bounds on both datasets, compared to the state-of-the-art results. Specifically, we reduce the error bound from 24.19% to 16.91% with ℓ∞ norm ϵ = 0.3 on MNIST, and from 46.11% to 43.68% with ℓ∞ norm ϵ = 2/255 on CIFAR10. In summary, this paper makes the following main contributions: - We propose Robustra, a novel approach for training robust ReLU-based DNNs. Robustra formalizes the problem of robust training as a min-max optimization over the adversarial space of a reference model. - We propose an algorithm that leverages the monotonicity and boundedness of the slack variables in the dual problem to efficiently solve the optimization problem. - We evaluate Robustra on both MNIST and CIFAR10 datasets. The evaluation results show that Robustra produces DNNs with significantly better provable adversarial error bounds compared to the state-of-the-art results. Our code and model weights are available at https://github.com/llylly/Robustra. ## 2 Preliminaries In this work, we consider a pair of ReLU-based DNNs f and g, where f is the trainable model, and g is the reference model. We refer to f as fθ in some places to explicitly emphasize the trainable parameters θ. Let n denote the dimension of input vector, and m denote the number of classes. The ReLU function is ReLU(x) = max(x, 0). f and g are formally defined as follows: Namely, f (resp. g): Rn → Rm is a k1 (resp. k2)-layer neural network with parameters Wi, bi, 1 ≤ i ≤ k1 (resp. Ui, bi, 1 ≤ i ≤ k2). All activations functions are ReLU functions in f and g. Given an input x, we have f(x), g(x) ∈ Rm, representing the predicted probability for each class. Let (f(x))i (resp. (g(x))i ) represent the ith dimension of f(x) (resp. g(x)), i.e., the predicted probability of class i. In this paper, we use ℓ∞ norm to measure the adversarial perturbation. We also support to work on ℓ1 norm or ℓ2 norm by applying the techniques introduced in [Wong et al., 2018]. ## 3 RelatedWork and Background Attacks and Empirical Defenses. Szegedy et al. [2014] discover the broad existence of adversarial examples in neural networks. From then on, various attack approaches have been proposed, such as FGSM [Goodfellow et al., 2015], CW [Carlini and Wagner, 2017b; Carlini and Wagner, 2017a], and PGD [Madry et al., 2018]. At the same time, heuristic defenses have been proposed, such as Distillation [Papernot et al., 2016] and Defense-GAN [Samangouei et al., 2018]. Although these heuristic defenses have empirically shown effectiveness against existing attacks, they can be adaptively attacked again after being proposed [Athalye et al., 2018; Carlini, 2019]. Figure 1: A heuristic training approach that aims at reducing the overlap of adversarial space to a reference model can make the model internally robust (see red curve). ![Image](https://ijcai.org/proceedings/2019/fulltext/654/image_000000_b5057e9748afcb40614c6ddef107c8980b87ece900db74870313f902c789a3f9.png) Provable Defenses. Provable defenses train DNNs with low provable error bound, i.e., they can provably guarantee robustness for a fraction of test set inputs against any attacks for the trained DNNs. Existing provable defenses use the upper bound of loss function as (part or all of) the training objective. Existing upper-bound derivation approaches include SDP [Raghunathan et al., 2018], LP-dual [Wong and Kolter, 2018; Wong et al., 2018], and LP [Mirman et al., 2018; Singh et al., 2018]. Besides, concurrent work by Xiao et al. [2019] combines PGD adversarial training with regularization for weight sparsity and ReLU stability. However, provable error bounds of DNNs obtained from these existing approaches are far from satisfaction. DNNVerification. DNNverification approaches determine provable error bound for trained DNNs. Reluplex [Katz et al., 2017] pioneers the field but is not scalable to verify DNNs with more than a thousand neurons. By using Mixed Integer Programming, Tjeng et al. [2019] provide a much faster approach for DNN verification. Other approaches provide relaxed provable error bound by using LPbased relaxations [Weng et al., 2018; Singh et al., 2019; Salman et al., 2019] or SDP-based relaxations [Fazlyab et al., 2019]. ## 4 Motivation: An Empirical Observation Our approach is inspired by an empirical observation: during training, merely limiting overlap of the adversarial space with a reference model can make the model internally robust. This observation indicates that the adversarial space of one model should be defended against with high priority. Specifically, given an input x and its true label y, a naturally trained reference model g(·), we train a model f(·) by modifying the training objective from original loss function ℓf def = ℓ (f(x), y) to ℓf + λ| cos〈▽xℓf ,▽xℓg〉|, where λ is a tunable hyper parameter, being set to 0.1; g, the reference model, is a naturally trained model. Our intuitive approach aims at guiding the local gradients between two models to be diverse (orthogonal) in terms of their cosine angle, hence reducing the overlap of their adversarial spaces. Figure 1 shows the error curves by training epochs. The error rate is measured by the success rate of untargeted PGD attack bounded by ℓ∞ with ϵ = 0.1. The blue curve represents the natural trained model g, where as the natural training goes, the error rate slightly increases. The two dashed curves represent the transfer attack's success rate, where adversarial examples are generated from f/g model and used to attack the other model. The curves show that the transfer error rate is reduced as expected. The red curve represents the error rate of model f. We find that, after a few epochs, the error rate of model f decreases below 20% although we never deliberately train the model to be self-robust. This observation inspires us to train a robust model constrained on the adversarial space of another model. ## 5 Robustra In this section, we introduce Robustra in detail. ## 5.1 Min-Max ProblemFormulation We formalize our target task as a min-max game. Given an input sample x∗ , the true label y∗ , and some target label ytarg ̸= y∗ , we define Aϵ(x∗ ), the adversarial space of g bounded by ℓ∞ norm with ϵ, as follows: where t measures the margin between the decision boundary of adversarial examples in Aϵ(x∗ ). Particularly, when t = 0, Aϵ(x∗ ) is the exact adversarial space of g; when t decreases, Aϵ(x∗ ) becomes larger, vice versa. We want the model f to be robust to adversarial examples of the reference model g. Specifically, for each input in the adversarial space Aϵ(x∗ ), the output of f has a larger value at y∗ than at ytarg . We formalize the objective as the following optimization problem: Let c = eytarg - ey∗, and let FA denote the value space of Aϵ(x∗ ), i.e., Then, the optimization (Eqn. 2) can be rewritten as follows: Since the set FA(x∗ ) is consecutive and highly non-convex, solving such optimization problem is computationally intractable. Figure 2: Visual illustration of approximation by linear convex relaxation. From the exact space Aϵ(x∗ ), the relaxation of model g brings convex space ˆ Aϵ(x∗ ). Then, the relaxation of model f brings convex space ˆ F ˆ A(x∗ ). ![Image](https://ijcai.org/proceedings/2019/fulltext/654/image_000001_781b582b5854920787b298bbd968449ce6bd7e552fa1ca7e848a35aa263de6c8.png) ## 5.2 Linear Convex Relaxation In order to solve the optimization problem, we approximate the optimization space FA(x∗ ) of the problem by using relaxation of the ReLU function. A convex space ˆ F ˆ A(x∗ ) is obtained from the approximation. Since both f(·) and g(·) are ReLU-based DNNs, we use the linear relaxation for ReLU function. Let o = ReLU(i) denote the ReLU function and [l, u] denote the range of input i, i.e., l ≤ i ≤ u. The approximation of ReLU function corresponds to its convex outer space: 1. When l ≤ u ≤ 0, o = 0; 2. When 0 ≤ l ≤ u, o = i; We replace each ReLU function in the problem with corresponding linear constraints according to the range of the input. We apply the relaxation to both f(·) and g(·) models, as shown in Figure 2. First, we apply the relaxation to the ReLU neurons in model g(·). Let ˆG(·) denote the output space after applying the relaxation. Note that ˆG(x) ⊆ Rm, while g(x) ∈ Rm. Accordingly, the adversarial space Aϵ(x∗ ) is replaced with its approximation subspace ˆ Aϵ(x∗ ): Note that ˆ Aϵ(x∗ ) is a convex subspace of Aϵ(x∗ ), because ˆG(x) is a convex outerspace of g(x). Then, we obtain an approximated optimization subspace F ˆ A(x∗ ) (shown in Figure 2). Second, we similarly apply the relaxation to the ReLU neurons in model f(·). Let ˆ F(·) denote the output space after applying the relaxation. Then, we obtain ˆ F ˆ A(x∗ ) = ⋃x∈ ˆ Aϵ(x∗ ) ˆ F(x), which is a convex approximation space of FA(x∗ ). After the two-step relaxation, the optimization problem that we would like to address is as follows: It is an approximation of the original optimization problem (Eqn. 4). Figure 2 illustrates the procedure of the relaxation. At the beginning, the optimization space FA(x∗ ) is non-convex; after relaxation of model g, we obtain a subspace F ˆ A(x∗ ); after relaxation of model f, we obtain ˆ F ˆ A(x∗ ), which is a convex approximation of the original space. We address the optimization problem over this approximation convex space. ## 5.3 Duality Training on the outer minimization in Eqn. 6 requires to calculate the gradient of model parameter θ w.r.t. the inner maximization problem: ▽θ maxv c⊤v = ▽θc⊤v∗ , where v∗ is the solution to the inner problem. In order to calculate the gradient, efficiently solving the inner problem, i.e., finding v∗ , is desirable. Since the inner maximization is an optimization over linear convex space ˆ F ˆ A(x∗ ), the minimum of its dual problem corresponds to the solution due to strong duality. Inspired by previous work [Wong and Kolter, 2018; Wong et al., 2018], we formulate the dual problem by a feedforward network as follows: ν and q are defined as follows: In Eqn. 8 and 9, ui,j and li,j represent the upper and lower bound of the ReLU function input for the j th neuron in layer i of network f(·). Similarly, u′i,j and l′i,j represent the upper and lower bounds of the ReLU function input for the j th neuron in layer i of network g(·). For layer i in model f and g, I + i and Q+i represent the sets of neurons where the inputs are always positive, respectively (0 ≤ l ≤ u); similarly, I - i and Q-i are the sets of neurons where the inputs are always negative (l ≤ u ≤ 0); and Ii and Qi are the sets of neurons spanning zero (l < 0 < u). ν, ˆ ν, q, ˆ q, and η are newly introduced dual variables. We transform the original problem to an optimization problem over the new variable η. ## 5.4 Gradient Monotonicity and t selection In order to solve the dual problemminη≥0 hc(η), we turn to the gradient ▽ηhc(η), which can be written as follows: where γ(η) = ∑nj=1 sgn(ˆ v1,j + ηˆ q1,j) · ˆ q1,j and C is a constant independent of η and t. Note that γ(η) is the analytic form of ▽η‖ˆ ν1 + ηˆ q1‖1. Theorem 1 (Property of γ(η)) γ(η) is a bounded nondecreasing step-function, and the transition points are {-ˆ ν1,j /ˆ q1,j : 1 ≤ j ≤ n}. The theorem can be proved by case discussion over sign of ˆ q1,j. Since γ(η) is the only η-dependent term in Eqn. 10, ▽ηhc(η) has the same property, i.e., ▽ηhc(η) is a bounded non-decreasing step-function. Thus, we can obtain the value range of the gradient of hc(η). Specifically, we have Theorem 2 (Property of hc(η)) When the domain of hc(η) is [0,∞), let ηl = 0, ηr = maxj(-ˆ ν1,j /ˆ q1,j), the gradient value ▽ηhc(η) ∈ [l, r] def = [▽ηhc(η)|η=ηl ,▽ηhc(η)|η=ηr ]. Let us define adversarial space constraints to be constraints imposed by the reference model, i.e., those corresponding to ((g(x))ytarg - (g(x))y∗ ≥ t) in Eqn. 1. We can relate the solution for minη≥0 hc(η) to sign of l and r: - If l ≤ r ≤ 0, when η → +∞, hc(η) → -∞. According to the duality theorem, there is no solution to the original problem maxv c⊤v, indicating that the space ˆ F ˆ A(x∗ ) is empty. In this situation, we regard adversarial space constraints to be infeasible. We need to decrease t, i.e., enlarge adversarial space ˆ Aϵ(x∗ ). - If l < 0 < r, a positive η solution exists. In this situation, we regard adversarial space constraints to be tight. - If 0 ≤ l ≤ r, the solution is η = 0. As seen from Eqn. 8, reference-model-related variables are all eliminated from objective function hc(η), indicating that the adversarial space constraints are loose. In this situation, we would like to increase t, i.e., narrow adversarial space ˆ Aϵ(x∗ ). The ideal situation is that for all optimization objectives hc(η), the adversarial space constraints are tight and the solution exists, i.e., l < 0 < r. To guarantee so, we fix a reasonable η as the solution and inversely obtain the corresponding t. Specifically, we set η to be the median number of γ(η) transition points. Combining Theorem 1, Theorem 2, and constraint η ≥ 0, we pick the median number in {-ˆ ν1,j /ˆ q1,j : 1 ≤ j ≤ n,-ˆ ν1,j /ˆ q1,j > 0} as the solution for η, denoted as ηmed. ηmed being the solution indicates ▽ηhc(η)|η=ηmed = 0, which yields t = t0 = ϵγ(ηmed) + C. Thus, the hyperparameter t is set to t0 according to ηmed. As result, we effectively solve the inner maximization problem minη≥0 hc(η) by forward passing c to the network defined in Eqn. 9 and extracting the median number using ˆ v1 and ˆ q1. After that, we use t0 and ηmed to directly calculate hc(η). Formally, ## 5.5 Scaling To scale up the training process, we find that Cauchy random projection estimation of ℓ1 norm [Wong et al., 2018] can be directly applied in our approach. When a vector multiplies a standard Cauchy random matrix, the median number of the result vector is an estimation of ℓ1 norm of the vector. Using this property, we can approximately calculate ∑k1-1 i=2 ∑j∈Ii li,j[νi,j]+ and ∑k2-1 i=2 ∑j∈Qi l′i,j [qi,j]+ of Eqn. 8 in linear complexity w.r.t neuron numbers [2018]. With this calculation, our approach has the same order of complexity with [Wong et al., 2018]. This calculation enables our approach to scale up to large datasets such as CIFAR10 and large DNN models such as ResNet. ## 5.6 Training During the training process, we use the solution for each ytarg as the probability of that class. Then we use cross-entropy with softmax as the training loss to jointly minimize errors for all ytarg ̸= y∗ . We adopt a manual training scheme to optimize a pair of models. Initially, f(·) and g(·) are randomly initialized independently. When the model size is small, in each epoch, we train model f(·) where model g(·) is the reference, and then train model g(·) where model f(·) is the reference. When the model size is large, we accelerate the process by distributing model f(·) and model g(·) to two GPUs. By loading the last epoch weights of the other model as the reference, two models are trained parallelly, both using the other model as the reference at the same time. This training scheme optimizes both models efficiently. Table 1: Statistics of the models used in our experiments. | Dataset | Model | # Layers | # Hidden Units | # Parameters | |-----------|---------|------------|------------------|----------------| | MNIST | Small | 4 | 4, 804 | 166, 406 | | MNIST | Large | 7 | 28, 064 | 1, 974, 762 | | CIFAR10 | Small | 4 | 6, 244 | 214, 918 | | CIFAR10 | Large | 7 | 62, 464 | 2, 466, 858 | | CIFAR10 | ResNet | 11 | 107, 496 | 4, 214, 850 | ## 6 Experiments We evaluate Robustra on image classification tasks with two datasets: MNIST [LeCun et al., 1998] and CIFAR10 [Krizhevsky and Hinton, 2009]. We use the same DNNs as used in [Wong et al., 2018] for comparison. All DNNs are convolutional neural networks with multiple layers, using only ReLU activations. Table 1 shows the statistics of DNNs that we use. For each model and dataset, we run 100 epochs on the training set. Adam optimizer is used for MNIST models, and SGD optimizer (0.9 momentum, 5 × 10-4 weight decay) is used for CIFAR10 models. The ℓ∞ norm ϵ is initialized by 0.01, and then it linearly increases to the configured ϵ (0.1 or 0.3 for MNIST, 2/255 or 8/255 for CIFAR10) in the first 20 epochs. In the first 20 epochs, the learning rate is set to be 0.001; then, it decades by half every 10 epochs. The batch size is set to 50. The scaling approximation (Section 5.5) is applied for training 'Large' and 'ResNet' models, where the projection dimension is 50. Note that no hyperparameter selection or tuning is applied to guarantee the soundness of the results. All experiments are run on Geforce GTX 1080 Ti GPUs. ## 6.1 Provable Error Bound We use two provable error bounds to evaluate the models trained by Robustra: LP bound [Wong and Kolter, 2018] and MILP bound [Tjeng et al., 2019]. The full test set is used in our evaluation. We compare the error bounds of Robustra to the state of the art on the same model structures [Wong et al., 2018; Wong and Kolter, 2018]. The results in Table 2 show that on both the MNIST dataset and CIFAR10 dataset, Robustra outperforms the state of the art in most of the settings. Specifically, on the MNIST dataset, with ϵ = 0.1, Robustra significantly improves the MILP bound on 'Large' model from 2.74% to 2.09%; with ϵ = 0.3, Robustra achieves 16.91% provable test error using 'Small' model and improves LP bound, from previous 43.10%/45.66% to 31.42%/34.59% for 'Small' and 'Large' models, respectively. On the CIFAR10 dataset, with ϵ = 2/255, Robustra exceeds the state of the art on all models. It reduces the previous bound from 46.11% to 43.68%. With ϵ = 8/255, Robustra reduces the error bound from 77.60% (on 'ResNet', MILP bound) to 74.87% (on 'Small', MILP bound). Clean error represents the error rate of a model on a clean (i.e., unperturbed) test set. The model trained by Robustra has similar or smaller clean error rate compared to state-ofthe-art models. Furthermore, we find that a model with less clean error usually has a tighter provable error bound. Table 2: Provable error bound of Robustra and the state of the art (SOA) [Wong et al., 2018; Wong and Kolter, 2018]. Two bounds are used for evaluation: LP bound [Wong and Kolter, 2018] and MILP bound [Tjeng et al., 2019]. For SOA models, we use the error bounds reported in their papers. We mark a '-' on an entry if there are no reported results in the corresponding paper. For our models that are too large for MILP bound to be calculated in feasible time (i.e., 24 hours), we mark '/' on the entry. In addition, we compare clean example test error rate (Clean Err.) of SOA models and our models. | Dataset | ϵ | Model | LP bound - SOA | LP bound - Robustra | MILP bound - SOA | MILP bound - Robustra | Clean Err. - SOA | Clean Err. - Robustra | |-----------|---------------|--------------------|----------------------|-----------------------|--------------------|-------------------------|----------------------|-------------------------| | MNIST | 0.1 | Small Large | 4.48% 3.67% | 4.84% 3.93% | 4.38% 2.74% | 2.55% 2.09% | 1.26% 1.08% | 1.01% 0.83% | | MNIST | 0.3 | Small Large | 43.10% 45.66% | 31.42% 34.59% | 25.79% 24.19% | 16.91% 24.43% | 11.40% 11.16% | 7.37% 11.61% | | | CIFAR10 2 255 | Small Large ResNet | 52.75% 46.59% 46.11% | 51.47% 43.68% 44.43% | 50.20% - - | 47.93% / / | 38.91% 31.28% 31.72% | 36.03% 28.48% 29.51% | | | 8 255 | Small Large ResNet | 79.25% 83.43% 78.22% | 76.29% 78.32% 79.57% | - - 77.60% | 74.87% 77.56% 78.10% | 72.24% 80.56% 71.33% | 66.34% 71.79% 72.10% | Figure 3: Provable robust error bound and clean error curves of each epoch, evaluated on the MNIST test set, with ϵ = 0.3. Provable robust error bound represents LP bound. Clean error represents the error rate on clean examples. f(·) and g(·) stand for the two mutually trained models. ![Image](https://ijcai.org/proceedings/2019/fulltext/654/image_000002_c48c1b9c2a8de2ba28691471711b55b06fa8804eaa9aa501f6ec37f6fed3bc5c.png) ## 6.2 Training Progress The training curves are shown in Figure 3. Provable error is measured by LP bound. Clean error is measured by error rate on clean (i.e., unperturbed) examples. Both are evaluated on the test set. In the first 20 epochs, ϵ used for training is linearly increased to desired ϵ (0.3). The provable robust error keeps being 100% for these first 20 epochs, and then a significant drop occurs as the training ϵ reaches 0.3. The result reveals that the model is not robust to larger perturbations unless it is trained at that perturbation level. During these first 20 epochs, the clean error increases while the provable robust error bound decreases. Then both provable errors and clean errors decrease. At each epoch, both models are trained mutually: we first regard g(·) as the reference model and train the model f(·); then, we set the trained f(·) as the reference model and train the model g(·). Thus, at each epoch, the test error of g(·) is slightly smaller than the test error of f(·), as shown in Figure 3. ## 6.3 t Selection Effectiveness In our approach, we select some t to solve the inner maximization problem, as discussed in Section 5.4. Figure 4a plots the curve of selected t. Larger t corresponds tighter reference space, as shown in Eqn. 1. In the first 20 epochs, t is small and sharply increases to around -3. This result indicates that our approach dynamically tightens these constraints along with increasing training ϵ. After 20 epochs, as the reference model is trained more robust, its adversarial space becomes smaller. The approach gradually decreases t to loosen the constraints. Figure 4: On MNIST with ϵ = 0.3: (a) curve of selected t; and (b) tightness status of adversarial space constraints of each epoch when t = 0. ![Image](https://ijcai.org/proceedings/2019/fulltext/654/image_000003_c9f9ebd1a5edc5785341882b8febb786f840af3970af180693095a7a042db890.png) In Figure 4b, on MNIST with ϵ = 0.3, we study the solution status on test dataset if fixing t = 0. In the first 20 epochs, non-robust models make almost all constraints loose. After 20 epochs, the robust models make almost all constraints infeasible. Thus, when t = 0, we are not able to effectively solve the problem. Instead, we need to dynamically select t as we propose in Section 5.4. ## 7 Conclusion We have presented Robustra, an approach for training provable robust neural networks. In particular, we formalize the training procedure as a min-max game over the adversarial space of the reference model, and effectively solve the minmax game. The experimental results have shown that Robustra significantly outperforms the state-of-the-art approach. ## Acknowledgments This work was supported in part by NSF under grants no. CNS-1513939, CNS-1564274, CCF-1816615. ## References 1. [Athalye et al., 2018] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pages 274-283, 2018. 2. [Carlini and Wagner, 2017a] Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: By- passing ten detection methods. In ACM Workshop on Ar- tificial Intelligence and Security, pages 3-14, 2017. 3. [Carlini and Wagner, 2017b] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural net- works. In IEEE Symposium on Security and Privacy, pages 39-57, 2017. 4. [Carlini, 2019] Nicholas Carlini. Is AmI (attacks meet inter- pretability) robust to adversarial examples? arXiv preprint arXiv:1902.02322, 2019. 5. [Fazlyab et al., 2019] Mahyar Fazlyab, Manfred Morari, and George J. Pappas. Safety verification and robust- ness analysis of neural networks via quadratic con- straints and semidefinite programming. arXiv preprint arXiv:1903.01287, 2019. 6. [Goodfellow et al., 2015] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. 7. [Katz et al., 2017] Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In In- ternational Conference on Computer Aided Verification, pages 97-117, 2017. 8. [Krizhevsky and Hinton, 2009] Alex Krizhevsky and Geof- frey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009. 9. [LeCun et al., 1998] Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning ap- plied to document recognition. Proceedings of the IEEE, 86(11):2278-2324, 1998. 10. [Madry et al., 2018] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. 11. [Mirman et al., 2018] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Confer- ence on Machine Learning, pages 3578-3586, 2018. 12. [Papernot et al., 2016] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense to adversarial perturbations against deep neu- ral networks. In IEEE Symposium on Security and Privacy, pages 582-597, 2016. 13. [Raghunathan et al., 2018] Aditi Raghunathan, Jacob Stein- hardt, and Percy Liang. Certified defenses against adver- sarial examples. In International Conference on Learning Representations, 2018. 14. [Salman et al., 2019] Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relax- ation barrier to tight robust verification of neural networks. arXiv preprint arXiv:1902.08722, 2019. 15. [Samangouei et al., 2018] Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-GAN: Protecting classifiers against adversarial attacks using generative models. In International Conference on Learning Representations, 2018. 16. [Singh et al., 2018] Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Ad- vances in Neural Information Processing Systems, pages 10802-10813, 2018. 17. [Singh et al., 2019] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. In ACM SIGPLAN Sympo- sium on Principles of Programming Languages, volume 3, page 41, 2019. 18. [Szegedy et al., 2014] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. 19. [Tjeng et al., 2019] Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019. 20. [Weng et al., 2018] Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inder- jit S Dhillon, and Luca Daniel. Towards fast computa- tion of certified robustness for ReLU networks. In Inter- national Conference on Machine Learning, pages 5273- 5282, 2018. 21. [Wong and Kolter, 2018] Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Con- ference on Machine Learning, pages 5283-5292, 2018. 22. [Wong et al., 2018] Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pages 8400-8409, 2018. 23. [Xiao et al., 2019] Kai Xiao, Vincent Tjeng, Nur Muham- mad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing ReLU sta- bility. In International Conference on Learning Represen- tations, 2019.