Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper discussed a technique to obtain a neural network with verifiable
robustness guarantee. The approach is based on a redesign of neural network
building blocks. Instead of using matrix multiplication, the authors propose
to use the L_\infty norm operator, which is itself non-linear and Lipschitz.
The authors successfully train L_\infy network with several training tricks on
MNIST and Fashion-MNIST, and the verified accuracy is close to the
state-of-the-art results.

Strength:

1. The idea of using L_\infty operations as basic building blocks of a neural
network is simple. It provides verifiable robustness in a new way, and can be
useful for future works on improving verifiable robustness.

2. The authors prove that a Linf-dist net is an universal function
approximator for bounded 1-Lipschitz functions.

3. The authors discuss a few training tricks to train L_\infty net, such as
using an increasing p norm (from a small value to infinity) during training.

4. The paper is overall well written, well motivated and organized well.

Weakness:

1. Only very limited empirical evaluation is done on two small datasets.
Especially, it is claimed that the proposed approach is "scalable", yet only
results on small datasets are shown. Actually, in my opinion IBP is also
scalable; CROWN-IBP has recently been scaled up to ImageNet as well (according
to information on their github [1]).

2. It is unclear if L_\infty net can be extended to convolutional neurons to
work on larger datasets such as CIFAR. I think it should be possible to use
convolutional neurons with weight sharing here, so if the authors can include
convolutional L_\infty net results that will be a big plus.

3. The approach cannot outperform existing baselines (IBP and CROWN-IBP) on
MNIST and Fashion-MNIST. But I am okay with it. If the authors can show L_\infy
net on more challenging dataset such as CIFAR-10, it might be able to
outperform previous baselines.

Other points:

1. In table 2 why there is no standard acc and robust acc for IBP? And why not
include CROWN-IBP results as in Table 1 (it should be quite easy to change
MNIST to Fashion-MNIST in training). 

2. In section 3.1 an inaccurate reference is given for the NP-completeness of
robustness verification. The correct paper to cite is Katz et al. [2], which
gives the proof in section I. The currently cited paper discussed complexity of
approximate verification algorithm which is a different setting.

3. Is it possible to generalize the L_\infty network to other general p norms
such as the L2 norm? A recent work on L2 norm verifiable training is [3].


Despite that the evaluation of the proposed algorithm is relatively weak, I
appreciate this approach and I am overall positive with this paper. I hope the
authors can provide more evaluation results as mentioned above during the
discussion period to make this paper stronger. I will consider increasing my
rating based on the author's response.


[1] Xu, Kaidi, et al. "Provable, Scalable and Automatic Perturbation Analysis on General Computational Graphs." NeurIPS 2020. https://arxiv.org/pdf/2002.12920

[2] Katz, Guy, et al. "Reluplex: An efficient SMT solver for verifying deep neural networks." International Conference on Computer Aided Verification. Springer, Cham, 2017.

[3] Singla, Sahil, and Soheil Feizi. "Second-Order Provable Defenses against Adversarial Attacks." ICML 2020. arXiv:2006.00731 (2020).


review_title: Review for Paper2097

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a new kind neural network based on a new kind of activation function, the L_\infty-Dist neuron, which they then demonstrate how to train, and show is both experimentally and certifiably robust.  Furthermore, they provide a theoretical result demonstrating that the network can approximate any desired function.

In terms of novelty, this paper has a lot of promise.  In particular:
* This approach to producing robust networks appears promising and fundamentally different from other approaches which either certify preexisting networks or smoothing approaches built on top of preexisting architectures.
* The theoretical result that their network can approximate lipschitz continuous functions is a helpful addition when considering an entirely new architecture.
* The training approach for a network without multiplications seems like a novel contribution in its own right. 

However, the experimental section is lacking which diminishes my score.  Specifically, my main issue is that the utility of the method is dependent on its advantage over prior robust training and certification algorithms, and here it is only shown to perform similarly to prior approaches on the easy datasets of MNIST and FashionMNIST.  To properly evaluate the method, more difficult datasets need to be demonstrated, in particular - CIFAR10.   On Fashion-MNIST, no comparison is made to IBP in standard accuracy and while it outperforms CAP, cap is known to underperform other methods on other datasets.

=======================================================================
Update:

I thank the authors for providing additional data, however the additional data is insufficient for me to recommend acceptance.   While the approach is certainly novel, it appears to performs worse in the relevant metrics than other methods while working on less standard networks.  As the networks are so far from standard, it is necessary to see how they (and the method) behave on commonly accepted datasets.

Furthermore, AnonReviewer4 pointed out the similarities to AdderNet which I had overlooked.   Given these similarities I expect a more thorough methodological and experimental comparison to the original AdderNet.
review_title: Interesting technique but needs more thorough evaluation

final_score: rating: 6: Marginally above acceptance threshold
review_content: **Summary:**

The contribution of the paper is threefold: First, it proposes a novel variation of AdderNet (Chen et al. 2020) that ensures the network is always 1-Lipschitz with respect to $\ell_{\infty}$ norm. The architecture allows one to generate robustness certificates with respect to $\ell_{\infty}$ norm with only a single forward pass, which is computationally cheap compared to many of the previous methods. Second, it analyzes the expressive power and robust generalization of the architecture. Finally, it proposes two training techniques (bias batchnorm and p-norm schedule) that overcome the optimization problem inherent with training $\ell_{\infty}$ Net and analyzes its empirical performance with respect to the previous methods.


**Strength:**
- The approach is easy to implement while performing reasonably well.
- Similar to (Anil et al. 2019), the approach is very efficient requiring only a single forward pass for certification, and it performs substantially better on MNIST in comparison with (Anil et al. 2019). 
- The expressiveness of the architecture is analyzed, though the proof is simple, it is nice to settle the issue within the paper.
- I like that they are studying  $\ell_{\infty}$ robustness since it has been shown to be a more important problem compared to $\ell_{2}$ robustness (Goodfellow et al. 2018). This is in contrast with the recent popular randomized smoothing approach, which tends to focus more on $\ell_{2}$ robustness.


**Weakness:**
- The experiments do not include results for the convolutional variant of the model nor results for CIFAR-10. It is odd that the convolutional variant of the model is not included since the original AdderNet was developed specifically for convolution. Even though (Anil et al. 2019) did not include results for CIFAR-10, all the other related papers (Wong et al. 2018, Sven 2018, Zhang 2019)  included results for CIFAR-10. I don’t think performance on these experiments is a deal-breaker, but it is important to include these results so that future researchers can build upon your work and put your work in the context of existing literature.

**Recommendation**

Overall, I like the paper and recommend acceptance. I would further raise the score if the experimental concern above is addressed.

I find enforcing the 1-Lipschitz property through architecture to be a very promising direction for efficient robustness certification, and the work proposes an interesting and reasonably effective method for enforcing the 1-Lipschitz property with respect to $\ell_{\infty}$ norm. My main concern is that the experiments are not comprehensive enough. It is okay if it does not significantly outperform the previous methods, but it would be easier for the community to build upon your work if experiments are more comprehensive.


**Miscellaneous:**
- Since the approach is so similar to AdderNet, I recommend giving more credit to it. I wouldn’t have realized the similarities between them unless I dug into the citation.
- In Table 1 and 2, why are IBP, CROWN-IBP, and GroupSort considered as not scalable in the comparison? IBP & CROWN-IBP only cost ~2 times for certification compared to normal inference. Groupsort network requires only a single forward pass to calculate the certified radius. 
- The generalization bound looks nice but I find that it slightly distracts from the main point of the paper. I am not too keen on the generalization bound that depends on Rademacher complexity in general since it does not consider the model learnable through gradient descent (not that it is an easy thing to do). This comment is more for future references, and I am okay with the way the paper is laid out right now.


[1] Chen, Hanting, et al. "AdderNet: Do we really need multiplications in deep learning?." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020.

[2] Goodfellow, Ian. “Defense against the Dark Arts: An overview of adversarial example security research and future research directions.” https://www.iangoodfellow.com/, 2018, https://www.iangoodfellow.com/slides/2018-05-24-DLS.pdf. Accessed 2020.

[3] Anil, Cem, James Lucas, and Roger Grosse. "Sorting out lipschitz function approximation." International Conference on Machine Learning. 2019.

[4]Wong, Eric, and Zico Kolter. "Provable defenses against adversarial examples via the convex outer adversarial polytope." International Conference on Machine Learning. PMLR, 2018.

[5]Gowal, Sven, et al. "On the effectiveness of interval bound propagation for training verifiably robust models." arXiv preprint arXiv:1810.12715 (2018).

[6]Zhang, Huan, et al. "Towards Stable and Efficient Training of Verifiably Robust Neural Networks." International Conference on Learning Representations. 2019.

review_title: Simple and effective proposal for $\ell_{\infty}$ certifiable robustness. Experiments could be more comprehensive.

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, the authors consider the task of adversarial/robust learning with respect to neural networks. The problem is a well-motivated one: suppose there is a neural network that on input a training set T={(x_i,y_i)} does a good classification job, but an adversary comes along and modifies some parts of T, then it is very possible that the neural network will classify almost incorrectly and hence isn't robust. In this paper they consider this setting and ask if we can naturally make neural networks robust. 

In this direction, the authors propose a major change: in the conventional neural networks, one has sigmoid function which on input x, outputs sigma( w^T x ) (let's ignore bias for the time being) and the authors observe this functions is neither Lipschitz nor is it robust to noise. Instead, the author propost an ell_inf neuron which is just || w - x ||_inf. In this direction, they consider a neural network that is built out of ell_inf neurons. Simply by definition, it isn't too hard to see that this function is Lipschitz with respect to the ell_inf norm. The authors go on to show that every function can be represented using this new ell_inf NNs with sufficiently many neurons and sufficiently large depth. Furthermore, they go on to perform certain simulations for MNIST data. 
In my opinion here are the pros and cons of the paper:

1) Pros: I think the problem is very well motivated and has been extremely well-studied. I am not an expert in this area, but i find their ell_inf neuron pretty interesting as well. Their simulations also seem very intriguing that such neurons seem to work after all (which is slightly surprising to me based on what I say next)

2) Cons: In my opinion, the authors do not make a sincere effort to compare both the models. A simple example where the new model is *extremely* inefficient is simply to compute the inner product function. It is easy to do it in the standard neural model (albeit its not robust), but in the new model, even the non-robust setting, I don't think the inner product can be computed easily. SO it seems to me that their "fix for robustness"might lack the decades of research that has been done in understanding and proving results about the standard sigmoid function. This is an important aspect which is missing in their work. 

Overall, I think the idea is nice, but I'd tend towards rejection since their fix could be nice if they can show that everything computable in the standard NN model can be computed in their new ell_inf NN model (with approximately the same complexity), but this seems to be missing in its current form.
review_title: Review for new robust neural network definition 

Meta-review: In this paper, the authors propose a theoretically principled neural network that inherently resists ℓ∞ perturbations without the help of adversarial training. Although the authors insist to focus on the novel design with comprehensive theoretical supports, the reviewers still concern the insufficient empirical evaluations despite the novel idea and theoretical analysis.
Decision: Reject