Limitations of Piecewise Linearity for Efficient Robustness Certification
Authors: Klas Leino
Venue: Submitted to ICLR 2023 (2023)
Keywords: robustness
certification
Lipschitz
limitations
adversarial examples

Abstract: Certified defenses against small-norm adversarial examples have received growing attention in recent years; though certified accuracies of state-of-the-art methods remain far below their non-robust counterparts, despite the fact that benchmark datasets have been shown to be well-separated at far larger radii than the literature generally attempts to certify. In this work, we offer insights that identify potential factors in this performance gap. Specifically, our analysis reveals that piecewise linearity imposes fundamental limitations on the tightness of leading certification techniques. These limitations are felt in practical terms as a greater need for capacity in models hoped to be certified efficiently. Moreover, this is _in addition_ to the capacity necessary to learn a robust boundary, studied in prior work. However, we argue that addressing the limitations of piecewise linearity through scaling up model capacity may give rise to potential difficulties---particularly regarding robust generalization---therefore, we conclude by suggesting that developing _smooth_ activation functions may be the way forward for advancing the performance of certified neural networks.

Under review as a conference paper at ICLR 2023
LIMITATIONS OF PIECEWISE LINEARITY FOR EFFICIENT ROBUSTNESS CERTIFICATION
Anonymous authors Paper under double-blind review
ABSTRACT
Certified defenses against small-norm adversarial examples have received growing attention recent years; though certified accuracies of state-of-the-art methods remain far below their non-robust counterparts, despite the fact that benchmark datasets have been shown to be well-separated at far larger radii than the literature generally attempts to certify. In this work, we offer insights that identify potential factors in this performance gap. Specifically, our analysis reveals that piecewise linearity imposes fundamental limitations on the tightness of leading certification techniques. These limitations are felt in practical terms as greater need for ca- pacity in models hoped be certified efficiently. Moreover, this is in addition the capacity necessary to learn a robust boundary, studied in prior work. How- ever, we argue that addressing the limitations of piecewise linearity through scal- ing up model capacity may give rise to potential difficulties- paacouuuiiisppttulllrrllll regard- ing robust generalization therrfr, we conclude by suggesting that developing smooth activation functions may be the way forward for advancing the perfor- mance of certified neural networks.
INTRODUCTION
Since the discovery of adversarial examples (Szegedy et al.
2014). defenses against malicious input
perturbations deep learning systems have received notable attention. While many early-proposed defenses- -uchh as adversarial training (Madry et al. 2018) are heuristic in nature, growing body
of work secking provable defenses has arisen (Cohen et al. 2019
Croce et al.] [219 Fromherz et al.)
2021 Huang et al., 2021; Jordan et al.]
2019 Lee et al. 2020 Leino & Fredrikson, 2021 Leino
et al.
2021 Li et al. 2019; Singla et al.
2022 Trockman & Kolter [201] Wong et al. 2018 Zhang
al. 2018). Generally, such defenses attempt to provide certificate of local robustmess (given
formally in Definition M. which guarantees network's 's prediction on given point is stable under small perturbations (typically in Euclidean sometimes tor space); this precludes the possibility of small-norm adversarial examples on certified points.
The success of certified defense is typically measured empirically using verified robust accuracy (VRA), which reflects the fraction of points that are both (i) classified correctly and (ii) certified as locally robust. Despite the fact that perfect robust classification (i.e., 100% VRA) is known to be possible on standard datasets at the adversarial perturbation budgets used in the literature (Yang al. (20206), this possibility is far from realized the current state of the art. For example, on the benchmark dataset CIFAR-10. sate-of-the-ar methods offering deterministic guarantees of & ro- bustnes have remained at approximately 60% VRA (Huang et al. 2021 Leino al. 2021 (Singla al. 2022 Trockman & Kolter 2021). while non-robust models handily eclipse 95% accuracy.
is difficult to precisely account for this discrepancy; though among other reasons, otate-of-the-art methods typically use loose bounds to perform certification- as exact certification is (for general ReLU networks) NP-complete (Katz et al. 2017 Sinha et al., 2018) which conceivably leads to falsely flagging truly robust points or to over-regulaee rewurrrrizztiinnnn of the learned model. While conservative approximations may be necessary to perform efficient certification (and to facilitate efficient robust training), it is certainly possible that they foil reasonable hopes for "optimality." In this work,
In this work we primarily consider certified defenses that provide deterministic guarantee of local robust- ness, as opposed statistical guarantce. For further discussion of this point, Section 4

---

Under review as a conference paper at ICLR 2023
offer further insight into the shortcomings of modern certification techniques by analyzing their limitations in the context of the architectural settings in which they are conventionally employed.
In particular, we find that piecewise linearity- a practically ubiquitous property of neural networks considered in the certification literature (c.g., standard ReLU and the more recently popularized "MinMax" (Anil et al.) (019)) activations are both piecewise (thear)-fundanne of Lipschitz-based Eg local robustness certification. In effect, we argue, this means that extra capacity is needed simply for facilitating efficient certification-in addition to whatever capacity may be required for learning a robust boundary (e.g., as examined by Bubeek & Sellke (202T))
limits the power
On the other hand, perhaps surprisingly, we prove that free from the constraint of piecewise lin- earity, Lipschitz-basee certification is powerful enough to perform complete certification on any decision boundary. provided the implementation of the function giving rise the boundary is under the learner's s control (indeed, this is consistent with the fact that the highest performing certified defenses incorporate Lipschitz- based certification into training). These latter findings suggest that continued progress towards improving state-of-the-art VRA may be enabled through carefully cho- sen smooth activation functions P which do not inherently limit the power of what are currently the most promising forms of efficient local robustness certification.
In summary, the primary contributions of this work are as follows: (1) we show that piecewise linearity imposes inherent limitations on the tightness of efficient robustness certification-onn pri- mary focus is Lipschitz- based certification, but we discuss similar limitations of other methods in Appendix B (2) prove that Lipschitz- -based certification is fundamentally powerful for tight bustness certification, provided (i) the robust learning procedure has power over the implementation of the classifier, and (ii) the hypothesis class is not limited piecewise linear networks; and (3) we demonstrate that tight Lipschitz-based certification may require significant capacity overhead in piecewise-linear networks. These findings offer new perspective on the sticking points of modern certified training methods, and suggest possible paths forward.
We begin in Section 2 introducing the limitations piecewise linearity imposes on robustness certi- fication, starting generally, and narrowing our focus specifically to Lipschitz- bbase certification. We then discuss the role that capacity plays in mitigating these limitations Section which concludes with discussion of the implications of our findings, both retrospectively and prescriptively. Finally, we discuss related work in Section and offer our concluding remarks in Section 5
2 LIMITATIONS OF PIECEWISE LINEARITY
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. Therefore, in order for certification procedure to precisely recover the set of robust points-those which lie a distance of at least from the deci- sion boundary it must be capable of producing a boundary between robust and non-robust points that is not pnecewise-linean even on networks that are. However, as we will see, Lipschitz- based certification, for example, in fact constrained on piecewise-linear networks, as the set of just-certifiable points essentially corresponds to level curve the output of the network being certified.
produce a piecewise- -innerr---inarrr "certified frontier"
On the other hand, if the level curves of the function being certified correspond (up to some constant factor) to their distance from the decision boundary (and must therefore include smooth curves), Lipschitz-based certification identifies precisely the points that are truly e-locally robust, provided a tight bound on the Lipschitz constant. As we will make clear, this has important implications regarding the power of Lipschitz-based certification in properly suited network architectures.
In the remainder of this section, we formalize this intuition and discuss some of its implications. Section 2.1 introduces main theorem regarding the limitations imposed by piecewise linearity, along with the necessary background and definitions. Section 2.2 narrows the focus to Lipschitz- based certification, showing that despite being powerful in general. is fundamentally limited within the hypothesis class of piecewise linear networks. Finally, Section 2.3 presents a thought experiment that provides basic intuition about the possible scale of the problems caused by these limitations.
"Or least, activation functions which enable learning curved (as opposed to piecewise linear) functions.
2

---

Under review as a conference paper at ICLR 2023
2.1 FUNDAMENTAL LIMITATIONS TO CERTIFICATION COMPLETENESS
For our purposes, we will consider a neural network to be a function f Rn + Th mapping n- dimensional inputs to logit values corresponding m different classes. From the network function f. we derive a neural classifier, F : IR" - RRm, by letting F(#) = argmax f(xx). When it is clear from the context which we are referring to, we will use the term "neural network" for both the network function f and its corresponding classifier F. Note that two different neural network functions, f and f', may lead to the same predictions everywhere, i.e., Vx F(x) Fx(x). When this happens, we say that and f' share the same decision boundary, where the decision boundary is simply the set of points where [i( = [z) for some i + j E [m]]
In this work, we consider the problem of local robustness certification. As in prior work, we define local robustness as a property of point r and classifier F. parameterized by perturbation budget, or robustness radius, e, as in Definition [T
Definition 1 (e-Local Robustness). A classifier F R" + [m] is e-locally robust at point R", with respect to norm ||: 1b if
Va' E" |10 x' l SE = =(x)=((x')
A certification procedure, cert, is function that takes a neural network, f. point, and perturbation budget, e, and produces a label in {0, 1}, where an output of means that f certi- fied as e-locally robust at x. A valid certification procedure must be sound, i.c., cert(f,x, F is e-locally robust at æ; however, need not be complete, i.e. it may be the case that (ert(f,z,e) 0 and yet F is in fact e-locally robust at x.
For given certification procedure, let the certified regions of J. Ceere be the set of points that can be positively certified by cert. Similarly, let the robust regions of be given by the set R(F, e) = {a F is e-locally robust at æ} of e-locally robust points (note that, in contrast to Czart, R does not depend the implementation of f, only its classification outputs, given by F).
= (f.
(:::::er(ti) cert(J, a, })}
Soundness entails that Vf (c.r=(f.c) S. R(F,c), but clearly it is desirable for Ccert (f,c) to match e) as tightly as possible; when this is achieved perfectly we can consider cert to be "complete." " However, as Coart (J) can depend on the underlying function, J. which has surjective mapping to classifiers, F, derived from the same hypothesis class, we must be careful in defining completeness precisely. Let F be hypothesis class-a a family of functions of type R" + R". c.g., that are captured by some neural network architecture. We will also use the slight abuse of notation, F E F, to denote any F: R - [m] such that there exists a function I' F which produces the same labels as F on all inputs, i.e., Vx F(x) argmax [m(] (x)). We say that certification procedure, cert, is complete on F if all possible decision boundaries achievable by functions in the hypothesis class have at least one implementation in FF for which cert perfectly recovers the true robust regions. This is stated formally in Definition [
Definition 2. A certification procedure, cert, is complete on hypothesis class, F, if > 0
FF EF (Yx.. F(x)= = argmax M(x)) ^ (Cae
(e(m)
Essentially, completeness over hypothesis class entails a notion of compatibility between the cer- tification procedure and the hypothesis class; specifically, it means that for any decision bound- ary expressible by the hypothesis class, it is possible for a learning procedure to produce a model that implements the decision boundary in a way that makes the certification procedure complete. provides key relaxation from a stricter notion of completeness that would require Coert (f, R(F.e) e) for all f. as this would not be achievable by any polynomial certification procedure Katz et al., 2017 Sinha et al. 2018). By requiring tight certification only modulo the decision boundary, we avoid this limitation, splitting the responsibility for completeness between the certification procedure, the learning algorithm, and the hypothesis class.
Definition 2
Next, we will also find it useful to define the certified frontier of F under cert (Definition 3) essentially, the set of points that are just barely certified, which lie at the frontier of the certified
Asssumngg P NP.
3

---

Under review as a conference paper at ICLR 2023
regions. We will similarly define the robust frontier as the set of points that are just barely e-locally robust, which lie at the frontier of the robust regions.
Definition 3 (Certified Frontier). The certified frontier of neural network, F R - [m]] under certifier, cert, at perturbation budget, e, is the set of points
={ {= cert(f.x,e)
(48=0.-0 (60=0.-cet(ffeett)) }.
([Ccer((f.e) =
We now turn to the specifics of one of our main results, namely. that piecewise linearity is lim- iting factor for tight certification. Of course, as alluded to earlier, some certification procedures do achieve complete certification et al. ( such methods are invariably exponential. Thus, we characterize the set of piecewise-linear limited (PI..) methods in Definition Intuitively, certification procedure is PLI. if it is constrained to produce piecewise-linead certified frontiers on piecewise-linee -ineer models.
seceewsse-iinat networks- e.g.. (Jordan et al.) 2019; Tjeng
Definition 4 (Piecewise-linee piecewise-lineal limited (PI..) if
Limited Certification). A certification procedure, cert. is
vf f is piecewise-linear = A(Ccert is piecewise-
Note that the robust frontier of network F is, in general, not piecewise linear, even if F (and thus its decision boundary) is piecewise linear. Thus, if the certified frontier of cert is piecewise linear, cert cannot be complete, i.c., C * R. Moreover, this means that any piecewise- winnar limited certification procedure cannot be complete on the hypothesis class of piecewise linear networks (Theorem D}. The proof of Theorem is given formally in Appendix[A.]
Theorem 1. Any piecewise-lineur limited certification procedure is incomplete on the hypothesis class of piecewise linear networks.
The proof of Theorem Taeeemm[reiiee relies on the fact that piecewise- linear function cannot be equal a fune- tion exhibiting smooth curves. However, it is known that neural networks, provided with enough capucity, can approximate any function with arbitrary precision (Hornik) [991}. We address this point in Section 3 where we discuss the implications of Theorem regarding the capacity require- ments of tightly certifiable networks.
2.2 THE POWER AND LIMITATIONS OF LIPSCHITZ-BASEI CERTIFICATION
We will now narrow focus to consider the specific family of Lipschitz- basedd certification meth- ods. Such methods perform certification by using an upper bound, K, on the network's Lipschitz constant; essentially, a point is certified if the margin by which the top-predicted class exceeds all other classes is greater than ek. In our work, we will set aside the details around how the Lipschitz obtained, though this is also source of potential looseness in the general approach. That is, we will (optiisttcallly) take for granted that tight bound is obtained in our analysis.
Lipschitz-based certification has proven effective in the literature, achieving state-of-the-ar performance-wine -when paired with an appropriate training routine-despinn its simplicity (Leino et al.) 2021 Trockman & Kolter 202T). Lipschitz-based certification is advantageous in many ways; in addition to being casy to incorporate into robust learning objective, it enables zero-cost certifica- tion at run time, as the Lipschitz constant does not need to be recomputed after training. On the other hand, it would seem that Lipschitz-based certification is fundamentally underpowered- the "global" Lipschitz constant is a conservative estimate of the local Lipschitz constant, which in turn gives conservative estimate of how much the net output can change within given neighborhood. If a primary sticking point for advancing certified accuracy is loose certification, it is fair to ask how promising Lipschitz-based certification will continue to be.
The philosophy behind incorporating Lipschitz- based certification into training is essentially that the potential shortcomings of Lipschitz-basee certification can be addressed by learning a easily certifiable network function. We show that this intuition is essentially correct. Perhaps surprisingly, show that Lipschitz-based certification is sufficiently powerful to be complete the hypothe- sis class of Lipschitz functions") [ However, we also show that Lipschitz-based certification is PLL, meaning this potential cannot be achieved with hypothesis class constrained by piecewise linearity.
'I.c,, with bounded Lipschitz constant. Note that this is not meaningful constraint for neural networks, as any neural network with I Lipschitz activation functions and finite weights Lipschitz in this sense.
4

---

Under review as a conference paper at ICLR 2023
2.2.1 LIPSCHITZ-BASER CERTIFICATION IS POWERFUL
We begin by showing that for any boundary achievable by a Lipschitz network function, when the learner is given control over the precise network function implementing the boundary, it is always possible to find an implementation that can be tightly certified using Lipschitz-bais basseitz-based certification. This is stated formally in Theorem
Theorem 2 further entails that there exists a network function for any 2e- 2e-separated data that achieves perfect VRA under Lipschitz-based certification. The proof of Theorem is given in Appendix A.2 Theorem 2. When the hypothesis class, F, is given as the set of Lipschitz functionn, Lipschitz-based certification is complete on F.
2.2.2 LIPSCHITZ- CERTIFICATION IS LIMITED BY PIECEWISE-LINEARRTY
Despite the power of tipschitz-based certification for general functions, when restricted to the hy- pothesis class of piecewise linear networks, it becomes fundamentally limited. That is, formally, Lipschitz-based certification is PLL (Proposition 3)
Proposition 3. Lipschitz-basse based certification is piecewise- limited.
Proposition follows essentially because the certified frontier of Lipschitz-based certification cor- responds to a particular level curve of the network function, which is piecewise linear whenever the function is. As direct consequence of Proposition and Theorem [ arrive Corollary 4
Corollary 4. Lipschitz-basee certification is not complete on the hypothesis class of piece-wise linear networks.
Note that taken in the context of Theorem 2 Corollary means that in sense, the fundamen- tal limitation of Lipschitz-based certification is not intrinsic to its simplicity (e.g.. because the lo- cal Lipschitz constant might be tighter than the global constant on some functions), but rather, is related to the hypothesis class of networks being certified. Put differently, piecewise linearity imposes real limitations on Lipschitz- based certification that cannot be attributed to practical, but non-fundamental. issues, such efficient computation of Lipschitz bounds, etc.
2.3 THE PROBLEM WITH CORNERS AND THE CURSE OF DIMENSIONALITY
The incongruence between the piecewise-lineal certified frontier of Lipschitz-basee methods, and the robust frontier of piecewise- linear boundary, which features smooth curves, becomes relevant when the boundary comes to a "corner," or relatively sharp inflection point. At corners, the robust frontier curves a fixed radius around the corner, while the certified frontier, absent aid from addi- tional capacity (see Section 3). runs parallel to the facets forming the corner, offset by fixed amount (see Figure 2 in Appendix D for an illustration). The sharper the corner, the larger the difference will be between the corresponding robust and certified regions. Additionally, we will see that this also true the higher the dimension of the corner, i.e., the more independent half-spaces meet to create the corner.
As thought experiment, we will model a dddimensional corner as the intersection of d orthogonal half-spaces. Assuming the level curves near the corner run parallel to the half-spaces, h E H. forming the corner, in the best case, the certified region given by the union of half-spaces obtained by flipping each h H and shifting it by e. Consider the hypercube of width just opposite the corner. This hypercube lies entirely outside the robust region, meaning all points within it cannot be certified using Lipschitz-based certification. However, only the points intersecting the hypersphere of radius e centered at the corner are truly non-c-robust. We can compute the ratio of the volume of the hypercube the intersecting portion of the hypersphere, given by Equation] T
4/2
2c
As the dimension increases, this ratio tends to zero, meaning that in high dimensions, almost all points in this region opposite the comner are incorrectly uncertified. Furthermore, the maximum distance from an uncertified point within this region to the boundary is equal to the diagonal of the hypercube, which is given by vd This means that even points that are significantly more robust than required may yet be uncertified.
5

---

Under review as a conference paper at ICLR 2023
VRA 0,909
MiA 0.885
yial 0,947
VIA 0.3
(a)
(b)
(d)
Figure 1: (a) synthetic dataset with two classes (shown in purple and yellow) derived to be positioned at distance from ideal boundary that forms 90 corner. (b) MinMax network implementing (with minimal capacity) an optimal boundary with respect to which all points are e-locally robust. The non-certifiable region is shown in green, and the level curves are also depicted. The Lipschitz constant of this network is 1, but not all points in the top right quadrant can be certified. {c d networks trained with 1x, 10x, and 100x the minimal capacity required for the optimal boundary in (b). With 10x capacity the learned VRA exceeds that of the minimal implementation, but near- perfect performance not obtained with less than 100x capacity. The code used to generate these examples is included in the supplementary material. Details are provided in Appendix C
3 THE ROLE OF CAPACITY
The primary limitation of Lipschitz- certification in sencewise-linear networks derives from the fact that we cannot have smoothly curved level curves in such networks (or, more generally, that PLL certification methods cannot have smoothly curved certified frontiers in such networks). However, while this true in the strictest sense, function with smooth curves can be approximated with arbitrary precision, given sufficient capacity. In other words, increased network capacity may be one possible option to mitigate the fundamental limitations discussed throughout Section 2 this section, we investigate the capacity requirements necessary for tight PLL certification in piccewise- linear networks.
While the precise meaning of "capacity"" in a quantifiable sense is bit nebulous, for our purposes, we will consider capacity in a piccewise-linear network to correspond to the number piecewise- linear regions. This grows with the number of internal neurons, though the relationship may vary depending on other aspects of the network architecture, e.g., the depth of the network.
Previous work has studied the capacity implications for learning robust decision boundary, finding that separating points while controlling Lipschitzness may require additional capacity beyond what would be necessary simply separate them (Bubeck & Sellke 202T). Besides the capacity required to represent the decision boundary in a robust network, our work asks instead about the capacity required tightly certify given boundary. We find that in a piecewise linear network, even if the boundary is optimal- in that all points in the distribution are indeed distance of or more from it the network may require additional capacity to be able to prove this using the Lipschitz constant.
Taking the data distribution aside, we consider the goal of certifying all points that are sufficiently far from the boundary. As highlighted in Section 2.3 places where the decision boundary forms high-dimensional "corners," " there may be relatively large volumes of points that are e-far from the boundary but cannot be certified as long as the level curves simply run parallel to the boundary. In such cases, tight certification requires extra capacity specifically to round out the level curves around the corners in the decision boundary. We begin by demonstrating this concept via an illustrative example. We conclude by discussing the implications of our results and suggest avenues for future work.
3.1 AN ILLUSTRATIVE EXAMPLE OF HOW CAPACITY ENABLES TIGHT CERTIFICATION
As an example of how Lipschitz-bard certification can require excess capacity beyond what is necessary to learn robust boundary, consider synthetic 2-D dataset that can robustly separated by a simple piecewise linear boundary. An illustration is provided in Figure Ia We begin with a decision boundary given by B {(11, 22) max(#1, 0): this boundary separates points

---

Under review as a conference paper at ICLR 2023
with negative X- and y-coordinates from points in the other three quadrants, and forms a 90 corner at the origin. The data are then generated such that all the points with label 0 lie a distance of at least below and to the right of the boundary, and the points with label lie distance of at least above and to the right of the boundary. Specifically, the 1-labeled points curve around the boundary such that there is a tight margin of exactly 2e about the boundary.
By construction, the function f(z) = [0, max( =2)] produces logit values that yield the boundary B. with respect which all points the dataset are e-locally robust. This function can be trivially implemented with minimal capacity by a simple MinMax network, f(xx =<<WW)) where
the MinMax activation function, and W and W2 are given by Equation 2
101
1 0 1
W = 0 0
[
W
Furthermore, the Lipschitz constant of f 1 this can even be tightly obtained by taking the layer- wise product of the layer operator norms, as is typically done in practice. Hence, the points that can be certified will be those for which (x) - fo(=)] 2 e; that is, the points outside the level curves max(x1, 222 = - and max((11, x2) = e. However, we see that this certified frontier fails to certify many points in the positive x-y quadrant, despite the fact that all the points are indeed robust with respect to the boundary of f. This is depicted in Figure lb
In order to certify these points, we need the level curve corresponding to f1 (x) fo(x) = e to bend smoothly around the boundary, rather than forming the same 90º angle. This requires more capacity.
To gain a sense of how this plays out in practice, we consider adding capacity via expanding the number of neurons in the hidden layer (which contained only two neurons in minimal example). In Figures and Tel we show the boundaries of two additional learned networks, 9 and h, with 20 and 200 internal neurons, respectively. We see that increasing the number of internal neurons by an order of magnitude yields a better set of level curves, but the network still must compromise as the level curves are not smooth enough to tightly follow the contour of the data. Finally, when we increase the number of internal neurons by two orders of magnitude, we at last obtain a function h that achieves nearly 100% VRA on our sample data. This function, as desired, forms essentially smooth level curves that bend around the boundary corner with radius of c. Interestingly, h learns a boundary that is somewhat different from the boundary originally used to derive the data; however, both boundaries can be thought of as "equivalent" in the sense that they produce the same margin, reflecting that the optimal boundary for this dataset is not unique.
Discussion. In our example, we needed 100 times more neurons than were necessary to construct an optimal decision boundary order to tightly certify the boundary with the Lipschitz constant. While it is difficult to extrapolate from this toy example to a "real world" scenario, our results suggest that smoothing the level curves may require significant overhead beyond the capacity necessary to produce truly robust boundary.
Another aspect of this experiment worth noting is that when the network had insufficient capacity to learn an optimally robust, tightly certified boundary (e.g., in Figures Ic and [d), the resulting model tended to compromise by making the corner less sharp (compared to the desired 90º angle). Geomet- rically, when the boundary has inflection with wider angle, the difference between the certifiable frontier and the frontier of robust points is less pronounced (consider for example, what happens then the inflection approaches 180"). In effect, this means that while under- paddeepprrmettiizzationn of piecewise-lines models may be a problem for robust model performance in practice, this limitation may be (at least in part) manifested as an under-fit model opposed to one with many robust. but non-certifialle points. This is reflected in the empirical results for certifiably trained models in the literature, which typically have lower "clean accuracies" than their Handard-trained counterparts. However, we note that these models also exhibit a discrepancy between their certified accuracy and their vulnerability to actual attacks, leaving the possibility that they may also fail to certify some truly robust points.
'oore properly put, the Lipschitz constant of [f woich represents the margin by which the predicted class exceeds the poe-predicted class-is 1.
7

---

Under review as a conference paper at ICLR 2023
3.2 POTENTIAL DRAWBACKS OF THE CAPACITY ESCAPE HATCH
As we have seen, by adding capacity, we can help overcome the limitations of piecewise linearity by enabling the network to approximate smooth curves around corners in the decision boundary. For universal tight certification, this needs to be done in the neighborhood of all corners on the decision boundary. To the extent that each corner requires independent capacity, hopes for the scalability of such an approach seem slim; albeit, VRA only requires tight certification on the data manifold, meaning that extra capacity should only be needed places where the decision boundary has sharp inflections near in-distribution points.
However, this, too, presents an interesting problem. Namely, the network only has incentive to allocate capacity to round the level curves in the places that are necessary to certify its training set; i.e. where inflections
the decision boundary encroach on training points. Meanwhile, if similar inflections exist near test points not seen during training, the learned network may fail to certify them-even if the boundary is general, and even if it is also robust. In other words, we are faced with not only the challenge of learning a generally robust boundary, but additionally of learning generally certifiable function. Indeed, generalization of VRA is empirically observed to be worse than the corresponding "clean accuracy" would indicate principle that has been noted in prior work due to its privacy implications (Yoom et al. (020)).
A Proposed Way Forward. Another possibility for addressing the fact that Lipschitz- cer- tification is PL.L is to expand the hypothesis class to enable smooth curves in the decision surface. Ultimately, our analysis shows that Lipschitz-based certification is most effective when the level curves of the network function accurately reflect the & distance to the boundary, which requires the possibility of smooth curves. This goal may be best achieved by purpose-built activations, as piecewise linearity stems from the choice in activation function.
State-of-the-ee Lipschitz-based certifiable training methods have enjoyed increased success in re- cent years through leveraging MinMax activations (Anil et al. 2019) or variant thereof proposed by /iingla al. (2022) are piecewise linear. MinMax has distinct advantage over the more common ReLU activation, due to its gradient-norn -oree-reeeno----innn (GNP) property, which [Anil et al.) demonstrate is key for tight, efficient Lipschitz bounds. While the need for gradient norm preserva- tion remains clear, we posit that some form of smoothness is an additional desirable property, as it would free the hypothesis class from piecewise linearity. We believe the task of designing suitable smooth activation functions for PLL-certified networks is a promising avenue for future work.
4 RELATED WORK
Power and Limitations of Lipschitz-based Certification. Several of the early efforts around ro- bustness certification focused on post hoc certification of networks trained outside of the control of the certifier. This is a fundamentally hard problem, shown to be NP-complete by Katz et al. (2017) and (iinha et al. (2018). While this fundamentally limits the tractability of complete post hoc certi- fication, the limitation is of lesser concern for modern approaches that incorporate certification into the training objective, thus encouraging learning models that better facilitate efficient certification.
The specific limitations of Lipschitz-based certification have also been of great interest in the prior literature. Most of these results particularly consider the practical problem of bounding neural network's Lipschitz constant. For example, Huster et al. (2018) note that the common method of using the product of the layer-wise operator norm cannot tightly bound the Lipschitz constant of even basic functions in ReLU networks. Anil et al. 2019) study this point further demonstrating a trade-off between expressive power and efficient Lipschitz bound computation in networks with non-gradient--one -orrieenntto-----o moom--pessrring activation functions. This limitation is handled by using network ar- activation function such as MinMax, and orthonormal
chitectures with paadienttnorm-preseevee linear operators (though the latter need not necessarily be strictly enforced as it is learnable ob- jective). Anil et al. conjecture that such networks are universal I-Lipschita,funce function approximators, suggesting that learning any Lipschitz function in such way that the Lipschitz constant can be bounded tightly and efficiently is possible. By contrast, our work points to previously unstudied limitations that separate from the Lipschitz constant bounding problem, and are indeed not miti- gated through the use of MinMax activations, which are piecewise linear. However, we propose that the limitations brought forth in our work may similarly be addressed via novel activation functions.
8

---

Under review as a conference paper at ICLR 2023
On the flip side, previous work has also touched on the power of Lipschitz- certification. (Leino jet al. 202I) showed that certification with the global Lipschitz constant can be as powerful as with the local Lipschitz constant when the model is under the learner's control. We extend this result in a number of key ways. First, we prove a stronger result that can be stated for all points, rather than for finite set of points certified via the local Lipschitz constant. Second, we explicitly consider the hypothesis class, demonstrating that smoothness is a necessary condition to achieve this result.
Capacity Requirements for Robust Neural Networks. Understanding the role of capacity in deep neural networks has been a topic of interest in general, particularly due to the demonstrated effectiveness of highly over-parameterized models (Arora et al. 2018 Bubeck & Sellke| 2022 || Du jet al. 2019; Garg et al. 2022] Zhang et al. 2017). Recent work has also investigated this subject in the particular context of robust models. Bubeck & Sellke (2021) showed that under mild regularity assumptions, learning a highly accurate model with small Lipschitz constant requires significantly more parameters than would be required with no constraint on the Lipschitz nonstant-where the capacity overhead, in terms of the number of parameters, scales with the dimension. While a con- trolled Lipschitz constant is central successful Lipschitz-based certification, our work (e.g.. our example in (ection(.1l) shows that Lipschitz interpolation between points of opposite class is not sufficient for certification. As our analysis is focused on certification rather than Lipschitz interpo- lation, we complement the work of Bubecck & Sellke| showing that even further capacity may be required to appropriately bend the function's 's level curves to facilitate Lipschitz- based certification.
In addition to the information--heoreld capacity requirements, large numbers of parameters in deep networks may be necessary to facilitate efficient learning (Arora et af. 2018 Du et al. 2019). Re- cently, Garg et al. (2022) showed that robust learning in particular may require even greater over- parameterization than standard learning. Results such as these are complimentary to work such as ours, which focus minimal parameterizations.
Randomized Smoothing. Our work has focused on deterministic certification. By contrast, ran- domized smoothing (Cohen et al. 2019 Lecuyer et al. 2018) has become a popular method that instead provides a statistical guarantee of robustness. Randomized smoothing (RS) essentially modifies the original function by predicting the expected label under Gaussiar noise. These predic- tions are empirically determined through sampling, with the statistical certificate depending on the unanimity of the sample labels. While RS provides a weaker robustness guarantee, it solidly out- performs deterministic methods in terms of certified accuracy. Interestingly, it seems clear that RS is not PLL, since it naturally smooths piecewise linear networks, leading to a smooth boundary and certified frontier-this may be one of the keys to its success. This observation gives further support to the notion that ofate-of-the-ant art deterministic methods may be held back by piecewise linearity, and may benefit from smooth activation functions.
CONCLUSIONS AND FUTURE DIRECTIONS
Incorporating Lipschitz- based certification into robust training procedures has proven to be the most effective way to achieve high deterministic & verified-robust accuracy yet considered in the litera- ture. Due to our Theorem 2] there is reason to believe Lipschitz-base certification has the power remain as promising as current results suggest. However, we also showed that restricted to the hypothesis class of piecewise-linear networks, as has been the standard regime, Lipschitz-based certification becomes fundamentally limited. For piccewise-lie Lipschitz- based certification may require significantly more parameters, which, even if tractable, can complicate certifiably robust generalization (e.g., see Section 3.2). On the other hand, rather than viewing this as fundamental drawback for Lipschitz-based certification, we propose that purpose-built activations- is promising avenue for future work to free the most promising form of efficient deterministic certification from the limitations of piecewise linearity.
networks, this means that tight
the correct smoothness and gradient-norm -orr--resermvn-ng properties-
Prior work has considered other distributions well (Yang et al. 2020al

---

Under review as a conference paper at ICLR 2023
REFERENCES
Cem Anil, James Lucas, and Roger Gross. Sorting out Lipschitz function approximation. In Inter- national Conference on Machine Learning (ICML), 2019.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparamcterization. In JCML, 2018.
Sebastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. In NIPS, 2021.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning (ICML), 2019.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of ReLU net- works via maximization of linear regions. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes wwer-parameterized neural networks. In ICLR, 2019.
Aymeric Fromherz, Klas Leino, Matt Fredrikson, Bryan Parn,, and Corina Päsäreanu. Fast ge- ometric projections for local robustness certification. In International Conference on Learning Representations (ICLR), 2021.
Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, and Mingyuan Wang. Over- parameterized (robust) models from computational constraints, 2022.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 1991.
Yujia Huang, Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar. Training certifi- ably robust neural networks with efficient local lipschitz bounds. In NIPS, 2021.
Todd Huster, Cho- Yu Jason Chiang, and Ritu Chadha. Limitations of the lipschitz constant as de- fense against adversarial examples. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Dalabases, 2018
Matt Jordan, Justin Lewis, and Alexandros G. Dimakis. Provable certificates for adversarial exam- ples: Fitting a ball the union of polytopes. In Neural Information Processing Systems (NIPS), 2019.
Guy Katz, Clark W. Barrett, David L. Dill. Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer-Aided Verification (CAV), 2017.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy (S&P), 2018.
Sungyoon Lee, Jaewook Lee, and Saerom Park. Sipschitz-certifaatee training with a tight outer bound. In Neural Information Processing Systems (NIPS), 2020.
Klas Leino and Matt Fredrikson. Relaxing local robustness. In Neural Information Processing Systems (NIPS), 2021.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference on Machine Learning (ICML), 2021.
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Joern-Henrik Jacob- sen. Preventing gradient attenuation in lipschitz constrained convolutional networks. In Neural Information Processing Systems (NIPS), 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
10

---

Under review as a conference paper at ICLR 2023
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. In NIPS, 2019.
Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on cifar- 10 and cifar-100. In ICLR, 2022.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations (ICLR), 2018.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations (ICLR), 2014.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations (ICLR), 2019.
Asher Trockman and Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations (ICLR), 2021.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In International Conference Machine Learning (ICML). 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In ICML, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Neural Information Processing Systems (NIPS), 2018.
Kai Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster
adversarial robustness verification via inducing relu stability. In International Conference Learning Representations (ICLR), 2019.
Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya P. Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. 2020a.
Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R. Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. In Neural Information Processing Systems (NIPS), 2020b.
Samuel Yeom, Irene Giacomelli, Alan Menaged, Matt Fredrikson, and Somesh Jha. Overfitting, robustness, and malicious algorithms: A study of potential causes of privacy risk in machine learning. Journal of Computer Security, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.
Huan Zhang, Tsui Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Neural Information Processing Systems (NIPS). 2018

---

Under review as a conference paper at ICLR 2023
A PROOFS
A.1 PROOF OF THEOREM
1
Theorem Statement. Any srrcewise-linedd limited certification procedure is incomplete on the hypothesis class of piecewise linear networks.
Proof. It suffices to show that there exists boundary achievable by a piecewise-lineal network for which no PLL certification method can tightly certify. We proceed by producing a piecewise linear boundary that induces a smooth robust frontier. This is sufficient to prove our theorem, as A (CCee (f. # A((((F))) = Coert (f.c) # R(F,e).
Consider the 2-D boundary given by max(x, v) 0. Clearly, this boundary exists within the class of piecewise linear functions as the function [(r,, v) = max(x, y) piecewise linear. Now consider the points in the positive x-y quadrant. The points in this quadrant that are at distance from the boundary are given by Vx2² + y² which is not piecewise linear. By definition, any certification method that is PLL must have certified frontier that piecewise linear. Thus, the certified frontier of such any such method cannot be equal to /x² - y² e in this quadrant.
A.2 PROOF OF THEOREM 2
Theorem Statement. When the hypothesis class, F, is given as the set of Lipschitz functions, Lipschitz-batee certification is complete on J.
Proof. Let F be the set of Lipschitz functions. Consider the decision boundary any function f F. Define f' follows: let d(xx) be the minimum distance of from the decision boundary and let f'(x)= = d(x)) 1 P(a), where 1l F(x) is the one-hot encoding of F(x).
First, observe that S f is 1-Lipschitz for all + j. see this consider the following. The Lipschitz constant is given by
(U](()) - f(()))
-(('))
[5(00 - f7(x') + f((')- [x))
sup 12.2
suup ",,0
|| x'1l
1|
Consider points and a', and let assume that ||x-x'11 6. We would like to bound the quantity given by (4) the numerator in 3 by 8. (z)(z) f((2') f((2²) f(()
(4)
There are a few cases to consider. First if F(x) and F(x') are both different from é and j. then (4)
is 0 5. Since (4) is symmetric in both i and j. and and x', without loss of generality, assume F(x)= = j. This leaves two cases: when F(x') = j. and when F(x') A j. (in the latter case will not be concerned with whether not F(x') i).
will
In the first case we have
- (d(x) d(z')l d(x:) - d(x')
(5)
without loss of generality
(6)
Let be the nearest point on the boundary to x', such that which d(x') || all. Thus,
d(x)) S ||x - all
as a is on the boundary
(7)
- || - I'll + 1|
all
by the triangle inequality
(8)
= + d(x')
(9)
d(x) d(x') < 8
as desired
(10)
In the second case, x and x' are given different labels and we have
4 fz(x) + f((x')) S <d(r)) + d(x²)
(1I)
f((') is at most d(x') (achieved when F(x')
(12)
12

---

Under review as a conference paper at ICLR 2023
Since and x' are given different labels, there must be at least one part of decision boundary that bisects the line segment connecting z and x²; let a be this intersection point. Additionally, since
is on the boundary, must have that d(x) $ || all and d(x') || all. Thus, desired,
d(x) + d(x') S || all + ||æl all = This allows us to conclude that - - f is I-Lipschitz for all + j. as claimed.
(13)
The points that are certified by Lipschitz- based certification are those for which 14 holds, where j = F()) and Kj; is the Lipschitz constant of fj ft.
min (f)(z) ((()) EK -eKKiKKiii 20 ig)
(14)
Notice that when * F(x), f((x) = 0. Thus 14 can be simplified to fz(z) = d(x) 2 e, noting also that K3 j. Therefore, the points that can be certified via Lipschitz-based certification are those for which d(x:) 2 which are precisely the points that are locally robust.
A.3 PROOF OF PROPOSITION 3
Theorem Statement.
Lipschitz-based certification is piecewiss- limited.
Proof. Assume the function, f. being certified is piecewise linear. Without loss of generality, con- sider inputs for which the network predicts class j. The margin by which class j surpasses all other classes is given by m(x) min; {f, f((x)) Note that m piecewise linear as f is piecewise linear. Let K be the Lipschitz constant of The largest radius that can be certified at then mt/k. Thus, the certified frontier given by m/K K = e; this corresponds to the level curve K. Since is piecewise linear, this level curve is piecewise linear.
of corresponding to Thus, the certified frontier is piecewise linear, and Lipschitz-baud certification is PLL.
B LIMITATIONS OF OTHER CERTIFICATION METHODS
B. LIMITATIONS OF LOCAL-LIPSCHITZ- BASED CERTIFICATION
State-of-the--e deterministic &z certified performance is currently achieved using Lipschitz-based certification, which outperforms other types of certified training methods (Leino et al. 2021 Trock- man & Kolter 2021) such those based on convex relaxations-e. e.g.. (Wong et al.] [0018]
max-
imizing linear regions-e.g. (Croce et al. 2019 Xiao et al. 2019). Unsurprisingly, however, meth- ods that use the local Lipschitz constant for certification can achieve similarly high VRA (Huang et al. 2021), though this comes at the cost of significantly slower certification.
The local Lipschitz constant at point is given by (x) in Definition 5 which essentially corre- sponds to the maximum slope of the function within an neighborhood of æ.
Definition 5. The local Lipschitz constant is given by
[f(z)) f(x2)) ||01
K2(x)
sup
||
| m
Se
x2
Lucal-Lipschitz-bused certification, similar to Lipschitz-based certification (Section 2.2). certifies points, when the margin by which the top-predicted class, F(x). exceeds all other classes is greater than e (x)
While the local Lipschitz constant is always lower bound for the global Lipschitz constant- and therefore local-Lipschitz-bene based certification can possibly be tighter- Lece-lloal---L Lowcal--ipschitz-baeeee certifi- cation is nonetheless equally limited.
We will consider a generous setting in which the bound used for certification is exact, i.e., where the certification procedure has oracle access to K. Because K2 (z(x) is not piecewise linear, local- Lipschitz- based certification is not strictly piecewise-linee limited (PLL) in this setting. It is worth noting, however, that methods for approximating the local Lipschitz constant may not leverage this
13

---

Under review as a conference paper at ICLR 2023
smoothness in practice. Regardless, we show that docal-Lipschitz-basee certification is incomplete on piecewise-linext networks (Theorem 5).
This result is related to the fact that when the learner is given control over the implementation of certification can match the power of local- sooal-Lipschitz-basce
the boundary, (global) Lipschitz-bars certification; this result has been proven in slightly weaker formulation by Leino et al. (2021). We
provide an alternative theorem statement and proof here that better aligns with the insights in this work.
Theorem 5. Local- Doaal-Lipschitz-based certification is not complete the hypothesis class of piecewise-linees networks.
Proof. It suffices show that there exists boundary achievable by a piecewise-liness network for which no corresponding piecewise-lineal implementation can be tightly certified by Dipsh--ipschitz- based certification. Recall that by Corollary there exists such boundary for (global) Lipschitz- based certification. We will consider one of the same such boundaries.
For particular value of e, consider the points (R(F, e)), which are at distance exactly e from the boundary. There are two cases to consider: either (1) the local Lipschitz constant is always the same everywhere, i.e., VE > 0, Van, 32 A ( F, s)), (a(mn) = (x2), or (2) there some variation in the local Lipschitz constant, such that 36 0, 22 E A (R(F,e) where K, (x(z) * K. (x2)).
K (the global Lipschitz constant), meaning that local- Lipschitz-based certification will certify the exact same points (global) Lipschitz-based certifi- cation. Thus, by Corollary f
In the first case, we see that K²(x)
there must be point which is robust at radius but not certifiable.
In the second case, without loss of generality, assume Ke(z1) > Kr (12). Because / is piecewise linear, it is comprised of a finite number of linear functions, which in turn have a finite number of distinct slopes (gradient norms). Thus, if K. (x1) > (x2))) K, (x1)) - (x2))) 8 where 8 belongs to some finite set of strictly positive values.
Furthermore, without loss of generality, 21 and 22 be chosen to be arbitrarily close together, ie., they lie arbitrarily near a point where the local Lipschitz constant changes. We will therefore consider and T2 that are chosen such according Equation I5
| x2ll < 6-6
(15)
K
Let my be the margin by which the top-predicted class, F(22), exceeds all other classes. The maximum radius that can be certified 22 thus ma/K.(wa)). Note that as certification is sound, have
m2
S
(16)
Kx(22)
Now consider the maximum radius that can be certified at 31. Let m, be the margin by which the top-predicted class, F(z1), exceeds all other classes. The maximum radius that can be certified at Tj thus (1/K.(z1)
m1
m7
by assumption
(17)
K. K.(x1)
K. (x:2 +
m2 + K| K| x22
by definition of the Lipschitz constant
(18)
K, (x2) +
m2 + e 8
by our choice of || - x2|| in 15
(19)
K. (x22 +
Kx(I2) ) + 8
by [66
(20)
(x(22) + 8
=E
(2l)
Thus, we see that 2, cannot be certified with radius e, despite that its distance from the boundary is exactly
14

---

Under review as a conference paper at ICLR 2023
B.2 OTHER PIECEWISE- LIMITED METHODS
Our work focuses primarily on Lipschitz-based certification, which we demonstrate is fundamen- tally limited on the hypothesis class of piecewise linear networks. However, this limitation is not due specifically to the use of the Lipschitz constant per se; instead, we attribute it more generally to the fact that Lipschitz-based certification always produces a piecewise-linear certified frontier on piccewise-linear networks, a property we refer to as PLL (Definition 4). In this section we briefly discuss how this property may apply to other flavors of certification techniques that have been pro- posed in the literature.
Convex Relaxations and Dual Networks. One classic approach for certification is through con- vex relaxation. A survey of such methods is given by (Salman et al. (2019), who point out the limi- tations (regarding tight certification) of convex relaxations (though the authors do not consider our setting where the learner may control the implementation of the boundary, but rather focus post hoc certification). Though many approaches in this family have been proposed, we will consider two baseline methods that capture a primal and dual formulation of convex relaxations: Fast-Lin (Weng et al. 2018), and an approach proposed by Wong & Kolter (2018), often referred to as "KW."
Fast-Lin directly derives upper and lower bounds on the output of ReLU network in order to determine if an adversarial example might exist. This is done by iteratively computing upper and lower bounds for the neurons each layer and using them to replace the ReLU activations with linear upper and lower bounds. This computation resembles a piecewise-linear network, suggesting that Last-Lin is PL..
The KW approach formulates the adversary as an LP that optimizes over the convex outer approxi- mation of the set of top-level activations reachable through a norm- boundbdunde perturbation. Crucially, for the sake of tractability, the LP can be bounded by the feasible set of the dual, which WWng & Kolter show can be expressed as a dual network, which resembles a backwards pass in the network being certified. For ReLU networks, the activations in the dual network are replaced with their upper convex envelopes (a linear function) over the bounded set [e, u]. where and u represent lower and upper bounds on the Rre-ReLU neural activations. The upper and lower bounds can be iteratively computed in a similar way to in Fast-Lip; thus, in its simplest form the dual network inherits the piecewise linearity of the original ReLU network being certified, suggesting the resulting certified frontier is piecewise linear, and certification is PLL.
Hyperplane Projections. As exact certification is NP-complete, the literature has often turned to training procedures that help simple, approximate certification enjoy greater success. In piecewise linear networks, the input can be partitioned into a polyhedral complex where each convex region corresponds to single activation pattern, over which the network is linear (Croce et al., 2019 Fromherz et al., [022 Jordan et al. 2019). Motivated by this view of ReLU networks, one family of robust training approaches attempts to expand the linear regions of the network to simplify the com- binatorial analysis of the possible ReLU activation patterns (Croce et al. 2019 Xiao et al.) 2019). Croce et al. proposed a simple certification technique for networks trained with their "Maximum Margin Regularization" (MMR), where a point, x, is certified only if (1) the entire e-ball around x is contained in single convex activation region, and (2) the linear function corresponding to the region does not have a boundary within c from x. This approach is clearly PLL, as the certified regions can be obtained by shrinking each activation region (possibly split in two if a linear decision boundary crosses it) by e. Since the original regions are convex polytopes, so too are the certified regions, thus the certified frontier is piecewise-linee
In contrast to our findings for Lipschitz- based certification, it is worth noting that the limitations of this approach go beyond PLL. as completeness of the MMR approach is direct conflict with non-linearity; and moreover, the approach is designed specifically for piecewise-linear networks.
C DETAILS ON EXPERIMENTS
The experiments presented in Figure in Section 3 were performed using the gloro Python li- brary, which implements the GloRo Net method of Leino et al. (2021) for training certifiably robust
Thii approach has heen refined in subsequent work that do consider here Wong ct al. 2018
15

---

Under review as a conference paper at ICLR 2023
f(x)= =E.K K
f(x)
Figure 2: Illustration of the "corner problem" described in Section 2.3
models by incorporating Lipschitz-based certification into training. All networks in the experiments consisted of 1 1-hidden layer dense network with MinMax [Anil et al. (2019) activations; three spe- cific architectures were used, with 2, 20, and 200 hidden units, respectively. Models were trained for 64 epochs, with batch size of 128. We chose hyperparameters inspired by those used by Leino et al. (see the original paper for details on the meaning of the various hyperparameters); namely, we used GloRo-TRA TRADES loss with À 1.2, scaled logarithmically to its ultimate value of 0.5 by the half-way point of training, and we linearly decreased the learning rate from 10-3 to 0 half-way through training.
D AN ILLUSTRATIVE EXAMPLE OF THE CORNER PROBLEM
For illustrative purposes a diagram is provided in Figure that serves a visual explanation of the "corner problem" described in Section 2.3 The boundary of neural network, shown by the bold black line, forms a sharp corner. The complement the robust region, i.e., the set of points that are not robust, is shown in gray. A simple implementation of this boundary has level curves that make similar sharp corners; the level curve corresponding to the certified frontier is shown by the dotted line, and the certified region is colored in blue. The region opposite the corner in the boundary is highlighted. We see that this region, there is set points, shown orange, that are not certified, despite the fact that they robust, being at distance greater than from the boundary. In this two-dimensional example, these falsely flagged points make up relatively small fraction of the uncertified points opposite the comner (represented the union of the orange points and the highlighted gray points in the diagram); however, in high dimensions, virtually all uncertified points in this region would be falsely flagged, indicated by Equation
16


Reviews:
[{"review_id": "lS4BX5NG2F", "reviewer": "Reviewer_SHQ9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "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. \n\n- 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? \n\n- 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. \n\n## Minor Comments/Feedback\n- 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. \n- 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\n- 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? \n- In Def 3, it should be  \\forall delta>0, \\neg cert(f, *x*, \\epsilon + delta)\n- 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? \n- In Appendix A.1, proof of Theorem 1, should it be \\sqrt{x^2+y^2} = \\epsilon ? \n- In Appendix A.2, proof of Theorem 2, should it be \"d(x) be the minimum distance of *x* from ...\"\n- I request that the authors add an explicit proof of Proposition 3 even if obvious. \n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dM5PW6nrV7D", "reviewer": "Reviewer_gENj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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:\n\n- 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)\n- Evidence (example + formal proof) explaining why PLL certification procedures can perform poorly around sharp inflection points in the boundary found in piecewise-linear networks.", "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.", "strength_and_weaknesses": "The paper is clear and presents a novel idea that advances our understanding of Lipschitz-based verifiability.\n\nThe paper has two key weaknesses:\n\n1. 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.\n2. 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.\n\nSome suggestions:\n\n- 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\")\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LiCsIDTL_G", "reviewer": "Reviewer_qESg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "summary_of_the_review": "\nThe 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. \n\n\nI 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. ", "strength_and_weaknesses": "Strengths:\n* 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. \n\nWeaknesses:\n\n* 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. \n\n* 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)? \n\n* Section 3 on capacity is based on a case study only, without formal theories. \n\n* The paper is poorly written. Many theorems are not clearly stated, especially with unclear conditions:\n  - 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. \n  - 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.”\n  - 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. \n  - 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).\n  - In Definition 2, why does there have to be f’? Why can’t it be contained in “cert” already (the certification procedure?)\n \nSalman, 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "7EroNZ8KcH", "reviewer": "Reviewer_uK69", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "### Strength\n\nThe authors present an interesting theoretical discussion regarding Lipschitz-based certification with regard to piece-wise linear activations.\n\n### Weakness\n- 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.\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject