Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Per data-example, a local Lipschitz bound on the neural network output is computed and then used to certify robustness. This bound is made tighter by exploiting invariances of the ReLU activations throughout the network under small perturbations around the given data point. The paper further increases invariances by clipping ReLU and training the clipping threshold.
main_review: Strengths:
+ Simple and computationally efficient method of obtaining tight local Lipschitz bound makes this algorithm practical for usage in training
+ The Lipschitz bound improvement relies only on ReLU outputs being constant in some region. This makes the method plug-and-play and also applicable to most modern neural networks.
+ Experimental results show good improvements over baselines in terms of the bound, training loss, and final accuracy

Weaknesses / suggestions:
- Computational cost is explored in terms of number of iterations of the power method. A more appropriate metric would be total number of floating point operations or compute time. A comparison along these metrics can then be made with the other methods that use global Lipschitz bounds (such as GloRo)
- The clipped version of ReLU can make it harder for the network to learn since there are more regions with zero-gradients. Does this happen? Are there ways this was overcome (e.g. through reducing the magnitude of the initialized weights?). This could be explored further to explore the strengths and limitations of the ReLU_theta approach
- For local Lipschitz bound, the authors split the expression for F(x, W) in Eqn. 4 into a product of matrices, and then take the spectral norm of each. However, a direct spectral norm of the entire matrix that premultiplies x can be considered. This would provide an even tighter local Lipschitz bound due to the sub-multiplicative nature of spectral norm. While this method is likely to incur a large computational penalty (due to matrix-matrix multiplications), it could be tried on smaller problems (e.g. MNIST) and it would be interesting to know how much better the local Lipschitz bound can become and its eventual effect on certified accuracy. An alternative is to consider a different grouping of the matrices.

Typos:
- Abstract: “training algorithms can certified robustness” (grammar)
- Line 147: I_c and I_v definition swapped?
- Eqn 4 should have I_v instead of D_v. (since Wx already equals z_i, and so multiplying with D_v would produce z_i^2, which should not be there. 
- Eqn. 10 also seems to have a similar error as above
limitations_and_societal_impact: No immediate societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a trainable local Lipschitz upper-bound for a neural network that is tighter than the global Lipschitz upper-bound computed via multiplying the Lipschitz constant of each individual layer. By making use of the interaction between the weight matrices and the piece-wise linear activation functions, the authors demonstrate that the global Lipschitz bound could be improved when the activation functions are constant locally. In addition, the authors proposed a variant of ReLU that is clipped at a certain upper threshold to increase the constant region to help achieve a tighter Lipschitz upper-bound. Empirically, the authors showed that optimizing the local Lipschitz bound, along with using the modified ReLU, improved the certified robust performance of existing algorithms on several standard image classification tasks.
main_review: ## Strengths
*Originality* - The proposed approach is elegant and seems to be easy to implement in existing neural network architectures.

*Quality* - Theorem statements all make intuitive sense and are likely to be sound (though I admittedly did not carefully check all the proofs). 

*Clarity* - The paper is well-written and easy to follow. 

## Weaknesses
*Significance* 
1. Several important baselines are missing from the experimental comparisons (e.g., [1, 4]). Also, why is the performance of GloRo reported in the current paper (Table 1, 49.0% certified accuracy for CIFAR-10) much weaker than the performance reported in the original GloRo paper? (Table 1, 58.4% certified accuracy for CIFAR10) [2].
2. The proposed approach seems to successfully improve the performance of ReLU(-like) networks, but the best reported robust accuracy is still worse than existing Lipschitz-constrained models. For example, the best model in the current paper has a certified accuracy of 54.3% on CIFAR-10 benchmark while GloRo has already achieved 58.4% certified accuracy for the same benchmark.

Overall, I think this paper presents an interesting approach that tightens the local Lipschitz bound, but the current empirical evaluations seem to suggest that the proposed approach has a weaker performance than some baselines in the literature. I wouldn't recommend acceptance before more thorough experiments and comparisons are made with these baselines.

(See the limitation section for the references)

***** Edit *****
Based on the new results on MaxMin activation functions, I have decided to raise my score to 6. 
limitations_and_societal_impact: One major limitation of the work is that it would only tighten the Lipschitz constant bound when the activation functions have constant region (e.g., the output of the activation function is constant with a range of input). This can be an issue nowadays because it precludes the usage of activations without constant regions (e.g., MaxMin/OPLU [3, 5]). In particular, MaxMin has adapted in several recent works in Lipschitz-constrained neural networks and achieved better certified robust accuracy compared against ReLU (e.g., [1, 2, 4]). 

[1] Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=Pbj8H_jEHYv. 

[2] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6212–6222. PMLR, 18–24 Jul 2021. URL http://proceedings.mlr.press/v139/leino21a.html. 

[3] Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 291–301. PMLR, 09–15 Jun 2019. URL http://proceedings.mlr.press/v97/anil19a.html. 

[4] Qiyang  Li,  Saminul  Haque,  Cem  Anil,  James  Lucas,  Roger  B  Grosse,  and  Joern-Henrik  Jacobsen. Preventing  gradient  attenuation  in  lipschitz  constrained  convolutional  networks. In  H.  Wallach,   H.  Larochelle,   A.  Beygelzimer,   F.  d'Alch ́e-Buc,   E.  Fox,   and  R.  Garnett,   editors, Advances  in  Neural  Information  Processing  Systems,   volume  32.  Curran Associates,   Inc.,   2019. URL https://proceedings.neurips.cc/paper/2019/file/1ce3e6e3f452828e23a0c94572bef9d9-Paper.pdf.

[5] Artem Chernodub and Dimitri Nowicki. Norm-preserving orthogonal permutation linear unit activation functions (oplu). arXiv preprint arXiv:1604.02313, 2016.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a new method for certified robustness that tightly bounds the local Lipschitz constants for models by exploiting zero-activation of ReLU. For each data point, the proposed method first calculates the positions where feature maps become zero by ReLU. Next, since the row vector of the weight matrix before the ReLU outputs zero does not affect the output, the proposed method eliminates such row vectors and computes the Lipschitz constants of the modified weight matrix. Experiments demonstrate that the proposed method outperforms previous methods in terms of clean accuracy, robust accuracy against PGD, and certified robust accuracy.

main_review: The proposed approach is moderately interesting and its idea might inspire researchers of adversarial robustness. However, I think the technical contributions are not high and experimental results seem to be not very strong. Therefore, I tend to vote to reject.

- Strength   
   1. The idea that focuses on zero activations for ReLU is interesting. Ignoring weight vectors corresponding to these zero activations can contribute to more robust models or a better trade-off between clean accuracy and robustness.

   1. Experiments demonstrate the proposed method outperforms other methods. These baseline methods seem to be sufficiently new and reasonable though I do not have very expertise in this research area.

   1. This paper is well written and easy to follow.


- Weakness  
  1. Experimental results are not very strong.
In Table 1, the proposed method outperforms other methods. However, accuracies for GloRo in Table 1  are A few percentage points less than those reported in the original paper [4]. In addition, reported accuracies in [4] are higher than those of the proposed method in Table 1. I would like to know why these results are different from the original results.

  1. Theoretical results are trivial, and the technical contribution is not very high. In fact, this paper does not provide proof of Theorem 1 because this result is obvious. Proposition 1 is also a trivial result, which is broadly known results in the matrix computation. 
The techniques that constitute the proposed method are not very new. For example, the proposed method naively uses previous methods for computing upper and lower bounds of pre-activations for certifying zero-activation of ReLUs, and the proposed method exploits a power method to compute Lipschitz constants.


- Minor comments  
  1. The proposed method is based on the combination of ReLUs and linear operations. Can you use the proposed method with batch normalization? In addition, can you use the proposed method in the ResNet? [15] uses Wide ResNet for evaluation of BCP in , but this paper does not.
  1. Are matrices D in equations (5) and (11) correct? If they are correct, I think the computation of each layer becomes $z=ReLU(Wx)\odot Wx$.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Summary: 
The authors propose a training scheme that regularizes against the worst-case logit, as computed by a novel technique for bounding the local Lipschitz constant of a ReLU network. 
main_review: Originality: 
The key novelty in this approach is to use box constraints to determine local information about the stability of ReLU neurons to yield a differentiable upper bound for the L2-Lipschitz constant. Several theoretical results are presented, though it is unclear if the authors' intended them to be taken as novel results: in particular, Theorem and Proposition 1 are known in the literature and can be explained as a simple application of Cauchy's interlacing theorem.  The application of a local Lipschitz upper bound to generate worst-case logits to be used is training is reminiscent of (and should be compared to) other differentiable techniques to generate worst-case logits for use in training, such as DiffAI. Similarly, the hinge-loss for IBP and the notion of regularizing to enforce ReLU stability is similar to the approach in "Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability" by Xiao et al and this should be cited/compared against. 

Quality: 
The proposed Lipschitz estimation technique is sound, efficient, and differentiable; and while the theoretical underpinnings of removing rows/columns from matrices reducing their spectral radii is known, to the best of my knowledge, it had not been used in such a fashion to generate a Lipschitz upper bound. My primary complaint with this paper is the lack of thoroughness and comparisons in the experimental section. With respect to training a network to have a low Lipschitz constant and/or be adversarially robust, non-certifiable training methods such as AT/TRADES/etc should be considered and compared against (as these are known to regularize the Lipschitz constant of neural networks and provide robustness), as well as the other non-Lipschitz-based certifiable training methods. With respect to the proposed hinge loss for enforcing ReLU stability, the techniques proposed in Xiao et al (see above) should be considered. With respect to this Lipschitz estimate as a certification procedure, comparisons should be made against other techniques designed to certify a fixed, post-training, network (see the VNN challenge). 

Clarity: 
While the paper was fairly easy to read follow, and explained the key concepts well, this paper could benefit from better organization. Separating and framing this approach as primarily a Lipschitz estimator, that can then be used during training to provide robustness, or alternatively that can be used after training to certify robustness would help clarify the novelties. The ReluTheta activation could then be presented as a means to encourage ReLU stability and thereby tighten the Lipschitz bound, in an orthogonal direction to other such relu-stability techniques. 

Significance: Training neural networks that are certifiably robust against adversarial examples is a very important problem that has received significant attention from the community. Provable guarantees leveraging (local) Lipschitz continuity are a promising approach, however it is not clear to me that the proposed approach in this work advances the state of the art in a demonstrable fashion. 

Overall: 
This approach is novel and promising. However it requires more thorough experimentation and comparison to other Lipschitz--approximation/robustness-certification/relu-stability techniques to be worthy of acceptance, in my opinion. 

**** Edited score after reading reviewer rebuttals from 3->5 *********
limitations_and_societal_impact: No limitations were discussed, and negative societal impacts were not thoroughly considered.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes using local Lipschitz bound to obtain certified robust neural networks. The use of local Lipschitz constant strictly results in a provable tighter bound than the commonly used global Lipschitz bound. To incorporate the proposed certification method into training, the authors further proposed a modified ReLU function with a learnable upper threshold, and hinge loss to encourage the pre-activation states to be constant past ReLU function.

The proposed method is sound, numerical experiments show promising improvement over the existing certified robust training methods.
main_review: Originality:

The use of local Lipschitz constant as certified upper bound for training robust neural networks is a novel contribution.

Quality:

The submission is technically sound. The main claim is supported by the numerical experiments. The use of local Lipschitz constant is less aggressive on the limited network capacity, which results in better certified robustness. 

Clarity:

I believe that the submission needs more spelling checking. Especially in Sec 3.2 which is the main sub-section. I think equation (4) does not make clear sense based on the definitions of those notations.

Significance:

Certified robustness training is an important direction in adversarial robustness researches. Although the proposal is simple, its effectiveness on the improvement can be appreciated by future works.
limitations_and_societal_impact: The authors have discussed the computational cost of the proposed training method. I think the proposed method is practical since the extra computational overhead is not very heavy.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies certified robustness from the perspective of computing Lipschitzness bounds. Prior work compute global bounds on the Lipschitz constant of the network; this paper takes an alternative approach which computes local Lipschitz bounds around a specific input. These local Lipschitz bounds are based on interval bounds for the hidden layers on each data point, and computing a tighter Lipschitz constant based on eliminating rows/columns of the weight matrices when the interval bounds indicate that a neuron is inactive. 

To train certifiably robust models, the worst-case loss is optimized based on these Lipschitz bounds. There are several other ingredients for the proposed method: a modified ReLU activation which truncates when the output is a large positive value, and a sparsity-inducing regularization meant to limit the number of neurons where the upper and lower activation bounds differ. The authors compare certified robustness w.r.t. $\ell_2$ perturbations against other Lipschitzness-based baselines and demonstrate improvements. 
main_review: The paper proposes a certified robustness method based on nice and novel insights about training the local Lipschitz constants rather than the global constants. The method produces empirical improvements over existing methods; however, there is still some uncertainty about the effects of different components of the proposed methods, which aren't adequately addressed in the ablations.  (More details below.) For this reason, I'm recommending weak accept, but am willing to change my score based on the authors' response.

Originality: the idea of regularizing local Lipschitzness is novel and a nice way to improve over prior work. 

Quality: the paper appears to be technically sound, but it would be helpful to have more experiments which isolate the effects of each component of the proposed method (see below).

Clarity: the paper is generally well-written, though there are some portions where clarification would help (see questions below.)

Significance: setting aside the above concerns, this paper makes nice contributions to certified robustness.

More details about questions/ concerns:
- First, regarding the different components of the objective -- it would be nice to see how much of the improvement is due to the sparsity-inducing loss and how much is due to regularizing the local Lipschitz constant. Table 5 in the supplementary material does perform an ablation on this, but when $\lambda = 0$ (no sparsity loss), the reported numbers are actually worse than the reported numbers for BCP in Table 1. This makes me concerned that a lot of the improvement might actually come from including the sparsity loss, not regularizing the local Lipschitz constant. 

Another concern is how much the change in architecture accounts for the differences in performance -- it would be nice to see an ablation study on the impact of the modified ReLU activation. 

-- It's also unclear how exactly the local lipschitz constant is optimized. E.g. is the power iteration unrolled, and backprop is performed through the power iterations?

Some other questions/clarifications:
-- The definition of D_V in (5) doesn't appear completely right -- shouldn't it be a binary diagonal matrix? 
-- For equation (6), would it also be possible to bound the Lipschitz constant by $\|\prod_l I^l W^l I^{l - 1} \|$ instead of the product of the norms? This seems like it could lead to a tighter bound. 

=======================================================================
Update after reading the author responses and other reviews. While I appreciate and thank the authors for their thorough response to my questions, I think this paper remains borderline, especially given some of the concerns raised by other reviewers. Thus, I'm keeping my score the same.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: All the reviewers agreed that the paper provides interesting results in bounding the (local) Lipschitz constant of NNs with piece-wise linear activation functions. The reviewers had a number of concerns which were mostly resolved after the authors' responses. I would strongly recommend that the authors incorporate all the comments mentioned in the reviews in their updated version (e.g. the additional experimental results, comparison with prior work, etc).  
Decision: Accept (Poster)