Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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. 

My major concerns:

1 - **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).

2 - **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.

Minor points:
- Typos: “overparameteried” (abstract), “overparameterized” (page 2), “maxmization” (page 3), “Pr(|w_r(0)^T x_i )” (page 7)
- “Training can converge to a point” is being used frequently but not clear what it is
- The perturbations are additive, but this is not mentioned. There are other well-known perturbations including multiplicative, affine, or functional transformations. 
- 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?
- Section 2.1: “based on linear relaxation” -> linear relaxation “of what” is not clear
- Section 2.2: “to a globally optima” -> optima is plural
- 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)
- Page 3: “Inner maximization is achieved” is not very clear
- 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)
- 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.
- Page 4: u is not defined when l(u) is being introduced
- Page 4 onward: sometimes u_i is being used, sometimes u_i(W,a,x_i)
- Some sentences claim a result for \Delta_i, but do not define i (or state “for all i= 1,…,n)
- Assumption 2: “j” is not defined
- 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  \}?
- Usage of “we only care about” is perhaps a bit informal
- Page 5: “to denote the value at time t” -> “value of what” is not clarified
- 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 “)
- “Least eigenvalue” -> smallest/minimum eigenvalue?
- Theorem 1 and throughout the paper: $\xi$ is never defined
- Referring to “Section 2” in the statement of Theorem 1 is perhaps a little bit informal
- Theorem 1 is overall very hard to read. Could the author(s) please split it to multiple sentences and present it more clearly?
- Section 4.3: in the beginning ||w_r(t) - w_r(0)||_2 \leq R is being used without defining “r” or “t”.
- Overall, Theorem 1 and Lemma 2 state at least “1-\delta” without defining \delta
- Lemma 3 mentions the result holds when Assumption 2 is satisfied, but Assumption 1 is not mentioned in the other results relying on that.
- Page 8: “then we want to make” is unclear
- Lemma 7: The sentences are not complete
- Page 8: “Plug in Eq. (30)…” is this a typo?
- 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?
- 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.
- Conclusion: “which converges to 100%” terminology is not clear to me
- The references are not consistent: e.g., “In ICLR, 2015” versus “In International Conference on Learning Representations, 2020a”. 
- Appendix: “at most 1 minus the probability …” this is informal
- I can share a further list of minor editorial suggestions should the chairs decide to accept this work.

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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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.

While 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).
Furthermore, 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.

Minor comments:
- In Theorem 1 it is said "the IBP certified robust accuracy [...] can converge to zero": do the authors mean "the IBP certified robust loss"?
- 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.
- in the conclusions, "our results has a condition" -> "our results have a condition"

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

The 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. 

Further Questions for the authors:
- Please speculate: Do you expect a similar result for arbitrary depth instead of arbitrary width?
- Does Assumption 1 hold for the MNIST dataset? If, not, can this be fixed by offsetting all pixel values by a small positive constant?
- Why is Assumption 2 needed intuitively? Could this assumption potentially be relaxed or do you expect that then the theorem would not hold anymore?
- What are the the technical similarities and differences to Du et al. (2018b)? 

Minor:
- Eq. 6: Here, it could be clarified notationally that $\bar{L}$ is obtained using IBP.
- Eq. 11: One “-“ to much?
- Eq. 12: Clarify that the ‘ in l’ denotes the derivative. 
- 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_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.
review_title: null

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)