Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This is a theoretical work studying the limitations of piecewise linear functions in robustness certification. Main findings include: 1) Any piecewise linear certification is incomplete for piecewise linear networks; 2) For Lipschitz networks, when the learner can control the network, there exists some implementation such that Lipschitz-based certification is tight, but Lipschitz-based certification is piecewise-linear limited when restricted to the hy- pothesis class of piecewise linear networks. 3) Capacity can help tight certification, but using Lipschitz-based certification may need additional capacity. 

strength_and_weaknesses: Strengths:
* This work conducted some theoretical analysis on the fundamental limits of piecewise linearity. The study concluded the limitation of piecewise linear certification and Lipschitz-based certification under certain conditions. 

Weaknesses:

* Theorem 1 talks about “piecewise-linear limited certification procedure”. But it is unclear what certification methods the paper is referring to by “piecewise-linear limited certification”. I didn’t see a concrete example in the paper for “piecewise-linear limited certification”. I know many works use convex relaxation based certification. But the limitation of convex relaxation based certification is already known as the convex relation barrier in Salman et al., 2019 which is missing in this paper. Thus I am concerned if the contribution on Theorem 1 is significant. 

* Theorem 2 sounds kind of trivial to me. The existence of a Lipschitz function which can be tightly verified does not seem to be quite useful. In particular, are such Lipschitz functions nontrivial (i.e., do they correspond to any network with a good accuracy)? 

* Section 3 on capacity is based on a case study only, without formal theories. 

* The paper is poorly written. Many theorems are not clearly stated, especially with unclear conditions:
  - In Section 2.2.1, it is mentioned that the learner needs to be given control over the network implementation, which seems to be a condition of Theorem 2 but is missing in the Theorem. 
  - In Section 2.2.2, it looks like Proposition 3 is only applicable when the networks are restricted to the hypothesis class of piecewise linear networks. This condition is also missing in Proposition 3 which simply says “Lipschitz-based certification is piecewise-linear limited.”
  - Section 2.3 is very poorly presented. The section describes some geometry  elements such as “corner”, “point”, etc., without any figure. In the current form, it is difficult for readers to understand this section. At least the writing should be combined with a figure. 
  - In Section 2, “the main insights in this work stem from the simple, yet crucial observation that the points lying at a fixed Euclidean distance from a piecewise-linear decision boundary, in general, do not them- selves comprise a piecewise-linear surface.” But doesn’t certification considers points within a distance on the **input space** rather than the output space? Why do the authors consider “fixed Euclidean distance from a piecewise-linear decision boundary” (output space rather than input space).
  - In Definition 2, why does there have to be f’? Why can’t it be contained in “cert” already (the certification procedure?)
 
Salman, H., Yang, G., Zhang, H., Hsieh, C. J., & Zhang, P. (2019). A convex relaxation barrier to tight robustness verification of neural networks. Advances in Neural Information Processing Systems, 32.

clarity,_quality,_novelty_and_reproducibility: - Clarity and quality: Many parts of the paper are unclear, as detailed above. 
- Novelty: Not novel. 
- Reproducibility: N/A.

summary_of_the_review: 
The theoretical contributions are not significant enough in the current form. The writing of the paper is quite unclear. Discussion on capacity is based on a case study and lacks formal theories or solid experiments. Therefore, it seems that this paper is not ready for publication in its current form. 


I suggest the authors make the writing much more clear. Theorem 1~2 needs to be supported by concrete examples and their significance needs to be improved. Section 3 on capacity needs to be supported by either formal theories or solid experiments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper attempt to understand the fundamental limitations of Lipschitz-based certification for piecewise-linear hypothesis classes. They show that piece-wise linear certification methods cannot sufficiently capture a true robust frontier of data that is curved and hence might need additional parameters. I commend the authors for proposing a unique viewpoint for understanding the gap between existing robustness certificates vs actual robust accuracy. 
strength_and_weaknesses: On a broad scope my take-away from the results of the paper feels very different to the author's inference and I am eager to hear the author's opinion on this and ready to change my mind on the following observations. 

- In Theorem 2, why is the hypothesis class cal{F} restricted to be set of Lipschitz functions? Even for arbitrary label classifiers f, one can  construct f' based on d(x) : the distance to boundary. Additionally if one has access to d(x), then there is no certification to speak of? The label classifier f is epsilon-locally robust at x for all epsilon <= d(x) by definition..? So this result does not meaningfully show that Lipschitz-based certification is a good approach. In this ideal case, there is no need for certification. Additionally, even when "the learner is allowed flexibility over the precise flexibility over the network function" shouldn't f' also be a neural network of the same architecture? How is the f' constructed a valid instance? 

- The fundamental issue appears to be a mismatch between level curves of a hypothesis and the shape of the data manifold. This issue is independent of Lipschitz-based certification right? The authors show in Figure 1 that if the data curved but the function class is piece-wise linear then one can find pockets that escape certification analysis. However if one uses this information to switch the function class to be smooth, couldn't we have the reverse issue? i.e. when the data is piece-wise linear opposite the boundary induced by the function which is now curved? Further, at different parts of the image manifold the local shape can vary in regularity and thus any structured hypothesis might necessarily need more parameters to learn a good boundary. If this thought is sound, then the take-away is that any certification is only as good as how well the regularity of the hypothesis matches shape of data manifold across the distribution. 

## Minor Comments/Feedback
- The analysis implicitly assumes that the unit ball induced by the norm is a curved surface (which can reduce to piece-wise linear when the norm is \ell_1 for e.g.) so I request that the authors explicitly mention this upfront. 
- I would appreciate if the authors remove overloaded notation and have a single use of F, f and cal{F} and of the term "network function". O
- In page 3,"Note that two different neural networks f, f' may lead to the same predictions everywhere", are there examples of such networks f, f' where the weights aren't equivalent modulo layer-wise scaling? Also in this statement can f,f' be different architectures? 
- In Def 3, it should be  \forall delta>0, \neg cert(f, *x*, \epsilon + delta)
- Can the authors provide an example of when the robust frontier of a network is not piecewise linear? Is this only limited to situations where the data is supported on a curved (or non piecewise-linear) surface? 
- In Appendix A.1, proof of Theorem 1, should it be \sqrt{x^2+y^2} = \epsilon ? 
- In Appendix A.2, proof of Theorem 2, should it be "d(x) be the minimum distance of *x* from ..."
- I request that the authors add an explicit proof of Proposition 3 even if obvious. 
 
clarity,_quality,_novelty_and_reproducibility: The writing is imprecise in parts and I hope the authors make edits to address the minor comments. The ideas outlined are novel and interesting. The authors have provided code to reproduce their experiments. 
summary_of_the_review: I think this paper undertakes an interesting perspective on why there is a gap between Lipschitz-based certificates and robust accuracy we observe in practice. However for reasons outlined above, I feel that the connection to Lipschitz certification is weak and this work while interesting needs to further evolve before it can be published.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper discusses the fundamental problem for certification using piece-wise linear activations like ReLU. Lipschitz-based certification is mainly investigated and advocated with smooth activations.
strength_and_weaknesses: ### Strength

The authors present an interesting theoretical discussion regarding Lipschitz-based certification with regard to piece-wise linear activations.

### Weakness
- Branch and bound (BaB) is widely adopted to break the barrier for piece-wise linear activations and enable complete certification. Representative works include the recent VNN-COMP winner alpha-beta-crown, as well as other participants like OVAL, VeriNet, Marabou, ERAN, etc (see VNN-COMP21 report [A] for details and VNN-COMP22 for updates). These SOTA complete verifiers significantly scale certification to larger models, speeding up certifications, and generalizing to different robustness properties and architectures. The paper does not mention any of them in related works or evaluation. Analysis and discussion on this are crucial to making claims solid and convincing.
- To support the power/limitations of Lipschitz-based certification approaches, it is necessary to use existing Lipschitz-based certification approaches to confirm the theoretical observations and insights on either toy examples or standard robustness benchmarks. Also, many existing works including some tools mentioned before support smooth activations. Experimental evaluation should be presented to support using smooth activations over piece-wise linear activations.
clarity,_quality,_novelty_and_reproducibility: The paper has moderate clarity. Claims are new but not well supported by evaluation results. 
summary_of_the_review: Overall, the paper missed extensive evaluations to support the proposed theoretical claims. Also, key components (branch and bound approaches) missing in theoretical analysis.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper shows how piecewise-linear networks limit the tightness of "piecewise-linear limited" (PLL) certification procedures (such as Lipschitz-based certification). In particular, it demonstrates why piecewise-linear networks that require a small capacity to produce a robust boundary can require a much larger capacity to be _verifiable_ via a PLL certification procedure. Among the contributions of the paper include:

- Clear definitions for new ideas (e.g. completeness of certification procedures on a hypothesis class of decision boundaries; the notion of a certified frontier; PLL certification)
- Evidence (example + formal proof) explaining why PLL certification procedures can perform poorly around sharp inflection points in the boundary found in piecewise-linear networks.
strength_and_weaknesses: The paper is clear and presents a novel idea that advances our understanding of Lipschitz-based verifiability.

The paper has two key weaknesses:

1. It is not clear what certification techniques are PLL; the paper could do a survey of leading techniques and characterize each of them. Even better: the paper could demonstrate that any non-PLL certification procedure must be exponential in the number of non-linear units.
2. The paper does not provide any hypothesis classes that are both gradient-norm-preserving and yet enable smooth curves in the decision surface. While showing how PLL certification procedures are limited is a strong result, the paper would have been made even stronger if paired with examples of hypothesis classes that reduce the excess capacity required. A negative result (i.e. no hypothesis class requires less capacity than piecewise-linear networks) would also be valuable.

Some suggestions:

- Suggestion: The title of the paper is very broad. What about specifying exactly when exactly limitations are encountered (e.g. "Limitations of Efficient Lipschitz-based Robustness Certification for Piecewise Linear Networks")
- Suggestion: Similarly, the abstract is vague on what certification techniques are affected by piecewise-linearity (it refers to "leading certification techniques", while only showing the Lipschitz-based methods are PLL). If no other certification techniques are shown to be PLL, the paper should either 1) provide evidence that Lipschitz-based methods significantly outstrip all other techniques 2) be more specific tha only Lipschitz-based methods are affected.
clarity,_quality,_novelty_and_reproducibility: ### Clarity

The paper does a good job explaining ideas, with clear definitions and no unnecessary jargon. I particularly liked the example in Section 3.1. 

Some typos I noticed while reading the paper:

- Page 4: "Lipschitz-based certification has proven effective in the Literature"
- Page 6: "Would be necessary to simply separate them Bubeck & Sellke (2021)
- Page 9: "Due our Theorem 2"

### Quality
The paper advances our understanding of the role of capacity in Lipschitz-based _verifiability_. This builds on existing work that demonstrates that constraining the Lipschitz constant of the network (without concerning ourselves verifiability) means that additional capacity is required in the network. As outlined in Section 3.2, other researchers could build on this work to improve Lipschitz-based certifiable training methods by designing better hypothesis families.

### Novelty
To the best of my knowledge, the results and ideas in this paper are novel.

### Reproducibility
Reproducibility is not much of an issue as the paper is largely theoretical.

Minor issues:

- No details are provided on how the networks in Section 3.1 were trained. This makes it difficult to be certain that the order-of-magnitude increase in the number of neurons required to get to close to perfect VRA was not due to improper training. (For example: were the network trained adversarially? If so, what attack was used during adversarial training?)
summary_of_the_review: This paper advanced our understanding of the limitations of Lipschitz-based verification techniques in verifying the robustness of piecewise-linear networks, and points to a way to reduce the excess capacity required for verifiability. As existing Lipschitz-based verification techniques are the state of the art for $l_2$ norm-bounded perturbations, this represents a valuable contribution to the field. Nevertheless, my enthusiasm for this paper is tempered by its failure to consider other verification techniques and the fact that it does not show that it is in fact possible to reduce the excess capacity currently required by piecewise-linear networks. (Otherwise, I would have rated it at 8, rather than the current 6). Keeping in mind that this is a conference paper of limited length, I would still vote to accept unless some other reviewer identifies an issue I missed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors develop results showing limitations of certain classes of robustness certification procedures (those based on an analysis of global Lipschitz constants) for piecewise linear neural networks. 

Strengths:
1. Shedding light on fundamental limitations of particular verification approaches is valuable since it can help focus attention on other approaches that do not suffer from these.

Weaknesses:
1. The limitations developed do not apply to SOTA methods like alpha-beta CROWN (https://github.com/Verified-Intelligence/alpha-beta-CROWN). 
2. The authors do not study how the data distribution impacts this in practice, since the high density regions of the data distribution may not have significant overlap with the regions of input space where the decision boundary exhibits the properties the authors' results depend on.
3. The paper is framed too broadly and the claims are not well justified by the actual results. 

Hence, I recommend rejection. The reviewers agreed though, that the paper has some interesting ideas. I would encourage the authors to submit a revision to a future venue addressing the weaknesses.
justification_for_why_not_higher_score: The claims in the paper are misleading and not justified by the results.
Decision: Reject