On the Convergence of Certified Robust Training with Interval Bound Propagation
Authors: Yihan Wang
Zhouxing Shi
Quanquan Gu
Cho-Jui Hsieh
Venue: ICLR 2022 Poster (2022)
Keywords: Certified robustness
Adversarial robustness
Convergence

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 when using  IBP training to train a randomly initialized two-layer ReLU neural network with logistic loss, gradient descent can linearly converge to zero robust training error with a high probability if  we have sufficiently small perturbation radius and large network width.

Published as a conference paper at ICLR 2022
ON THE CONVERGENCE OF CERTIFIED ROBUST TRAINING WITH INTERVAL BOUND PROPAGATION
Yihan Wang*, Zhouxing Shi Quanquan Gu, Cho-Jui Hsieh University of California, Los Angeles {yi Syihanwang, zshi, egu, chohsi eh @css uula .ddu EEuul contribution
ABSTRACT
Interval Bound Propagation (IBP) is far the base of state-of-the-ar 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 when using IBP training to train a randomly initialized two-layer ReLU neural network with lo- gistic loss, gradient descent can linearly converge to zero robust training error with a high probability we have sufficiently small perturbation radius and large network width.
INTRODUCTION
has been shown that deep neural networks are vulnerable against adversarial examples (Szegedy al.) 2014; Goodfellow et al., 2015), where 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 al. [2019] Guo et al. 2018: Song et al., 2018; Xiao et al. 2020). However, due the lack of reliable measurement adversarial robustness, many defense methods are later broken by
stronger attacks (Carlini & Wagner, 2017 Athalye al., 2018 Tramer al. 2020).
There are recently line of robust training works, known certified robust training (certified de- fense), focusing on training neural networks with certified and provable robustness - the network is considered robust an example if and only if the prediction is provably correct for any perturbation
in predefined set (e.g., a small &oo ball) (Wan et al. [0188 Bunel et al. 2018 Zhang et al. 2018
Wang et al. 2018c; Wong & Kolter 2018; (Singh et al. 2018 2019: Weng al.) [0188] Xu al.
2020). Certified defense methods provide provable robustness guarantees without referring to any specific attack and thus do not rely the strength of attack algorithms.
To obtain a neural network with certified robustness, 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, and then train the model by optimizing the loss defined on the worst- case output from verification w.r.t. any possible perturbation. Many methods along this line have been proposed (Wong & Kolter 2018 Wong et al., 2018 Mirman et al. 2018 Gowal et al., 2018 Raghunathan al. [018a] Zhang al. (220a)). Among these methods, Interval Bound Propagation (IBP) (Mirman et 2018 Gowal et al.) 2018) is a simple but effective and efficient method so far, which propagates the interval bounds each neuron through the network to obtain the output bounds of the network. Most of the latest state-of-ther -fre--rrttt certified defense works are at least partly based on IBP training (Zhang et al., 2020a Shi et al.) 2021 Lyu et al. 2021 Zhang et al. 2021).
However, the convergence properties of IBP training remained unknown. For standard neural net- work training (without considering adversarial perturbation, aka natural training), has been shown provably converge to global minimizer with random initialization (Li Liang, 2018; Du et al., 2019b at Jacot et al., 2018 Allen-Zhii
that gradient descent for overparameterized networks
et al. 2019 Zou et al. 2018). Compared to standard training, IBP-based robust training has very

---

Published as a conference paper at ICLR 2022
different training scheme which requires different convergence analysis. First, in the robust train- ing problem, input can contain perturbations and the training objective is defined differently from standard training. Second, IBP training essentially optimizes different network augmented with IBP computation, as illustrated in /Zhang et al. (2020a). Third, in IBP training, the activation state of each neuron depends the certified bounds rather than the values in standard neural network computation, which introduces special perturbation-related terms in our analysis.
In this paper, we conduct theoretical analysis to study the convergence of IBP training. Follow- ing recent convergence analysis on Stochastic Gradient Descent (SGD) for standard 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 contribu- tions below:
We provide the first convergence analysis for IBP-based certified robust training. On a two-layer overparameterriee ReLU network with logistic loss, with sufficiently small per- turbation 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.
This result also 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 and identify particular challenges in the convergence analysis for IBP train- ing compared to standard training.
Notation We use lowercase letters to denote scalars, and use lower and upper case boldface let- ters to denote vectors and matrices respectively. 1(-) stand for the indicator function. For a d- dimensional vector Rdd ||x||p is its -n-om.m For two sequences {a,} and (bn). 0, we have an = Ob,,,) if and only if 3C > 0, 3N > 0, Vn > N, on I Cbayr And we have an = (b,,, if and only if 3C' > EN Vn N. an 2 C'b
2
RELATED WORK
2.1 CERTIFIED ROBUST TRAINING
The goal of certified robust training is to maximize the certified robust accuracy of a model evalu- ated by provable robustness verifiers. Some works added heuristic regularizations during adversarial training to improve certified robustness (Xiao et al. 2019 Balunovic & Vechev 2020). More ef- fectively, certified defense works typically optimize certified robust loss which certified upper bound of the loss w.r.t. all considered perturbations. Among them, Wong & Kolter (2018); Mirman let al. (2018); Dvijotham et al. (2018); WWong et al. (2018); ;); Wang et al. (2018a) used verification with linear relaxation for nonlinear activations, and Raghunathan et al. (2018b) used semi-definite relaxation. However, IBP (Mirman et al., 2 Gowal et al. (2018), which computes and propagates interval lower and bounds for each neuron, has been shown as efficient and effective and can even outperform methods using more complicated relaxation (Lee al. 2021 Jovanović et al. 202I). Most of the effective certified defense methods are at least partly based on IBP. For example. Zhang al. (2020a) combined IBP with linear relaxation bounds; Lyu al. (202)) designed a parameter- ized activation; Zhang et al. (2021) designed I-Lipschitz layer with &. -norm computation before layers using IBP: Shi et al. (2021 accelerated IBP training with shortened training schedules. As most state-of-the-art art methods so far contain IBP as important part, 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 approxima- tion of IBP verification bounds, and WWang et al. (2020) extended the analysis to other activation functions beyond ReLU, However, to the best of our knowledge, there is still existing work analyzing the convergence of IBP training.
The aforementioned methods for certified robustness target at robustness with deterministic certifi- cation. There are also some other works on probabilistic certification such as randomized smooth- ing (Cohen et al. 2019 Li al. 2019 Salman et al. 2019) which is out of our scope.
2

---

Published as a conference paper at ICLR 2022
2.2 CONVERGENCE OF STANDARD NEURAL NETWORK TRAINING
There have been many works analyzing the convergence of standard neural network training. For randomly initialized two-layer ReLUU networks with quadratic loss, Du et al. (2019b) proved that gradient descent can converge to globally optimum with a large enough network width polynomial in the data size. Ji & Telgarsky (209 pushed the requirement of network width to polylogarithmic function. For deep neural networks, Allen-Zhu et al. (2019) proved that for deep ReLU networks, gradient descent has a linear convergence rate for various loss functions with width polynomial in network depth and data size. Chen et al. 2019) proved that a polylogarithmic width is also sufficient for deep neural networks to converge. However, they only focus on standard training and cannot be directly adapted to the robust training settings.
2.3 CONVERGENCE OF EMPIRICAL ADVERSARIAL TRAINING
Robust training is essentially a min-max optimization. For a training data distribution N. the objec- tive for learning model fo parameterized by 0 can be written a
arg min (xxg)=> max ((fo A).9). DER
where (x.y) is sample, {(-,8) v) is the loss function, S is the space of perturbations. Empirical adversarial training approximates the inner minimization by adversarial attacks, and some works analyzed the convergence of adversarial training: Wang et al. (2019) considered a first-order station- ary condition for the inner maximization problem; [ao et al. (2019): ; Zhang et al. (2020b) showed converge to state with robust loss close to O and the the inner maximization by adversarial attack is nearly optimal; and Zou et al. 2021 showed that adversarial training provably learns robust halfspaces in the presence of noise.
that overparameterized networks with projected gradient descent
However, there is a significant difference between empirical adversarial training and certified robust training such IBP. Adversarial training involves concrete perturbation A, which is an approx- imate solution for the inner maximization and could lead to a concrete adversarial input x + A. However, in IBP-based training, the inner maximization is computed from certified bounds, where for each layer, the certified bounds of each neuron are computed independently, and thereby the cer- tified bounds of the network generally do not correspond any specific A. Due this significant difference, prior theoretical analysis on adversarial training, which requires a concrete A for inner maximization, is not applicable to IBP.
3 PRELIMINARIES
3.1 NEURAL NETWORKS
Following Du et al. (2019b), we consider similar two-layer ReLU network. Unlike Du et al.) (019b) which considered a regression task with the square loss, we consider a classification task where IBP is usually used, and consider binary classification for simplicity. On training dataset {(x;, y: ) for every E [n], (x,, yi) is a training example with d-dimensional input xx, E Rd)) and label y: ( E {+1}), and the network output
aW))
Σ (a.(w,..)))) x;),
where is the width of hidden layer (the first layer) in the network, W E Rmxd is the weight ma- trix of the hidden layer, w,-(r E [m]) is the r-th row of W, a E R. is the weight vector of the second layer (output layer) with elements ... , am. and o (-) is the activation function. We assume the ac- tivation is ReLU as IBP is typically used with ReLU. For initialization, we set a, unif[[[1 11]1 and w, ~ N (O, I). Only the first layer is trained after initialization. Since we consider binary classifica- tion, we use a logistic loss. For training example (x,, W1), we define u. (W, x,) := yuf(W, W.aa a, x²),
'erre use notations to denote the general robust training problem, but in our later analysis, will have different notations for simplified problem setting.
3

---

Published as a conference paper at ICLR 2022
the loss on this example is computed I(u (W, a, x:)) log(1 + exp(- u, (W, a.)x))) and the standard training loss on the whole training set is
Σ (uulW, a, x.))
Σ log
3.2 CERTIFIED ROBUST TRAINING
In the robust training setting, for original input x; (Vi E [n]), we consider that the actual input may perturbed into x; + A; by perturbation A, For a widely adopted setting, we consider foc. perturbations, where A; is bounded by an fo ball with radius <(0 I S 1), i.e., || I c. For the convenience of subsequent analysis and without loss of generality, we make the following assumption each X;, which can be easily satisfied by normalizing the training data:
Assumption 1. Vi E [n], we assume there exists some { > 0, such that x; E (e, 1]% ||x 2
In Du et al. (2019)), 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 e, we assume that Vi.j E [m], i + j. Vx, E (x,(x;;)) c), VX/ E (x;, x *X*,
where Boo (xi: t) stands for the Ebul with radius centered at X;.
IBP training computes and optimizes a robust loss L, which is an upper bound of the standard loss for any possible perturbation A; (Vi E [nz]):
I |14 S se
L max log 1 e
To compute L, since log(-) and exp(-) are both monotonic, for every i E [n]. IBP first computes the lower bound of u(W, a, X; A,) for ||A I e, denoted as 2, Then the IBP robust loss is:
-= Σ log(1 + exp(-u;)) where u, S min (W + A,) (i E [m]).
(2)
IBP computes and propagates an interval lower and upper bound for each neuron in the network, and then M; is equivalent the lower bound of the final output neuron. Initially, the interval bound
of the input is [x; c 1,x + e 1] given | I c, since x; - c 1 S x; + A; S X; + e 1 element-wise wisell holds. Then this interval bound propagated to the first hidden layer, and we have the interval bound for each neuron in the first layer:
Vr E [m], a (w,. x; - -/[wwrl)) S <o(w, [x; A.)) S (w, + +el[w
These bounds are further propagated to the second layer. We focus the lower bound of u, which can be computed from the bounds of the first layer by considering the sign of multiplier y:a,:
u. (W, A.)
Vi
Σ (w, (x, + A.))
m
1lvia = (w, el(wrll
m
+ 11sa, = -1)o (w, <||wwrll)) = 24
(3)
Then the IBP robust loss can be obtained Eq. 2 And we define u (M, U2. 2
We define certified robust accuracy in IBP training as the percentage of examples that IBP bounds can successfully certify that the prediction is correct for any concerned perturbation. An example i(i E [nx] is considered as robustly classified under IBP verification and only if n, > 0. Let ü, be the exact solution of the minimization in Eq. ( rather than relaxed IBP bounds, we also define the true robust accuracy, where the robustness requires य > The certified robust accuracy by IBP provable lower bound of the true robust accuracy.
4

---

Published as a conference paper at ICLR 2022
3.3 GRADIENT FLOW
Gradient flow is gradient descent with infinitesimal step size for continuous time analysis, and adopted in prior works analyzing standard training (Arora al. 2018 Du et al. 2019a b). In IBP training, gradient flow is defined as:
dw, (t) dl
aL(t) Ow, (1)
Vr E [m]]
(4)
where w1 (t), w2(t).... (m) are rows of the weight matrix time i, and T((t) is the IBP robust loss defined as Eq. (2) using weights at time t.
3.4
GRAM MATRIX
Under the gradient flow setting as Eq. 44) for all E [n], we analyze the dynamics of u, during IBP training. and use (t) to denote its value at time t:
d dt (1) = Σ
Ou,()) dw,(l) (t,(t)'
Σ (L, H1)
where ((())) is the derivative of the loss, H(t) is Gram matrix and defined as H (t)
(V1 S i,j S n). We provide a detailed derivation Appendix B.1 The dynamic of u, can be described using H.
Σm (t) on, (t)
(w,(t) (w,
From Eq. (3), [m], re E [m]] derivative (v,(0) can be computed as follows: aw,(1)
(1,(1) (t) 1
yaar (At:(t) ssign(,, + A,7(1) + esign (r,gn((,((5) wr (t)(
(t, V
where sign(w,(t)) is element-wise for (t). and we define indicators
(t) = (yya, 1, (t) ell,, > 0),
AT,(1) lyya, -1, (t) x; + el, > 0).
Then elements H can be written as:
(1)
(At(0((s esign( + 11, eign
r=1
(t) (xx, eisin((w, (t))) (r) x esign(w,(tt))
Yilli
x; xj
aris (t) - > (3,r (+)(())))+))))))))) sign(w,(t))) +c2
Tris (t)
(6)
where are Bri, (1), Yrij())
are defined as follows
(tr (47(1) + (7)))44)())) 4,()),
(t) = (41004)) (,)()), (t))()) =
A7)(1))
Further, we define a which is the elementwise expectation of H(0), to characterize H()) on the random initialization basis:
v1 visisnn
where Hyy( (0) depends the initialization of weights w, and a,. We also define Ào Amin (H as the least eigenvalue of H We will prove that H(0) is positive definite with high probability, by showing that o is positive definite and bounding the difference between H(O) and H
5

---

Published as a conference paper at ICLR 2022
4 CONVERGENCE ANALYSIS FOR IBP TRAINING
We present the following main theorem which shows the convergence of IBP training under certain conditions perturbation radius and network width:
Theorem 1 (Convergence of IBP Training). Suppose Assumptions and
hold for the train-
ing data, and the to perturbation radius satisfies S 50O min
X0
VadR where
logl R
R.
cb n.
/2TE For two-layer ReLU network (Eq. (7)) suppose its width for the
first hidden layer satisfies 2 S2 d2-Dnttha )) and the network is randomly initialized 8323-
as o, unift (1, -11, wr I), with the second layer fixed during training. Then for any confidence 8(0 < 8 <1), with probability at least 1 - ō, IBP training with gradient flow can converge to zero training error.
The theorem contains two findings: First, for given c, as long as it satisfies the upper bound on c specified in the theorem, with sufficiently large width m, convergence of IBP training is guaranteed with high probability; Second, when is larger than the upper bound, IBP training not guaranteed to converge under our analysis even with arbitrarily large m, which is essentially different from analysis on standard training and implies a possible limitation of IBP training.
In the following part of this section, we provide the proof sketch for the main theorem.
4.1 STABILITY OF THE GRAM MATRIX DURING IBP TRAINING
We first analyze the stability of H during training since H can characterize the dynamic of the training as defined in Eq. (5). We show that when there exists some R such that the change of Wrrr E (ml) is restricted to [[w,(t)- - w, (0)ll2 S R during training, we can guarantee that Auin (H) 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 a later part.
For all r [m], with the aforementioned constraint on wr((), we first show that during the IBP training, most of Orri (4), 3ysy((), (rrs()) (1) terms in Eq. (6) remain the same as their initialized values (t = 0). This is because for for each of 0ryy (4), Bray (4), Tris (!), the probability that its value changes during training can be upper bounded by polynomial in R. and thereby the probability can be made sufficiently small for a sufficiently small R. as the following lemma shows:
Lemma 1. Vr E [m], at some time >> 0, suppose [[w,(() w,(()]l2 < R holds for some R, and /2dR holds, then for all 1 Liij n. we have log( V (pp
12
Pr(arij(t) + Pr(ri(() # Bro Pr(mn)() # Yray (0)) S (1 (1+c) = R. V2TE
We provide the full proof in Appendix A. Probabilities in Lemma 1 can be bounded as long as the probability that each of indicator A (), (1), (t) A, (t) changes is upper bounded respec- tively. When the change of w, w,,() (t) is bounded, the indicators can change during the training only if at initialization (w-(0) x, = (l)) (0) is sufficiently small, whose probability can be upper bounded (notation = here means the analysis is consistent for both + and cases). To bound this probability, while Du et al.) (2019b) simply used the anti-concentration of standard Gaussian distribution in their terms d||w,, (0) and we combine anti-concentration and the tail bound of standard Gaussian in our proof.
standard training setting, here our analysis is different due to additional perturbation-
We can then bound the change of the Gram matrix, i.e., [[{))) H(0))2
Lemma 2. Vr E [m], at some time t > O, suppose [tw,((t) w, (0)ll2 S R. holds for some constant R. for any confidence 5(0 < 1), with probability at least 5, it holds that
12(1 + () + + c² 2)d2..52 R.
(t) - H(O))22 <
V2TE6
This can be proved by first upper bounding E H (t) (O)( (41 S iijj S n) using Lemma I and then by Markov's inequality, can upper bound [H((I) H(O)]l2 with high probability.

---

Published as a conference paper at ICLR 2022
We provide the proof in Appendix A.2 Amin (H(t)):
And by triangle inequality, can also lower bound
Corollary 1. Vrr E [m], at some time O, suppose l|w,(t) w, w, S holds for some
constant R, for any confidence 8(0 < 5 < 1), with probability at least 1 - 6, is holds that
Amin (((t)) 2 Amin (H()) 12(1 + c) + 2c + +22 ed)
R.
(8)
V2
where Xmin()) stands for the minimum eigenvalue.
We also need to lower bound Amin (H) in order to lower bound Amin (H())). Given Assumption 2 show that the minimum eigenvalue of H is positive:
Lemma 3. When the dataset satisfies Assumption 2 Ao = Amiu (H²) > 0 holds true.
The lemma can be similarly proved as Theorem 3.1 in Du et al. (2019b), but we have a different Assumption considering perturbations. We discuss in more detail in Appendix A.3 Then we can lower bound Amiu (H())) by Lemma 3.1 from Du et al. (011bb):
Lemma 4 (Lemma 3.1 from Du et al. (2019b). If X 0, for any confidence 8(0 < 8 < 1), take
m 2 a log(#) )), then with probability at least 1 - 8, it holds true that Xuin (H()) ( 2 3 2
Although we have different values in H()) for IBP training, we can still adopt their original lemma because their proof by Hoeffding's 's inequality is general regardless of values in H(O). We then plug in Amia (H())) 2 3 Ao to Eq. (). and we solve the incquality to find a proper R such that Amin (t) 2 Ag as shown in the following lemma (proved in Appendix A.4):
4
Lemma 5. For any confidence 5(0 < 6 < 1), Vr E [m], suppose [|w,(t) (t) w, & R holds,
codo where R y with
2 then probability least 8, Amin (H(()) da holds.
384
Therefore, we have shown that with overparameterization (required by Lemma E. when w, is rel- atively stable during training for all r E [mz] i.c., the maximum change on w,, (t) is upper bounded during training (characterized by the ε--norm of weight change restricted by RR), H(t) is also rela- tively stable and remains positive definite with high probability.
4.2 CONVERGENCE OF THE IBP ROBUST LOss
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 linear convergence rate, and meanwhile we have an upper bound on the change of (t((t) w.r.t. time t:
Lemma 6. Suppose for 0 S s SSt. Amin (H(t))= 2 Ao
we have
2
2L()) L(0) exp (-
Aot
[[w,(() (,)ll) S nf Vm
L(I) S exp
2
This lemma proved in Appendix To guarantee that Amin (H(s))
A.5 which follows the proof of Lemma 5.4 in Zou et al. (2018).
An for < t, by Lemma 5 we only require Vm R
es which holds sufficiently by 2.
d
Meanwhile, for each example i, the model can be certified by IBP on example with any too per- turbation within radius if and only if u, > 0, and this condition is equivalent to ((2,) < k, where = log(1 + exp( Therefore, to reach zero training error on the whole training set time t, we can require L(t) K, which implies that V1 < < n, n,,(u)) < K. Then with Lemma 6 we want the upper bound of L(t) to be less than k::
(T(O))T(()))mm T.(1) exp (2T(0) T.(0) exp (- (-dol Apl
(-22
Ki
7

---

Published as a conference paper at ICLR 2022
which holds sufficiently by
I(0)
+ [(0)
log
(10)
K
To make Eq.
reachable at some t, with the constraint Eq.
9 we require:
L(0) + I(0)
codovm d2.5n3
log
(11)
The ceft-hand-side of Eq. [11 can be upper bounded by
4
L(0)
4 (L(0) + log(L(0)) - log(k)) ) 5 (2L(0) log(#)).
log
(())
Ao
Ao
Ao
Therefore, in order to have Eq. hold, suffices to have
códoy/m
d6 m
(2I - log(k))
L(0) +
(12)
Ao
d
d1.5
where c¹ == and oo are positive constants.
Since I(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 5(0 1). with probability at least 1 6,
[(O) = ( holds. In IBP training, for any confidence 5(0 < 8 < 1), with probability at least
1 - 6, [(0)= = 0( O"" /mdde
3) holds.
And this lemma implies that with large and there exist constants C1, C2 C3 such that
[(0) < min/mmee
C2n
8 + C3.
(13)
Plug Eq. (1) into Eq. (12).
then the requirement Eq. (12 can be relaxed into:
26 m d
/n//mdd
C2
c c cinde
C2n 8
+ + +
+ Ca.
(14)
5
d
where = + is constant. As long as Eq. 14 holds, Eq. (1I also holds, and thereby IBP training guaranteed converge to zero IBP robust error on the training set.
4.3 PROVING MAIN THEOREM
Finally, we are ready to prove the main theorem. To make Eq. 11 satisfied, we want to make its relaxed version, Eq. (14 hold by sufficiently enlarging m. This requires that the coefficient of /m
in Eq. 14
cinde to be positive, and also plug in the constraint in Lemma
cinde
V2dR
d
log(
2nd (xd
Combining these two constraints, we can obtain the constraint for in the main theorem:
d'
22dR
min
2nd {) log(
Then by Eq.
[4 our requirement on width m is
d 1
S
82 2.p
This completes the proof of the main theorem.s ss In our analysis, focus IBP training with 0. But IBP with 0 can also be viewed as standard training. By setting
if m 2 2 " ) result implies that for any confidence 5 (0 8 1). standard training with logistic loss also converges to zero training error with probability at least 1 - ò. And as e gets larger, the required m for convergence also becomes larger.
8

---

Published as a conference paper at ICLR 2022
1.4
3.3
Error
standard training
Error
03
IBP training with 0.04
0.52
IBP training with - 0.001
3.2
hidden layer width=2000
hidden layer width=5 000
3.9
530
20.00
Model width m
f. perutbration radius e
(a) Final training error of standard training and
(b) Final training error of IBP training (on models with width 2000 and 5000 respectively), when the perturbation radius is varied.
IBP (with {0.001, 0.04)) respectively, when the width m of the model is varied.
Figure 1: Experimental results.
5 EXPERIMENTS
We further conduct experiments to compare the convergence of networks with different widths for natural training and IBP training respectively. We use the MNIST (LeCun et al., 2010) dataset and take digit images with label 2 and for binary classification. And we use a two-layer fully-connected ReLU network with a variable width. We train the model for 70 epochs with SGD, and we keep fixed throughout the whole training process. We present results in Figure [ First, compared with standard training, for the same width m, IBP has higher training errors (Figure Tap. Second, for relatively large (e = 0.04), even we enlarge m up to 80,000 limited by the memory of a single GeForce RTX 2080 GPU, IBP error is still far away from O (Figure Taa. This is consistent with our main theorem that when e is too large, simply enlarging m cannot guarantee the convergence. Moreover, when is larger, IBP training falls into local minimum of random guess (with errors close to 50%) (Figure 1b). We conjecture that this is partly because An can be very small with large perturbation, and then the training can be much more difficult, and this difficulty cannot be alleviated by simply enlarging the network width m. Existing works with IBP-based training typically use scheduling on and gradually increase from 0 until the target value for more stable training. Overall, the empirical observations match our theoretical results.
CONCLUSION
In this paper, 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 perturbation radius and network width. Meanwhile, since the IBP robust accuracy lower bound of the true robust accuracy (see Section 3.2). upon convergence the true robust accuracy also converges 100% on training data and the certification by IBP accurately reflects the true robustness. Our results have condition requiring small upper bound on e, and it will be interesting for future work to study how relax this condition, take the effect of scheduling into consideration, and extend the analysis to deeper networks.
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their helpful comments. This work is partially supported by NSF under AS-2008173, IIS 2048280 and by Army Research Laboratory under agreement num- ber 1011NFF20-2-0155: QG is partially supported by the National Science Foundation CAREER Award 1906169 and IIS 100200.. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

---

Published as a conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 242-252, 2019. URLittp://procediing
mlr.
press/v97/ane allen zhul9a html
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Im- plicit acceleration by overparamettrivatton. In International Conference on Machine Learn- ing, volume 80 of Proceedings of Machine Learning Research, pp. 244-253, 2018. URL http://proceede
mir prwss/essss....... v80 w800aarorala..ttm
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses adversarial examples. In International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 274-283, 2018.
URL http:::ppppcccccninggeeooooo www.iis.......p........mmmm prwss v80/ http////aaaaaaaaaaaaaaaaea html
Maximilian Baader, Matthew Mirman, and Martin T. Vechev. Universal approximation with certified networks. In International Conference on Learning Representations, 2020. URL https://
openreview net/ http::/ooorouuaddBBlg..11111.11.
Mislav Balunovic and Martin T. Vechev. Adversarial training and provable defenses: Bridging
the gap. In International Conference on Learning Representations, 2020. URL https://
openreview net www.:eeooooondddsssseoeae
Rudy Bunel, Ilker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and Pawan Kumar Mudigonda. A unified view of piecewise linear neural network verification. In Advances in Neural Information Processing Systems, pp. 4795-4804, 2018. URL https //tp://eeioc/gessseeeeoe nwwrips....... cc/
-eteteeebbbbbbbaaactaeae .act.aat.ttatat.. .html
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 3-14, 2017.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over pueererammteiiitiionnn is suffi- cient to learn deep relu networks? CoRR, abs/1911.12360. 2019. URL http:/ttt///xii..orrttt
abs/ 11911 12360
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via random- ized smoothing. In International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, 2019. URL httt:::/prrooeeeinng.g mmrr
preas/v97/n wttp///////cc//n//ooo//////
cohen 9c. html
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learn- ing, volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685, 2019a. URL
mm www.pessw.r....e.eeemmmmmmmere wwt.p/ewwss//ep.mm 997/dul 9c. html
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizze neural networks. In International Conference Learning Representations, 2019b. URL http:ps://opeeneeiiieee
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan
O' O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned ver- ifiers. arXiv preprint arXiv:/805, /0265, 2018.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang, and Jason D. Lee. Convergence of adversarial training in overparametrized neural networks. Advances in Neural Information Pro- cessing Systems, pp. 13009-13020, 2019. URL
ngs neurips cc/ html
paper/201
Ian J. Goodfellow. Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial
examples. International Conference on Learning Representations, 2015. URL http://
arxiv. wwki.orrg/bb///412/ 6572
10

---

Published as a conference paper at ICLR 2022
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:/810.12711: 2018.
Chuan Guo, Mayank Rana, Moustapha Cissé, and Laurens der Maaten. Countering adversarial images using imput transformations. In International Conference on Learning Representations, 2018. URL htttsss//ppeerreieeww www. http:///ww...ettooooomaaaa/////-
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Newral Information Processing Systems, pp. 8580-8589, 2018. URL -bbrebbb.b..iltttbtttttttt..... .acttaat.tttta............. 5a4be (el.eeee22bbaaeec..999.222226252
sew.igg...eiii..... cc/papper/211/tastt//
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small error with shallow relu networks. CoRR, abs/1909. 2019. URL
http://arxiv. orw.orggaaa ha////bss///9 12292
Nikola Jovanović, Mislav Balunović, Maximilian Baader, and Martin Vechev. Certified defenses:
Why tighter relaxations may hurt training? arXiv preprint arXiv:2102.06700, 2021.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv: arXiv: 1607.0253,, 2016.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. http//aannllcuuu.com http://ww...cc...o////////me///e wwt.cco//////miist...mmm 2010.
Sungyoon Lee, Woojin Lee, Jinseong Park, and Jaewook Lee. Loss landscape matters: Training
certifiably robust models with favorable loss landscape. OpenReview, 2021.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neurul Information Processing Systems, pp. 9464-9474, 2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gra- dient descent on structured data. In Advances in Neural Information Processing Systems, pp.
2018. URL http::://pproceeednggs..... neurips........p...............e wtt.:/rwwpp.....ppaeee///0////.. ct/pppper/2111//aat///
Zhaoyang Lyu, Minghao Guo, Tong Wu, Guodong Xu, Kehuan Zhang, and Dahua Lin. Towards evaluating and training verifiably robust neural networks. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 4308 4317, 2021.
Aleksander Madry, Alcksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, To- wards deep learning models resistant adversarial attacks. In International Conference on Learn- ing Representations, 2018. URL https: opwnrevierrreeeeeeeeeee .et. forum 2
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, vol- ume 80 of Proceedings of Machine Learning Research, pp. 3575-3583, 2018. URI. http: //proceedings. ml prwss//esseee. v mi rman Ab. html
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018a. URL https:
//openreview www.:eet.foooo htt.///rmmmmmmm wtt.://rmmmdd-yyydsaaoase Boy Rb.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pp. 10900-10910, 2018b. URL
http:://ppooeeednnnneeeeeeeeeeee .html
hash/
Hadi Salman, Jerry Li, Ilya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 1 11300, 2019. URL 3a24 bb24 66a 22441e195537--20 Abst 2at.aa/2.....a02a..a.aaaaaaaaaa.
neuripss http://www....oooppp///////////.

---

Published as a conference paper at ICLR 2022
Zhouxing Shi, Yihan Wang, Huan Zhang. Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training via better initialization and shorter warmup. arXiv preprint arXiv:2103. 2021.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, 2018. URL https: :ttttp::///ooceeee //wcce/ddoo..o.e....oooo www.innuipp... hwtp:app.cpppppppp.peeeep hash/ (atp://e444.eBeeeece..aaaaaaaaa.
pp.
Abstrratbbt......c..... .html
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certi- fying neural networks. Proceedings of the ACM on Programming Languages, 3(POPL):41, 2019.
Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. In Interna- lional Conference Learning Representations, 2018. URL https: htttt:::///peenrvvieee net.
Forum?id=x.Jyxxxb
Christian Szegedy. Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL
abs 1312. 61 6199.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint 3xXi:2002.083444 2020.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv preprint arXiv:1811.0200 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pp- 6369-6379, 2018b. URL htt.t:::://occccaiaggeeooo//eeee
nww..ps.......pp...............e Abst html
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In 27th (USENIX) Security Symposium ( ([USENIX) Security 18), pp. 1599-1614, 2018c.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6586-6595, 2019, URL http://proceediingg .wr. www.srressseeee /v25//////// https///////wggg///// //w//wangl9.. html
Zi Wang, Aws Albarghouthi, Gautam Prakriya, and Somesh Jha. Interval universal approximation for neural networks. arXiv preprint arXiv:2007.06093 2020.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song. Cho-Jui Hsich, Luca Daniel, Duane S. Boning, and Inderjit S. Dhillon. Towards fast computation of certified robustness for relu net- works. In International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5273-5282. 2018. URL http::/proceedinng
mlr.press.
v8C/ 3BC0/weg18a.. html
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pp. 5283-5292, 2018. URL httt:::/prrceeeeingg/
m A.r.po (wppss/svv) h00//wng////aae.mmmmmo html
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling prov- able adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8410-8419, 2018. URL httts::/pproceedineeeee neurips. wttpppppp//..////eeeo.eppp 358f9e7bed 000999eeb69977000 77c1 7dod11ff7358433 -Astt-558-030----saaatttt...
Abst htmll
Chang Xiao, Peilin Zhong, and Changxi Zheng. Enhancing adversarial defense by k-winners-
take-all. In International Conference on Learning Representations, 2020. URL https:
//openreview. wtw.eeeww.ettttttteeiee htt.://wwww......ooooooooooeeeee
12

---

Published as a conference paper at ICLR 2022
Kai Y. Xiao, Vincent Tjeng, Nur Muhammad (Mahi) Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. In International Confer- Learning Representations, 2019. URL https:///penreview net. http://wwwee//ooummmem forum?id- BJfTVjAcKm
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 33, 2020.
Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwei Wang. Towards certifying l-infinity ro- bustness using neural networks with l-inf-dist neurons. International Conference on Machine Learning. pp.
PMLR, 2021.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7472-7482,
2019. URL http: http://rroceeeingg mlr
www. press/ / httpa/s//////2hggggggg zhang1 html
Huan Zhang, Tsui- Wei Weng. Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. Advances Neural Information Processing Systems, pp. 4944 2018. URL -at.
ngs newrips....... .c/ Absttrassssss.. .html
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane S. Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2020a. URL BRR/httts:://penerrr/
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. arXiv preprint arXiv:2002.0666 06668, 2020b.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888. 2018.
Difan Zou, Spencer Frei, and Quanquan Gu. Provable robustness of adversarial training for learning halfspaccs with noise. arXiv preprint a:X1v:2104.09437, 2021.
13

---

Published as a conference paper at ICLR 2022
A PROOF OF LEMMAS
A.1 PROOF OF LEMMA I
Proof. For all E [m].r r E [m]] we first consider the change of indicator (t) x;=e|||w,(t))) >
0) during training compared to the value at é = 0 (the notation + here means the analysis is consis- tent for both + and cases). Under the constraint that have (see Appendix B.2 for details):
S Rnd ||x:|lsc E 1]
(w,(t) T x; + cl [w - (w, xx (00)) aR
(15)
Thereby, if sign(w,(t)) x; + cl]w,( + sign ww (0) x; < ( then at initialization, we must have
w, (0) Tx; + - & (1+ VVR..
(16)
We want to upper bound the probability that Eq. (I6) holds. It is easy to show that the following two inequalities hold, then Eq. (16) does not hold for sure:
w.(0) x 2 2(1 + edRdR, <lww-(0)|l: (1+ c)vR).
(17)
(18)
Therefore,
Pr (w) x; + dll,, s (1 c)vaR
$ Pr [w, x, > 2(1 + Vn and |w,(0)]l s s (1+
For Eq. 17h. by anti-conneentaation inequality for Gaussian, we have
Pr([w,(0) xx| S 2(1 + +c)vaR) s 4(1 +evaR
(19)
V2Tg
In other words, with probability least 4(1 + ()V/R/((22t Eq. 18
17 holds. And for Eq.
by the tail bound of standard Gaussian and union bound, we have
2(1 + ) dR
(e(el/w, (1 + e)vd)) 2 1 - 2d exp
(20)
2
Combining Eq. 19 and Eq. 20 Eq. (6 holds with at most the following probability
4(1 + el + 2dexp
(- 2(1 + 211 d)dd
(21)
V
2
Here we require to he sufficiently small such that
(1 + cl+R
2(1 + cRR
2 dexp
(22)
V2TT
22
and we can solve the inequality to obtain an upper bound for e (detailed in Appendix B.3)
2d
6
(23)
log(
2nd 5)
and in this case Eq. 21 holds with probability at least
6
(1 + Vd.R
V2TE
14

---

Published as a conference paper at ICLR 2022
Therefore, upper bound the probability:
Pr (sign(w,(() + ellw,(())l)) + sign(w,(0)"* =l],, <
(1 e) VdR.
2
Thereby
6 V2m
Vi [n],r [m], (r(A)(()) + 47)0), + A,)(0)
(1+ eevdR.
Note that least one of (t) and (t) always remains zero during training, because condition y;d, in (1) and condition year -1 in (4) mutually exclusive. Then
(r(A)(() + (,)(1) # A (0) + (,) I
(1 c)vaR,
V
(r(A - (,, + (7 A,,(0) 2
(1 VR.
2
Next we can upper bound the probability that each of Orij (1), Brg (1), Tri (1) (Vi,j E [n].r [m] changes respectively:
12
(r(Orig(() * Oriig (0), # (r) # (r) S
(1 c)vaR.
A.2
PROOF OF LEMMA 2
Proof. With Lemma
1
bound the expectation of the change for each element in Htt) (Eq-
6)) as:
B (() (,)(
< 1 E (.Emillx 1212 + em](([]x)]1 + ||x|||2) (t))l2) + cdmR)
m
5 Rd((1 + 2E +
12(1 (1 + 2E + ddds
(Vi,j [m])
2t
Then by Markov's incquality, we have that with probability at least 6,
Hty(t) H,y(0) < 12(1 + c) + 2c + 2dd
H(t)) H())22 < Σ
R.
V2n58
JEIN
A.3 PROOF OF LEMMA 3
Proof. First for simplicity, we define P = AA)(0) + A,,(0) (pr E {-1,0, (-1,0, 1}), and
cpc sign (w.( > >0. >
o(x;)(w,(0)) y/ + cp, sign(w.
x; (x (w)(
To prove that do O. similar as Theorem 3.1 in Du al. 2019b), we need to prove that for any r E [m], if 7h ....... 7n (vi E [m], T7 E IR satisty >i= o w, (0) = 0 almost everywhere (a.e.) for any w, (0). we have vi E [m]. T =
In Theorem 3.1 in Du et al. 2019b). it is proved that for d' (x(x)((w) = x; (w1 (t E [n]). when vi # J. x, it x, holds, any ?) 72, ..., .,., (Vi E [n]. n7 E R), if
Σ (w, = 0.
15

---

Published as a conference paper at ICLR 2022
then Vi [n]] 7/ 0. For any E [m], by taking Vi [n],
ep; sign w, (0)),
have ((x)((w.(0) = (w (0)), and holds that x E (x, E Bx (X,, E). Then
X; H X,, V. mh, '2,..., Tm satisfy Ex= no (w, = 0 a.c., we have vi E [n], 77 0.
Therefore if Vi,j [m], + 3. VX2 B (x,, e), VXj Bo (xj, t), x H x if m Un satisfy
Σ mo(xx)(w,,()) = 0,
then
Σ no (w,(x))ww,()) =
also holds, and then Vi E [ml]
0.
A.4 PROOF OF LEMMA 5
Proof. The lemma can be proved by solving inequality
Amin (H({)) Amin (H(O)) 12(1 + c)(1 + 2c + e
n2
do
R2
(24)
V2TE6
2
According to Lemma 4 Amin (H())) An- And with Eq. we can make
(8
in order ensure Xmin (H(t))
2
12(1 + e) + 2e + c² )d
n²
Ao 4
R <
V2T56
This yields
R < 48(1 + +] + 2e + 22 2n,
Note that 0 < E < 1, and thus 1 5 1 1+ 2E + x² < 4 can be upper bounded by constants respectively. Then we can take
V2TEd
cōAp d1.5n2
V2T
R <
where
38
384
and in this case Amin (H())) 2 w.p. at least 1 probability.
A.5 PROOF OF LEMMA 6
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 fI2).... (I,)), where f(x) is scalar function and is vector
of length n. When Amin (s) 2 No holds for I, we can bound the derivative of T.()):
16

---

Published as a conference paper at ICLR 2022
(L(u)
du
((())
dt
01
Σ ((u))
( Hy
(u
(I)
( 0
(((;))²
2
(9) A0 (u:)
(110)
An Σ
I(u:)
min(1/2,
2 i=1
2
(10)
Au
((us)
min
1/2,
2
2
x=1
Ao
I(u)
min
min(1/2,
Ao
2 2 2/L(u)
where (i) is due to Amiu (H) 2 Ao. (ii) is due to -1'(u) S 1, (iii) holds due to the following property of cross entropy loss (u) 2 min(1 (2, ].)), (iv) holds due to the function min(1/2,zr) is concave function and Jenson's 's inequality, (v) holds due to min(a, b) 2 1/a+1/b
Therefore, have
dL(u) 2 dL(uu)
Ao
S
dt
L(u) dt
2
By integration on both sides from to f, we have
T(u(t)) T(((()) log (((((t)) - loog (T(u(O)) Therefore, have
Anl
S
4
log [(u(tt) s 4
Aot
+ I(u(O)) + log [(u(o)).
which yields
(- (- Aot
((((t) S exp And we can bound the change of w,.. (t)
- --4)
exp [(u(())) Ll(()).
dL(t)
dt
2 dw,
=
(1(
a- (ww,o + + =ellw.lli)
mm
| (2,)))12
Vm
/m m
17

---

Published as a conference paper at ICLR 2022
where o') stands for the derivative of the ReLU activation. Thus
(,)0)]l2 < nt
(1)
V m
A.6 PROOF OF LEMMA 7
Proof. We first prove the standard training part. As we have defined previously that
L(0) = Σ log( exx(-u((0))),
where
u,(0) = ys m
a a (0, x,).
For each (w, xz), E [m]. E [n]. note that the randomness only comes from random initialization for wy, there is 3 possibility that it is equal to O, and another possibility that follows normal distribution N (0, of), where o, = |xx, Therefore, we have
(w, xx)) 0, (en(a,o(w,,100) (0) xx,)) xi) (0)Tx;)
of 2
Var w.
E
a wr (0)
0,
m
= of
Var
a, w, (w, xi)
2
Therefore, by Chebyshev's inequality, we can bound
Pr[[u:(0]] S 2 6.
28
And bound L(0) O max""
=0²) with probability at least 8.
20
For IBP training,
(0)
Σ 1 (y:a, = 1)o(w, x; (0)l) + I(ya, -1)o Tx, + (0)l).
m
Thus
(0) uz(0)) S me [w]]]]] /mm]|w,.
Vm
By [[[[ww]])) (d) and Markov's inequality, with probability least 1 6,
(0) u4 (0) s O /mde
And bound T.(0) 0 mdr
/)
with probability at least 5.
18

---

We provide detailed derivation on the dynamics of (t) presented in Eq. 5 which we use H. describe (t): Published as a conference paper at ICLR 2022
B DETAILED DERIVATION FOR OTHER EQUATIONS OR INEQUALITIES
B.1 DERIVATION ON THE DYNAMICS OF (t)
d
m
(t),
dw,(t)
(t) dt
(t),
dt
(t)
(L((((),e)) a)
(1)
(w,(1)
Ot,(t)
((U))) (1)(1)
Ow,
Ow, (t)
Ou,(1) (t) (u,(t)
((uy))
Ow, (1) (1)
H
Hi
B.2 DERIVATION FOR EQ. 15
Eq. 155) basically comes by triangle inequality:
(t) T x; <t)w, (w) T x; ///
(w)(() w-(()) T x; - </ </ww((()] + //]ll
(w, (t) (0)) 'x,] + + (t]ll 10)la
(w, (t) (,) +<|[w-(f) -w
< (1 c)dd).
B.3 DERIVATION FOR Eq. (2
We solve the inequality in Eq.
22 to derive an upper bound for in Eq. 23
2(1 +
dRR
(1 + +e)edR
VdR 2 dexp
V
V2TE
62
2(11 (-2(1+
e)
exp
v 2Td
22
R.
2(1 + dRR
log
V2Tdgg
and then we can require
R
2dR
2(1 + d)
V2dR
log
2
V2
22
2
log(
2nd
5)
18
19


Reviews:
[{"review_id": "vjXz-Ft8DAS", "reviewer": "Reviewer_n3Ki", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although I am aware of the line of research “certifiably robust training of neural networks”, I have not seen any work on the analysis of convergence of the gradient descent algorithm, especially in the IBP setting. Hence, assuming there is really no work doing this, I believe this paper studies a very essential and relevant problem. The mathematical steps look correct to me. \n\nMy major concerns:\n\n1 - **Presentation.** Overall, I believe the paper does not introduce the literature thoroughly, includes multiple typos, and has mistakes in the terminology. I will list some of those at the end of my review, but I think in general the paper should undergo a major review (language, terminology, editorial positioning, presentation of the existing literature, presentation of the main theorem, and the proofs).\n\n2 - **Generality and Assumptions.** Sections 1-3 are on known work and Section 5 is not very critical since this paper proves a convergence result theoretically.  Hence, this paper’s contribution can be summarised by Theorem 1 (and the Lemmas leading to it). This result is for i) overparametrised networks, ii) box perturbations with small enough radius , iii) +-1 classification problems, iv) ReLU networks, v) single and wide hidden layer. Even in the presence of these assumptions, the results are “with high probability”. Although having some assumptions is essential (e.g., bounding the perturbation radius), most results follow from the specific set of assumptions that work for this case but cannot be easily extended (e.g., the classes being +-1 is helping largely to look at the sign of the linear expressions to classify, etc.). Moreover, the upper bound on the error radius decays if we require a stronger result, not the other way around. Moreover, currently, if we fix an architecture then we should decrease the error radius until the result works.\n\nMinor points:\n- Typos: “overparameteried” (abstract), “overparameterized” (page 2), “maxmization” (page 3), “Pr(|w_r(0)^T x_i )” (page 7)\n- “Training can converge to a point” is being used frequently but not clear what it is\n- The perturbations are additive, but this is not mentioned. There are other well-known perturbations including multiplicative, affine, or functional transformations. \n- End of Section 1: “under certain conditions” -> this is not clear unless someone reads the whole paper. Could the author(s) please mention the conditions briefly?\n- Section 2.1: “based on linear relaxation” -> linear relaxation “of what” is not clear\n- Section 2.2: “to a globally optima” -> optima is plural\n- problem(1): (x,y) \\sim \\mathcal{X} is not clarified as \\mathcal{X} is a training set (please explain how an expectation is being taken over the training set)\n- Page 3: “Inner maximization is achieved” is not very clear\n- Page 3: “You et al. (2021) showed that adversarial training provably learn robust halfspaces in the presence of noise” -> the context of ‘robust half spaces’ is not clarified (it does not have meaning alone)\n- Section 2.3: Last paragraph follows simply from the definition of robust optimisation: we typically minimise theta for the worst-case solution which depends on theta so the inner problem cannot be solved numerically rather its tractable counterpart is derived analytically. This is well-known already.\n- Page 4: u is not defined when l(u) is being introduced\n- Page 4 onward: sometimes u_i is being used, sometimes u_i(W,a,x_i)\n- Some sentences claim a result for \\Delta_i, but do not define i (or state “for all i= 1,…,n)\n- Assumption 2: “j” is not defined\n- Definition of \\overline{L} in equation (6) is not in line with the standard definitions (maybe in the summation you can already include the domains of maximisation problems as max_{ \\Delta _i } \\{log(…) | ||\\Delta_i||_{\\infty}\\leq \\epsilon  \\}?\n- Usage of “we only care about” is perhaps a bit informal\n- Page 5: “to denote the value at time t” -> “value of what” is not clarified\n- Page 5: A_{ri}^{+} and A_{ri}^{-} are being used before being defined. Also, the definitions are in general not clear (using = instead of := or mentioning “let … be “)\n- “Least eigenvalue” -> smallest/minimum eigenvalue?\n- Theorem 1 and throughout the paper: $\\xi$ is never defined\n- Referring to “Section 2” in the statement of Theorem 1 is perhaps a little bit informal\n- Theorem 1 is overall very hard to read. Could the author(s) please split it to multiple sentences and present it more clearly?\n- Section 4.3: in the beginning ||w_r(t) - w_r(0)||_2 \\leq R is being used without defining “r” or “t”.\n- Overall, Theorem 1 and Lemma 2 state at least “1-\\delta” without defining \\delta\n- Lemma 3 mentions the result holds when Assumption 2 is satisfied, but Assumption 1 is not mentioned in the other results relying on that.\n- Page 8: “then we want to make” is unclear\n- Lemma 7: The sentences are not complete\n- Page 8: “Plug in Eq. (30)…” is this a typo?\n- Section 4: Last paragraph -> when epsilon = 0 the result should be well-known. Could the author(s) please cite relevant papers’ and the convergence mentioned there to show whether the results found in this paper match these results?\n- Numerical experiments are not very clear. The MNIST dataset is being used but the paper relies on binary classification problems. Overall I think the numerical experiments could be explained more clearly.\n- Conclusion: “which converges to 100%” terminology is not clear to me\n- The references are not consistent: e.g., “In ICLR, 2015” versus “In International Conference on Learning Representations, 2020a”. \n- Appendix: “at most 1 minus the probability …” this is informal\n- I can share a further list of minor editorial suggestions should the chairs decide to accept this work.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper studies a very relevant problem. There are no mistakes in the proofs as far as I can see. However, the main concerns are (i) the paper is hard to read and understand, (ii) the convergence result relies on many assumptions that cannot easily be extended to more general settings, (iii) the convergence is probabilistic and if the desired probability gets \"finer\" then the required radius of the infinity-ball will get smaller hence one needs to also increase the number of parameters of the network so the results do not work for a fixed architecture or a fixed error radius.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "r6N1m1PQRw_", "reviewer": "Reviewer_YCZg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors build on previous work on proving the convergence of gradient descent for \"natural\" training of over-parametrized networks. In particular, relying on similar assumptions and derivation to (Du et al. 2018b), the authors extend the proofs to the case of the upper bound to the robust loss as given by IBP. It is proved that IBP training converges to zero certified robust loss with high probabiliy. The choice of IBP is relevant, as it forms the basis of most state-of-the-art certified training algorithms.\n\nWhile the assumptions seem to be quite restrictive (two-layer ReLU network of constrained width, and the upper bound on the perturbation radius), the community could start from this work to provide similar extensions as those provided for natural training by (Allen-Zhu et al. 2019).\nFurthermore, as corollary of the convergence proof, it is implied that the IBP certified robust accuracy will converge to the true robust accuracy: this complies with the folkore observation in the community that methods trained with a given algorithm are more easily verify with the same certification method. Moreover, I found the observations in the experimental section to be of interest to the community. In particular, point (b), providing a possible explanation for the commonly employed epsilon warm-up schedules.\n\nMinor comments:\n- In Theorem 1 it is said \"the IBP certified robust accuracy [...] can converge to zero\": do the authors mean \"the IBP certified robust loss\"?\n- epsilon=0.03 is actually a fairly small value, as opposed to epsilon=0.1 or epsilon=0.3, which are more commonly employed in MNIST.\n- in the conclusions, \"our results has a condition\" -> \"our results have a condition\"\n", "summary_of_the_paper": "The paper presents (to the best of my knowledge) the first convergence analysis of IBP training, a method commonly employed to train networks that are certifiably robust to adversarial examples.", "summary_of_the_review": "The authors non-trivially extend theoretical analyses previously presented in the context of natural training of overparametrized networks to the context of IBP training. While the assumptions that lead to the results are fairly restrictive, I believe the results are of great interest to the community and could lay the ground for further work in the area.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-bxHa4Iiv-w", "reviewer": "Reviewer_Ysed", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper explores the training dynamics of IBP training and provides a convergence analysis. This is a novel direction for certified robust training and as such valuable for the research community. Specifically, the authors restrict themselves to a (presumably simpler then the general) setting of 2 layer ReLU networks, where only the weights of the first layer will get changed during training, the weights of the second layer remain unchanged and are either -1 or 1.  The authors then proceed to establish various relationships with between the (time dependent) network weights, and eigenvalues of a matrix governing the training dynamics. Finally they establish that a growing network width will with high probability lead to a convergence of the IBP certified robust error is zero. The high level ideas seem to check out, the proofs where sporadically checked. \n\nThe background section (Section 3) provides a good introduction to the techniques the paper builds upon. However, Section 4 needs to be improved. Between the many Lemmas, the central theme is sometimes not clear. Section 4 would benefit from adding more explanations and more intuition. To give an example, the step from Eq. 30 to Eq. 31 seems not obvious. Further, if i understood the paper correctly, it should be clarified in the conclusion that the certified robust accuracy converges to 100% on the training set. \n\nFurther Questions for the authors:\n- Please speculate: Do you expect a similar result for arbitrary depth instead of arbitrary width?\n- Does Assumption 1 hold for the MNIST dataset? If, not, can this be fixed by offsetting all pixel values by a small positive constant?\n- Why is Assumption 2 needed intuitively? Could this assumption potentially be relaxed or do you expect that then the theorem would not hold anymore?\n- What are the the technical similarities and differences to Du et al. (2018b)? \n\nMinor:\n- Eq. 6: Here, it could be clarified notationally that $\\bar{L}$ is obtained using IBP.\n- Eq. 11: One “-“ to much?\n- Eq. 12: Clarify that the ‘ in l’ denotes the derivative. \n- Theorem 1: Do I suppose correctly the authors mean here that the IBP certified robust error converges on the training set to zero with high probability instead of the IBP certified robust accuracy?", "summary_of_the_paper": "This work provides a theoretical analysis on the convergence of IBP training on overparametrized networks. The main Theorem states that the (IBP) certified robust training error can converge to zero with high probability. ", "summary_of_the_review": "This paper explores the certified robust training dynamics and proves convergence with high probability on a training set under certain assumptions. While the direction is novel, the writing and presentation should be improved. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Verifying robustness of neural networks is an important application in machine learning. The submission takes on this challenge via the interval bound propagation (IBP) framework and provides a theoretical analysis on the training procedure. They establish, in the large network with case, that the certification via IBP reflects the robustness of the neural network. Despite the tensions between the changing architecture and the required accuracy, the results are insightful. The AC recommends the authors to revise the paper, correcting the significant amounts of typos and improve the presentation for its final version.
Decision: Accept (Poster)