Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective
Authors: Bohang Zhang
Du Jiang
Di He
Liwei Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Adversarial Robustness
Certified Defense
Lipschitz Neural Network
Expressive Power

Abstract: Designing neural networks with bounded Lipschitz constant is a promising way to obtain certifiably robust classifiers against adversarial examples. However, the relevant progress for the important $\ell_\infty$ perturbation setting is rather limited, and a principled understanding of how to design expressive $\ell_\infty$ Lipschitz networks is still lacking. In this paper, we bridge the gap by studying certified $\ell_\infty$ robustness from a novel perspective of representing Boolean functions. We derive two fundamental impossibility results that hold for any standard Lipschitz network: one for robust classification on finite datasets, and the other for Lipschitz function approximation. These results identify that networks built upon norm-bounded affine layers and Lipschitz activations intrinsically lose expressive power even in the two-dimensional case, and shed light on how recently proposed Lipschitz networks (e.g., GroupSort and $\ell_\infty$-distance nets) bypass these impossibilities by leveraging order statistic functions. Finally, based on these insights, we develop a unified Lipschitz network that generalizes prior works, and design a practical version that can be efficiently trained (making certified robust training free). Extensive experiments show that our approach is scalable, efficient, and consistently yields better certified robustness across multiple datasets and perturbation radii than prior Lipschitz networks.

Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective
Bohang Zhangl.3.4 Du Jiang' Di He Liwei Wang
National Key Laboratory of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University
Center for Data Science, Peking University Peng Cheng Laboratory "Pazhou Laboratory (Huangpu) (zhangbohang,dd) duj iang, dihe) edu. wanglwdcis .ku. edu.
edu. cn
Abstract
Designing neural networks with bounded Lipschitz constant is promising way to obtain certifiably robust classifiers against adversarial examples. However, the relevant progress for the important t.o perturbation setting is rather limited, and principled understanding of how to design expressive &o Lipschitz networks is still lacking. this paper, we bridge the gap by studying certified loo robustness from a novel perspective of representing Boolean functions. We derive two fundamental impossibility results that hold for any standard Lipschitz network: one for robust classification on finite datasets, and the other for Lipschitz function approximation. These results identify that networks built upon norm- conn-bundded affine layers and Lip- schitz activations intrinsically lose expressive power even in the two-dimennt two-dimensional case, and shed light on how recently proposed Lipschitz networks (e.g.. GroupSort and lx distanee nets) bypass these impossibilities by leveraging order statistic functions. Finally, based on these insights, we develop a unified Lipschitz network that generalizes prior works, and design practical version that can be efficiently trained (making certified robust training free). Extensive experiments show that our approach is scalable, efficient, and consistently yields better certified robustness across multiple datasets and perturbation radii than prior Lipschitz networks.
Introduction
typically suffer from severe drawback of lacking adversarial robustness. In classification tasks, given an image æ correctly classified by neural network, there often exists small adversarial perturbation ô, making the perturbed image x + look indistinguishable humans but fool the network to predict a wrong class with high confidence [57
Modern neural networks, despite their great success in various applications (22 13
is well-known that the adversarial robustness of neural network is closely related its Lipschitz continuity 8 61 (see Section 3.1). Accordingly, training neural networks with bounded Lipschitz constant has been considered a promising way to address the problem. variety of works studied
Lipschitz architectures for the ordinary Euclidean norm [61] 60 36 [4]] and recent works even established ofate-of-the-art (deterministic) certified & robustness [55
40 However, when comes
to the more critical (realistic) f. perturbation setting, the progress seems to be rather limited. In fact, standard Lipschitz ReL.U networks have been shown to perform poorly in terms of &o robustness [6] [24 2 While other more advanced Lipschitz networks have been proposed 22 1O], the achieved
results are still not satisfactory even on simple datasets like MNIST. Until recently, Zhang et al.
73 74] designed quite unusual Lipschitz network based heuristic choice of the loo -distance function, which surprisingly established sate-of-the-an certified &oo robustness on multiple datasets over prior works. Yet, it remains unclear why previous Lipschitz networks typically failed, and what the essential reason behind the success this particular &o distance network structure.
Conrespondence to Liwei Wang <wanglw@cis .ku, edu. en> and Di He <dihe@pku. edu en>
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Theoretical contributions. In this work, we systematically investigate how to design expressive Lipschitz neural networks (w..tt -nom)) through the novel lens of representing discrete Boolean functions, which provides a deep understanding on the aforementioned problems. Specifically, we first figure out a fundamental limitation of standard Lipschitz networks in representing a class of logical operations called symmetric Boolean functions (SBF), which comprises the basic logical AND/OR as special cases. We prove that for any non-constant SBF of d variables, there exists a finite dataset of size (dd) such that the certified Lo robust radius must vanish as (1/d)) for any classifier induced by a standard Lipschitz network. Remarkably, since logical AND/OR operations correspond to perhaps the most basic classifiers, our result indicates an intrinsic difficulty of such networks in fitting high-dinn sigh-dimenssioal real-world datasets with guaranteed certified & robustness.
Our analysis can be readily extended into the Lipschitz function approximation setting, We point out the relationship between monotonic SBF and the order statistics (which are I-L-ipschitz functions), and then prove that any d-dimensional order statistic (including the max/min function) on a compact domain cannot be approximated by standard Lipschitz networks with error O(1 1/d), regardless of the network size. This impossibility result is significant in that: (i) it applies to all Lipschitz activations (thus extending prior works 12 24D) (ii) it resolves an open problem raised recently in 43 and (iii) quantitatiiv lower bound of approximation error is established.
Equipped by the above impossibility results, we proceed to examine two advanced Lipschitz ar- chitectures: the GroupSort network [2] and the recently proposed - net [73 [7].. We find that besides the linear operation, both networks incorporate other Lipschitz aggregation oper- ations into the neuron design, especially the order statistic functions, thus shedding light on how they work. However, for the MaxMin network 2 a computationally efficient version of the GroupSort network implemented in practice, representing Boolean functions and order statistics is possible only when the network is very deep. In particular, we prove that representing certain d-dimensional Boolean functions requires depth of (dd),, implying that shallow MaxMin networks are not Lipschitz-universal function approximators. In contrast, we show a two-layer loo -distance net suffices to represent any order statistic function on a compact domain or even all Boolean functions. This strongly justifies the empirical success of lo distancee net over GroupSort (MaxMin) networks.
Practical contributions. Our theoretical insights can also guide in designing better Lipschitz network architectures. Inspired by the importance of order statistics, we propose a general form of Lipschitz network, called SortNet, that extends both GroupSort and fox distance networks and incorporates them into a unified framework. Yet, the full-sort operation computationally expensive and leads to optimization difficulties (as with the GroupSort network). We further propose a specialized SortNet that can be efficiently trained, by assigning each weight vector w using geometric series, i.e. w; proportional to p² for some 0 S < 1. This leads to a restricted version of SortNet but still covers 2o -iistanee net as a special case. For this particular SortNet, we skillfully derive a stochastic estimation that gives an unbiased approximation of the neuron output without performing sorting operations explicitly. This eventually yields an efficient training strategy with similar cost as training standard networks, thus making certified robust training free. Extensive experiments demonstrate that the proposed SortNet is scalable, efficient, and consistently achieves better certified robustness than prior Lipschitz networks across multiple datasets and perturbation radii. In particular, our approach even scales on a variant of ImageNet, and surpasses the best-known result 69 with a 22-fold decrease in training time thanks our "free" certified training approach.
The contribution and organization of this paper can be summarized as follows:
We develop a systematic study for the expressive power of Lipschitz neural networks using the tools of Boolean function theory. We prove the impossibility results of standard Lipschitz networks in two settings: a) certified tx robustness on discrete datasets (Section 3.2); b)
Lipschitz function approximation (Section 3.3)
We provide insights into how recently proposed networks can bypass the impossibility results. In particular, we show that a two-layer fic-dist net can precisely represent any Boolean functions, while shallow GroupSort networks cannot (Section 3.4).
We propose SortNet, Lipschitz. network that generalizes GroupSort and -isttancee net. For a special type of SortNet, we derive a stochastic training approach that bypasses the difficulties in calculating sorting operations explicitly and makes certified training free (Section 4.
Extensive experiments demonstrate that SortNet exhibits better certified robustness on several benchmark datasets over baseline methods with high training efficiency (Section

---

2 Related Work
Extensive studies have been devoted to developing neural networks with certified robustness guaran- tees. Existing approaches can be mainly divided into the following three categories.
Certified defenses for standard networks. A variety of works focus on establishing certified robustness for standard neural networks. However, exactly calculating the certified radius of a standard ReLU network is known to be NP-hard [28]. Researchers thus developed a class of relaxation-baseed approaches that provide a tight lower bound estimate of the certified robustness efficiently. These approaches typically use convex relaxation to calculate bound of the neuron outputs under input perturbations layer by layer [65] 66 644 [33 19 62 76]. See also [5] [6 47 48 688 II (35 63 23] [T] for more advanced approaches. However, most of these works suffer
from high computational costs and are hard to scale up to large datasets. Currently, the only scalable
convex relaxation approach is based interval bound propagation (IBP) [42] 21 75 69 52 but
the produced bound is known to be loose [50], and a recent study showed that IBP cannot achieve enough certified robustness on simple datasets for any standard ReLU network 41.
Certified defenses using Lipschitz networks. On the other hand, Lipschitz networks inherently imply certified robustness, resulting in much simpler certification process based on the output margin (see Proposition [.I] Yet, most prior works can only handle the & no-orrm Lipschitz situation by
leveraging specific mathematical properties such as the spectral norm 88 71 20 61 17
46 2 36 40]
or orthogonality of weight matrices [39 60
54 55]. For the &o -norm, standard Lipschitz networks
were shown give only vanishingly small certified radius [61]. Huster et al.
[24 found that
standard Lipschitz ReLU networks cannot represent certain simple functions such as the absolute value, which inspired the first expressive Lipschitz architecture called the GroupSort network (2). Since then, GroupSort has been extensively investigated [0] 588, but its performance still much worse than the above relaxation-based approaches even on MNIST. Recently, Zhang et al. [73 74
first proposed a practical I-Lipschitz architecture w.r.t. &o -orm based on special neuron called the -xe-ttttacce neuron, which can scale TinyImageNe with state-of-the-art ofett--rrtt certified robustness over ollxxation-based approaches. However, despite its practical success, it is rather puzzling how such a simple architecture can work while prior approaches all failed. Answering this question may require an in-depth re- re-examination of Lipschitz networks (w.r.t. Eoo -norm), which is the focus of this paper.
Certified defenses via randomized smoothing. As a rather different and parallel research line, randomized smoothing typically provides probabilistic certified lg robustness guarantees. Due to the wide applicability, randomized smoothing has been scaled up to ImageNet and achieves state-of- 49 72 277. However, certifying robustness with high probability requires sampling large number of noisy inputs (e.g.. 109) for single image, leading to a high computational cost at inference. Moreover, theoretical results pointed out that it cannot achieve non-trivial certified for robustness if the perturbation radius is larger than (22d11/2)
the-art certified accuracy for & perturbations 33 38 9
where d is the input dimension 70 30 67).
3 The Expressive Power of Lipschitz Neural Networks
3.1 Preliminaries
Notations. We use boldface letters to denote vectors (e.g., x) or vector functions (c.g., f), and use I, (or f.) to denote its i-th element. For unary function a, (x) applies a--) element-wise on vector æ. The fp-norm (p 2 1) and -orm of vector æ are defined as ||~ = (Σ, [x, 1/ and || = max; |as],, respectively. The matrix co-norm is defined as || = max; l. where W..; the i-th row of the matrix W. The k-th largest element of vector æ denoted as T(k)- We n). and use e, to denote the unit vector with the i-th element being
use [n] to denote the set (1..... one. We adopt the big O notations by using ((),, 2(-). and O(-) to hide universal constants.
Lipschitzness. A mapping f R + R. is said to be L-Lipschitz continuous w.r.t norm || if for any pair of inputs æι, 22 E IR""
[[( f(2))l < L||=; 22|1-
(I)
If the mapping f represented by neural network has a small Lipschitz constant L,, then ① implies that the change of network output can be strictly controlled under input perturbations, resulting in certified robustness guarantees as shown in the following proposition.
3

---

Proposition 3.1. (Certified robustness of Lipschitz networks) For a neural network f with Lipschitz
constant L under ep e--norm || lll. define the resulting classifier 9 as g(x) == arg max fi (2) an
impul n. Then g is provably robust under perturbations ||0||p < margin(f ie.
g( + = g(xx) for all 6 with ||6|p < c/ margin (x)).
(2)
Here c = 4/2/2 is constant depending only on the norm || 1 1lp. which is 1/2 the -orm and (f(rgn(((()) the margin between the largest and second largest output logits.
The proof of Proposition 3.J is simple and can be found in Appendix B.I or 39 Appendix PJ. It can be seen that the robust radius is inversely proportional to the Lipschitz constant L.
Standard Lipschitz networks. Throughout this paper, we refer to standard neural networks as neural networks formed by affine layers (e.g., fully-connected or convolutional layers) and element wise activation functions. Based on the Lipschitz property of composite functions, most prior works enforce the 1-Lipschizzness of multi-layer neural network by constraining each layer be 1- Lipschitz mapping. For the fo -norm, it is further equivalent to constraining the weight matrices to have bounded co-norm, plus using Lipschitz activation functions [2]. which can be formalized as
s.t. |/ I and (()) being I-Lipschitz, ( E [M]] (3) Here M is the number of layers and usually (x) = x is the identity function. The network takes x (0) := x as the input and outputs (M) For K-class classification problems, x(M) E R and
x (1)) = (1)) ( + b(9)
(M) We refer the resulting network as the network predicts the class g(x²) :- arg [a] 4x standard Lipschitz network.
3.2 Certified robustness on discrete Boolean datasets
In this section, we will construct a class of counterexamples for which certified &oo robustness can be arbitrarily poor using standard Lipschitz networks. We focus on the Boolean dataset, a discrete dataset where both inputs and labels are Boolean- and the relationship between inputs and their labels (o="), ()) E {0, 1 x {0, 1} can be described using Boolean function و" 1 + {0, 1j. The key motivation lies in the finding that Boolean vectors correspond to the vertices of d' d-dimensional hypercube, and thus are geometrically related to the f -iittane metric. In particular, the e -distance between any two different data points in Boolean dataset is always 1, which means that the dataset is well-separated. This yields the following proposition, stating that it is always possible to achieve optimal certified t. robustness on Boolean datasets by using Lipschitz classifiers
Proposition 3.2. For any Boolean dataset D {xx(
(xx))))(())) )) there exists a classifier 9 : . {0, 1} induced by a I-Lipschitz mapping f _dd + R2, succ that 9 can fit the whole dataset with margin(f(a: = 1 Vi E [n), thus achieving a certified foo radius of 1/2 by Proposition 3.1
The key observation in the proof (Appendix B.2p is that one can construct so-called nearest neighbor classifier that achieves a large margin on the whole dataset and is I-Lipschitz. Based on Proposition
3.2. it is natural to ask whether standard Lipschitz networks of the form can perform well on Boolean datasets. Unfortunately. we show is not the case, even on a class of simple datasets constructed using symmetric Boolcan functions.
Definition 3.3. A Boolean function ga (0, 1)dd - {0, 1} is symmetric if it is invariant under input permutation, i.e. g (Ir,.... ... .aa = (rr ... (d) for any x E (0, 1]a and ι E S..
Example 3.4. Two of the most basic operations in Boolean algebra are the logical AND/OR, both of which belong to the class of symmetric Boolean functions. Other important examples include the exclusive-or (XOR, also called the parity function). NAND, NOR, and the majority function (or generally, the threshold functions). See Appendix Appendix(A.2]oor a detailed description of these examples.
Theorem 3.5. For any non-constant symmetric Boolean function g" {0, 1] -> {0, 1), there exists a Boolean dataset with labels (i (x(x))) such that no standard Lipschitz network can achieve a certified f.x. robust radius larger than 1 /22d on the dataset.
Implications. Theorem 3.5 shows that the certified radius of standard Lipschitz networks must vanish as dimension d grows, which is in stark contrast to the constant radius given by Proposition 3.2 Also, note that the logical AND/OR functions are perhaps the most basic classifiers (which simply make predictions based on the existence of binary input features). is thus not surprising to see that standard I Lipschitz networks perform poorly on real-world datasets (e.g., even the simple MNIST dataset where input pixels are almost boolean-valuee (black/white) (61].

---

We give an elegant proof of Theorem 3.5 in Appendix B.3
where we also prove that the bound of 1/2d is tight in Proposition B.8 Moreover, we discuss the sample complexity by proving that a dataset of size ((d) already suffices to give ((1/d) certified radius (Corollary B.10)) To the best of our knowledge, Theorem 3.5 is the first impossibility result that targets the certified foc robustness of standard Lipschitz networks with an quantitative upper bound on the certified radius. In the next section, we will extend our analysis to the function approximation setting and make discussions with literature results [24]]]]
3.3 Lipschitz function approximation
Classic approximation theory has shown that standard neural networks are universal function approxi- mators [7].7] in that they can approximate any continuous function on a compact domain arbitrarily well. For 1-Lipschitz neural networks, an analogous question is whether they can approximate all 1-Lipschitz functions accordingly. Unfortunately, the result in Section a.ready implies a negative answer. Indeed. by combining Proposition 3.2 and Theorem 3.5 f is clearly 1-Lipschitz function that cannot be approximated by any standard Lipschitz network.
To gain further insights into the structure of unrepresentable 1-Lipschitz functions, let us consider the continuousization of discrete Boolean functions. For the symmetric case, needs to find class of 1-Lipschitz continuous functions that are also invariant under permutations. It can be found that a simple class of candidates is the order statistics, i.e. the k-th largest element of a vector. One can check that the k-th order statistic ((A) is indeed I-Lipschitz and is precisely the continuousization of the k-threshold Boolean function defined y (Bx((a)) == I[E xi 2 k). In particular, I(1) max; I; and (i()) = min; Zj corresponds to the logical OR/AND functions, respectively. Importantly, note that any Boolean function that is both symmetric and monotonic is a k-threshold function, and vice versa (Appendix (..2)) Therefore, k-threshold functions can be regarded as the most elementary Boolcan functions, suggesting that the ability to express order statisties is necessary for neural networks.
Unfortunately, using similar analysis as the previous section, we have the following theorem:
Theorem 3.6. Any standard Lipschitz network f TR. - TR. cannot approximate the simple 1- Lipschitz function x T(k) for arbitrary k E [d] on bounded domain K. = [], if d > 2. Moreover, there exists a point &. E K., such that
1 1
(f(0) 2 (x)
(4)
2 2d'
We give a proof in Appendix B.4 The above theorem indicates that order statistics cannot be uniformly approximated using any standard Lipschitz network regardless of the network size. Moreover, note that the trivial constant function f(x) = 1/2 already achieves an approximation error of 1/2 uniformly on K,, implying that standard Lipschitz networks can hardly improve upon trivial solutions. Remark 3.7. Theorem3.66 c.6 be casily generalized to weaker forms of non-unifore approximation, e.g.: using the fy-norm as distance metrics [45]. by proving that there exists a hypercube Bxx (.) centered at & with length ((1), such that [ (w) 2 ((1) holds for all ă E (x) when
d 2 2. See Corollary B.13 for details.
Discussion with prior works (2) 24 43). The work of Anil et al. also gave negative results on the expressive power of standard Lipschitz network Theorem 1]. They proved a different (weaker) version of Theorem 3.6, showing that if the activation function is monotonic, the network cannot precisely represent niner 1 I-Lipschitz functions whose gradient norm is almost everywhere (e.g.. the absolute value function proved before by (44). They did not give a quantitative approximation error. The intuition is that any monotonic non- linear 1-Lipschitz activation (e.g., ReLU) must have regions with slopes less than 1, leading to gradient attenuation during backpropagation. The authors thus attributed the reason to the activation function, which is not gradient-norn preserving (GNP). However, such an explanation is still not fully satisfactory, GNP can be simply achieved using non-monotonic activation (e.g., a (z) = (z:)). Consequently, one may expect that a standard Lipschitz network built on a suitable (non- monomonnot activation function can have sufficient expressive power. Such an idea is recently explored in [43], where the authors proved that using a general I-Lipschitz piecewise linear activation with 3 linear regions, the corresponding network achieves the maximum expressive power compared with other Lipschitz activations and can approximate any one-dimensional 1 1-Lipschitz function. They pose the high dimension setting as an open problem.
'Th result is described w.r.t. no-mm, but with some effort, it can be extended to the foe -oom case.
5

---

Unfortunately, Theorem 3.6 addressed the open problem with negative answer, stating that such networks are not expressive even for the two-dimensional setting. It also implies that GNP is not sufficient to explain the failure of standard Lipschitz networks. Instead, we draw a rather different conclusion, arguing that the lack of expressiveness is due to the inability of weight-constraiig transformations to perform basic Boolean operations (even in two dimensions). A further justification is given in Section 3.4 Finally, compared with Anil et al. [2], the form of Theorem (3.6) is more
affine
fundamental, in the sense that it does not make assumptions on the activation function, and it gives quantitative error bound on the approximation that is arbitrarily close to the plain fit f(x) = 1/2.
3.4 Investigating more advanced Lipschitz networks
Seeing the above impossibility results, we then examine two representative works of (non-standard) Lipschitz networks in literature: the GroupSort network [2] and the recently proposed for disttace net 73 74). Notably, both networks are Lipschitz-universal function approximators and thus fully expressive. The GroupSort network makes minimum changes to standard Lipschitz networks ( by replacing element-wiss activation a with GroupSort layers. GroupSort partitions the input vector into groups, sorts the sub-vector of each group in descending order, and finally concatenates the resulting sub- sub-vectors. Since sorting is computationally expensive, the authors considered a practical version of GroupSort with group size of 2, called MaxMin, which simply calculates the maximum and minimum pair by pair [6]. fo -distance net, on the other hand, is fundamentally different from standard Lipschitz networks. Each neuron in an -istaance net is designed based on the -distance function y ||æ w|l.c + b (with parameters {w, b)). Despite the somewhat unusual structure, distanne net has been shown to substantially outperform GroupSort (MaxMin) in terms of certified Lx robustness according to 77 a puzzling thing to be understood.
We provide a possible explanation for this. We find that both networks incorporate order statistics into the neuron design, either explicitly (GroupSort) or implicitly (foe -istancee net), thus bypassing the impossibility result in Theorem 3.6] Indeed, the sorting operations in GroupSort explicitly calculate order statistics. As for &ec -di-ttnne net, we show its basic neuron can implicitly represent the max function on bounded domain, by assigning the weight w -el and the bias 6 - with sufficiently large constant
y | w|1oo +b= max, [x; --c)l-c= max, Tj if Z max; Ti
(5)
and thus represent the logical OR operation. In general, we have the following theorem:
Theorem 3.8. A two-layer lox distance net can exactly represent the following functions: (i) any discrete Boolean function: (ii) any continuous order-statistic function on a compact domain.
We give a proof in Appendix B.5] Our proof uses the fundamental result in Boolean algebra that any Boolean function can be written in its disjunctive normal form (DNF, see Appendix (A.I). which can be further reduced to using only the composition of logical OR operations of literals and thus be realized by two-layer foo -distanec net. To represent order statistics, we formulate them as nested max-min functions, which can also be realized by a two-layer foo -distance net. Therefore, the construction in our proof provides a novel understanding of the mechanism behind the success of l disttanee nets, since each loo- distance neuron can be regarded as a basic "logical gate" and the whole network simulate any Boolean circuit.
For GroupSort networks with a group size G 2 d, similar result holds. However, is not the case for practically used MaxMin networks (G = 2), where we have the following impossibility results: Theorem 3.9. An M -lyerr MaxMin network
Rdd + I cannot approximate any k-th order statistic function on a bounded domain K.- = [0, 1]d if M < [log, d] (no matter how wide the network is). Moreover, there exists a point ② K. such that
2
(f( - RR)
d 2 if S [logz dJ.
(6)
Theorem 3.10. Let Ma be the minimum depth such that an Ma-layer MaxMin network can represent any (discrete) d-dimensional Boolean function. Then Ma- = (dd)..
The above theorems show that MaxMin networks must be very deep in order to represent Boolean
functions and order statistics, which is in stark contrast to Theorem 3.8 as a constant depth is sufficient for -di-ttttecee nets. Based on Theorem 3.10 we directly have the following corollary: Corollary 3.11. The function class induced by Ma-layer MaxMin networks is not a universal approximator to the d-dimensional I -uintchitt,functionss if Ma o(d).

---

The proof' of Theorems 3.9 and 3. 5.10 are deferred to Appendix B.oo
B.6 and B.7 respectively. In particular, the proof of Theorem 3.10 is non-trivial and makes elegant use of Boolean circuit theory, so we present proof sketch here. The key insight is that for any Boolean function, if it can be expressed by some MaxMin network f. then can be expressed by a special Max Min network with the same topology as f such that all the weight vectors w are sparse with at most one non-zero element, either 1 or -1 (Corollary [.23). This implies that weight vectors have no use in representing Boolean functions and thus MaxMin networks reduce to 2-ary Boolean circuit, i.e. directed acyclic graphs whose internal nodes are logical gates including NOT and the 2-ary ANDIOR. Note that for a 2-ary Boolean circuit that has M layers and outputs scalar, the number of nodes will not exceed 2 2M+1 (achieved by a complete binary tree). However, the classic result in Boolean circuit theory (Shannon 1942) showed that for most Boolean functions of d variables, a lower bound on the minimum size of 2-ary Boolean circuits is 2222 /d). which thus yields M = (2(d) and concludes the proof.
In Appendix, we also discuss the tightness of the above theorems. We prove that a depth of Ologg, d) sufficient to represent any order statistic function using Boolean circuit theory (Theorem 1919). and straightforward construction using DNF shows that depth of (dd) is sufficient to represent any Boolean functions (Proposition B.20). Thus both theorems are tight.
Unfortunately, training deep MaxMin networks is known to be challenging due to optimization difficulties [TO] Consequently, prior works only use a shallow MaxMin network with no more than 4 layers [10. which severely lacks expressive power. One possible solution is to increase the group size, and several works explored this aspect using toy examples and observed significant benefits empirically [10 588. However, large group size involves computationally expensive sorting operations and makes the network hard to train 22. limiting its value in practice.
4 A Unified Framework of Lipschitz Neural Networks
The above theoretical results have justified order statistics as a crucial component in representing class of Boolean functions, shedding light how GroupSort and -distanee net work. Based on these insights, in this section, we will propose a unified framework of Lipschitz networks that take the respective advantage of prior Lipschitz architectures, and then give a practical (specialized) version that enables efficient training.
Consider general Lipschitz network constructed using the following three basic types of I-Lipschitz operations: (i) com-bounded affine transformations, e.g. y w x (|]w|| S 1) and y = x + b; (ii) 1- I-Lipschitz unary activation functions σ; (fii) order statistics. The first two types extensively used in standard Lipschitz networks, while the last type is motivated by Section and is of crucial importance. We propose the following network which naturally combines the above components:
Definition 4.1. (SortNet) Define an M-layer fully-connected SortNet f as follows. The network (1) is computed by
takes x = (0) as input, and the k-th unit in the 1-th hidden layer 1
(1) (w.)+ (a 1) + B(Ck))) s.t. w (t.A) 1/2 S 1, LE [MMM,, E [d]]
(7)
k
where di is the size of the 1-th layer, and sort(x) == (z(1)) (())) calculates all order statistics of E IR.. The network outputs f(x) (Mf + bout Here (w))) (b(lA) and bost are parameters.
is easy to see that SortNet is I-Lipschitz w.r.t. norm. We now show that SortNet a general architecture that extends both GroupSort and exc networks into unified framework. Proposition 4.2. Any GroupSort network with an arbitrary group size on a compact input domain can be represented by a SortNet with the same topological structure using activation (xx) xr
Proposition 4.3. Any toe -distannc net can be represented by a SortNel with the same topological structure by fixing the weights w (!)k)) = =1 and using the absolute-value activation o d(x) = |z].
See Appendix C for proof. As a result, SortNet can exploit the respective advantage of these Lipschitz networks. Compared with GroupSort, SortNet can freely use activation functions such as the absolute value, thus easily addressing the problem claimed in (24 22. Moreover, unlike GroupSort, the bias vector ((.,k) in SortNet ( can be assigned diversely for different neurons in the same layer. In this way, one can control the sorting behavior of each neuron individually by varying the bias value without disturbing the output of other neurons, which is very beneficial (see Appendix C for details). Compared with for distance net, SortNet adds linear transformation and incorporates all order statistics (rather than only the maximum), thus can represent certain functions more effectively.
7

---

A practical version of SortNet. As with GroupSort networks, we also design practical (specialized) version of SortNet which enjoys efficient training. But different from the MaxMin network that reduces the group size, we keep the full-dimensional order statistics as they are crucial for the expressive power (Section (e.ction3.4.... The key observation is that in (7). the only required computation is the linear combination of order statistics (i.e. w sort(-)), rather than the entire sorting results (i.e. sort(-)). We find that for certain carefully designed choices of the weight vector w, there exist efficient approximation algorithms that can give good estimation of w" sort(.). In particular, we propose an assignment of the weight vector that follows geometric series, i.e. w; proportional to p². in which case we have the following result:
Proposition 4.4. Let w E Rd be vector satisfying w, = (1 - p)p' (d]orr some 0 S p < 1. Then for any vector x E R4 with non-negative elements,
w sort(x)) = (E-BBr((-p)) [max s,z:).
(8)
Here is random vector following independent Bernoulli distribution with probability 1 p being I and p being O.
Proof. Without loss of generality, assume "1,-. Zd are different from each other. Denote J1. jd as the sorting indices such that sort(x) = (T) 1 ; Then
E BarBar(p)) [max; stx,]
ExE(q Pr PrawBer(p) [max, 8;2; = =J, =1
= =Ene(g Pr Pra-Ber(o)) [8)c = and 83. = 1000 Tyz
=Exeja(1 p)pk-1 I(()) w (art
It is easy to check that the weight w in the above proposition satisfies | 1, which guarantees the Lipschitzness. The non-negative condition on æ in Proposition 4.4 holds when using a suitable activation function in neuron 77. such as the absolute value function.
Proposition 4.4 suggests that one can use max; s to give an unbiased estimation of wT sort(w). In this way, the expensive sorting operation is avoided and replaced by max operation, thus significantly reducing the computational cost in training. We give an efficiently GPU implementation for training SortNet in Appendix D Note that is random Bernoulli vector, the above calculation is similar to applying a mask on the input of each neuron, like dropout [56]. It means that the introduced stochasticity may further prevent overfitting and benefit generalization performance.
Regarding the value of p. When p = 0, only the maximum value is taken into the computation and the resulting network can recover the loo -distance net by choosing the activation function a (zz) |x] This means the specialized SortNet still extends Lo -distancce net and thus has sufficient expressive power. When p > 0, all order statistics become utilized. A simple way of selecting p is to regard it as a hyper-parameter and set its value by cross vols-valldattio, which is adopted in our experiments. One can also consider treating / as learnable parameters for each neuron that participate in the optimization process, but this involves calculating the gradient of p which may be complicated due to the stochastic sampling procedure ( We will leave the study future work.
5 Experiments
In this section, we perform extensive empirical evaluations of the proposed SortNet architec- ture as well as various prior works in the certified fo robustness area. To show the scalability of different approaches, we consider variety of benchmark datasets, including MNIST (33) CI (29]. TinyImageNet (32), and ImageNet (64 64) [7]. Due to space limitations, a complete training recipe is given in Appendix
E. Our code and trained models are released at
5.1 Experimental setting
SortNet model configuration. Since SortNet generalizes the loc -distanne net, we simply follow the same model configurations as (3] and consider two types of models. The first one a simple SortNet consisting of M fully-connected layers with a hidden size of 5120, which is used in MNIST and C1FAR-10. Like (73), we choose M for MNIST and M = 6 for CIFAR-10. Since SortNet Lipschitz, we directly apply the margin- based certification method to calculate the certified accuracy
8

---

To achieve the best results on ImageNet-like datasets, in our second type of model we consider using a composite architecture consisting of base SortNet backbone and a prediction head (denoted as SortNet+MIP)) Following 773, the SortNet backbone has 5 layers with a width of 5120 neurons, which serves as a robust feature extractor. The top prediction head is a lightweight 2-layer perceptron with 512 hidden neurons (or 2048 for ImageNet), which takes the robust features as input to give classification results. We also try a larger SortNet backbone, denoted as SortNet+MLP (2x), that has roughly four times the training cost (see Appendix E.2 for architectural details). We use the same approach as [73] to train and certify these models, I.c. by combining margin-based certification for the SortNet backbone and interval bound propagation for the top MLP 21
(Proposition 3.1
Baseline methods and metries. We compare SortNet with representative literature approaches including relaxation-base certification (for standard networks), maargin-based certification (using Lipschitz networks), and mixed-ing -enteee linear programming (MILP) [59]. In Appendix G we also discuss randomized smoothing approaches [9]] which provide probabilistic guarantees rather than deterministic ones. For each method these tables, we report five metrics: (i) training efficiency, measured by the wall-clock time per training epoch; (ii) certification efficiency, measured by the time needed to calculate the certified accuracy on the test dataset; (iii) the clean test accuracy without perturbation (denoted as Clean); (iv) the robust test accuracy under 100-step PGD attack (denoted as PGD); (v) the certified robust test accuracy (denoted as Certified). For a fair comparison, we reproduce most of baseline methods using the official codes and report the wall-clock time under the same NVIDIA- RTX 3090 GPU. These results are presented in Tables [ and 3 In Appendix HH] we also show the training variance of each setting by running 8 sets of experiments independently, and full results (including the median performance) are reported in Table 9 and 10
5.2 Experimental results
Performance on MNIST. The results are presented in Table 1 Following the common practice, we consider both a small perturbation radius e = 0.1 and a larger one 0.3. It can be seen that the SortNet models can achieve 98.14% (e 0.1) and 93.40% (e 0.3) certified accuracy, respectively, both of which outperform all previous baseline methods. In contrast, the GroupSort network can only achieve a trivial certified accuracy for 0.3. This matches our theory in Section 3.4 indicating that the expressive power of shallow MaxMin networks is insufficient in real-world applications.
Performance CIFAR-10. The results presented in Table 2 Following the common practice, we consider two perturbation radii: <= 2/255 and c = 8/255. Our models can achieve 56.94% % (c 2/255) and 40.39 (c 8/255) certified accuracy, respectively. Moreover, the training approach proposed in Section is very efficient, e.g., with a training time of 13~14 seconds per epoch. For both radii, our models perform the best among all existing approaches that can be certified in a reasonable time. Compared with relaxation-bait -based methods, the certified accuracy of SortNet models is much higher (typically +3 +6 point for both radii), despite our training speed being several times faster. Such results may indicate that certified loo robustness can be better achieved by designing suitable Lipschitz models than by devising relaxation procedures for Lipschitz models.
Performance on Tiny Ietge and ImageNet. To demonstrate the scalability of SortNet models, we finally run experiments two large-scale datasets: -mageNn and ImageNet (64 x 64). Notably, the ImageNet dataset has 1000 classes and contains 1.28 million images for training and 50,000 images for testing. Due both the large size and the huge number of classes, achieving certified Ex robustness on the ImageNet level has long been a challenging task.
Table presents our results along with existing baselines. Among them, we achieve 18.18% certified accuracy on TinylmageNet and achieve 9.54% certified accuracy on ImageNet, both of which establish state-of-the SortNet+MPP model already outperforms the largest model of [69] while being 22 times faster to train. Even for the largest model (SortNet+MLP 2x), the training is still 7 times faster, resulting in training overhead of 4 days using two GPUs We suspect that continuing to increase the model size will yield better results, given the noticeable improvement of the larger model over the smaller one.
results. The gap is most prominent on ImageNet. where our small
Comparing with distancce net. As can be seen, SortNet models consistently achieve better certified accuracy than lox -dittance nets for all different datasets and perturbation levels, and the performance gap is quite prominent compared with the original work [73]. Very recently, follow-up paper [4] significantly improved the performance of lo -distance net using carefully designed

---

Table 1: Comparison of results with existing methods on MNIST dataset.
Train
(N 0.1)
MNIST (E = 01.3)
Method
Time (8)
Clean
PGD
Certified
Clean
PGD
Certified
IBP
17.5
98.92
97.98
97.25
97.88
93.22
91.79
Relaxation
IBP
52
34.7
98.84
97.95
97.67
93.10
CROWN-IBP 75
60.3
98.
98.19
97.76
98.18
93,95
92.98
GroupSort (MaxMin)
97.0
84.0
79.0
97.0
34.0
2.0
Roo-dist Net 73
17.2
98.66
97.85
97.73
98.54
94.62
92.64
Lipschitz
-ist Net+MLP
17.2
98.86
97.77
97.60
98.56
95.05
93.09
foc-dist Net [74
17.0
98.93
98.03
97.
98.56
94.73
93,20
SortNet
10.6
99.01
98.21
98.14
98.46
94.64
93.40
MILP
COLT
99.2
97.1
97.3
85.7
Table 2: Comparison of our results with existing methods on CIFAR-10 dataset.
Time Train
2/255
8/255
Method
Certify
Clean
PGD
Certified
Clean
PGD
Certified
CAP [66
659.0
7,570
68.28
53.89
28.67
21.78
IBP 21
19.0
2.74
61,46
50.28
44.79
50.99
31.27
29.19
Relaxation
IBP
52
70.4
4.02
66.84
52.85
48.94
34.97
CROWN-IBI
75
87.2
7.01
71.52
59.72
53.97
45.98
34.58
33.06
CROWN-IBP
69
45.0
4.02
46.29
35.69
33.38
Eoo-dist Net
73
19.7
1.73
60.33
51.55
50.94
56.80
36.19
33.30
loc- -dist Net+MLP
77
19.7
1.74
65.62
51.47
51.05
50.80
36.51
35.42
Lipschitz
foo-dist Net 74
18.9
1.73
60.61
54.28
54.12
54.30
41.84
40.06
SortNet
14.0
8.00
65.96
57.03
56.67
54.84
41.50
40.39
SoL
13.4
8.01
67.72
57.83
56.94
54.13
41.58
39.99
MILP
COLT
252.0
10
78.4
60.5
51.7
27.5
Table 3: Comparison of our results with existing methods on TinylmageNet and ImageNet datasets.
TinylmageNet
1/255)
ImageNet 64
64
1/255)
Method
Time (s)
Clean
FGD
Certified
Time (8)
Clean
PGD
Certified
IBP [21
735
26.46
20.60
14.85
11,026
15.96
9.12
6.13
IBP 522
284
25.71
17.64
CROWN- -BP 69
1,256
27.82
20.52
15.86
16,269
16.23
10.26
8.73
Lo dist Net+MLP
73
55
21.82
16.31
foo-tist Net 77
55
12.57
11.09
11.04
Sor
39
24.17
20.57
17.92
715
13.48
10.93
9,02
MoP (2x larger)
156
25.69
21.57
18.18
2,192
14.79
11.93
9.54
training strategy, creating strong baseline CIFAR-10. However, we find their approach does not suit the ImageNet-like datasets when the number classes large (see Appendix E.6). In contrast, SortNet models enjoy great scalability ranging from MNIST to ImageNet and consistently outperform [74]. The improvement is also remarkable for = 2/255 on CIFAR-10 (+7.11% and +2.82% in clean certified accuracy).
In Appendix we conduct ablation studies on CIFAR-10 by varying the value and comparing SortNet models (p 0) with -dsttance net (p 0), under the same training strafegy in this paper without additional tricks. We observe large gain in certified accuracy when switching from Lo disttanee net general SortNet. This empirically indicates that incorporating other order statistics has extra benefits in certified lo robustness than using only the maximum (the first order statistic).
6 Conclusion
In this paper, we study certified to robustness from the novel perspective of representing Boolean functions. Our analysis points out an inherent problem in the expressive power of standard Lipschitz networks, and provides novel insights on how recently proposed Lipschitz networks resolve the problem. We also answer several previous open problems, such as (i) the expressive power of standard Lipschitz networks with general activations [33 and (ii) the lower bound on the depth of MaxMin networks to become universal approximators [58 43 Finally, guided by the theoretical results, design new Lipschitz network with better empirical performance than prior works.
10

---

Limitations, Open Problems, and Broader Impact
Regarding the f,-norm. One major limitation of this work is that we only focus on & robustness. While such results may shed light on general f--norm settings when is large, it does not apply to the standard 22-or.. In particular, in this case MaxMin equivalent to the absolute value activation function in terms of expressive power (2]. which contrasts to the -nom case for which MaxMin networks are strcitly more expressive. Moreover, empirical results suggest that these & Lipschitz networks may have sufficient expressive power [55] (although it remains fantastic open problem to prove that MaxMin networks with bounded matrix 2-norm are universal approximators).
Based on the above finding, this work reflects an interesting "phase transition" in the expressive power standard Lipschitz networks when p is switched from a large number. Coincidentally, similar limitation is also proved when using randomized smoothing, which suffers from the curse of dimensionality when p [7].. This raises an interesting question of why the effect of p is very similar for both methods and how things change increases.
Beyond standard Lipschitz networks. Another limitation is that our results apply only for standard Lipschitz networks. When the Lipschitz constant is constrained using carefully designed bounding methods 47
(rather than simple stacking of I-Lipschitz layers). the robustness certifica- tion will be less efficient, but the resulting networks are likely to bypass the impossibility results in this paper. It is an interesting direction to study whether we can just use standard networks with carefully-designe Lipschitz bounding method that can achieve good certified robustness while still keeping adequate efficiency.
18 31 51
Other promising directions. On the application side, is interesting to study how to design efficient training approaches for the general SortNet models with learnable weights learnable p. Another meaningful question is how to encode inductive biases into these Lipschitz networks (e.g., designing convolutional architectures) better suit image tasks.
Broader impact. Interestingly, our theoretical results point out a surprising connection between MaxMin/& -ditsann/e--iissance networks and Boolean circuits. We believe the value of this paper may go -distance beyond the certified robustness community and link to the field of thcoretical computer science.
Acknowledgement
This work is supported by National Science Foundation of China (NSFC62276005), The Major Key Project of PCL (PCL2021A12), Exploratory Research Project of Zhejiang Lab (No. 2022RC0AN02), and Project 2020BD006 supported by PKUBaidu Fund. Bohang Zhang would like to thank Ruichen Li and Yuxin Dong for helpful discussions. We also thank all the anonymous reviewers for the very careful and detailed reviews as well as the valuable suggestions. Their help has further enhanced our work.
References
[1] Miklós Ajtai, János Komlós, and Endre Szemerédi. An 0 (n log n) sorting network. In Proceedings of the fifieenth annual ACM symposium on Theory of computing, pages 1-9, 1983.
[2] Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In International Conference on Machine Learning, pages 291-301, 2019.
[3] Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2020.
[4] Battista Biggio, Igino Corona, Davide Maiorea, Blaine Nelson, Nedim Šmniić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference machine learning and knowledge discovery in databases, pages 387-402. Springer, 2013.
[5] Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify lox0 robustness for high-dimensional images. arXiv preprint arXiv:2002.03517 2020.
11

---

[6] Artem Chermodub and Dimitri Nowicki. Norm-preserv orthogonal permutation linear unit activation functions (oplu). arXiv preprint arXiv: 2016.
[7] Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprini 170.008707.
[8] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pages 854-863, 2017.
[9] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
[10] Jeremy EJ Cohen, Todd Huster, and Ra Cohen. Universal Lipschitz approximation in bounded depth neural networks. arXiv preprint arXiv: 04861, 2019.
[11] Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of ReLU networks via maximization of linear regions. In the 22nd International Conference on Artificial Intelligence and Statistics, pages 2057-2066. PMLR, 2019.
[12] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
[13] Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT (1), 2019.
[14] Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. MMA train- ing: Direct input space margin maximization through adversarial training. In International Conference Learning Representations, 2020.
[15] Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. dual approach to scalable verification of deep networks. arXiv preprint arXiv: see::0033.055 2018.
[16] Krishnamurthy Dj Dvijotham, Robert Stanforth. Sven Gowal, Chongli Qin, Soham De, and Pushmeet Kohli. Efficient neural network verification with exactness characterization. In Uncertainty Artificial Intelligence, pages 497-507. PMIR, 2020.
[17] Farzan Farnia, Jesse Zhang, and David Tse. Generalizable adversarial training via spectral normalization. In International Conference on Learning Representations, 2019.
[18] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of Lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[19] Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen. Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. A12: Safety and robustness certification of neural networks with abstract interpretation. 2018 IEEE Symposium on Security and Privacy (SP), pages 3-18. IEEE, 2018.
[20] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing Lipschitz continuity. arXiv preprint arXiv:1804.04360 2018.
[21] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 18:::/1/000 12715, 2018.
[22] Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[23] Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local Lipschitz bounds. Adyances in Neural Information Processing Systems, 34, 2021.
12

---

[24] Todd Huster, Cho- Yu Jason Chiang, and Ritu Chadha. Limitations of the Lipschitz constant as a defense against adversarial examples. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 16-29. Springer, 2018.
[25] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pages 448-456, 2015.
[26] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, volume 31, 2018.
[27] Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. Advances in Neural Information Processing Systems, 33, 2020.
[28] Guy Katz, Clark 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, pages 97-117. Springer, 2017.
[29] Alex Krizhevsky et al. Learning multiple layers of features from tiny images. Technical Report 7R-2009, 2009.
[30] Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learning, pages
PMLR, 2020.
[31] Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference on Learning Repre- sentations, 2020.
[32] Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
[33] Yann LeCun, Corinna Cortes, and Chris Burges. MNIST handwritten digit database, 1998.
[34] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656-672. IEEE, 2019.
[35] Sungyoon Lee, Jaewook Lee, and Sacrom Park. Lipschitz certifibl training with tight outer bound. Advances in Neural Information Processing Systems, 33, 2020.
[36] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference on Machine Learning (ICML), 2021.
[37] Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
[38] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin, Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems, 32:9464-9474, 2019.
[39] Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger Grosse, and neen-HHerri Jacobsen. Preventing gradient attenuation in Lipschitz constrained convolutional networks. Advances in Neural Information Processing Systems, 32: 15390-155400 2019.
[40] Laurent Meunier, Blaise Delattre, Alexandre Araujo, and Alexandre Allauzen. A dynamical system perspective for Lipschitz neural networks. 10.iv:21 2022.
[41] Matthew Mirman, Maximilian Baader, and Martin Vechev. The fundamental limits of interval arithmetic for neural networks. arXiv preprint arXiv:2112.05235, 2021.
[42] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pages 5578-3586 PMLR, 2018.
13

---

[43] Sebastian Neumayer, Alexis Goujon, Pakshal Bohra, and Michael Unser. Approximation of Lipschitz functions using deep spline neural networks. arXiv preprint arXiv:2204.06223,, 2022.
[44] Ryan O' D'Donnell and Karl Wimmer. Approximation by DNF: examples and counterexamples. In International Colloquium on Automala, Languages, and Programming, pages 195-206. Springer, 2007.
[45] Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta numerica, 8:143-195, 1999.
[46] Haifeng Qian and Mark N. Wegman. 12-nonexpansive neural networks. In International Conference on Leurning Representations, 2019.
[47] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018.
[48] Aditi Raghunathan, Jacob Steinhardt, and Percy S. Liang. Semidefinite relaxations for certifying robustness adversarial examples. In Advances in Neural Information Processing Systems, pages 10900-10910, 2018.
[49] Hadi Salman, Greg Yang, Jemry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 11292 11303, 2019.
[50] Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. Advances in Neural Information Processing Systems, 32:9835-9846, 2019.
[51] Zhouxing Shi, Yihan Wang. Huan Zhang, Zico Kolter, and Cho-Jui Hsieh. Efficiently computing local Lipschitz constants of neural networks via bound propagation. In Advances in Neural Information Processing Systems, volume 35, 2022.
[52] Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Fast certified robust training with short warmup. Advances in Neural Information Processing Systems, 34, 2021.
[53] Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effeective robustness certification. In Advances in Neural Information Processing Systems, pages 10802-10813, 2018
[54] Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference on Machine Learning, volume 139, pages 9756-9766. PMLR, 2021.
[55] Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on CIFAR-10 and CIFAR-100. In International Conference on Learning Representations, 2022.
[56] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1229-1958, 2014.
[57] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312,699, 2013.
[58] Ugo Tanielian and Gerard Biau. Approximating Lipschitz continuous functions with groupsort neural networks. In International Conference on Artificial Intelligence and Statistics, pages 442-450. PMLR, 2021.
[59] Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019.
[60] Asher Trockman and Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference Learning Representations, 2021.
14

---

[61] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-marre training: Scalable certifi- cation of perturbation invariance for deep neural networks. Advances in Neural Information Processing Systems,
1-550, 2018.
[62] Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, volume 31, 2018.
[63] Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. Advances in Neural Information Processing Systems, 34, 2021.
[64] Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In International Conference on Machine Learning. pages 5276-520 5285. PMLR, 2018.
[65] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5286-5295. PMLR, 2018.
[66] Eric Wong. Frank R Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adver- sarial defenses. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 8410-8419 101-8449,,2000 2018.
[67] Yihan Wu, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günnnemann. Completing the picture: Randomized smoothing suffers from the curse of dimensionality for large family of distributions. In International Conference on Artificial Intelligence and Statistics, pages 3763-3771. PMLR, 2021.
[68] Kai Y Xiao, Vincent Tjeng, Nur Muhammad Mahi Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing ReI.U stability. In International Conference on Learning Representations, 2019.
[69] Kaidi Xu, Zhouxing Shi, Huan Zhang. Yihan Wang, Kai- Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsich. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 33, 2020.
[70] Greg Yang. Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pages 10693-10705. PMLR, 2020.
[71] Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generaliz- ability of deep learning. arXiv preprint arXiv: 2017.
[72] Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong. Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang, MACER: Attack-free and scalable robust training via maximizing certified radius. In International Conference on Learning Representations, 2020.
[73] Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwei Wang. Towards certifying L-infinitty robustness using neural networks with L-inf-dist neurons. In International Conference Machine Learning, pages 22368-1237., PMLR, 2021.
[74] Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Boosting the certified robustness of L-infinity distance nets. In International Conference on Learning Representations, 2022.
[75] Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. International Conference on Learning Representations, 2020.
[76] Huan Zhang, Tsui-Wer Weng. Pin-Yr Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems, volume 31, pages 4939-4948, 2018
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have discussed the limitations of this work in detail.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work is only for academic research purpose, without any foreseeable negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs are given either the main text or in Appendix
3. If you ran experiments...
(a) Did you include the code. data, and instructions needed reproduce the main perimental results (either the supplemental material or as a URL)? [Yes] We give complete implementation details in Appendix E Our code and models will be re- leased once the paper is published. We use public benchmark datasets which can be downloaded freely.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix E
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Appendix F
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix B
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We use public benchmark datasets which can be downloaded freely.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] We use public benchmark datasets which can be downloaded freely.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "xRwBlZjTNW9", "reviewer": "Reviewer_G1MR", "summary": "This paper presents novel theoretical results and a novel architecture for designing Lipschitz constrained neural networks (with respect to the infinity norm). The theoretical results provide new insights on two prior approaches and give a strong justification for the method introduced by the authors. The authors also provide a novel stochastic approximation to train their model efficiently. If I understand correctly, this comes at with a cost to expressiveness but is seemingly insignificant. Overall, I found this paper to be clearly written and with significant theoretical and empirical results.\n\nThe theoretical results are thorough and exciting. Unlike some prior work (e.g. Anil et al.) the authors provide (lower) bounds on approximation quality in addition to exact completeness results. Theorems 3.5 and 3.6 show that standard Lipschitz neural networks fail to achieve robustness as input dimensionality increases for simple 1-Lipschitz functions. These results are not surprising but are more concrete than prior results that I am aware of. Theorem 3.8 then gives a finite-dimensional completeness result for the distance nets that were introduced in prior work (though universal approximation results have already been shown, e.g. Zhang et al. 2021). Theorem 3.9 then shows that the previously introduced MaxMin networks require depth that grows with input dimension to approximate the order statistics accurately (confirming a negative result that had been explored empirically by Anil et al. 2019 and theoretically by Huster et al. 2019).\n\nEmpirically, the introduced SortNet architecture shows excellent performance (relative to the class of models it is compared against). SortNet typically achieves clean accuracy that is comparable to the clean accuracy of other certified networks but achieves improved certified robustness across the board. Importantly, it is also faster to train and compute certified bounds than other methods.", "questions": "\"Based on our knowledge of Boolean circuit theory\" --- as somebody without this knowledge, I'm keen to know a little more about this. Can you provide some brief intuition (in response, and in the paper) for why MaxMin nets require O(d) scaling while the distance nets appreciate constant depth.\n\nThe SortNet architecture introduces the weights as network parameters. To make the network training efficient, the weights are fixed to a geometric series. This contains the distance nets as a special case, but once the weights are fixed the networks are now, assuming an identity activation, less expressive than GroupSort networks that are able to learn the weights alongside using the order statistics. Is learning the weights entirely unimportant? Is it beneficial to fix them?\n\n\n### Minor comments\n\nIn line 227 you refer to the absolute value function as an example of a GNP element-wise activation function. This is just a small comment that absolute value and MaxMin are equivalent in terms of expressivity (at least in both the 2-norm and infinity-norm settings). See Appendix A.3 in Anil et al. (it is shown explicitly for 2-norm).\n\nL198-199: The negative answer is only shown for so-called Standard 1-Lipschitz neural networks.\n\nL170: \"Lipschitz\" -> \"1-Lipschitz\"\n\nL274: \"MinMax networks\" should be \"MaxMin\" networks as elsewhere in the paper", "limitations": "The authors do discuss limitations but only very briefly. So far as I can tell, they only discuss:\n\n- Not proving a tight upper bound on MaxMin networks for general Boolean functions\n- Not treating rho as a learnable parameter\n\nI feel that there are more details to be discussed here, some of which I raise in review. A broader discussion of the limitations of this research relative to related work would be appreciated. All of these may not be necessary, but here are some areas that could be discussed:\n- Architecture limited to fully-connected networks\n- Results/architecture only applicable under l_p norm constraints [though I believe some of the same ideas could be transferred more generally]\n- Limitations of norm-bounded threat models for robustness in practice\n- Limitations of margin-based robustness guarantees (in terms of training and certification)\n- Fixed weights when using stochastic approximation (related to fixed rho, but more general)", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe theoretical results are well presented and complete, providing upper and lower bounds on approximation error and highlighting order statistics as an important class of functions. There is more to do in this space. For example, the authors show that order statistics are hard to learn for MaxMin networks but why is this important for classification tasks? But I consider the paper to address all reasonable areas of interest in sufficient depth.\n\nI found the SortNet architecture compelling and the stochastic approximation of the linear function of the order statistics is very neat. The dropout connection is also interesting (and perhaps nested dropout is worth a mention).\n\nThe empirical results are thorough and compare across the appropriate metrics for the tasks considered. As always, including error bars would strengthen the empirical results further.\n\n## Weaknesses\n\nThe authors address only the infinity norm and make no claims on how these results may generalize to other l_p norms beyond section 3.1.\n\nThe authors results are only (obviously) applicable to fully-connected networks. This is a limitation which is shared by other work in the area, but not exclusively (Li et al. 2019 study 1-Lipschitz convolutions with respect to the 2-norm). It is unclear whether incorporating convolutional layers would improve performance on tasks which typically demand them (ImageNet).\n\nGenerally, it seems that the larger community has disengaged a little with norm-bounded threat models for adversarial robustness. This _is_ still an active area and I personally believe that certified robustness guarantees in this model remain an important topic of study. However, I reduce my score a little, in part, because I do not think the empirical results presented here would be enough to make waves in the deep learning community more broadly.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hi34jv2_VtB", "reviewer": "Reviewer_6St4", "summary": "The paper studies certifiably robust Lipschitz continuous neural networks. To this end they first prove a couple of impossibility results for standard Lipschitz networks, i.e., feedforward networks of the form $x_{k+1} = \\sigma(W_k x_k + b_k)$ where the activation $\\sigma$ is $1$-Lipschitz and the weight matrices have unit norm. Their first results deal with the approximation of Boolean functions $g^B : \\lbrace 0,1\\rbrace^d\\to\\lbrace 0,1\\rbrace$ and prove that no standard Lipschitz networks can achieve a robustness radius of more than $1/2d$, which obviously deteriorates in high dimensions. Consequently, these impossibility results are transferred to general Lipschitz functions by proving that the order statistics, the 1-Lipschitz function taking its input $x$ to the $k$-th largest component $x_{(k)}$, cannot be approximated by a standard 1-Lipschitz network.\n\nThe authors then continue the discussion by studying GroupSort and $\\ell_\\infty$-distance architectures, which are non-standard and are known to be universal Lipschitz function approximators. They prove that the simplified GroupSort architecture called MaxMin, which is commonly used since it's feasible to train, is NO universal Lipschitz function approximator. Furthermore, they prove that $\\ell_\\infty$-distance architectures can exactly represent certain Boolean functions and order statistics. \n\nMotivated by these insights they suggest a new architecture, SortNet, which has both GroupSort and $\\ell_\\infty$-distance networks as special cases. In particular, it is a universal Lipschitz function approximator. Then, they suggest a practical version of of SortNet which replaces the expensive sorting operation by an unbiased estimator which just evaluates the maximum of a masked vector. In contrast to the MaxMin simplifcation, their simplified SortNet is still an universal approximator.\n\nThey conclude with numerical results which show that the proposed SortNet architecture is consistently slightly to significantly better than $\\ell_\\infty$-distance networks and significantly better than GroupSort. \n\n######POST-REBUTTAL######\nI increased my score to strong accept.", "questions": "I only have very few minor comments which could further improve the presentation:\n\n- p.5, l.198: \"whether they can approximate all Lipschitz functions\" should be \"whether they can approximate all 1-Lipschitz functions\"\n- bibliography: capitalization should be fixed, e.g., lipschitz, Mnist, Mma, etc...\n- p.21, l.862: blank missing in \"some k\"", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is very well-written and organized. All proofs are deferred to an appendix but at the same time they are concise, clear, and correct (I check most of them, not all). The paper has a clear golden thread: first, impossibility results for standard networks are proved, then theoretical explanations for the success and failure of the known GroupSort and $\\ell_\\infty$-distance networks are proved, finally a novel and unifying architecture is suggested and evaluated.\n\nWeaknesses: \n\nN/A", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CkaS5pPHcDr", "reviewer": "Reviewer_P71v", "summary": "The authors present a generalization of some recently proposed variants of $\\ell_\\infty$-Lipschitz networks, i.e., networks that by design are 1-Lipschitz with respect to the $\\ell_\\infty$-norm, that come with guarantees of expressivity. This type of networks are useful as they automatically come with certificates of robustness without requiring expensive additional procedures, however some previous proposed designs suffered from low expressivity or difficulties during training.\n\nThe authors also present a stronger versions of a negative results on approximation of Lipschitz functions by standard Lipschitz neural networks (those with bounded weight matrices and element-wise 1-Lipschitz activations), as well as new negative results on the expressivity of MaxMin networks.\n\nThe proposed architecture is expensive to evaluate and hence, the authors propose to replace the layers with a stochastic approximation that drastically reduces the computation. The performance of the proposed approach is compared with state-of-the-art baselines showing promising but inconclusive results. Remarkably, the proposed architecture can be trained in a reasonable amount of time on the TinyImagenet and Imagenet datasets, which previously proposed methods found to be challenging.\n\n*** after rebuttal ***\nAuthors have addressed most of my concerns. I am inclined to increase my score. Will expand later on why.", "questions": "1. can you provide confidence intervals for the numbers in the experimental section?\n2. could you better back up the claim that the improvements over $\\ell_\\infty$-distance nets are significant?\n3. Could you clarify if there is a theoretical advantage of SortNet over $\\ell_\\infty$-distance net?\n4. Could you clarify in line 34 what you mean by *far from satisfactory*? Is there a number that would be considered *satisfactory*?", "limitations": "One limitation that I think is not mentioned, is that by introducing an stochastic estimation *between layers*, the gradient at a realization of the stochastic variables might not constitute an stochastic gradient of the full loss, and hence the optimization algorithms falls out of the SGD paradigm. Nevertheless in practice it looks like the performance obtained by this training procedure (similar to dropout) is enough to justify its heuristic nature.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**: The paper builds upon previous work that introduced the GroupSort activation and another work that introduced $\\ell_\\infty$-distance networks, but generalizes both approaches to a more expressive architecture. The expressivity claim is backed by formal approximation results that show, in particular, that the more computationally efficient version of the GroupSort-activation network, the MaxMin network still has limited expressivity. To my knowledge, such results are new. Another new result is that the $\\ell_\\infty$-distance network can approximate any discrete boolean function, a result that was not part of the original paper introducing such architecture. In contrast proposition 3.1 is well-known (or a slightly less general version) but is provided mostly for completeness.\n\n**Quality** + **Clarity**: The work backs up all claims with carefully presented proofs. Indeed the readability of the paper is vastly above the average subsmission and overall, the statements, proofs and high level ideas of the paper are easy to grasp, even though the proofs have a high level of technical difficulty. This is a major strength of this work. Nevertheless, we also find what in my opinion is the main weakness of this paper. Sadly, **the accuracy/robustness/certified-robustness numbers in the experimental evaluation are provided without a confidence interval**. Because some of these numbers appear to improve over the baselines by small amounts, it is not clear if such improvements are significant enough to warrant presenting them in **bold** and claiming a real improvement.\n\nPerhaps the authors have had time to do multiple runs between the time of submission and rebuttal period, and could clarify if the results do not appear to be better only by chance. One issue is that such experiments are costly to evaluate, but confidence intervals, at least for the smaller scale datasets like MNIST, CIFAR10, multiple runs should be standard and I think it is reasonable to expect them. On the other hand, the time numbers are clearly lower and one would not expect the randomness to drastically change them. Another good thing is that the biggest increase in performance appears to be in the Imagenet Dataset, which is usually considered more significant. The inclusion of confidence intervals at least for MNIST+CIFAR10 would definitely improve my score.\n\n**Significance**: The certified robustness problem is a long-standing problem and understanding the limits of what can be achieved is a significant problem. Even though $\\ell_\\infty$-robustness can be seen as a simplified model of real threats to computer vision systems, it can be seen as a way to devise more robust models in practice. Having a general architecture that subsumes previous promising Lipchitz networks and showing it is expressive enough to represent all boolean functions while being able to train it in a reasonable time seems significant enough. However, it was not so clear to me what is the precise theoretical advantage of SortNet (this work) vs $\\ell_\\infty$-distance network. I think not theoretical advantage was presented but rather it was shown through experiments that SortNet is somehow easier to train.\n\n**miscellaneous:**\n1. missing references [A] (for $\\ell_2$-metric) and [B] (for $\\ell_\\infty$-metric) which are methods to compute the Lipschitz constant of neural networks, that can be used to regularize the loss and obtain certified robustness.\n2. Proof between lines 729-730 in the appendix: \"With loss of generality\" -> \"Without loss of generality\" (I think this is what you meant)\n\n**References**:\n[A] Efficient and accurate estimation of lipschitz constants for deep neural networks.\nMahyar Fazlyab,  Alexander Robey, Hamed Hassani, Manfred Morari, George J. Pappas. NeurIPS 2019\n\n[B] Lipschitz constant estimation of Neural Networks via sparse polynomial optimization \nFabian Latorre, Paul Rolland, Volkan Cevher. ICLR 2020\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1GbWfjtlNw", "reviewer": "Reviewer_wXX6", "summary": "1. Problem/Motivation\n- The paper looks into the relationship between certified robustness and Lipschitz continuity for the $l_\\infty$ case. \n- It has been observed that Lipschitz networks don't work for $l_\\infty$ as well as they work for $l_2$ setting. However, recent work from Zhang et al. created some particular 1-Lipschitz network which has good robustness.\n- The authors try to understand this phenomenon.\n\n2. Methodology/Technical Finding\n\nA) Methodology\n- Authors study this question by using discrete Boolean functions and prove some impossibility results (negative results) for this setting. \n- This relates to the difficulty in training certifiably robust Lipschitz network for the $l_\\infty$ perturbations setting.\n\nB) Explaining performance of recent Lipschitz networks (Zhang et al.)\n- Authors use the above machinery to examine how some recent networks for this setting work well thus justifying their empirical performance.\n\nC) Designing even better Lipschitz networks\n- From the above insights, authors propose new networks.\n\n3. Experiments\n- Authors show the empirical performance of the proposed SortNet, where the methods perform almost at par (maybe slightly better) than recent methods.\n\n########## POST REBUTTAL ##############\nAfter going through other reviews and the authors rebuttal, I have decided to keep my score as it is (borderline accept) and not increase the rating. My main concern remains the same, that we need to move beyond theoretically convenient settings, to scale to networks used in practise.\nThe authors shared 2 threads of work, which I am aware of. Here are my concerns with them:\n- Randomised smoothing: The test time cost of randomised smoothing is very high as it needs to run for many perturbations. Thus even if they work on large datasets, the methods are not practical.\n- Certified robustness using Lipschitz networks: Are we able to convince the practitioners to use Lipschitz networks? ", "questions": "These are suggestions regarding writing. I hope it is useful for authors.\n1. Better sectioning\n- Look at the summary I wrote and how I divided into subgroups. If you do so throughout the paper, it would be great. Start from the introduction where you can have these as different paragraphs with paragraph names as bold.\n- Then match them with same names (either as paragraphs or subsections) in the method section.\n\n2. In the method section, before bringing a theorem, you should try to motivate the theorem. More space should be spent of motivation and linking theorems to the whole them or theme of the subgroup (see point 1).", "limitations": "The work addresses Certified Robustness, which is on the reliability line of work, thus positive societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have given a thorough summary in the above box. \n\nStrengths\n- The technical part of the paper is solid. Authors have used Boolean functions to explain the workings/robustness of Lipschitz networks. \n\nWeaknesses:\n1. Writing: The method section can be improved. It is a bit dense and hard to follow. I have provided suggestions for improvement in the Questions box.\n2. Problem Relevance: I am not sure about this whole line of work. Certified robustness has been there for a while now. It is not scaling up and there is less chance of scaling up. So, I am not sure if this is so relevant for the community.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept