TACTICS ON REFINING DECISION BOUNDARY FOR IMPROVING CERTIFICATION-BASED ROBUST TRAINING
Year: 2021

Abstract:
In certification-based robust training, existing methods utilize relaxation based methods to bound the worst case performance of neural networks given certain perturbation. However, these certification based methods treat all the examples equally regardless of their vulnerability and true adversarial distribution, limiting the model’s potential in achieving optimal verifiable accuracy. In the paper, we propose new methods to include the customized weight distribution and automatic schedule tuning methods on the perturbation schedule. These methods are generally applicable to all the certifiable robust training with almost no additional computational cost. Our results show improvement on MNIST with = 0.3 and CIFAR on = 8/255 for both IBP and CROWN-IBP based methods.

text: In certification-based robust training, existing methods utilize relaxation based methods to bound the worst case performance of neural networks given certain perturbation. However, these certification based methods treat all the examples equally regardless of their vulnerability and true adversarial distribution, limiting the model’s potential in achieving optimal verifiable accuracy. In the paper, we propose new methods to include the customized weight distribution and automatic schedule tuning methods on the perturbation schedule. These methods are generally applicable to all the certifiable robust training with almost no additional computational cost. Our results show improvement on MNIST with = 0.3 and CIFAR on = 8/255 for both IBP and CROWN-IBP based methods.

heading: 1 INTRODUCTION
text: Deep neural networks (DNNs) have been shown to be highly vulnerable to adversarial attacks, carefully-crafted inputs that are nearly indistinguishable from naturally-occurring data but are misclassified by the network (Goodfellow et al., 2014; Szegedy et al., 2014). There exist many algorithms for both crafting adversarial attacks (Papernot et al., 2016) and building neural networks that are robust against such attacks. Fast gradient sign method (FGSM) (Goodfellow et al., 2014) was the very first approach to generate strong adversary. Projected gradient descent (PGD) (Madry et al., 2018) is one of the most successful and widely-used defense methods available. Adversarial training seeks to minimize the worst-case loss under adversarial perturbations within a pre-defined perturbation level, where multi-step PGD is used to estimate the worst-case attack during training. Compared to standard training, the adversarial term introduces risk of over-fitting (Moosavi-Dezfooli, 2021; Rice et al., 2020; Wang et al., 2019) and training instability (Tsipras et al., 2019; Zhang et al., 2020b) for adversarial training. There exist many related works on improving the model performance by additional regulation (Zhang et al., 2020b; Cisse et al., 2017) and customizing training curriculum (Zhang et al., 2019; Wang et al., 2020; Cai et al., 2018) for attack-based scenario. While adversarial training has been shown to be empirically effective against many types of attacks, it cannot be proven that the resultant models are robust against all adversaries. In fact, it has been shown that many defense methods dependent on heuristic techniques, including adversarial training, can be bypassed by stronger adversaries (Athalye et al., 2018).
This has motivated a separate branch of research focused on robustness certification/verification: computing provable guarantees on the robustness performance of neural networks against inputs with arbitrary perturbations within some `p norm-bounded ball. There are two main types of verification methods: complete and incomplete verification. The former computes exact robustness bounds using computationally-expensive methods such as mixed-integer programming (MIP) (Tjeng et al., 2019; Bunel et al., 2018), whereas the latter provides looser robustness bounds with different branches of methods like randomized smoothing (Cohen et al., 2019; Salman et al., 2019; Lecuyer et al., 2019), Lipschitz-based robustness(Trockman & Kolter, 2021; Tsuzuku et al., 2018) and convex adversarial polytype (Weng et al., 2018; Zhang et al., 2018; Dvijotham et al., 2018b; Gowal et al., 2019) on which in this paper we mainly focus. A sparsely related branch of research, called certified robust training (Dvijotham et al., 2018a; Gowal et al., 2019; Zhang et al., 2020a), aims to train a certifiably robust model. These methods compute verified robustness bounds and incorporate
them into the training process, such that the resultant models can then be proven to be robust using a verification method.
Currently, the most efficient certified training method is interval bound propagation (IBP) (Gowal et al., 2019), which requires only two additional forward passes during training. It is important to note that IBP is significantly more efficient than adversarial training, which often require many PGD steps to achieve high robustness (Madry et al., 2018). In standard certified training, a uniform and loss function weight are usually used across all the training examples, this is not ideal for optimal verified accuracy since the examples are not necessarily equivalent in terms of vulnerability.

heading: 1.1 OUR CONTRIBUTIONS
text: In this paper, we propose two novel methods to improve robustness via refining certified decision boundary for verifiable adversarial training methods such as IBP and CROWN-IBP. In particular, our algorithms are generally applicable to all the verifiable adversarial training methods at almost no additional computational cost. We sum up the key contributions as following: 1. Zeng et al. (2020) pointed out the adversarial example distribution deviates from the clean data. We further analyze the importance weight to correct empirical distribution from a novel perspective and theoretically prove more weight is needed for the examples closer to decision boundary if sampled from clean data distribution. 2. Building upon previous analysis, we come up with a symmetrical re-weighting function based on worst case margin of the correct labels, emphasizing the examples around the decision boundary. 3. For verifiable adversarial perturbation, empirically a slightly larger train achieves optimal evaluation robustness accuracy on eval, while this uniform setup is not ideal for examples around decision boundary. To address the issue of large perturbation, we developed an auto-tuning algorithm to customize the train for each individual example.

heading: 2 BACKGROUND

heading: 2.1 ADVERSARIAL ATTACKS AND TRAINING
text: Let D = {(xi, yi)}ni=1 represent the dataset, where xi ∈ X and yi ∈ Y = {0, 1, ..., C − 1}. Let B(xi, ) denote the set of points in the `p-norm ball with radius around xi. The objective function is
min θ
1
n n∑ i=1 l(fθ(x ′ i), yi), where x ′ i = arg max x′∈B(xi, ) l(fθ(x ′), yi) (1)
fθ : X −→ RC is a score function and l : RC × Y −→ R is the loss function. Adversarial training tackles this min-max problem by alternating between solving inner loop by attack method to estimate the worst-case adversarial scenario in B(xi, ) and outer loop to update the model parameters and minimize loss function.

heading: 2.2 CERTIFIED TRAINING
text: Robustness Verification. Different from attack-based training, certified training provides a guarantee for worst case scenario via bounding the neural network outputs. The certified accuracy is the lower bound of robustness accuracy under any attack method, thus improving the certified accuracy helps in understanding the potential of the neural network in defending against adversarial attacks.
Interval Bound Propagation. There have been many proposed neural network verification algorithms that can be used to compute worst case output. IBP (Gowal et al., 2019) utilizes a simple, interval arithmetic approach to propagate bounds through a network. Let zk−1 denote the input to a layer zk. IBP bounds zk by computing lower and upper bounds zk, zk such that zk ≤ zk ≤ zk holds element-wise. For affine layers represented by hk(zk−1) = Wzk−1 + b, IBP computes: zk = W zk−1+zk−1 2 − |W | zk−1−zk−1 2 + b and zk = W zk−1+zk−1 2 + |W | zk−1−zk−1 2 + b. Propagating the bounds through the network allows us to compute the upper and lower bound of last layer logits zK , zK and evaluate if an input x is verifiably robust. The logit of the true class equals the lower bound and the logits of other classes equal to the upper bound:
ẑK,m = { zK,m if m is the true class zK,m otherwise
(2)
IBP training uses a hyperparameter schedule on (starting from 0 and increasing to train, typically set at train which is slightly larger than eval) and a mixed loss function that combines natural and robust cross-entropy loss: minθ E(x,y)∼P [κl(zK , y) + (1 − κ)l(ẑK , y)], where P is the data distribution, l is the cross entropy loss, κ is a hyperparameter that balances the weight between natural and robust loss, and ẑK represents the worst case logits computed using IBP.
CROWN-IBP. CROWN was introduced by Zhang et al. (2018) and achieves a tight bound by adaptively selecting the linear approximation. Zhang et al. (2020a) proposed CROWN-IBP combining IBP forward bounding pass and CROWN style backward bounding pass. CROWN-IBP trained models has a tighter bound compared with IBP models under the IBP metric, with incurring cost on computational efficiency from CROWN backward propagation and generally requiring more epochs for training stability.

heading: 2.3 ATTACK-BASED RE-WEIGHTING
text: Motivated by the idea that all data points are not equally vulnerable to adversarial attack, researchers proposed methods to re-weight the minimax risk by adding a re-weighting term ω(xi, yi) ahead of individual example loss. For instance, Zeng et al. (2020) noted the adversarial distribution deviation from the clean examples and assigned weights that monotonically decreases with the examples’ confidence margin. The “confidence margin” is calculated by attack methods such as PGD, then the risk is re-weighted by a parameterized exponential family as: minθ 1 n ∑n i=1 ω(xi, yi)l(fθ(x ′ i), yi), s.t. ω(xi, yi) = exp(−α margin(fθ,xi + δi, yi)) , where α is a positive hyper-parameter and the new risk biases larger weights towards the mis-classified examples.
Zhang et al. (2020c) propose GAIRAT (Geometry-Aware Adversarial Training), a method to reweight adversarial examples based on how close they are to the decision boundary. During the training process, GAIRAT explicitly assigns larger/smaller weights to data points closer/farther to the decision boundary respectively: ω(xi, yi) = (1 + tanh(λ + 5 × (1 − 2 × κ(xi, yi)/K)/2, where λ is a hyper-parameter, K is the maximal allowed attack iteration and κ is the least iteration number that the attack method requires to fool the classifier. Similar to re-weighting, Wang et al. (2021) improves clean image performance by prioritizing the robustness between the most dissimilar groups

heading: 2.4 CUSTOMIZED ADVERSARIAL TRAINING
text: In most adversarial training methods, the adversarial attack strength usually follows a pre-defined scheduler throughout the training process. For instance, the perturbation is a uniform number for all examples and usually gradually increases. Cheng et al. (2020) argued that this assumption may be problematic given the fact that adversarial examples are not equally vulnerable and proposed an auto-tuning method by assigning individual i to each data and increasing it if the current attack is successful. In Zhang et al. (2020b), they proposed friendly adversarial training (FAT) by progressively increasing the attack perturbation with early-stop PGD and alleviating the issue of strong adversarial attack and cross-over mixture.

heading: 3 OUR PROPOSED METHODS

heading: 3.1 BOUND-BASED WEIGHTED LOSS
text: In classical classification tasks, training minimizes the following loss function: E(x,y)∼P [l(fθ(x), y)] estimated by 1n ∑n i=1[l(fθ(xi), yi)]. For adversarial training, let x
′ be the worst case input under verifiable adversary or perturbed example from attack, the adversarial examples (x′, y) ∼ P ′, where P ′ is an unknown distribution dependent on the clean example distribution P , perturbation method and neural network parameters. In practice, the training objective is usually 1n ∑n i=1[l(fθ(x ′ i), yi)] estimating E(x,y)∼P [l(fθ(x′), y)], while the true objective should
be E(x′,y)∼P ′ [l(fθ(x′), y)]. There exists a discrepancy between the true distribution and empirical sampling method. To bridge this gap, we follow Zeng et al. (2020) and introduce importance weight
s(fθ,x ′ i, yi) :=
P ′(x′i, yi) P (xi, yi) (3)
s.t.
1
n n∑ i=1 [l(fθ(x ′ i), yi)s(fθ,x ′ i, yi)] ≈ E(x,y)∼P [l(fθ(x′), y) P ′(x′, y) P (x, y) ]
≈ E(x′,y)∼P [l(fθ(x′), y)] (4)
As further exploration, we analyze the importance weight:
P ′(x′i, yi) P (xi, yi) = P ′(x′i|yi)P ′(yi) P (xi|yi)P (yi) = P ′(x′i|yi) P (xi|yi)
(5)
where the first equality follows from the definition of conditional probability and second equality is from the fact that the label yi and its distribution does not change through the adversarial process.
The probability ratio gives us more insight in designing the parametric function for importance weight. Given label yi, there exists a distribution of its corresponding clean image space P (x|yi) and similarly for worst case input space P ′(x′|yi). If the distribution of its corresponding worst case x′i gets more concentrated compared to clean image distribution P (x|yi), then more weight should be given to this example and vice versa.
Theorem 1. Given a binary classification task Rn −→ {+,−} with equal prior probability, assume the corresponding examples x+ and x− are uniformly distributed in region S+,S− ⊂ Rn,S+ ∩ S− = ∅. If there exists a bijection mapping m := S+ 7→ S−,S− 7→ S+ s.t. the post-mapping example x′+ and x ′ − distribution remains uniform in each region, the expectation of conditional distribution ratio P ′(x′|y) P (x|y) over original distribution P (x, y) is great or equal than 1.
Example 1. Figure 1 shows two extreme cases of adversarial example x′ distribution movement from clean x distribution given decision boundary in a simplified 2D scenario. When x is far away from decision boundary, the direction of attack or movement towards worst case example under verifiable adversary is same for all the x. In this case, P
′(x′|y) P (x|y) ≈ 1. In the second scenario, assume
the decision boundary is a perfect semicircle representing the local curvature of decision boundary and perturbed examples from both classes follow a uniform distribution, then the examples with ′−′ label in the outer arc condensed into the inner arc and vice versa for examples with ′+′ label moving to the external arc. Due to the existence of curvature, the area of the outer arc Sin is
greater than the inner arc Sout. Therefore, from Theorem 1 the expectation of P ′(x′|y) P (x|y) is greater than 1. Another detailed example is illustrated in Appendix B. In this later example, the uniform perturbation assumption replaced the post-mapping uniform distribution assumption, which is more realistic for adversarial scenario.
From the two extreme case analysis, we claim that the importance weight around decision boundary should be larger due to the local curvature, since any arbitrary x′ and x distribution pairs (local curvature is relatively larger than perturbation distance but its effect is not negligible on post adversarial distribution) can be seen as an intermediate case of two extremes. Therefore, we design a parametric weight function emphasizing the examples around the decision boundary in a symmetrical manner.
Similar to Zhang & Liang (2019), we define the margin of classifier f for a data point (x, y) as the probability difference between correct label and the most confident label among others. Specially, we use bound-based method such as IBP to get the margin under perturbation: P̂ = softmax(ẑK), where ẑK is the worst case logits as defined in equation 2, P̂ is the probability distribution calculated by softmax function given ẑK .
margin(f,x, y) = P̂ (f(x) = y)−max m 6=y P̂ (f(x) = m) (6)
The margin is positive when the example can be certified robust, otherwise the margin is negative. The magnitude of margin heuristically indicates the ”distance” of the example towards the current decision boundary. Left half of Figure 2 shows our implementation of re-weighting against vulnerability of examples, where the size of the labels indicate the weights and corresponding perturbations on clean data points. The most vulnerable examples are around the decision boundary, since the worst case scenario of a small perturbation could cross the decision boundary and fool the classifier. For the perturbed data points with smaller margin absolute value (closer to boundary), despite it being correctly classified, we assign larger weights to help the model focus on these data and accommodate more slightly mis-classfied data. On the other hand, for the data points farther from decision boundary, if it is mis-classfied (large negative margin), there is no need to assign large weight since the model capacity is limited. For correctly classified data, we also assign small weights because they are less related to the decision boundary.
We parameterize the importance weight in the following form:
ωi = e −γ∗(|margin(fθ,x′i,yi, )|) + α ∼ s(fθ,x′i, yi) (7)
where γ and α are both positive hyper-parameters to balance the effect of re-weighting. The full loss function after re-weighting is then defined as:
κ 1
n n∑ i=1 l(zK , y) + (1− κ) 1∑ ωi n∑ i=1 ωil(ẑK , y) (8)
where κ is a hyper-parameter to balance the trade-off between clean loss and re-weighted robustness loss.
As comparison with other re-weighting techniques, Zhang et al. (2020c) gives larger weights to the vulnerable points defined by least attack iterations to fool the model. Zeng et al. (2020) parameterizes the weight with a similar exponential function given attack-based margin. Both of their heuristic weight functions monotonically decrease against margin, in which case a heavily mis-classified point shares a large weight and a well classified point has a smaller weight. Our bound-based method method, backed up by a qualitatively theoretical analysis, emphasizes the data points symmetrically around the decision boundary.

heading: 3.2 AUTO-TUNING
text: In certified training, the training perturbation magnitude train is usually larger than the eval for optimal test accuracy. As Table 1 shows the robustness error against different train and eval, the optimal testing accuracy for test = 0.3, 0.35 were both achieved at train = 0.4 while smaller train fails certifying larger test.
With slightly larger perturbation during training, the model is more capable to handle unseen data in the testing. This observation is empirical, however, due to the limitation of model capacity, it is difficult for the model to handle all the examples with very large perturbation. When train = 0.45, we notice the training instability between different random seeds. Our intuitive explanation is shown in the right half of Figure 2: With large perturbation, for the vulnerable points around decision boundary, the worst case prediction (indicated by orange dots) protrudes the ideal boundary with a large margin and it is sometimes impossible for the model to fit these points. Including these worst case scenarios in training encourages over-fitting and compromises the model’s ability to find the right boundary. In implementation, very large perturbation does not help improve the verified accuracy. Besides, during the training stage, a fast growing perturbation schedule may potentially cause instability.
Following the above discussion, a natural solution would be customizing perturbation for each example in the training set. For the majority of points in the interior of decision zone, we would like to encourage large perturbation for the model to enforce a thick decision “gap” (grey colored thick line) for robustness consideration. Ideally, we would like to have the interior points to see large perturbations for optimal robustness and boundary points with moderate perturbations to avoid over-fitting. In the following, we propose an adaptive procedure to customize the perturbation for each example based on verified bound. The algorithm is shown in Algorithm 1.

heading: 4 EXPERIMENTS

heading: 4.1 DATASETS AND IMPLEMENTATION
text: We directly use the code from (Zhang et al., 2020a) provided for IBP and CROWN-IBP and leverage the same CNN architecture(DM-Large) and training scheduler on MNIST and CIFAR-10 datasets.
For MNIST IBP schedule, the neural network is trained for 100 epochs with a batch size of 100. The base scheduler of training starts from 0 after 3 warm-up epochs and linearly grows to desired maximum training with 17 ramp-up epochs, after which base stays at the targeted level. The Adam optimizer learning rate is initialized at 0.001 and decays by 10 times after 25 and 42 epochs. With MNIST CROWN-IBP schedule, the model is trained for 200 epochs with a batch size of 256. The ramp-up stage starts from epoch 10 and ends at epoch 50.
For CIFAR-10 dataset, a total of 3200 epochs including 320 warm-up epochs is used for training with a batch size of 1024 and learning rate of 0.0005 following two 10× decay after epoch 2600 and 3040. As a standard treatment, random horizontal flip and crops are used as data augmentation.
Algorithm 1: Bound-based Auto-Tuning algorithm Input: Training data set (X,Y ), standard perturbation scheduler, perturbation bound method, auto-eps maximum perturbation offset maxoff, network parameters θ, learning rate η initialize perturbation offset i,off = 0 for all the examples, initialize θ for epoch = 1,...,N do
for batch = 1,...,M do base ← scheduler() for i = 1,...,B do
i ← base − i,off get the upper and lower bound of classification logits with bound method: ˆz( i) = {z( i), z( i)} ← bound(fθ,xi, yi, i) calculate the softmax worst case probability: P̂ = softmax(ẑ( i)) calculate the margin: margini = P̂ (yi)−maxm 6=yi P̂ (m) if margini < 0 then
i,off ← −margini × i,maxoff else
i,off ← 0 end
end update the network parameter: θ ← θ − η∇θ ∑B i=1 l(fθ(xi + i, yi))/B
end end
Notice for CROWN-IBP implementation, we reduce the training batch size from 1024 to 256 due to memory constraint.
The hyper-parameter κ defined in equation 8 linearly decreases from 1 to 0.5 during ramp-up stage. According to Zhang et al. (2020a), this scheduler (κstart = 1, κend = 0.5) achieves better clean accuracy than (κstart = 0, κend = 0) and (κstart = 0, κend = 0) by ending up with weight on natural cross entropy loss. All the experiments were performed on 3 random seeds for reproducibility.
Our methods are generally applicable to any certifiable adversarial training method. In the next section, we first leverage IBP for illustrative examples followed by CROWN-IBP results.

heading: 4.2 RESULTS

heading: 4.2.1 EFFECTS OF RE-WEIGHTING
text: In Table 2, we show the effect of hyper-parameters used for the re-weighting under IBP, where a larger γ indicates a stronger re-distribution of weight for examples and α is a small number to prevent weight vanish when |margin| is close to 1. The hyper-parameters are evaluated on CIFAR10 at = 8/255 and MNIST at = 0.4. Our optimal hyper-parameter turns out to be γ = 5, α = 0.1 for both data sets. Re-weighting method gains 0.24% verified accuracy on MNIST and 0.82% on CIFAR-10.
The goal of re-weighting is to approximate the true adversarial distribution by sampling from clean data distribution. Unfortunately, it is difficult to visualize the intractable distribution. From another perspective, we can interpret re-weighting as concentration on the robustness decision boundary and encouragement for larger margin. Figure 3 shows the comparison of margin distribution for CIFAR-10 testing data set under testing = 8.8/255. With the vanilla model, the example margins
concentrate around the decision boundary. The re-weighting dilutes the example frequency to both sides, thus the classification results are less sensitive to perturbation change.

heading: 4.2.2 EFFECTS OF AUTO-TUNING
text: In robust training, a train usually produces good defensive model for eval which is slightly smaller than itself. Practitioners refrain from using an even larger due to the marginal gain of robustness accuracy with the cost of sacrificing natural accuracy.
The idea of using auto-tuning is to prevent improperly large perturbation for vulnerable points around decision boundary. When train is considerably larger than the testing , the worst case points exceed the decision boundary by a unrecoverable large margin due to model capacity. Our autotuning method trims the unnecessary perturbation to alleviate the counter effect for robust training.
Table 3 shows the hyper-parameters choice for auto-tuning . For the MNIST data set, we found the optimal hyper-parameter maxoff around 0.15 where the certified accuracy gains by 0.3% from baseline.
For the CIFAR data set, the standard train 8.8/255 is only 10% larger than the eval. In this case, our auto-tuning method performs worse compared to the baseline results because the extra 10% is necessary for certified training. By using larger train, it is possible to reach even smaller testing error. To show the effect of auto-tuning method, we will increase the train until the testing verified accuracy stabilizes. For train = 10/255, 14/255, 18/255, 22/255, we come up with verified accuracy = 70.62%± 0.62%, 70.50%± 0.62%, 70.31%± 0.83%, 71.19%± 0.21% which are roughly 2% lower than the standard result. We choose = 14/255 as the “sweet point”, beyond which any increase in does not provide any improvement in accuracy because the very large perturbation is harmful to training. With the optimal maxoff = 0.01, the verified accuracy is improved by 1.21% from baseline.

heading: 4.2.3 COUPLING OF TWO METHODS
text: By coupling two methods, we can further combine the improvements and achieve even better results. As shown in Table 6, for MNIST, using both optimal hyper-parameters from above individual tests we reach a verified accuracy of 8.01%, gaining 0.65% from baseline. For CIFAR-10, our best results beats the IBP baseline by 2.17%. We performed more experiments on other eval and other architecture and defer the results to Appendix C.

heading: 4.2.4 RESULTS ON CROWN-IBP
text: To illustrate that our methods generally work for all the certifiable training, we apply the same methods and optimal hyper-parameters from IBP setup directly to CROWN-IBP. For MNIST data, we achieves 0.32% improvement from baseline by re-weighting and 0.13% from auto-eps, combining the two is similar to using auto-eps only though. For CIFAR data, note that we use training batch size 256 instead of 1024 in Zhang et al. (2020a), the standard train 8.8/255 has verified error 68.10% ± 0.12% at eval = 8/255 from our experiments. By elevating the bulk train to 14/255, the verified error increases to 68.35%±0.43%. After applying the two methods, we achieve 66.72%± 0.7% and beat the baseline by 1.38%.

heading: 5 CONCLUSIONS
text: This paper proposed new methods to refine the decision boundary to improve the certifiable robustness accuracy. We prove the necessity to assign more weights towards adversarial examples around decision boundary by parameterizing the true adversarial distribution. A future direction could be exploring the adversarial mechanism for better approximation of re-weight function and promoting the idea of re-weighting to other non-adversarial tasks. For auto-tuning, our initial interest was to prevent extremely large train and a relatively large train is necessary to show the effect. In practice, we can increase train until accuracy stabilizes and achieve further optimal verified error. Our intuitive approach indeed finds a proper perturbation for each example. Given the fact that a larger train achieves optimal certifiable accuracy still exists as an empirical finding (Gowal et al., 2019; Zhang et al., 2020a), a rigorous theoretical thinking is needed to justify this approach.
ETHICS STATEMENT
This paper does not contain ethics concerns.

heading: A PROOF OF THEOREM 1
text: Theorem 1 (Restated). Given a binary classification task Rn −→ {+,−} with equal prior probability, assume the corresponding examples x+ and x− are uniformly distributed in region S+,S− ⊂ Rn,S+ ∩ S− = ∅. If there exists a bijection mapping m := S+ 7→ S−,S− 7→ S+ s.t. the postmapping example x′+ and x ′ − distribution remains uniform in each region, the expectation of conditional distribution ratio P ′(x′|y) P (x|y) over original distribution P (x, y) is great or equal than 1.
Proof. let x+,x−,x′+,x ′ − denote the pre-mapping and post-mapping examples for 2 labels, because both pre-mapping and post-mapping examples are uniformly distributed in each region, P (x+|y+), P (x−|y−), P ′(x′+|y+), P ′(x′−|y−) are constant. let S+ = ∮ x∈S+ dx, S− = ∮ x∈S− dx be the ”volume” of set S+,S−. Given total conditional probability equals 1:∫
x∈S+ P (x+|y+)d(x) = 1 ⇐⇒ P (x+|y+) ∫ x∈S+ d(x) = 1
⇐⇒ P (x+|y+) = 1/S+ Similarly we have other conditional probability equals the inverse of volume. Hence,
E(x,y)∼P [ P ′(x′|y) P (x|y) ] = P (y+) ∫ x∈S+ P (x+|y+) P ′(x′+|y+) P (x+|y+) d(x)
+ P (y−) ∫ x∈S− P (x−|y−) P ′(x′−|y−) P (x−|y−) d(x)
= 0.5( S+ S− + S− S+ ) ≥ 1
where the second equality comes from the balanced prior assumption(P (y+) = P (y−))
Notice we cannot directly cancel the conditional probability on the numerator and denominator, otherwise integrating x′ over dx is not tractable. The inequality holds when S− 6= S+.

heading: B A CONCRETE EXAMPLE ON IMPORTANCE WEIGHT EXPECTATION
text: Example 2. We assume label-balanced data x ∈ R2 and y ∈ {+,−} and positive constant σ, the clean data with label 1 were uniformly distributed in the inner ring Cin = {x|σ < ‖x‖2 < 2σ} and data with label 0 were uniformly distributed in the outer ring Cout = {x|2σ < ‖x‖2 < 3σ}. Then p(y = +) = p(y = −) = 0.5 and clean data distribution is: p(x|y) = 1 3πσ2 if y = +, σ < ‖x‖2 < 2σ 1
5πσ2 if y = −, 2σ < ‖x‖2 < 3σ 0 otherwise
assume the linear classifier f : R→ R uses r = ‖x‖2 as feature and outputs the logit for probability,
s.t. the probability after sigmoid function is pf (y|x) =
{ 1
1+es if y = + 1
1+e−s if y = − where s = r + 2σ The negative log-likelihood
NLL = −E(x,y)∼p(x,y)[log(pf (y|x))] = −p(y = +) ∫ p(x|y = +)log(pf (y = +|x))dx
− p(y = −) ∫ p(x|y = −)log(pf (y = −|x))dx
= −0.5( 1 3πσ2 ∫ r=2σ r=σ 1 1 + es 2πrdr + 1 5πσ2 ∫ r=3σ r=2σ
1
1 + e−s 2πrdr)
= −0.5( 1 3πσ2 ∫ s=0 s=−σ 1 1 + es 2π(s+ 2σ)ds+ 1 5πσ2 ∫ s=σ s=0
1
1 + e−s 2π(s+ 2σ)ds)
Notice the integral includes polylogarithm term thus the indefinite integral is not elementary function and it is unnecessary to attack the final integral. Instead, we apply adversarial directly to the above equation for (x, y) distribution. Calculate the adversarial gradient: for s ∈ [0, σ], dNLL(s)
ds = − 1 6πσ2 es 1+e−s 2π(s + 2σ), let ∆−(s) = d2NLL(s) ds2 = − 1 3σ2 1+e−s+e−s(s+2σ) (1+e−s)2 . For
s ∈ [−σ, 0], dNLL(s)ds = − 1 6πσ2 e−s 1+e−s 2π(s+ 2σ), let ∆+(s) = d2NLL(s) ds2 = − 1 3σ2 1+es−es(s+2σ) (1+es)2 .
∆+(s) and ∆−(s) denotes the attack gradient towards negative log-likelihood function on example (x, y) with s = ‖x‖2 + 2σ. Notice ∆+(s) > 0 and ∆−(s) < 0 because adversarial perturbs the correctly classified examples towards the decision boundary. Assume the attack step α = σ, there exist a mapping of attack m : R2×R→ R2×R. Because this is a 1 step attack on a 2D plane with gradient towards radial direction without projection, the mapping also corresponds to a verifiable worst case adversarial with max = σ under `2 norm. Rewrite (x, y) in the polar coordinate(r, θ, y),
(r′, θ′, y′) = m(r, θ, y) = { (r + σ, θ, y) if y = + (r − σ, θ, y) if y = −
After the attack, the importance ratio P ′(x′|y) P (x|y) = r r′ is inversely proportional to the radius change.
The expected importance ratio could be written as :
E(x,y)∼P [ P ′(x′|y) P (x|y)
] = P (y = −) ∫ P (x|y = −)P
′(x′|y = −) P (x|y = −) dx
+ P (y = +) ∫ P (x|y = +)P
′(x′|y = +) P (x|y = +) dx
= 0.5[ ∫ r=3σ r=2σ 1 5πσ2 r r − σ 2πrdr + ∫ r=2σ r=σ 1 3πσ2 r r + σ 2πrdr]
= 0.5[ ∫ t=3σ−σ t=2σ−σ 1 5πσ2 σ + t t 2π(σ + t)dt
+ ∫ t=2σ+σ t=σ+σ 1 3πσ2 −σ + t t 2π(−σ + t)dt]
= π[ 1
5πσ2 (σ2log(t) + 2σt+ t2/2) ∣∣∣∣t=3σ−σ t=2σ−σ
+ 1
3πσ2 (σ2log(t)− 2σt+ t2/2) ∣∣∣∣t=2σ+σ t=σ+σ
= 1
5σ2 (σ2log(2) + 3.5σ2) +
1
3σ2 (σ2log(1.5) + 0.5σ2)
≈ 1.14 > 1

heading: C MORE EXPERIMENTS

Review summaries:
This paper proposes bound-based weighted loss and epsilon auto-tuning to improve the performance of certifiable training. The insights of the improvements are mainly borrowed from well-developed adversarial training while they are customized for certifiable training considering bound margins provided bound propagation methods. The experimental results clearly show the improvements from individuals and the combination of the two methods.

This paper proposes two ideas for improving the performance of certified training. The first idea is to use assign weight for each input based on the margin to the decision boundary. The second idea is to use automatic scheduling of perturbation radius during training. They show that using these two ideas leads to improved certified robustness on MNIST and CIFAR-10 datasets.