Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: 1. Problem/Motivation
- The paper looks into the relationship between certified robustness and Lipschitz continuity for the $l_\infty$ case. 
- It has been observed that Lipschitz networks don't work for $l_\infty$ as well as they work for $l_2$ setting. However, recent work from Zhang et al. created some particular 1-Lipschitz network which has good robustness.
- The authors try to understand this phenomenon.

2. Methodology/Technical Finding

A) Methodology
- Authors study this question by using discrete Boolean functions and prove some impossibility results (negative results) for this setting. 
- This relates to the difficulty in training certifiably robust Lipschitz network for the $l_\infty$ perturbations setting.

B) Explaining performance of recent Lipschitz networks (Zhang et al.)
- Authors use the above machinery to examine how some recent networks for this setting work well thus justifying their empirical performance.

C) Designing even better Lipschitz networks
- From the above insights, authors propose new networks.

3. Experiments
- Authors show the empirical performance of the proposed SortNet, where the methods perform almost at par (maybe slightly better) than recent methods.

########## POST REBUTTAL ##############
After going through other reviews and the authors rebuttal, I have decided to keep my score as it is (borderline accept) and not increase the rating. My main concern remains the same, that we need to move beyond theoretically convenient settings, to scale to networks used in practise.
The authors shared 2 threads of work, which I am aware of. Here are my concerns with them:
- Randomised smoothing: The test time cost of randomised smoothing is very high as it needs to run for many perturbations. Thus even if they work on large datasets, the methods are not practical.
- Certified robustness using Lipschitz networks: Are we able to convince the practitioners to use Lipschitz networks? 
strengths_and_weaknesses: I have given a thorough summary in the above box. 

Strengths
- The technical part of the paper is solid. Authors have used Boolean functions to explain the workings/robustness of Lipschitz networks. 

Weaknesses:
1. Writing: The method section can be improved. It is a bit dense and hard to follow. I have provided suggestions for improvement in the Questions box.
2. Problem Relevance: I am not sure about this whole line of work. Certified robustness has been there for a while now. It is not scaling up and there is less chance of scaling up. So, I am not sure if this is so relevant for the community.
questions: These are suggestions regarding writing. I hope it is useful for authors.
1. Better sectioning
- Look at the summary I wrote and how I divided into subgroups. If you do so throughout the paper, it would be great. Start from the introduction where you can have these as different paragraphs with paragraph names as bold.
- Then match them with same names (either as paragraphs or subsections) in the method section.

2. In the method section, before bringing a theorem, you should try to motivate the theorem. More space should be spent of motivation and linking theorems to the whole them or theme of the subgroup (see point 1).
limitations: The work addresses Certified Robustness, which is on the reliability line of work, thus positive societal impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents novel theoretical results and a novel architecture for designing Lipschitz constrained neural networks (with respect to the infinity norm). The theoretical results provide new insights on two prior approaches and give a strong justification for the method introduced by the authors. The authors also provide a novel stochastic approximation to train their model efficiently. If I understand correctly, this comes at with a cost to expressiveness but is seemingly insignificant. Overall, I found this paper to be clearly written and with significant theoretical and empirical results.

The theoretical results are thorough and exciting. Unlike some prior work (e.g. Anil et al.) the authors provide (lower) bounds on approximation quality in addition to exact completeness results. Theorems 3.5 and 3.6 show that standard Lipschitz neural networks fail to achieve robustness as input dimensionality increases for simple 1-Lipschitz functions. These results are not surprising but are more concrete than prior results that I am aware of. Theorem 3.8 then gives a finite-dimensional completeness result for the distance nets that were introduced in prior work (though universal approximation results have already been shown, e.g. Zhang et al. 2021). Theorem 3.9 then shows that the previously introduced MaxMin networks require depth that grows with input dimension to approximate the order statistics accurately (confirming a negative result that had been explored empirically by Anil et al. 2019 and theoretically by Huster et al. 2019).

Empirically, the introduced SortNet architecture shows excellent performance (relative to the class of models it is compared against). SortNet typically achieves clean accuracy that is comparable to the clean accuracy of other certified networks but achieves improved certified robustness across the board. Importantly, it is also faster to train and compute certified bounds than other methods.
strengths_and_weaknesses: ## Strengths

The theoretical results are well presented and complete, providing upper and lower bounds on approximation error and highlighting order statistics as an important class of functions. There is more to do in this space. For example, the authors show that order statistics are hard to learn for MaxMin networks but why is this important for classification tasks? But I consider the paper to address all reasonable areas of interest in sufficient depth.

I found the SortNet architecture compelling and the stochastic approximation of the linear function of the order statistics is very neat. The dropout connection is also interesting (and perhaps nested dropout is worth a mention).

The empirical results are thorough and compare across the appropriate metrics for the tasks considered. As always, including error bars would strengthen the empirical results further.

## Weaknesses

The authors address only the infinity norm and make no claims on how these results may generalize to other l_p norms beyond section 3.1.

The authors results are only (obviously) applicable to fully-connected networks. This is a limitation which is shared by other work in the area, but not exclusively (Li et al. 2019 study 1-Lipschitz convolutions with respect to the 2-norm). It is unclear whether incorporating convolutional layers would improve performance on tasks which typically demand them (ImageNet).

Generally, it seems that the larger community has disengaged a little with norm-bounded threat models for adversarial robustness. This _is_ still an active area and I personally believe that certified robustness guarantees in this model remain an important topic of study. However, I reduce my score a little, in part, because I do not think the empirical results presented here would be enough to make waves in the deep learning community more broadly.
questions: "Based on our knowledge of Boolean circuit theory" --- as somebody without this knowledge, I'm keen to know a little more about this. Can you provide some brief intuition (in response, and in the paper) for why MaxMin nets require O(d) scaling while the distance nets appreciate constant depth.

The SortNet architecture introduces the weights as network parameters. To make the network training efficient, the weights are fixed to a geometric series. This contains the distance nets as a special case, but once the weights are fixed the networks are now, assuming an identity activation, less expressive than GroupSort networks that are able to learn the weights alongside using the order statistics. Is learning the weights entirely unimportant? Is it beneficial to fix them?


### Minor comments

In line 227 you refer to the absolute value function as an example of a GNP element-wise activation function. This is just a small comment that absolute value and MaxMin are equivalent in terms of expressivity (at least in both the 2-norm and infinity-norm settings). See Appendix A.3 in Anil et al. (it is shown explicitly for 2-norm).

L198-199: The negative answer is only shown for so-called Standard 1-Lipschitz neural networks.

L170: "Lipschitz" -> "1-Lipschitz"

L274: "MinMax networks" should be "MaxMin" networks as elsewhere in the paper
limitations: The authors do discuss limitations but only very briefly. So far as I can tell, they only discuss:

- Not proving a tight upper bound on MaxMin networks for general Boolean functions
- Not treating rho as a learnable parameter

I feel that there are more details to be discussed here, some of which I raise in review. A broader discussion of the limitations of this research relative to related work would be appreciated. All of these may not be necessary, but here are some areas that could be discussed:
- Architecture limited to fully-connected networks
- Results/architecture only applicable under l_p norm constraints [though I believe some of the same ideas could be transferred more generally]
- Limitations of norm-bounded threat models for robustness in practice
- Limitations of margin-based robustness guarantees (in terms of training and certification)
- Fixed weights when using stochastic approximation (related to fixed rho, but more general)
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a generalization of some recently proposed variants of $\ell_\infty$-Lipschitz networks, i.e., networks that by design are 1-Lipschitz with respect to the $\ell_\infty$-norm, that come with guarantees of expressivity. This type of networks are useful as they automatically come with certificates of robustness without requiring expensive additional procedures, however some previous proposed designs suffered from low expressivity or difficulties during training.

The authors also present a stronger versions of a negative results on approximation of Lipschitz functions by standard Lipschitz neural networks (those with bounded weight matrices and element-wise 1-Lipschitz activations), as well as new negative results on the expressivity of MaxMin networks.

The proposed architecture is expensive to evaluate and hence, the authors propose to replace the layers with a stochastic approximation that drastically reduces the computation. The performance of the proposed approach is compared with state-of-the-art baselines showing promising but inconclusive results. Remarkably, the proposed architecture can be trained in a reasonable amount of time on the TinyImagenet and Imagenet datasets, which previously proposed methods found to be challenging.

*** after rebuttal ***
Authors have addressed most of my concerns. I am inclined to increase my score. Will expand later on why.
strengths_and_weaknesses: **Originality**: The paper builds upon previous work that introduced the GroupSort activation and another work that introduced $\ell_\infty$-distance networks, but generalizes both approaches to a more expressive architecture. The expressivity claim is backed by formal approximation results that show, in particular, that the more computationally efficient version of the GroupSort-activation network, the MaxMin network still has limited expressivity. To my knowledge, such results are new. Another new result is that the $\ell_\infty$-distance network can approximate any discrete boolean function, a result that was not part of the original paper introducing such architecture. In contrast proposition 3.1 is well-known (or a slightly less general version) but is provided mostly for completeness.

**Quality** + **Clarity**: The work backs up all claims with carefully presented proofs. Indeed the readability of the paper is vastly above the average subsmission and overall, the statements, proofs and high level ideas of the paper are easy to grasp, even though the proofs have a high level of technical difficulty. This is a major strength of this work. Nevertheless, we also find what in my opinion is the main weakness of this paper. Sadly, **the accuracy/robustness/certified-robustness numbers in the experimental evaluation are provided without a confidence interval**. Because some of these numbers appear to improve over the baselines by small amounts, it is not clear if such improvements are significant enough to warrant presenting them in **bold** and claiming a real improvement.

Perhaps the authors have had time to do multiple runs between the time of submission and rebuttal period, and could clarify if the results do not appear to be better only by chance. One issue is that such experiments are costly to evaluate, but confidence intervals, at least for the smaller scale datasets like MNIST, CIFAR10, multiple runs should be standard and I think it is reasonable to expect them. On the other hand, the time numbers are clearly lower and one would not expect the randomness to drastically change them. Another good thing is that the biggest increase in performance appears to be in the Imagenet Dataset, which is usually considered more significant. The inclusion of confidence intervals at least for MNIST+CIFAR10 would definitely improve my score.

**Significance**: The certified robustness problem is a long-standing problem and understanding the limits of what can be achieved is a significant problem. Even though $\ell_\infty$-robustness can be seen as a simplified model of real threats to computer vision systems, it can be seen as a way to devise more robust models in practice. Having a general architecture that subsumes previous promising Lipchitz networks and showing it is expressive enough to represent all boolean functions while being able to train it in a reasonable time seems significant enough. However, it was not so clear to me what is the precise theoretical advantage of SortNet (this work) vs $\ell_\infty$-distance network. I think not theoretical advantage was presented but rather it was shown through experiments that SortNet is somehow easier to train.

**miscellaneous:**
1. missing references [A] (for $\ell_2$-metric) and [B] (for $\ell_\infty$-metric) which are methods to compute the Lipschitz constant of neural networks, that can be used to regularize the loss and obtain certified robustness.
2. Proof between lines 729-730 in the appendix: "With loss of generality" -> "Without loss of generality" (I think this is what you meant)

**References**:
[A] Efficient and accurate estimation of lipschitz constants for deep neural networks.
Mahyar Fazlyab,  Alexander Robey, Hamed Hassani, Manfred Morari, George J. Pappas. NeurIPS 2019

[B] Lipschitz constant estimation of Neural Networks via sparse polynomial optimization 
Fabian Latorre, Paul Rolland, Volkan Cevher. ICLR 2020


questions: 1. can you provide confidence intervals for the numbers in the experimental section?
2. could you better back up the claim that the improvements over $\ell_\infty$-distance nets are significant?
3. Could you clarify if there is a theoretical advantage of SortNet over $\ell_\infty$-distance net?
4. Could you clarify in line 34 what you mean by *far from satisfactory*? Is there a number that would be considered *satisfactory*?
limitations: One limitation that I think is not mentioned, is that by introducing an stochastic estimation *between layers*, the gradient at a realization of the stochastic variables might not constitute an stochastic gradient of the full loss, and hence the optimization algorithms falls out of the SGD paradigm. Nevertheless in practice it looks like the performance obtained by this training procedure (similar to dropout) is enough to justify its heuristic nature.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies certifiably robust Lipschitz continuous neural networks. To this end they first prove a couple of impossibility results for standard Lipschitz networks, i.e., feedforward networks of the form $x_{k+1} = \sigma(W_k x_k + b_k)$ where the activation $\sigma$ is $1$-Lipschitz and the weight matrices have unit norm. Their first results deal with the approximation of Boolean functions $g^B : \lbrace 0,1\rbrace^d\to\lbrace 0,1\rbrace$ and prove that no standard Lipschitz networks can achieve a robustness radius of more than $1/2d$, which obviously deteriorates in high dimensions. Consequently, these impossibility results are transferred to general Lipschitz functions by proving that the order statistics, the 1-Lipschitz function taking its input $x$ to the $k$-th largest component $x_{(k)}$, cannot be approximated by a standard 1-Lipschitz network.

The authors then continue the discussion by studying GroupSort and $\ell_\infty$-distance architectures, which are non-standard and are known to be universal Lipschitz function approximators. They prove that the simplified GroupSort architecture called MaxMin, which is commonly used since it's feasible to train, is NO universal Lipschitz function approximator. Furthermore, they prove that $\ell_\infty$-distance architectures can exactly represent certain Boolean functions and order statistics. 

Motivated by these insights they suggest a new architecture, SortNet, which has both GroupSort and $\ell_\infty$-distance networks as special cases. In particular, it is a universal Lipschitz function approximator. Then, they suggest a practical version of of SortNet which replaces the expensive sorting operation by an unbiased estimator which just evaluates the maximum of a masked vector. In contrast to the MaxMin simplifcation, their simplified SortNet is still an universal approximator.

They conclude with numerical results which show that the proposed SortNet architecture is consistently slightly to significantly better than $\ell_\infty$-distance networks and significantly better than GroupSort. 

######POST-REBUTTAL######
I increased my score to strong accept.
strengths_and_weaknesses: Strengths:

The paper is very well-written and organized. All proofs are deferred to an appendix but at the same time they are concise, clear, and correct (I check most of them, not all). The paper has a clear golden thread: first, impossibility results for standard networks are proved, then theoretical explanations for the success and failure of the known GroupSort and $\ell_\infty$-distance networks are proved, finally a novel and unifying architecture is suggested and evaluated.

Weaknesses: 

N/A
questions: I only have very few minor comments which could further improve the presentation:

- p.5, l.198: "whether they can approximate all Lipschitz functions" should be "whether they can approximate all 1-Lipschitz functions"
- bibliography: capitalization should be fixed, e.g., lipschitz, Mnist, Mma, etc...
- p.21, l.862: blank missing in "some k"
limitations: N/A
review_title: null

Meta-review: metareview: The paper presents novel theoretical results and a novel architecture for designing Lipschitz constrained neural networks (with respect to the infinity norm). The authors have addressed all the concerns from the reviewers properly. All the reviewers agreed that the paper contains significant contributions and should be accepted at NeurIPS 2022. 
confidence: Certain
Decision: Accept