Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose three methods to improve deterministic l2 robustness certificates of 1-Lipschitz convolutional neural networks. 

1. Last Layer Normalization (LLN): 
    (1) Relax the orthogonalization of the last weight layer of the network W. 
    (2) The direction of the rows in W can change freely; do not need to update other rows in W and forgot the learned information.
    (3) Efficient than original robustness certificate when the number of classes K is large. 
2. Certificate Regularizer (CR): 
    (1) Enable the gradients to continue increasing the margin M_f(x) while entropy loss becomes small by adding the regularization term. 
    (2) The relu function in the maximization term ensures that the optimization tries to increase the certificates only for the correctly classified inputs.
3. Householder Activation Functions (HH): 
    (1) Introduce a general linear GNP activation function named HH for the special case MaxMin used in Anil et al., 2018. and other works. 
    (2) Prove this HH transformation is necessary for any GNP piecewise linear function to be continuous. 
   
Their experimental results demonstrate the effectiveness of these proposed methods compared to the baseline method SOC. 
main_review: Pros: 
1. The authors find several limitations of existing works and propose three novel methods to address them. Both methods are very novel and have their advantages to address the problems. 
2. The authors present their findings and current problems and introduce the proposed methods very clear from a high level to a very detailed level. The notations, equations, and proofs are easy to follow. 
3. The figures and tables are clearly designed. Figure 1 illustrates the HH activation very clear and makes it easier to be understood. We can clearly see the improvements achieved by each method from Table1. 
4. This paper contributes a lot to the research area of 1-Lipschitz CNNs, especially the class of piecewise linear GNP activation functions HH. 

Cons: 
1. A minor issue is the structure of this paper. In the Introduction, the authors present the three methods in the order: HH, LLN, CR. However, the order in the method sections is LLN, CR, HH. The logic is a little bit messed up. 
2. It is not clearly explained why the original robustness certificate (Eq 4.) has a problem when the number of class k is large. And why LLB can not achieve significant gains on CIFAR10, just because of the small number of classes? 

Question: 
1. From Table 1, why the performance of LipConvnet-40 (45.84) is even worse than LipConvnet-5 (46.36) and other shallow networks? 
summary_of_the_review: The paper proposed three novel methods to address some limitations of existing works. It appears to be technically sound, but I have not carefully checked every detail. The experimental evaluations convincingly support the main claims. This paper contributes some new ideas in this specific research area.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work is following the line of (Anil et al 2018), its goal is to propose criteria that allows to train models wirth orthogonal weights and to certify they are. The authors generalize (Anil et al 2018) by considering a more expressive non-linearity which leads to unitary jacobians, with a softer criterium during supervision which allows to obtain better accuracies. Overall, I feel the paper is well motivated, and the results are convincing.
main_review: Pros:
- Excellent numerical improvements
- The paper is clearly written
- The contributions are mainly from the engineering point of view and this paper demonstrates the method works well, with coherent explanations.

Cons:
- I have a minor concern w.r.t. the structure of the paper, I think some of the “Theorem” could be simply called “Proposition”: please don’t get me wrong, I simply think it’s good to distinguish crucial mathematical results from trivial properties (here continuous functions).
Theorem 1, I think, should be phrased differently: it requires to introduce formally the robustness certificate first. Then, one find a property of this certificate which can be stated as a proposition. Again, I feel Theorem 2 is a too strong statement for this. It’s also strange to see that the Theorem 1 uses phrasing from the Definition 1 but is still above this latter.
- I think the choice of the parameter $\gamma$ should be fully detailed. In other words, that it has been cross-validated on a subset of the training set. Otherwise, a suspicious reader could believe the accuracy has been optimized on the test set.
summary_of_the_review: The scientific contribution of this paper is solid in my opinion: a problem is introduced, solved with a generalization of a previous framework. The explanations of the improvements are clear, and because the contribution is fully technical and the results are good, I think, except if I missed an element (such as a working with a similar result) that this paper would be a nice contribution to ICLR.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the problem of provable L2 robustness in image classification.
Three techniques are proposed as additions on top of the SOC work (Singla & Feizi, 2021):
1) let the last linear layer be non-orthogonal and adjust provable L2 robustness calculation accordingly;
2) add a loss term that encourages larger margins in logits;
3) a new nonlinearity.

Comparisons against the original SOC work are reported on CIFAR-10 and CIFAR-100.
main_review: The main issue of this paper is evaluation. And the SOC work (Singla & Feizi, 2021) has the same issue.
The Lipschitz constant of an SOC layer is not strictly bounded by 1 and is only approximately 1.
Let X be the product of the Lipschitz constants of all layers in a network.
With many layers and multiplications, X could deviate sizably above 1.
This effect can get exacerbated after the extra loss term "Certificate Regularizer" (CR) is added which encourages the SOC layers to amplify logits and hence signals in all intermediate layers.
This explains why, in Table 2, the effect of CR grows stronger as the network gets deeper.

Therefore, the reported provable robustness numbers, which are measured by margins in logits, are not reliable:
* The absolute numbers of provable robust accuracies could be overestimated for all models in Tables 1 and 2.
* The relatively comparisons in Tables 1 and 2 are not with constant X. Since the comparisons are in the range of a few percentage points, the actual robustness difference between models can easily get lost in the fluctuation of X of different networks.

In such situation, please consider the following:
* Report measured robustness by running adversarial attacks. While doing that, the comparison should not be limited to SOC and should include other techniques like adversarial training.
* After training is done, calculate the actual X of the final network and then divide logits by X before measuring margins for provable robustness assessment.

summary_of_the_review: The evaluation setup is flawed and therefore unable to judge the value of the proposed techniques. Update: ratings adjusted based on new results from authors.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed a procedure to certify the robustness of 1-Lipschitz CNNs by 

(i) relaxing the orthogonalization of the last linear layer of the network, while requiring that all rows of the last layer matrix are normalized -- Last Layer Normalization;

(ii) introducing a certificate regularization that increases the robust certificate for correctly classified examples;

(iii) introducing a class of Gradient Norm Preserving activation functions called Householder activations which are necessary for any GNP piecewise linear function to be continuous.

They proved the success of the proposed procedure on CIFAR-10 and CIFAR-100 by showing improvements in provable robust accuracy with a comparable standard accuracy.
main_review: This paper is well-written. I am not very familiar with the field of certified robustness, but the three bullet points listed in my Summary of Paper are well motivated and justified, and their success has been proved in numerical experiments. My major concerns are about the explanation of the numerical results. The authors have observed improvement in standard accuracy in certain circumstances, which needs more explanation on why this happened. Is it because you relax the orthogonalization requirement of the last linear layer?

A minor comment on Page 2, when introducing \rho, it would be good to define what it is. For readers who are not familiar with the field, it looks a bit confusing. I only got what it means when reading later sections of the paper.

Another comment at the end of Section 2, where you mentioned some past work focusing on l1 norm certificate. Can you expand a little bit explaining what is the motivation for considering l2 certificate, difference and applicable settings for these two concepts?

Lastly about the numerical section, is it possible to include results on large datasets such as ImageNet, to test the effectiveness, scalibility of the proposed procedure? Also, you observed different performance gains on different architectures. Can you provide an explanation on why this is so, and give a short summary regarding when your procedure would work best, and when it yields negligible gains?
summary_of_the_review: Overall I like this paper and the proposed ideas were well justified. My comments on the weakness mainly involve the explanation of the numerical results, and whether it is possible to include more results on larger datasets. It would be good if the authors can provide a short summary on when their method would work the best.
review_title: null

Meta-review: The paper provides a procedure for certifying L2 robustness in image classification. The paper shows that the technique indeed works in practice by demonstrating it's accuracy on CIFAR-10 and CIFAR-100 datasets. 

The reviewers are positive about the paper. Please do incorporate feedback, especially around experimental setup to ensure that the work compares various methods fairly and provides a clear picture to the reader.
Decision: Accept (Spotlight)