Year: 2021

Abstract:
Interval Bound Propagation (IBP) is so far the base of state-of-the-art methods for training neural networks with certifiable robustness guarantees when potential adversarial perturbations present, while the convergence of IBP training remains unknown in existing literature. In this paper, we present a theoretical analysis on the convergence of IBP training. With an overparameterized assumption, we analyze the convergence of IBP robust training. We show that for a randomly initialized two-layer ReLU neural network with logistic loss, with sufficiently small perturbation radius and large network width, gradient descent for IBP training can converge to zero training robust error with a linear convergence rate for with a high probability, and at this convergence state the robustness certification by IBP can accurately reflect the true robustness of the network.

heading: 1 INTRODUCTION
text: It has been shown that deep neural networks are vulnerable against adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini & Wagner, 2017; Kurakin et al., 2016), where a human imperceptible adversarial perturbation can easily alter the prediction by neural networks. This poses concerns to safety-critical applications such as autonomous vehicles, healthcare or finance systems. To combat adversarial examples, many defense mechanisms have been proposed in the past few years (Kurakin et al., 2016; Madry et al., 2018; Zhang et al., 2019; Guo et al., 2018; Song et al., 2018; Xiao et al., 2020). However, due to the lack of reliable measurement on adversarial robustness, many defense methods are later broken by stronger attacks (Carlini & Wagner, 2017; Athalye et al., 2018; Tramer et al., 2020).
There are recently a line of robust training works, known as certified defense, focusing on training neural networks with certified robustness, where the evaluation of robustness needs to be provable – the network is considered robust on a test example if and only if the prediction is provably correct for any perturbation in a predefined set (e.g., a small `∞ ball) (Wang et al., 2018b; Bunel et al., 2018; Zhang et al., 2018; Wang et al., 2018c; Wong & Kolter, 2018; Singh et al., 2018; 2019; Weng et al., 2018; Xu et al., 2020). Unlike empirical methods that evaluate robustness with adversarial attacks and thus the evaluation can be limited by the strength of the attack algorithm, certified defense methods provide provable robustness guarantees without referring to any specific attack.
To obtain a neural network with certified robustness, a common practice is to derive a neural network verification method that computes the upper and lower bounds of output neurons given an input region under perturbation (e.g., a small `∞ ball around an unperturbed sample), and then train the neural network to optimize the loss defined not on the original output, but on the worst-case output produced by the verification method. Many methods along this line have been proposed in the past few years (Wong & Kolter, 2018; Wong et al., 2018; Mirman et al., 2018; Gowal et al., 2018; Raghunathan et al., 2018a; Zhang et al., 2020a). Among these methods, Interval Bound Propagation (IBP) (Mirman et al., 2018; Gowal et al., 2018) is a simple but effective and efficient method for certified robust training. It simply propagates the interval bound of each neuron through the network in the forward pass to obtain output bounds of the network. Most of the latest state-ofthe-art certified defense methods are still at least partly based on IBP training (Zhang et al., 2020a; Shi et al., 2021; Lyu et al., 2021; Zhang et al., 2021).
Despite being one of the most successful certified defense methods, the convergence properties of IBP training remained unknown. For natural neural network training (training without considering
adversarial perturbation, aka standard training), it has been shown that gradient descent for overparameterized networks can provably converge to a global minimizer with random initialization (Li & Liang, 2018; Du et al., 2019b;a; Jacot et al., 2018; Allen-Zhu et al., 2019; Zou et al., 2018). Compared to natural neural network training, IBP-based robust training has a very different training scheme, and thus requires a different convergence analysis. First, in the robust training problem, input data can contain adversarial perturbations, and the training objective is to minimize a robust loss rather than a natural loss. Second, IBP training essentially optimizes an augmented network which contains IBP bound computation rather than standard neural networks, as illustrated in Zhang et al. (2020a). Third, in IBP training, the activation state of each neuron depends on the certified bounds rather than the value in natural neural network computation, and this introduces additional perturbation-related terms in the convergence analysis for IBP.
In this paper, we conduct a theoretical analysis to study the convergence of IBP training. Following recent convergence analysis on Stochastic Gradient Descent (SGD) for natural training, we consider IBP robust training with gradient flow (gradient descent with infinitesimal step size) for a two-layer overparameterized neural network on a classification task. We summarize our contributions below:
• We provide the first convergence analysis for IBP-based certified robust training. On a two-layer overparameterized ReLU network with logistic loss, with sufficiently small perturbation radius and large network width, gradient flow with IBP has a linear convergence rate, and is guaranteed to converge to zero training error with high probability.
• Our result implies that IBP converges to a state where the certified robust accuracy measured by IBP bounds tightly reflects the true robustness of the network.
• We show additional perturbation-related conditions required to guarantee the convergence of IBP training so far, and identify additional challenges in the convergence analysis for IBP training compared to standard training.

heading: 2 RELATED WORK

heading: 2.1 CERTIFIED ROBUST TRAINING
text: The goal of certified robust training is to maximize the robust accuracy of the model under the evaluation by provable robustness verifiers. Some works add heuristic regularizations during adversarial training to improve certified robustness (Xiao et al., 2019; Balunovic & Vechev, 2020). Some others optimize a certified robust loss which is a certified upper bound of the loss function under all considered perturbations, computed from certified bounds by robustness verifiers. Among them, Wong & Kolter (2018); Mirman et al. (2018); Dvijotham et al. (2018); Wong et al. (2018); Wang et al. (2018a) used verification with linear relaxation for nonlinear activation functions, and Raghunathan et al. (2018b) used semi-definite relaxation. However, Interval Bound Propagation (IBP) (Mirman et al., 2018; Gowal et al., 2018) which computes and propagates an interval lower and upper bound for each neuron, has been shown as efficient and effective and can even outperform methods using more complicated relaxation as partly discussed by Lee et al. (2021); Jovanović et al. (2021). At least partly based on IBP, Zhang et al. (2020a) combined IBP with linear relaxation bounds; Lyu et al. (2021) designed a parameterized activation; Zhang et al. (2021) designed a 1-Lipschitz layer with `∞-norm computation before layers using IBP; Shi et al. (2021) improved IBP training with shortened training schedules. Yet, the state-of-the-art methods still contain IBP as an important part, and thus we focus on analyzing the convergence of IBP training in this paper.
On the theoretical analysis for IBP bounds, Baader et al. (2020) analyzed the universal approximation of IBP verification bounds, and Wang et al. (2020) extended the analysis to other activation functions beyond ReLU. However, to the best of our knowledge, there is still no existing work analyzing the convergence of IBP training.
The aforementioned methods for certified robustness target at robustness with deterministic certification. There are also some other works on probabilistic certification such as randomized smoothing (Cohen et al., 2019; Li et al., 2019; Salman et al., 2019) which is out of our scope.

heading: 2.2 CONVERGENCE OF STANDARD NEURAL NETWORK TRAINING
text: There have been many works analyzing the convergence of standard neural network training. For two-layer ReLU neural networks with quadratic loss, Du et al. (2019b) proved that randomly initialized gradient descent can converge to a globally optimum with a large enough network width m which is polynomial in the number of training examples n. Ji & Telgarsky (2019) pushed the requirement of network width m to a polylogarithmic function. For deep neural networks, Allen-Zhu et al. (2019) proved that for randomly initialized ReLU deep neural networks, gradient descent has a linear convergence rate for various loss functions with width polynomial in network depth and number of training examples. And Chen et al. (2019) proved that a polylogarithmic width is also sufficient for deep neural networks to converge to the optimal point. However, these works only focus on standard training, and cannot be directly adapted to the robust training setting.

heading: 2.3 CONVERGENCE OF EMPIRICAL ADVERSARIAL TRAINING
text: Robust training including both certified training and empirical adversarial training is essentially a min-max optimization. For a training data distribution X , the objective for learning a model fθ parameterized by θ can be written as1:
arg min θ E(x,y)∼X max ∆∈S `(fθ(x + ∆), y), (1)
where (x, y) is an example sampled from X , `(·, y) is the loss function for ground truth y, S is the space of all possible perturbations. Empirical adversarial training approximately solves the inner minimization by running adversarial attacks. Some works have analyzed the convergence of adversarial training. Wang et al. (2019) considered a first-order stationary condition for solving the inner constrained maximization problem. Gao et al. (2019); Zhang et al. (2020b) showed that overparameterized networks with projected gradient descent can converge to a state where the surrogate robust loss by adversarial attack is close to the true robust loss (i.e., the inner maximization by adversarial attack is mostly optimal) and the robust loss is close to 0. Zou et al. (2021) showed that adversarial training provably learns robust halfspaces in the presence of noise.
However, there is a significant difference between empirical adversarial training and IBP training. In adversarial training, there is a concrete perturbation ∆ generated for the inner maximization, and there is a concrete adversarial input x+ ∆. However, in IBP-based training, the inner maximization is computed from certified bounds, where for each layer, the interval certified bounds of each neuron are computed independently. Thereby, the certified bounds of the network generally no longer correspond to any concrete ∆. Due to this significant difference, prior theoretical analysis on adversarial training, which required there to be a concrete ∆ for inner maximization, is not applicable to IBP.

heading: 3 PRELIMINARIES

heading: 3.1 NEURAL NETWORKS
text: We consider a similar network architecture as used in Du et al. (2019b) – a two-layer ReLU network. Unlike Du et al. (2019b) which considered a regression task with a square loss, here we consider a classification task where IBP is usually used, and we consider binary classification for simplicity. On a training dataset {(xi, yi)}ni=1, for every i ∈ [n], (xi, yi) is a training example with d-dimensional input xi(xi∈Rd) and label yi(yi∈{±1}), and the network output is:
f(W,a,xi) = 1√ m m∑ r=1 arσ(w > r xi), (2)
where m is the width of hidden layer (the first layer) in the network, W ∈ Rm×d is the weight matrix of the hidden layer, wr(r ∈ [m]) is the r-th row of W, a ∈ Rm is the weight vector of the second layer (output layer) with elements a1, · · · , am, and σ(·) is the activation function. We assume the activation is ReLU as IBP is typically used with ReLU. For initialization, we set ar ∼
1Here we use notations to denote the general robust training problem, but in our later theoretical analysis, we will have different notations for a simplified problem setting.
unif[{1,−1}] and wr ∼N(0, I). Following Du et al. (2019b), we assume the second layer is fixed after initialization, and we only train the first layer. Since we consider binary classification, we use a logistic loss. For training example (xi, yi), we define ui(W,a,xi) := yif(W,a,xi), and then the loss for this example is computed as l(ui(W,a,xi)) = log(1 + exp(−ui(W,a,xi))), and the standard training loss on the whole training set is
L = n∑ i=1 l(ui(W,a,xi)) = n∑ i=1 log ( 1 + exp(−ui(W,a,xi)) ) . (3)

heading: 3.2 CERTIFIED ROBUST TRAINING
text: In the robust training setting, for some original input xi (∀i ∈ [n]), we consider that the actual input to the model may be perturbed into xi + ∆i by perturbation ∆i. For a widely adopted setting in the adversarial robustness area, we consider `∞ perturbations, where the perturbation is bounded by an `∞ ball with radius (0 ≤ ≤ 1), i.e., ‖∆i‖∞ ≤ . For the convenience of subsequent analysis and without loss of generality, we set the following assumption on each xi: Assumption 1. ∀i ∈ [n], we assume there exists some ξ > 0, such that xi ∈ [ , 1]d, ‖xi‖2 ≥ ξ.
This assumption can be easily satisfied by normalizing the training data. Through out the remaining part of this paper, we assume this assumption holds. In Du et al. (2019b), they also assume there are no parallel data points, and in our case we assume this holds under any possible perturbation, formulated as: Assumption 2. For perturbation radius , we assume that
∀i, j ∈ [n], i 6= j, ∀x′i ∈ B∞(xi, ), ∀x′j ∈ B∞(xj , ), x′i ∦ x′j , (4)
where B∞(xi, ) stands for the `∞ ball with radius centered at xi.
IBP training computes and optimizes a robust loss L, which is an upper bound of the standard loss for any possible perturbation ∆i(∀i ∈ [n]):
L ≥ n∑ i=1 max ∆i { log ( 1 + exp(−yif(W,a,xi + ∆i)) ) | ‖∆i‖∞ ≤ } . (5)
To compute L, since log(·) and exp(·) are both monotonic, for every i ∈ [n], IBP first computes the lower bound of ui(W,a,xi + ∆i) for ‖∆i‖∞ ≤ , denoted as ui. Then the IBP robust loss is:
L = n∑ i=1 log(1 + exp(−ui)), where ui ≤ min ∆i ui(W,a,xi + ∆i) (i = 1, 2, · · · , n). (6)
For all i ∈ [n], IBP computes and propagates an interval lower and upper bound for each neuron in the network, and then ui is equivalent to the lower bound of the final output neuron. Initially, the interval bound of the input is [xi − · 1,x + · 1]. Given constraints of ∆i, we have the interval bound of each neuron in the first layer:
∀r ∈ [m], σ ( w>r xi − ‖wr‖1 ) ≤ σ ( w>r (xi + ∆i) ) ≤ σ ( w>r xi + ‖wr‖1 ) . (7)
Then these interval bounds are propagated to the second layer. We focus on the lower bound of ui, which can be computed from the bounds of the first layer by considering the sign of multiplier yiar:
ui = yi 1√ m m∑ r=1 arσ(w > r (xi + ∆i)) (8)
≥ 1√ m m∑ r=1 1(yiar = 1)σ ( w>r xi − ‖wr‖1 ) + 1(yiar = −1)σ ( w>r xi + ‖wr‖1 ) := ui. (9)
Then the IBP robust loss can be obtained as Eq. (6). And we define u := (u1, u2, · · · , un). For certified robust training, we can define a certified robust accuracy in IBP training, which is the percentage of examples that IBP bounds can successfully certify that the prediction is correct
for any possible perturbation. For every example i(i ∈ [n]), it is considered as classified correctly and robustly under IBP verification, if and only if ui > 0 where ui is computed from IBP. Let ũi be the exact solution of the minimization in Eq. (6) rather than relaxed IBP bounds, we can also define a true robust accuracy, where the robustness of prediction requires ũi > 0. The certified robust accuracy by IBP is a provable lower bound of the true robust accuracy.

heading: 3.3 GRADIENT FLOW
text: To analyze the convergence of IBP training, we adopt a continuous time analysis with gradient flow, which is gradient descent with infinitesimal step size and is also used in prior works for standard training (Arora et al., 2018; Du et al., 2019a;b). In the gradient flow for IBP training,
∀r ∈ [m], dwr(t) dt = − ∂L(t) ∂wr(t) , (10)
where w1(t),w2(t), · · · ,wm(t) are rows of the weight matrix at time t, and L(t) is the IBP robust loss defined as Eq. (6) using weights at time t.

heading: 3.4 GRAM MATRIX
text: Under the gradient flow setting as Eq. (10), for all i ∈ [n], we analyze the dynamics of ui during IBP training, and we use ui(t) to denote the value of ui at time t:
d dt ui(t) = m∑ r=1 〈 ∂ui(t) ∂wr(t) , dwr(t) dt 〉 = n∑ j=1 −l′(uj)Hij(t), (11)
where l′(uj) is the derivative of the loss, H(t) is defined as Hij(t) = ∑m r=1 〈 ∂ui(t) ∂wr(t) , ∂uj(t) ∂wr(t) 〉 (∀1 ≤ i, j ≤ n), and we provide a detailed derivation in Appendix B.1. With the definition of H, we can describe the dynamic of ui under the gradient flow using H.
From Eq. (9), ∀i ∈ [n], r ∈ [m], derivative ∂ui(t)∂wr(t) can be computed as follows:
∂ui(t) ∂wr(t) = 1√ m yiar
( A+ri(t)(xi − sign(wr(t))) +A − ri(t)(xi + sign(wr(t))) ) , (12)
where sign(wr(t)) is element-wise for wr(t), and we define indicators
A+ri(t) := 1(yiar = 1,wr(t) >xi − ‖wr(t)‖1 > 0), (13) A−ri(t) := 1(yiar = −1,wr(t) >xi + ‖wr(t)‖1 > 0), (14)
where terms (wr(t)>xi − ‖wr(t)‖1 > 0) and (wr(t)xi + ‖wr(t)‖1 > 0) stand for the active status of the activation. Then elements in H can be written as (∀1 ≤ i, j ≤ n):
Hij(t) = 1
m yiyj m∑ r=1 a2r ( A+ri(t)(xi − sign(wr(t))) +A − ri(t)(xi + sign(wr(t))) )> ( A+rj(t)(xj − sign(wr(t))) +A − rj(t)(xj + sign(wr(t))) ) (15)
= 1
m yiyj
( x>i xj m∑ r=1 αrij(t)− ( m∑ r=1 (βrij(t)xi + βrji(t)xj) > sign(wr(t)) ) + 2d m∑ r=1 γrij(t) ) ,
(16)
where αrij(t) = (A+ri(t) +A − ri(t))(A + rj(t) +A − rj(t)), (17)
βrij(t) = (A + ri(t) +A − ri(t))(A + rj(t)−A − rj(t)), (18)
γrij(t) = (A + ri(t)−A − ri(t))(A + rj(t)−A − rj(t)). (19)
Further, we define Gram matrix H∞ which is the elementwise expectation of H(0), to characterize H(0) on the random initialization basis:
∀1 ≤ i, j ≤ n, H∞ij := E∀1≤r≤m,wr∼N(0,I),ar∼unif[{−1,1}]Hij(0), (20)
where Hij(0) depends on the initialization of weights wr and ar. We also define λ0 := λmin(H∞) as the smallest eigenvalue of H∞. We will show that H∞ is positive definite, and with high probability, we can upper bound the difference between H(0) and H∞, and thereby we can prove that H(0) is positive definite.

heading: 4 CONVERGENCE ANALYSIS FOR IBP TRAINING
text: We present the following main theorem which shows the convergence of IBP training under certain conditions on perturbation radius and network width: Theorem 1 (Convergence of IBP Training). Suppose Assumption 1 and 2 hold for the training data, and the `∞ perturbation radius satisfies ≤ O(min( δ 2λ20 d2.5n3 , √ 2dR log( √
2πd R ξ) )), where R = cδλ0d1.5n2 , c = √
2πξ 384 . For a two-layer ReLU network (Eq. (2)), suppose its width for the first hidden layer satisfies m ≥ Ω ((
d1.5n4δλ0 δ2λ20− d2.5n4
)2) , and the network is randomly initialized as ar ∼ unif[{1,−1}],wr ∼
N(0, I), with the second layer fixed during training. Then for any confidence δ(0 < δ < 1), with probability at least 1− δ, IBP training with gradient flow can converge to zero training error.
In the following part of this section, we provide the proof sketch for the main theorem.

heading: 4.1 STABILITY OF THE GRAM MATRIX DURING IBP TRAINING
text: We first analyze the stability of the Gram matrix H during training, since H can be used to characterize the dynamic of the training as defined in Eq. (11). We aim to show that when there exists some R such that the change of wr(∀r ∈ [m]) is restricted to ‖wr(t) − wr(0)‖2 ≤ R during training, we can guarantee that the minimum eigenvalue of H(t) remains positive with high probability. This property will be later used to reach the conclusion on the convergence. We defer the derivation for the constraint on R to the later part of this section.
For all r ∈ [m], with the aforementioned constraint on wr(t), we first show that during the IBP training, most of αrij(t), βrij(t), γrij(t) terms in Eq. (16) remain the same as their initialized values (t = 0). This is because for for each of αrij(t), βrij(t), γrij(t), the probability that its value changes during training can be upper bounded by a polynomial inR, and thereby the probability can be made sufficiently small for a sufficiently small R, as the following lemma shows: Lemma 1. ∀r ∈ [m], at some time t > 0, suppose ‖wr(t) −wr(0)‖2 ≤ R holds for some R, and ≤ √ 2dR
log( √
2πd R ξ)
holds, then for all 1≤ i, j≤n, we have
Pr(αrij(t) 6= αrij(0)),Pr(βrij(t) 6= βrij(0)),Pr(γrij(t) 6= γrij(0)) ≤ 12√ 2πξ
(1 + ) √ dR := R̃.
(21)
The full proof for the lemma is provided in Appendix A.1. Here we give a overview of the proof. Probabilities in Lemma 1 can be bounded as long as the probability that each of indicator A+ri(t), A − ri(t), A + rj(t), A − rj(t) changes can be upper bounded respectively. When the change of wr(t) is bounded, the indicators can change during the training only if at initialization |wr(0)>xi ± ‖wr(0)‖1| is sufficiently small with |wr(0)>xi ± ‖wr(0)‖1| ≤ (1 + ) √ dR as we show in the proof, whose probability can be upper bounded (the notation ± here means the analysis is consistent for both + and − cases). To upper bound this probability, our analysis is different compared to that for standard training in Du et al. (2019b), because we have additional perturbationrelated terms ‖wr(0)‖1. Du et al. (2019b) simply used the anti-concentration of standard Gaussian distribution to bound Pr(|wr(0)>xi|) ≤ R (they did not have √ d on the right-hand-side due to a different assumption on ‖x‖). Here when ‖wr(0)‖1 presents for the IBP case, we split the original
probability into two parts, Pr(|wr(0)>xi|) ≤ 2(1 + ) √ dR and Pr( ‖wr(0)‖1 ≤ (1 + ) √ dR), and then combine the results to upper bound the original probability. The first probability can still be bounded by anti-concentration, while the second probability can be bounded by the tail bound of standard Gaussian. Thereby we can prove the lemma.
Then we can then bound the change of the Gram matrix, i.e., ‖H(t)−H(0)‖2: Lemma 2. ∀r ∈ [m], at some time t > 0, suppose ‖wr(t)−wr(0)‖2 ≤ R holds for some constant R, for any confidence δ(0 < δ < 1), with probability at least 1− δ, it holds that
‖H(t)−H(0)‖2 ≤ 12(1 + )(1 + 2 + 2)d1.5n2√
2πξδ R. (22)
It can be proved by first upper bound E[|Hij(t)−Hij(0)|](∀1 ≤ i, j ≤ n), using Lemma 1, and then by Markov’s inequality, we can upper bound ‖H(t)−H(0)‖2 with high probability. We provide the proof in Appendix A.2. And by triangle inequality, we can also lower bound λmin(H(t)): Corollary 1. ∀r ∈ [m], at some time t > 0, suppose ‖wr(t) − wr(0)‖2 ≤ R holds for some constant R, for any confidence δ(0 < δ < 1), with probability at least 1− δ, it holds that
λmin(H(t)) ≥ λmin(H(0))− 12(1 + )(1 + 2 + 2)d1.5n2√
2πξδ R, (23)
where λmin(·) stands for the minimum eigenvalue.
We also need to lower bound λmin(H(0)) to lower bound λmin(H(t)). Given Assumption 2, we show that the minimum eigenvalue of H∞ is positive. Lemma 3. When the dataset satisfies Assumption 2, λ0 := λmin(H∞) > 0 holds true.
The lemma can be similar proved as Theorem 3.1 in Du et al. (2019b), but here we have a different Assumption 2 which considers perturbations. We discuss in more detail in Appendix A.3. Then we can lower bound λmin(H(0)) by Lemma 3.1 from Du et al. (2019b): Lemma 4 (Lemma 3.1 from Du et al. (2019b)). If λ0 > 0, for any confidence δ(0 < δ < 1), take m = Ω(n 2
λ20 log(nδ )), then with probability at least 1− δ, it holds true that λmin(H(0)) ≥ 3 4λ0.
Although we have different values in the Gram matrix H(0) for IBP training compared to the Gram matrix in Du et al. (2019b) for standard training, we can still adopt their original lemma because their proof by Hoeffding’s inequality is general for values in H(0) given the definition on λ0.
Given λmin(H(0)) ≥ 34λ0, we can guarantee that λmin(H(t)) remains positive by solving an inequality and choosing a proper R such that
λmin(H(t)) ≥ λmin(H(0))− 12(1 + )(1 + 2 + 2)d1.5n2√ 2πξδ R ≥ λ0 2 , (24)
as shown in the following lemma (proved in Appendix A.4): Lemma 5. For any confidence δ(0 < δ < 1), ∀r ∈ [m], suppose ‖wr(t) − wr(0)‖2 ≤ R holds, where R = cδλ0d1.5n2 with c = √ 2πξ 384 , then probability at least 1− δ, λmin(H(t)) ≥ λ0 2 holds.
Therefore, we have shown that with overparameterization (required by Lemma 4), when wr is relatively stable during training for all r ∈ [m], i.e., the maximum change on wr(t) is upper bounded during training (characterized by the `2 norm of weight change restricted by R), H(t) is also relatively stable and remains positive definite with high probability.

heading: 4.2 CONVERGENCE OF THE IBP ROBUST LOSS
text: Next, we can derive the upper bound of the IBP loss during training. In the following lemma, we show that when H(t) remains positive definite, the IBP loss L(t) descends in a linear convergence rate, and meanwhile we have an upper bound on the change of wr(t) w.r.t. time t.
Lemma 6. Suppose for 0 ≤ s ≤ t, λmin(H(t)) ≥ λ02 , we have L(t) ≤ exp ( 2L(0) ) L(0) exp ( − λ0t
2
) , ‖wr(t)−wr(0)‖2 ≤
nt√ m . (25)
This lemma is proved in Appendix A.5, which follows the proof of Lemma 5.4 in Zou et al. (2018). In this lemma, to guarantee that λmin(H(s)) ≥ λ02 for 0 ≤ s ≤ t, by Lemma 5, we only require
∀r ∈ [m], ‖wr(t)−wr(0)‖2 ≤ nt√ m ≤ R = cδλ0 d1.5n2 ⇒ t ≤ cδλ0
√ m
d1.5n3 . (26)
Meanwhile, for each example i, the model can be certified by IBP on example i with any `∞ perturbation within radius , if and only if ui > 0, and this condition is equivalent to l(ui) < κ, where κ := log(1 + exp(0)). Therefore, to reach zero training error on the whole training set at time t, we can require L(t) < κ, which implies that ∀1 ≤ i ≤ n, l(ui) < κ. Then with Lemma 6, we want the upper bound of L(t) to be less than κ:
L(t) ≤ exp ( 2L(0) ) L(0) exp ( − λ0t
2
) < κ⇒ t > 4
λ0
( log ( L(0)
κ
) + L(0) ) . (27)
To make Eq. (27) reachable at some t, with the constraint in Eq. (26) we require:
4
λ0
( log ( L(0)
κ
) + L(0) ) < cδλ0 √ m
d1.5n3 . (28)
The left-hand-side of Eq. (28) can be relaxed as
4
λ0
( log ( L(0)
κ
) + L(0) ) = 4
λ0 (L(0) + log(L(0))− log(κ)) ≤ 4 λ0 (2L(0)− log(κ)),
then the requirement Eq. (28) can be relaxed as
4 λ0 (2L(0)− log(κ)) < cδλ0
√ m
d1.5n3 ⇒ L(0) + c0 <
c′δλ20 √ m
d1.5n3 , (29)
where c′ := c8 and c0 are positive constants.
Since L(0) has randomness from the randomly initialized weight W, we need to upper bound the value of L(0) as we show in the following lemma (proved in Appendix A.6 by concentration): Lemma 7. In natural training, for any confidence δ(0 < δ < 1), with probability at least 1 − δ, L(0) = O(nδ ) holds. In IBP training, for any confidence δ(0 < δ < 1), with probability at least 1− δ, L(0) = O(n √ md δ + n δ ) holds.
And this lemma implies that with large n and m, there exist constants c1, c2, c3 such that
L(0) ≤ c1n √ md
δ + c2n δ + c3. (30)
Plug Eq. (30) into Eq. (29), and then requirement Eq. (29) can be relaxed into:
c′δλ20 √ m d1.5n3 > c1n √ md δ + c2n δ + c3 + c0 ⇒ ( c′δλ20 d1.5n3 − c1nd δ ) √ m > c2n δ + c4, (31)
where c4 := c3 + c0 is a constant. As long as Eq. (31) holds, Eq. (28) also holds, and thereby IBP training is guaranteed to converge to zero IBP robust loss on the training set.

heading: 4.3 PROVING THE MAIN THEOREM
text: Finally, we are ready to prove the main theorem. To make Eq. (28) satisfied, we want to make its relaxed version, Eq. (31), hold by sufficiently enlarging m. This requires that the coefficient of √ m in Eq. (31) , c ′δλ20
d1.5n3 − c1nd δ to be positive, and we also plug in the constraint on in Lemma 1:
c′δλ20 d1.5n3 − c1nd δ
> 0, ≤ √ 2dR log( √
2πd R ξ)
⇒ < min( c ′δ2λ20
c1d2.5n3 ,
√ 2dR
log( √
2πd R ξ)
). (32)
Then by Eq. (31), our requirement on width m is
m >
( c2n δλ0
+ c4 c′δλ20 d1.5n3 − c1nd δ
)2 ⇒ m ≥ Ω (( d1.5n4δλ0 δ2λ20 − d2.5n4 )2) . (33)
This completes the proof of the main theorem.
In our analysis, we focus on IBP training with > 0. But IBP with = 0 can also be viewed as standard training. By setting = 0, ifm ≥ Ω(n 8d3
λ40δ 4 ), our result implies that for any confidence δ(0 <
δ < 1), standard training with logistic loss also converges to zero training error with probability at least 1− δ. And as gets larger, the required m for convergence also becomes larger.

heading: 5 EXPERIMENTS
text: We further conduct experiments to compare the convergence of networks with different width m for natural training and IBP training respectively. We use the MNIST (LeCun et al., 2010) dataset and choose digit images with label 2 and 5 to construct a binary classification dataset. And we use a two-layer fully-connected ReLU network with a variable width. In each experiment, we train the model for 70 epochs. For IBP training, we keep fixed throughout the whole training process. For all the experiments, we use the SGD optimizer. We present results in Figure 1. First, compared with standard training, for the same network widthm, IBP has higher training errors (Figure 1a). Second, for relatively large ( = 0.04), even if we enlarge m up to 80,000 which is limited by the memory of a single GeForce RTX 2080 GPU, IBP certified robust error is far away from 0 (Figure 1a). This is consistent to our main theorem that when is too large, simply enlarging m can not guarantee the convergence. Moreover, when grows even larger, it can be difficult to even start the training, although standard training is possible. IBP training stucks in a local minima of random guess (with errors close to 50%) at the beginning of training (Figure 1b). Therefore in IBP-based training, existing works typically use a scheduling on to gradually increase from 0 until the target value. Theoretically, we believe that this is partly because λ0 can be very small with a large perturbation, and then the training can be much more difficult, while this difficulty cannot be alleviated by simply enlarging the network width m. Overall, the empirical observations match our theoretical results.

heading: 6 CONCLUSION
text: In this paper, we present the first theoretical analysis of IBP-based certified robust training, and we show that IBP training can converge to zero training error with high probability, under certain conditions on perturbation radius and network width. Meanwhile, since the certified robust accuracy by IBP is a lower bound of the true robust accuracy (see Section 3.2), and we have shown that it can converge to 100% on the training set, the true robust accuracy also converges to 100% on the training set. Therefore, our results also imply that upon convergence, the certification by IBP accurately reflects the true robustness of the network. However, our results have a condition requiring a small upper bound on . For future work, it will be interesting to study how to relax this condition, extend our analysis to deeper networks, or take the effect of scheduling into consideration.

heading: ETHICS STATEMENT
text: This work is basically a theoretical analysis on an existing method for training certifiably robust neural networks. We believe there is no potential ethical issue in our work.

heading: REPRODUCIBILITY STATEMENT
text: For all our theoretical results, the assumptions are stated clearly, and the complete proof can be found either in the main text or the appendix. We only have a small toy experiment by running IBP training with the open-source code from Shi et al. (2021), and any difference in the setting has been fully described in Section 5. Therefore, the results are reproducible.

heading: A PROOF OF LEMMAS

heading: A.1 PROOF OF LEMMA 1
text: Proof. For all i ∈ [n], r ∈ [m], we first consider the change of indicator 1(wr(t)>xi± ‖wr(t)‖1 > 0) during training compared to the value at t = 0 (the notation ± here means the analysis is consistent for both + and− cases). Under the constraint that ‖wr(t)±wr(0)‖2 ≤ R and ‖xi‖∞ ∈ [0, 1]d, we have (see Appendix B.2 for details):∣∣wr(t)>xi ± ‖wr(t)‖1 − (wr(0)>xi ± ‖wr(0)‖1)∣∣ ≤ (1 + )√dR. (34) Thereby, if sign(wr(t)>xi ± ‖wr(t)‖1) 6= sign(wr(0)>xi ± ‖wr(0)‖1), then at initialization, we must have
|wr(0)>xi ± ‖wr(0)‖1| ≤ (1 + ) √ dR. (35)
We want to upper bound the probability that Eq. (35) holds. It is easy to show that if the following two inequalities hold, then Eq. (35) does not hold for sure:
|wr(0)>xi| ≥ 2(1 + ) √ dR, (36)
‖wr(0)‖1 ≤ (1 + ) √ dR. (37)
Therefore,
Pr ( |wr(0)>xi ± ‖wr(0)‖1| ≤ (1 + ) √ dR ) (38)
≤ 1− Pr ( |wr(0)>xi| ≥ 2(1 + ) √ dR and ‖wr(0)‖1 ≤ (1 + ) √ dR ) . (39)
For Eq. (36), by anti-concentration inequality for Gaussian, we have
Pr(|wr(0)>xi| ≤ 2(1 + ) √ dR) ≤ 4(1 + ) √ dR√
2πξ . (40)
In other words, with probability at least 1 − 4(1 + ) √ dR/( √ 2πξ), Eq. (36) holds. And for Eq. (37), by the tail bound of standard Gaussian and union bound, we have
Pr( ‖wr(0)‖1 ≤ (1 + ) √ dR) ≥ 1− 2d exp ( − 2(1 + ) 2dR2
2
) . (41)
Combining Eq. (40) and Eq. (41), Eq. (35) holds with at most the following probability
4(1 + ) √ dR√
2πξ + 2d exp
( − 2(1 + ) 2dR2
2
) . (42)
Here we require to be sufficiently small such that
(1 + ) √ dR√
2πξ ≥ d exp
( − 2(1 + ) 2dR2
2
) (43)
and we can solve the inequality to obtain an upper bound for (detailed in Appendix B.3):
≤ √ 2dR log( √
2πd R ξ)
, (44)
and in this case Eq. (42) holds with probability at least
6√ 2πξ
(1 + ) √ dR.
Therefore, we upper bound the probability: Pr ( sign(wr(t) >xi ± ‖wr(t)‖1) 6= sign(wr(0)>xi ± ‖wr(0)‖1) ) ≤ 6√
2πξ (1 + )
√ dR.
Thereby
∀i ∈ [n], r ∈ [m], Pr(A+ri(t) 6= A + ri(0)),Pr(A − ri(t) 6= A − ri(0)) ≤ 6√ 2πξ
(1 + ) √ dR.
Note that at least one of A+ri(t) and A − ri(t) always remains zero during training, because condition yiar = 1 in A+ri(t) and condition yiar = −1 in A − ri(t) are mutually exclusive. Then
Pr(A+ri(t) +A − ri(t) 6= A + ri(0) +A − ri(0)) ≤ 6√ 2πξ
(1 + ) √ dR,
Pr(A+ri(t)−A − ri(t) 6= A + ri(0)−A − ri(0)) ≤ 6√ 2πξ
(1 + ) √ dR.
Next we can upper bound the probability that each of αrij(t), βrij(t), γrij(t) (∀i, j ∈ [n], r ∈ [m]) changes respectively:
Pr(αrij(t) 6= αrij(0)),Pr(βrij(t) 6= βrij(0)),Pr(γrij(t) 6= γrij(0)) ≤ 12√ 2πξ
(1 + ) √ dR.

heading: A.2 PROOF OF LEMMA 2
text: Proof. With Lemma 1, we can bound the expectation of the change for each element in H(t) (Eq. (16)) as:
E[|Hij(t)−Hij(0)|] ≤ 1 m E ( mR̃‖xi‖2‖xj‖2 + mR̃ ( (‖xi‖2 + ‖xj‖2)‖ sign(wr(t))‖2 ) + 2dmR̃ ) ≤ R̃d(1 + 2 + 2)
= 12(1 + )(1 + 2 + 2)d1.5√
2π (∀i, j ∈ [n])
Then by Markov’s inequality, we have that with probability at least 1− δ,
‖H(t)−H(0)‖2 ≤ ∑
i∈[n],j∈[n]
|Hij(t)−Hij(0)| ≤ 12(1 + )(1 + 2 + 2)d1.5n2√
2πξδ R.

heading: A.3 PROOF OF LEMMA 3
text: Proof. First for simplicity, we define
φ(xi)(wr(0)) = yi(xi + κi sign(wr(0))1(wr(0) >(xi + ρi sign(wr(0))) > 0)
where (ρi = −A+ri(0) +A − ri(0)) ∈ {1,−1}.
Similar as Theorem 3.1 in Du et al. (2019b), we need to prove that if η1, ..., ηn ∈ R satisfy η1φ(xi)(wr(0)) + ... + ηnφ(xn)(wr(0)) = 0 a.e., we have ηi = 0 for all i. In Theorem 3.1 in Du et al. (2019b), it is proved that if xi ∦ xj ,∀i 6= j, for φ(xi)(w) = xi1(w>xi), this statement is true. Similarly if ∀i, j ∈ [n], i 6= j,∀x′i ∈ B∞(xi, ),∀x′j ∈ B∞(xj , ), x′i ∦ x′j , this statement is true.

heading: A.4 PROOF OF LEMMA 5
text: The lemma can be proved by solving inequality Eq. (24).
Proof. According to Lemma 4, λmin(H(0)) ≥ 34λ0. And with Eq. (23), in order to ensure λmin(H(t)) ≥ λ02 , we can make
12(1 + )(1 + 2 + 2)d1.5n2√ 2πξδ R ≤ λ0 4 .
This yields
R ≤ √
2πξδλ0 48(1 + )(1 + 2 + 2)d1.5n2 .
Note that 0 ≤ ≤ 1, and thus 1 + ≤ 2 and 1 + 2 + 2 ≤ 4 can be upper bounded by constants respectively. Then we can take
R ≤ √
2πξδλ0 384d1.5n2 = cδλ0 d1.5n2
, where c = √ 2πξ
384 ,
and in this case λmin(H(t)) ≥ λ02 w.p. at least 1− δ probability.

heading: A.5 PROOF OF LEMMA 6
text: Proof. The proof of this lemma is inspired by the proof of Lemma 5.4 in Zou et al. (2018). In our proof, we define f(x) = (f(x1), f(x2), ..., f(xn)), where f(x) is a scalar function and x is a vector of length n. When λmin(H)(s) ≥ λ02 holds for 0 ≤ s ≤ t, we can bound the derivative of L(t):
dL(u)
dt = n∑ i=1 l′(ui) ∂ui ∂t
= − n∑ i=1 l′(ui) n∑ j=1 l′(uj)Hij
= −l′(u)>Hl′(u) (i) ≤ −λ0 2 n∑ i=1 l′(ui) 2
(ii)
≤ λ0 2 n∑ i=1 l′(ui)
(iii)
≤ −λ0 2 n∑ i=1 min(1/2, l(ui) 2 )
(iv)
≤ −λ0 2 min
( 1/2, n∑ i=1 l(ui) 2 ) = −λ0
2 min(1/2,
L(u)
2 )
(v) ≤ −λ0 2
1
2 + 2/L(u)
where (i) is due to λmin(H) ≥ λ0, (ii) is due to−l′(u) ≤ 1, (iii) holds due to the following property of cross entropy loss −l′(u) ≥ min(1/2, l(u)2 ), (iv) holds due to the function min(1/2, x) is a concave function and Jenson’s inequality, (v) holds due to min(a, b) ≥ 11/a+1/b
Therefore, we have
2 dL(u)
dt +
2
L(u)
dL(u) dt ≤ −λ0 2 .
By integration on both sides from 0 to t, we have L(u(t))− L(u(0)) + log(L(u(t)))− log ( L(u(0)) ) ≤ −λ0t
4 .
Therefore, we have
log(L(u(t))) ≤ −λ0t 4 + L(u(0)) + log(L(u(0))),
which yields
L(u(t)) ≤ exp(−λ0t 4 ) exp(L(u(0)))L(u(0)).
And we can bound the change of wr.
‖dwr(t) dt ‖2 = ‖ dL(t) dwr ‖2
= ‖ n∑ i=1 l′(ui) 1√ m aryiσ ′(〈wr,xi ± ‖wr‖1〉)(xi ± ‖wr‖1)‖2
≤ 1√ m n∑ i=1 ‖l′(ui)‖2 ≤ n√ m ,
where σ′(·) stands for the derivative of the ReLU activation. Thus
‖wr(t)−wr(0)‖2 ≤ nt√ m .

heading: A.6 PROOF OF LEMMA 7
text: Proof. We first prove the standard training part. As we have defined previously that
L(0) = n∑ i=1 log(1 + exp(−ui(0))),
where
ui(0) = yi 1√ m m∑ r=1 arσ(wr(0) >xi).
For each arσ(wr(0)>xi), r ∈ [m], i ∈ [n], note that the randomness only comes from random initialization for wr, there is 12 possibility that it is equal to 0, and another 1 2 possibility that it follows a normal distribution N (0, σ2i ), where σi = ‖xi‖22. Therefore, we have E(arσ(wr(0)>xi)) = 0,
Var(arσ(wr(0)>xi)) = σ2i 2 ,
E( 1√ m m∑ r=1 arσ(wr(0) >xi)) = 0,
Var( 1√ m m∑ r=1 arσ(wr(0) >xi)) = σ2i 2 .
Therefore, by Chebyshev’s inequality, we can bound
Pr(|ui(0)| ≤ σ2i 2δ ) ≥ 1− δ.
And we can bound L(0) = O(nmax n i=1 σ 2 i
2δ ) = O( n δ ) with probability at least 1− δ.
For IBP training,
ui(0) = 1√ m m∑ r=1 1(yiar = 1)σ ( wr(0) >xi − ‖wr(0)‖1 ) + 1(yiar = −1)σ ( wr(0) >xi + ‖wr(0)‖1 ) .
Thus
|ui(0)− ui(0)| ≤ 1√ m m ‖wr(0)‖1 = √ m ‖wr(0)‖1.
By E(‖wr‖1) = O(d) and Markov’s inequality, with probability at least 1− δ,
|ui(0)− ui(0)| ≤ O( √ md
δ ).
And we can bound L(0) = O(n √ md δ + n δ ) with probability at least 1− δ.

heading: B DETAILED DERIVATION FOR OTHER EQUATIONS OR INEQUALITIES
text: B.1 DERIVATION ON THE DYNAMICS OF ui(t)
We provide a detailed derivation on the dynamics of ui(t) presented in Eq. (11), which we use Hi(t) to describe ddtui(t):
d dt ui(t) = m∑ r=1 〈 ∂ui(t) ∂wr(t) , dwr(t) dt 〉
= m∑ r=1 〈 ∂ui(t) ∂wr(t) ,−∂L(W(t),a) ∂wr(t) 〉
= m∑ r=1 〈 ∂ui(t) ∂wr(t) ,− n∑ j=1 l′(uj) ∂uj(t) ∂wr(t) 〉
= n∑ j=1 −l′(uj) m∑ r=1 〈 ∂ui(t) ∂wr(t) , ∂uj(t) ∂wr(t) 〉
= n∑ j=1 −l′(uj)Hij(t),

heading: B.2 DERIVATION FOR EQ. (34)
text: Eq. (34) basically comes by triangle inequality:∣∣wr(t)>xi − ‖wr(t)‖1 − (wr(0)>xi − ‖wr(0)‖1)∣∣ = ∣∣(wr(t)−wr(0))>xi − ‖wr(t)‖1 + ‖wr(0)‖1∣∣
≤ |(wr(t)−wr(0))>xi|+ ∣∣‖wr(t)‖1 − ‖wr(0)‖1∣∣
≤ |(wr(t)−wr(0))>xi|+ ∥∥wr(t)−wr(0)∥∥1 ≤ (1 + ) √ dR.

heading: B.3 DERIVATION FOR EQ. (44)
text: We solve the inequality in Eq. (43) to derive an upper bound for in Eq. (44):
1√ 2πξ
(1 + ) √ dR ≥ 1√
2πξ
√ dR ≥ d exp ( − 2(1 + ) 2dR2
2
) ,
R√ 2πdξ
≥ exp ( − 2(1 + ) 2dR2
2
) ,
log( R√ 2πdξ ) ≥ −2(1 + ) 2dR2 2 ,
and then we can require
log( R√ 2πdξ ) ≥ −2dR 2 2 ≥ −2(1 + ) 2dR2 2 ⇒ ≤
√ 2dR
log( √
2πd R ξ)
.

Review summaries:
Training deep neural networks in the presence of adversarial perturbations (in the input data) is a very active research topic. There are lots of works defining notions of robustness, proposing solution algorithms, and introducing algorithmic improvements. Several of the recent techniques involve or extend the interval bound propagation (IBP) technique. However, there is no work analysing the convergence of IBP even in its simplest setting. In this paper, the author(s) analyse the convergence of IBP in a simplified setting for the first time.