Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies 1-Lipschitz constrained neural networks, and prove some results for this class of networks. The paper defines 1Lip nets as those networks for which the output function is Lipschitz constrained with a Lipschitz constant of 1. They cite a way to construct such feed forward networks based on the norms of the weight matrices. They then show that for any binary labelling function, one can get an equivalent 1-Lipschitz function which agrees with the labelling function on all points of the domain. They then empirically show that tuning the temperature hyper-parameter while learning with BCE loss is important, and imply connections between this hyper-parameter and the lipschitz constant. They then show that 1Lip network are certifiably robust to adversarial attacks, and that the discriminator of a WGAN, which is also a 1Lip network is the optimally robust classifier. Finally, they give generalization results of 1Lip networks, showing that this class of networks is PAC learnable with a VC dimension independent of the architecture.  
strengths_and_weaknesses: Strengths - 
1. The results in the paper are novel, interesting and important.
2. The generalization guarantees and robustness results can open up a new line of research into these architectures. 

Weaknesses - 
1. More empirical evaluation could benefit the paper.
2. The writing could be improved, in particular, a lot of prior knowledge is assumed.

questions: How does this analysis extend to other types of networks apart from feed forward networks?
limitations: Some of the limitations are listed in the weaknesses above. A more thorough empirical evaluation on other tasks and adversarial perturbations would be appreciated.
review_title: null

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: The authors theoretically studied several properties of 1-Lipschitz neural networks (LipNet1). They showed that LipNet1 can learn and approximate any classification decision boundary. Secondly, they showed that LipNet1 is certifiable robust and not prone to overfitting, unlike conventional unconstrained models. They showed that by varying margin for hinge loss or temperature for binary cross-entropy, one can control the trade-off between robustness and accuracy.
strengths_and_weaknesses: **Originality:**

- The paper derives several theoretical results. Yet, I am not confident to say that all the results presented here are original.

**Quality:**

- The authors state that the purpose of this paper is to address the common misconception that “they (1-Lipschitz neural networks) remain commonly considered as less accurate”. However, the authors do not cite any experimental study or theoretical work, where someone claimed that 1-Lipschitz neural networks are inherently less accurate or less expressive than unconstrained neural network models.
- The authors provide an interesting analysis of 1-Lipschitz neural networks and show that LipNet1 can have certain advantages over conventional neural networks.
- The theoretical analysis, however, is not very useful as 1) we do not know how many samples are required for the convergence of the LipNet1 models; 2) the initial VC dimension bounds are rather vacuous, see proposition 7, where VC bounds depend exponentially on the number of neurons.

**Clarity:**

- The paper at times is difficult to follow its main story is fragmented without sharing a common theme. The expanded experiments (not just toy experiments) should be included to expand the paper and confirm the main theoretical results.

**Significance:**

- The paper provides an analysis of the properties of LipNet1 models, which recently become of interest in the community recently. However, to highlight its significance, the authors should expand the experimental section to compare LipNet1 models and conventional models. At the present moment, the provided evidence that LipNet1 models are not prone to overfitting unlike conventional models is not conclusive.
questions: - Can the authors include experiments where LipNet1 model robustness with tuned $L$ or $\tau$ is tuned and compared with current state-of-the-art methods?
- How does the choice of the loss function affect the training dynamics and generalization?
limitations: The authors briefly discussed the limitations of their work: lack of convergence speed bounds. The limiations of this work can be expanded. The authors should describe all the assumptions in detail and clearly state their limitations when providing their theoretical results.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper proposes many theoretical statement Lipschitz neural network for classification and show that these specific networks follows attractive properties.
strengths_and_weaknesses: AllNet networks are defined as any neural networks without any constraints. This class does not produce Lipschitz function without any further hypothesis (such as activations are Lipschitz).

The paper is all over the place and the main research line is unclear. Most of the theoretical results are rather common or "trivial". The whole paper seeks for internal coherence and lacks of general purpose. As a reader, it is difficult to grasp what is the objective.
The present paper seems to be more adequate for a journal publication than to a conference.

* Global style as the biggest weakness

The main assumption behind the development of the theory is the fact that Lipchitz neural networks are "often perceived as not expressive", which I do not remember ever reading in the literature. Most of the paper seems fuzzy: it goes from BCE to robustness certification to a (trivial) convergence proposition (prop 4) to consideration about float32/64 (ex 1)... it is just too much. There are no transitions and at no moment the reader understands what is the point.

One of the biggest problem is the writing style that makes the paper hard and annoying (sorry...) to read.
For example among many other problems:

    - sentences must contain a verb and end with a '.'(even when it ends with a formula);
    - theorem should be self contained, exterior references should remain exceptional;
    - organize the equations in order to be easily readable;
    - separate definitions and remarks (e.g. def 1 & 2 contains definitions and remarks);
    - separate propositions and definitions (e.g. corollary 1 contains a definition and a proposition);
    - the proofs rely on many technical tools such as Lebesgue measure but the pre-requisite (Borel space etc) are never explicitely given.
Most of the proofs in the appendix should be re-written. More personal but I think the footnotes in the paper could be avoided.
The paper is full of references and it costs the readability of the arguments. The reader gets overwhelmed very quickly for the wrong reasons.

* References

most reference are incomplete (many article are reference as arxiv instead than the published and peer-reviewed version)

* Others

l94: one needs additional hypothesis on AllNet to claim that they have finite Lipschitz constant (Lipschitz activation would do).

l216: the reference to cor 1 seems dubious: it is a definition of \epsilon separation rather than about bias.
questions: I suggest that the other should carefully rewrite the paper with a clear objective, the typography should be respected.
The different results of the paper are nice, but in order to be published they should be properly articulated.
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper challenges the common belief that 1-Lipschitz natural networks are less generalizable than regular networks. It accomplishes this by proving a series of claims. The authors first demonstrate that any classification problem, under mild assumptions, has a 1-Lipschitz solution, and that the error is zero if the distributions of classes are well separated. They go on to show that 1-Lipschitz models can always minimize a tempered cross-entropy loss, while the generalization performance depends heavily on the temperature value. This paper suggests that the low performance of 1-Lipschitz networks in the literature can be attributed to the wrong choice of temperature. One positive thing about 1-Lipschitz networks is that one can certify the output margin $\|f(x)\|$ rather than the input margin, as the former is a lower bound of the latter. The paper demonstrates that the WGAN discriminator maximizes an average of the signed output margin, thus it is optimally robust in this respect. The WGAN discriminator has the disadvantage of not ensuring a very high level of accuracy. There are even classification problems for which the WGAN discriminator's accuracy can be arbitrarily low. Nevertheless, implicit/explicit regularizations with 1-Wasserstein distance can be used for a trade-off between accuracy and “certifiable” robustness in 1-Lipschitz networks. Finally, the paper discusses some guarantees on the learnability of 1-Lipschitz networks.
strengths_and_weaknesses: This is a thought-provoking paper that questions certain overlooked aspects of 1-Lipschitz networks that are associated with adversarial robustness. It contains many interesting insights as well as simple illustrations to demystify some myths about these networks. While discussing interesting aspects of Lipschitz networks, the paper does not present its results in a unified manner, rather it provides nuggets of understanding. I am pleased to learn that 1-Lipschitz networks may not be as weak as previously thought, but I would like to know how these insights can be used to build robust and accurate models. Additionally, the paper could have better positioned itself compared to previous studies.
questions: - Isn’t the requirement in Eq. (3) too conservative? Does changing the min over x to an expectation help here? 
- Are you sure about Lines 182 and 183? The MCR for Q is not missing here?
- Can you provide an example of the behavior discussed at the end of Sec. 5.2 for conv nets trained on datasets like CIFAR-10 or MNIST?
- There is no comparison with SotA certifiable networks in the current manuscript.
- Adversarial training of regular networks leads to a large gap between training and test losses. Should we expect this gap to disappear for adversarial training of 1-Lipschitz networks?
- Do the authors think that playing with the temperature of 1-Lipschitz networks is enough to build certifiable robust classifiers?
- The observation made in this paper bears some similarities to other publications, such as (On Calibration of Modern Neural Networks, Guo et al., ICML 2017) and (How Good is the Bayes Posterior in Deep Neural Networks Really?, Wenzel et al., ICML 2020).
- Some typos: L137, cannot guarantees; L138, “is not” repeated twice; L154: an unified.
limitations: The extent to which certain observations of this paper hold in practice is not clear enough.
review_title: null

Meta-review: metareview: The submission proposes a series of novel results for Lipschitz models on robustness, generalization, and empirical performances opening a new venue for working on Lipschitz neural networks for example. While these results are important and interesting, the authors have struggled to provide a clear takeaway from this submission but discussions with reviewers have provided improvements to this paper. Despite its clarity issues and after reading the paper, I still recommend this paper for acceptance.
confidence: Certain
Decision: Accept