Lipschitz constant estimation of Neural Networks via sparse polynomial optimization
Authors: Fabian Latorre
Paul Rolland
Volkan Cevher
Venue:  (2020)
Keywords: robust networks
Lipschitz constant
polynomial optimization

Abstract: We introduce LiPopt, a polynomial optimization framework for computing increasingly tighter upper bound on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (LP) or semidefinite (SDP) programming. We show how to use the sparse connectivity of a network, to significantly reduce the complexity of computation. This is specially useful for convolutional as well as pruned neural networks. We conduct experiments on networks with random weights as well as networks trained on MNIST, showing that in the particular case of the $\ell_\infty$-Lipschitz constant, our approach yields superior estimates as compared to other baselines available in the literature.


Published as a conference paper at ICLR 2020
LIPSCHITZ CONSTANT ESTIMATION OF NEURAL NET- WORKS VIA SPARSE POLYNOMIAL OPTIMIZATION
Fabian Latorre, Paul Rolland and Volkan Cevher EPFL, Switzerland
firstname lastname@epfl.
ABSTRACT
We introduce LiPopt, polynomial optimization framework for computing in- creasingly tighter upper bounds on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (L.P) or semidefinite (SDP) programming. We show how to use the sparse connectivity of network, to significantly reduce the complexity of computation. This is specially useful for convolutional well pruned neural networks. We conduct experiments net- works with random weights as well as networks trained on MNIST, showing that in the particular case of the foe -ipscchtzz constant, approach yields superior estimates, compared to baselines available the literature.
INTRODUCTION
We consider a neural network fa defined by the recursion:
f(x)) = W1
f((x) = ((o((i=())), i= 2
for an integer d larger than 1, matrices (Wi) of appropriate dimensions and an activation function understood to be applied wlement-wise. We refer to d as the depth, and we focus the case where fa has a single real value as output.
In this work, we address the problem of estimating the Lipschitz constant of the network fa. A function f is Lipschitz continuous with respect to norm ||-I| if there exists a constant L such that for all y have fz) f(y) < L| yll. The minimum over all such values satisfying this condition called the Lipschitz constant of f and denoted by I(.)).
The Lipschitz constant of neural network is of major importance in many successful applications of deep learning. In the context of supervised learning, [artlett et al.) (2017) show how it directly correlates with the generalization ability of neural network classifiers. suggesting plexity measure. It also provides a measure of robustness against adversarial perturbations (Szegedy) al. 2014) and can be used to improve such metric (Cisse al. 2017). Moreover, an upper bound on L fa) provides certificate of robust classification around data points (Weng et al. 2018).
model com-
Another example the discriminator network of the Wasserstein GAN (Arjovsky al. 2017 whose Lipschitz constant is constrained to be at most 1, To handle this constraint, researchers have proposed different methods like heuristic penalties (Gulrajani et al. 2017), upper bounds (Miyato) et al.) 2018), choice of activation function (Anil et al. 20119), among many others. This line of work has shown that accurate estimation such constant is key to generating high quality images.
Lower bounds or heuristic estimates of T.(Ja) can be used to provide general sense of how robust network is, but fail to provide true certificates of robustness to input perturbations. Such certificates require true upper bounds, and paramount when deploying safety-critical deep reinforcement learning applications (Berkenkamp et al.) 20177: Jin & Lavaci, 2018). The trivial upper bound given by the product of layer-wise Lipschitz constants is easy compute but rather loose and overly pessimistic, providing poor insight into the true robustness of a network (Huster et al., 2018).
Indeed, there is growing need for methods that provide tighter upper bounds on L(fa), expense of increased complexity. For example Raghunathan et al. (2018a); JJin Lavaci (2188) zlyab al. (2019) derive upper bounds based semidefinite programming (SDP). While expensive
the

---

Published as a conference paper at ICLR 2020
to compute, these type of certificates are in practice surprisingly tight. Our work belongs in this vein of research, and aims to overcome some limitations in the current state-of-the-an
Our Contributions.
>> We present LiPopt, a general approach for upper bounding the Lipschitz constant of a neu- ral network based on a relaxation 2015). This approach requires only that the unit ball be described with polynomial inequal- ities, which covers the common Eg- and 20 -norms.
polynomial optimization problem (POP) (Lasserre
Based on theorem due to Weisser et al. (2018), we exploit the sparse connectivity of neural network architectures to derive a sequence of linear programs (LPs) of considerably smaller size than their vanilla counterparts. We provide an asymptotic analysis of the size of such programs, in terms of the number of neurons, depth and sparsity of the network.
Focusing on the -nomm, we experiment on networks with random weights and networks trained on MNIST (Lecun al., [998). We evaluate different configurations of depth, width and sparsity and we show that the proposed sequence of LPs can provide tighter upper bounds on L(fa) compared other baselines available in the literature.
Notation. We denote by n, the number of columns of the matrix W, in the definition I of the network. This corresponds to the size of the i-th layer, where we identify the input as the first layer. We let = nn + ... na be the total number of neurons in the network. For vector x. Ding(x:) denotes the square matrix with x in its diagonal and zeros everywhere else. For an array X, vec is the flattened array. The support of a sequence supp(a:) is defined as the set of indices j such that Oj is nonzero. For x = [ In] and a sequence of nonnegative integers = [y1..... ?m] we denote by x the monomial x x.2 ... 27." The set of nonnegative integers denoted by N.
Remark,
The definition of network (T covers typical architectures composed of dense and convo- lutional layers. In general, our proposed approach can be readily extended with minor modifications to any directed acyclic computation graph c.g., residual network architectures (He et al. 2016).
2 POLYNOMIAL OPTIMIZATION FORMULATION
In this section we derive an upper bound on L(fa) given by the value of POP, i.e. the minimum value of a polynomial subject to polynomial inequalities. Our starting point is the following theorem, which casts L(f) as an optimization problem:
Theorem 1. Let f be a differentiable and Lipschitz continuous function on an open, convex subset X of an euclidean space. Let II-II, be the dual norm. The Lipschitz constant of f is given by
T.J) = sup [V[())..
xEX
For completeness, we provide a proof in appendix A function σ Lipschitz continuous and differentiable. In this case, the assumptions of Theorem I are fulfilled because fa is a composition of activations and linear transformations. The diffcrentiability assumption rules out the common ReLU activation a (xx) max(0, x), but allows many others such as the exponential linear unit (ELU) (Clevert et al. 2015) or the softplus.
In our setting, we assume that the activation
Using the chain rule, the compositional structure of fa yields the following formula for its gradient:
d-1
ff(z)) = WT II (o'agoo(()) (i (ff(
(3)
For every = 1....,d 1 introduce a variable s; a' (z)) corresponding to the derivative of a at the i-th hidden layer of the network. For activation functions like ELU or softplus, their derivative is bounded between 0 and 1, which implies that 0 < s; S 1. This bound together with the definition of the dual norm ||æ]|= == sup suppanis t x implies the following upper bound of L(fa):
d-1
L(fa) & max of (wW II
Diag(s; (s; WT, :0 OOSS s; 1, <
(4)
i=1
2

---

Published as a conference paper at ICLR 2020
We will refer to the polynomial objective of this problem the norm-gradient polynomial of the network fa, a central object of study in this work.
For some frequently used l ep-norms. the constraint ||t||p S 1 can be written with polynomial inequal- ities. In the rest this work, we use exclusively the fx -nom for which || S is equivalent to the polynomial inequalities -1 t, 1, for i 1,..., Mh1 However, note that when p 2 is a positive even integer, ||t||p I is equivalent to a single polynomial inequality ||t|| I 1, and our proposed approach can be adapted with minimal modifications.
In such cases, the optimization problem in the right-hand side of (4) is a POP. Optimization of
polynomials is NP-hard problem and we do not expect to have efficient algorithms for solving ( in this general form. In the next sections we describe LiPopt: systematic way of obtaining an upper bound on L(fa) via tractable approximation methods of the POP (4).
Local estimation. In many practical escenarios, we have additional bounds on the input of the network. For example, in the case of image classification tasks, valid input is constrained in hypercube. In the robustness certification task, we are interested in all possible input in e-ball around some data point. those cases, it is interesting to compute local Lipschitz constant, that is, the Lipschitz constant of function restricted to subset.
We can achieve this by deriving tighter bounds restricted input (see for example, Algorithm 1 in Wong & Kolter (2018). ) By incorporating this knowledge the optimization problem ( we obtain bounds on local Lipschitz constants of fa. We study this setting and provide numerical experiments in section 7.3
4 S 8; u < 1, as consequence of the
Choice norm. We highlight the importance of computing good upper bounds on L(Sa) with respect to the -orm. It is one of the most commonly used norms to assess robustness in the adversarial examples literature. Morcover, has been shown that, in practice, -nom robust networks also robust in other more plausible measures of perceptibility, like the Wasserstein distance (Wong et al. 2019). This motivates our focus on this choice.
3. HIERARCHICAL SOLUTION BASED ON A POLYNOMIAL POSITIVITY CERTIFICATE
For ease of exposition, we rewrite a POP constrained in [0, 1]" using the substitution 8p := (t+ 1)/2. Denote by p the norm-gradient polynomial, and let x: = [s...... 8d-1] be the concatenation of variables. Polynomial optimization methods (Lasserre 2015) start from the observation that a value À is an upper bound for p over set K if and only if the polynomial A is positive over K.
In LiPopt, we will employ a well-known classical result in algebraic geometry, the so-called Kriv- ine's 's positivity certificate but in theory
use any positivity certificate like -fm-of-squares (SOS). The following is a straightforward adaptation Krivine's certificate to our setting:
Theorem 2. (Adapted from Krivine (7964); Stengle (1974); Handelmar) (1988) If the polynomial p is strictly positive on [0, 1]",, then there exist finitely many positive weights Caß such that
X x
Σ (a,
Caphaa
has(x) = II (1-2,)
(5)
By truncating the degree of Krivine's positivity certificate (Theorem 2 and minimizing over all possible upper bounds À obtain hierarchy of LP problems (Lasserre 2015 Section 9):
0% min c20.A
A: A
Σ
CaphaB
(a,,))N2"
where N2n is the set of nonnegative integer sequences of length 2n adding up to at most k. This indeed sequence of LPs as the polynomial equality constraint can be implemented by equating coefficients in the canonical monomial basis. For this polynomial equality to be feasible, the degree
also known Krivine's 's Positivstellensatz
3

---

Published as a conference paper at ICLR 2020
of the certificate has to be at least that of the norm corm-gradient polynomial p. which is equal to the depth d. This implies that the first nontrivial bound (0% oo) corresponds to k =
The sequence {0x J j- is non-incresing and converges to the maximum of the upper bound (4) Note that for any level of the hierarchy, the solution of the LP (6) provides a valid upper bound on L(fa).
An advantage of using Krivine's positivity certificate over SOS is that one obtains LP hierarchy (rather than SDP), for which commercial solvers can reliably handle large instances. Other pos- itivity certificates offering similar advantage are the DSOS and SDSOS hierarchies (Ahmadi & Majumdar 2019), which boil down to LP or second order cone programming (SOCP), respectively.
Drawback. The size of the LPs given by Krivine's positivity certificate become quite large. The dimension of the variable c is | = (n²). For reference, we consider the MNIST dataset and a one-hidden-layer network with 100 neurons we have N = 1.5 10 while [13"] z 9.3 x 10 To make this approach more scalable, in the next section exploit the sparsity of the polynomial p to find LPs of drastically smaller size than (6. but with similar approximation properties.
Remark. In order compute upper bounds for local Lipschitz constants, first obtain tighter bounds 0 S 4 < 9, S. Uy and then perform the change of variables s, (s. - 4)/(w: - 4)) to rewrite the problem as POP constrained on [0, 1]".
REDUCING THE NUMBER OF VARIABLES
Many neural network architectures, like those composed of convolutional layers, have a highly sparse connectivity between neurons. Moreover, has been empirically observed that up to 90% of network weights can be prumed (set to zero) without harming accuracy (Frankle & Carbin 2019). In such cases their norm-gradient polynomial has special structure that allows polynomial positivity certificates of smaller size than the one given by Krivine's positivity certificate (Theorem 2}.
In this section, we describe implementation of LiPopt (Algorithm T that exploits the sparsity of the network to decrease the complexity of the LPs (6) given by the Krivine's 's positivity certificate. In this way, we obtain upper bounds on L(Ja) that require less computation and memory. Let start with the definition of a valid sparsity pattern:
Definition 1. Let I = {l....,1) n and be a polynomial with variable x E RR."" A valid sparsity pattern of p a sequence [1 of subsets of I, called cliques, such that U 1 and:
p = m Pj where ps is polynomial that depends only on the variables {æz : j 1,}
for all I,...,m m - there an I S such that (l++1 n 4
When the polynomial objective p in POP has valid sparsity pattern, there is extension of Theorem 2 due to Weisser et al. (2018), providing smaller positivity certificate for X over the sparse Krivine's certificate and we include it here for completeness:
11" We refer
Theorem (Adapted from Weisser al. (0188). Let a polynomial p have a valid sparsity pattern (4) Define N, as the set of sequences (a,, .3) E N2a where the support of both a and B is contained Is.
p strictly positive over =00, 1)", there exist finitely many positive
weights Cag such that
A p
has
h
Σ (a,3)EN
Caghaa
where the polynomials has are defined as in (5)
The sparse Krivine's certificate can be used like the general version [hheormm 2} to derive a sequence of LPs approximating the upper bound L(fa) stated in (4.. However, the number of different polynomials has of degree at most & appearing in the sparse certificate can be drastically smaller, the amount of which determines how good the sparsity pattern is.
We introduce a graph that depends on the network fa, from which we will extract a sparsity pattern for the corm-graddent polynomial of network.
4

---

Published as a conference paper at ICLR 2020
$
$1,1
$
$1.2
$0.3
$1.3
22,
#0.4
$1,4
Structure of one set in the sparsity pattern from Proposition [ for a network with 2D convolutional layers with 3 x 3 filters.
Figure 2:
Figure 1: Sparsity pattern of Proposition D for a network of depth three.
Definition 2. Let fa be a network with weights (Wi) Define directed graph G. = (V, E) as:
== {8Ls 0 0 S 1, S I nz} E {(.1,) 8i+ 11) : Si 2, Wila. # 0} which we call the computational graph of the network fa-
(8)
In the graph Ga the vertex {(ij) represents the j-th neuron the i-th layer. There is directed edge between two neurons in consecutive layers if they are joined by a nonzero weight in the network. The following result shows that for fully connected networks we can extract a valid sparsity pattern from this graph. We relegate the proof to appendix B
Proposition Let fa dense network (all weights are nonzero). The following sets, indexed by i 1, Rd. form valid sparsity pattern for the norm- corm-gradient polynomial of the network fa:
(5()-1,1) {s(2a)) there exists a directed path from (j.k) to ((d-1,)) in Ga}
We refer to this as the sparsity pattern induced by Ga. An example depicted in in Figure
Remark. When the network is not dense, the the second condition (Definition I for the sparsity pattern 9 to be valid might not hold. In that case we lose the guarantee that the values of the corresponding LPs converge the maximum of the POP (4). Nevertheless, it still provides valid positivity certificate that we use to upper bound L(fu). In Section 7 we show that in practice provides upper bounds of good enough quality. If needed, valid sparsity pattern can be obtained via a chordal completion of the correlative sparsity graph of the POP (Waki et al. 2006
We now quantify how good this sparsity pattern is. Let be the size of the largest clique in a sparsity pattern, and let N₁ be the subset of N₂ (defined in Theorem 3) composed of sequences summing up to k. The number of different polynomials for the k-th LP the hierarchy given by the sparse Krivine's certificate can be bounded as follows:
m
24 (2 - (ms*)
U i=1
N
S
Σ
(10)
We immediately see that the dependence on the number of cliques m is really mild (linear) but the size of the cliques as well as the degree of the hierarchy can really impact the size of the optimization problem. Nevertheless, this upper bound can be quite loose; polynomials has that depend only on variables in the intersection of two or more cliques are counted more than once.
The number of cliques given in the sparsity pattern induced by Ga is equal to the size of the last layer m = na and the size of each clique depends on the particular implementation of the net- work. We now study different architectures that could arise in practice, and determine the amount of polynomials in their sparse Krivine's certificate.
Fully connected networks. Even in the case of network with all nonzero connections, the sparsity pattern induced by Ga decreases the size of the LPs when compared to Krivine's 's certificate. this case the cliques have size n1 + ... + R but they all have the same common intersection equal to all neurons up to the second-to-las hidden layer. A straightforward counting argument shows that the total number of polynomials is (nn(n) + +... na-1 1-1), improving the upper bound (10)
5

---

Published as a conference paper at ICLR 2020
Unstructured sparsity. In the case of networks obtained by pruning (Hanson & Pratt 1989)
generated randomly from a distribution over graphs (Xie et al. 2019), the sparsity pattern can be arbitrary. In this case the size of the resulting LPs varies at runtime. Under the layer-wise assumption that any neuron is connected to at most r neurons in the previous layer, the size of the cliques (9) bounded as (rr))- This estimate has exponential dependency on the depth but ignores that many neurons might share connections to the same inputs in the previous layer, thus being potentially loose. The bound (IO) implies that the number of different polynomials is O(aar)).. )
2D Convolutional networks. The sparsity in the weight matrices of convolutional layers has a certain local structure; neurons are connected to contiguous inputs in the previous layer. Adjacent neurons also have many input pixels in common (see Figure 2) Assuming constant number of channels per layer, the size of the cliques in ( O(d)). Intuitively, such number proportional to the volume of the pyramid depicted in Figure where each dimension depends linearly on d. Using (10) we get that there are (ngadSk) different polynomials in the sparse Krivine's certificate. This drastic decrease in complexity when compared to the unstructured sparsity case.
The use sparsity in polynomial optimization preceeds Theorem Weisser et al. 2018). First stud- ied in the context of sum-of-squares by Kojima et al. (2005) and further refined in Waki et al. (2006); Lasserre (2006) (and references therein). it has found applications in safety verification (Yang et al., Zhang al. 2018), sensor localization Wang et al. (2006), optimal power flow (Ghaddar
2016
et al.
2015 and many others. Our work fits precisely into this set of important applications.
Algorithm LiPopt for ELU activations and sparsity pattern
Input: matrices { } sparsity pattern {T,)m hierarchy degree k.
1: < (2so WT
Diag(s;)W?
b compute norm-gradin corm-gradient polynomial
2: x , S
3: b < : E Nyl where p(z) Exeny byo7
compute coefficients of p in basis
4: for i = 11,...,,m1 do
5: No, + [(a, B) E N supp(aa n (3) S 4
6: N₂ NuK
7: h + E(a,))eN Capho
> compute positivity certificate
8: < (app (), E Na]; +- [].c]
> linear program variables compute coefficients of X - h in basis
9: Z + lZyhENN where A - h(x) >EN v)
return min(A:: Zy, y N2.
solve LP
QCQP REFORMULATION AND SHOR'S S SDP RELAXATION
Another way of upper bounding L(fa) comes from further relaxation of (4 to SDP. We consider the following equivalent formulation where the variables 8; are normalized to lie in the interval [-1, and rename 50:
d-
L(Sa) S max
T WT II Diag (3t + 1)W7 : 2d-1 90
-1 : 5
(11)
Any polynomial optimization problem like 11 can be cast as (possibly non-convex) quadratically constrained quadratic program (QCQP) by introducing new variables and quadratic constraints. This is well-known procedure described in Park & Boyd (2017) Section 2.1). When d = 2 problem is already a QCQP (for the foc and fo-norm cases) and no modification is necessary.
QCQP reformulation. We illustrate the case d 3 where we have the variables $1, 52 corre- sponding to the first and second hidden layer and a variable 5o corresponding to the input. The quadratic polynomial by
norm-gradient polynomial in this case is cubic, and it can be rewritten introducing new variables corresponding to the product of the first and second hidden layer variables.
More precisely the introduction of variable $1.2 with quadratic constraint $1.2 vec(s1s]] allows us to write the objective (IT) as a quadratic polynomial. The problem then becomes QCQP with variable y [1, 80, 81, 82, 21 of dimension 1 1272..

---

Published as a conference paper at ICLR 2020
SDP relaxation. Any quadratic objective and constraints then be relaxed to linear constraints on the positive semidefinite variable yy" = X > 0 yielding the so-called Shor's 's relaxation of (TT) (Park& & Boyd (2177] Section 3.3). When d 2 the resulting SDP corresponds precisely to the one studied in Raghunathan et al. (a)18a). This resolves a common misconception (Raghunathan et al., (0085) that this approach is only limited to networks with one hidden layer.
Note that in our setting we are only interested in the optimal value rather than the optimizers, so there is no need to extract a solution for (II) from that of the SDP relaxation.
This approach includes a further relaxation step from (TT), thus being fundamentally limited in how tightly it can upper bound the value of [(fa)- Moreover when compared to LP solvers, off-the--sell semidefinite programming solvers are, in general, much more limited in the number of variables they can efficiently handle.
Drawback.
In the case d = 2 this relaxation provides a constant factor approximation to the original QCQP YYe 1999). Further approximation quality results for such hierarchical optimization approaches to NP-hard problems are out of the scope of this work.
Relation to sum-of-squares. The QCQP approach might appear fundamentaly different to the hierarchical optimization approaches to POPs, like the one described in Section 3 However, it is known that Shor's SDP relaxation corresponds exactly to the first degree of the SOS hierarchical SDP solution to the QCQP relaxation (Lasserre] 2000). Thus, the approach in section 3 and the one in this section are, in essence, the same; they only differ in the choice of polynomial positivity certificate.
RELATED WORK
Estimation of L(Ja) with fg-norm is studied by Virmaux & Scaman (2018) Combettes & Pesquet 2019 Fazlyab et al.] (2019); Jin & Lavaci (2018). The method Seq proposed in Virmaux & Scaman (2018) has the drawback of not providing true upper bounds. It is in fact heuristic method for solving 4 but which provides no guarantees and thus can not be used for robustness certification. In contrast the LipSDP method of Fazlyab et al. (2019) provides true upper bounds on L(fa) and in practice shows superior performance over both SeqLip and CPLip (Combettes & Pesquet 2019).
Despite the accurate estimation of LipSDP, its formulation is limited to the fn-norm. The only estimate available for other e, f--norms comes from the equivalence of norms in euclidean spaces. For instance, we can obtain an upper bound for the foe -nor after multiplying the f2 Lipschitz constant upper bound by the square root of the input dimension. The resulting bound can be rather loose and our experiments in section 7 confirm the issue. In contrast, our proposed approach LiPopt can acommodate any norm whose unit ball can be described via polynomial inequalities.
Let us point to one key advantage of LiPopt, compared to LipSDP (Jin & Lavaei 2018 Fazlyab et al. 2019). In the context of robustness certification are given sample 2 and ball of radius around it. Computing an upper bound on the local Lipschitz constant in this subset, rather than global one, can provide a larger region of certified robustness. Taking into account the restricted domain we can refine the bounds in our POP (see remark in section []. This potentially yields a tighter estimate of the local Lipschitz constant. On the other hand, is not clear how to include such
additional information in LipSDP, which only computes one global bound on the Lipschitz constant for the unconstrained network.
Raghunathan et al. 2018a) find an upper bound for L(fa) with foo metric starting from problem 4 but only the context of one-hidden-layer networks (d -d= 2). To compute such bound they use its corresponding Shor's relaxation and obtain as byproduct differentiable regularizer for training networks. They claim such approach is limited the setting d but, as we remark in section 5 it is just a particular instance of the SDP relaxation method for QCQPs arising from polynomial optimization problem. We find that this method fits into the LiPopt framework, using SOS certificates instead of Krivine's. We expect that the SDP-based bounds described in can also be used as regularizers promoting robustness.
Weng et al. (2018) provide upper bound on the local Lipschitz constant for networks based on a sequence of ad-hoc bounding arguments, which are particular to the choice of ReLU activation function. In contrast, our approach applies in general to activations whose derivative is bounded.
7

---

Published as a conference paper at ICLR 2020
7
EXPERIMENTS
We consider the following estimators of L(fa) with respect to the Lo norm:
Name
Description
SDP
Upper bound arising from the solution of the SDP relaxation described in Sec- tion
LipOpt-k
Upper bound arising from the k-th degree of the LP hierarchy (6) based on the
sparse Krivine Positiistellenstatz.
Lip-SDP
Upper bound from Fazlyab et al. (2019) multiplied vd where is the input dimension of the network.
UBP
Upper bound determined by the product of the layer-wise Lipschitz constants with for metric
LBS
Lower bound obtained by sampling 50000 random points around zero, and evaluating the dual norm of the gradient
7.1 EXPERIMENTS ON RANDOM NETWORKS
We compare the bounds obtained by the algorithms described above networks with random weights and either one or two hidden layers. We define the sparsity level of a network as the maxi- mum number of neurons any neuron in one layer is connected to in the next layer. For example, the network represented on Figure has sparsity 2. The non-zero weights of network's i-th layer are where nı, is the number of neurons in layer i.
sampled uniformly in Vec
For different configurations of width and sparsity, we generate 10 random networks and average the obtained Lipschitz bounds. For better comparison, we plot the relative error. Since do not know the true Lipschitz constant, we cannot compute the true relative error. Instead, we take as reference the lower bound given by LBS. Figures 3 and show the relative error, i.e., (É LI.ns) LIN where LBS is the lower bound computed by LBS and is the estimated upper bound. Figures 9 and [О Appendix C we show the values of the computed Lipschitz bounds for and 2 hidden layers respectively.
When the chosen degree for LiPopt-k is the smallest as possible, i.e., equal to the depth of the network, we observe that the method is already competitive with the SDP method, especially in the case of hidden layers. When we increment the degree by 1, LiPopt-k becomes uniformly better than SDP over all tested configurations. We remark that the upper bounds given by UBP are too large to shown in the plots. Similarly, for the 1-hidden layer networks, the bounds from LipSDP too large be plotted.
Finally, we measured the computation time the different methods on each tested network (Fig- ures 4 and 6). We observe that the computation time for LiPopt-k heavily depends the network sparsity, which reflects the fact that such structure is exploited in the algorithm. In contrast, the time required for SDP does not depend the sparsity, but only the size of the network. Therefore as the network size grows (with fixed sparsity level), LipOpt-k obtains better upper bound and runs faster. Also, with our method, we see that possible to increase the computation power in order to compute tighter bounds when required, making it more flexible than SDP in terms of computa- tion/accuracy tradeoff. LiPopt uses the Gurobi LP solver, while SDP uses Mosek. All methods run on single machine with Core i7 2.8Ghz quad-core processor and 16Gb of RAM.
6.0
22.
62-
15.3
354
25.
131
15.0
178
214
353
150
232
350
120
262
(a) 40
40
(b) 80 x 80
160 X 160
(d) 320
320
Figure 3: Lipschitz approximated relative enror for 1-hidden layer networks
8

---

Published as a conference paper at ICLR 2020
(a) 40 40
(h) 80 X
80
(c) 160 x 160
(d) 320 320
Figure 4: Computation times for 1-hidden layer networks (scconds)
S0P
34
03
0.2
Spanity
Spaatty
(a) 5 x 5 X 10
(b) 10 X 10 X 10
(c) 20 x 20 10
(d) 40 x 40 x 10
Figure 5: Lipschitz approximated relative error for 2-hidden layer networks
30
Liee
Sprrdyy
(a) x X 10
(b) x 10 x 10
(c) X 20 10
(d) 40 X X 10
Figure 6: Computation times for 2-hidden layer networks (seconds)
7.2 EXPERIMENTS ON TRAINED NETWORKS
Similarly, we compare these methods on networks trained on MNIST. The architecture we use is a fully connected network with two hidden layers with 300 and 100 neurons respectively, and with one-hot output of size 10. Since the output is multi-dimensional, we restrict the network to a single output, and estimate the Lipschitz constant with respect to label 8.
Moreover, in order to improve the scalability of our method, we train the network using the pruning strategy described in Han et 22015 After training the full network using a standard technique, the weights of smallest magnitude are set to zero. Then, the network is trained for additional itera- tions, only updating the nonzero parameters, Doing so, we were able remove 95% of the weights, while preserving the same test accuracy. We recorded the Lipschitz bounds for various methods in Table 77.2 We observe clear improvement pared to SDP method, even when using k = 3. Also note that the input dimension is too large for method Lip-SDP to provide competitive bound, so we do not provide the obtained bound for this method.
the Lipschitz bound obtained from LiPopt-k com-
Algorithm Lipschitz bound
LBS
LiPopt-4
LiPopt-3
SDP
UBP
84.2
88.3
94.6
98.8
691.5
7.3 ESTIMATING LOCAL LIPSCHITZ CONSTANTS WITH LIPOPT
study the improvement the upper bound obtained by LiPopt, when we incorporate tighter upper and lower bounds on the variables s; of the polynomial optimization problem 4 Such bounds arise from the limited range that the pre-activation values of the network can take, when the input is limited to an fo. -orm ball of radius centered at an arbitrary point my-
In the of section 7.1
For training we used the code from this reference. is publicly available in htttp::/ htt.g/ttttu....ooo mi nightydevel oper /Deep//ep---eeeeeee /ttp///eoppppeeeeeeeeeeeeeee Compresepaaaoo. on- PyToohh

---

Published as a conference paper at ICLR 2020
The algorithm that computes upper and lower bounds the pre-activation values is fast (it has the same complexity as a forward pass) and is described, for example, in Wong & Kolter (2018). The variables 8; correspond to the value of the derivative of the activation function. For activations like ELU or ReLUU, their derivative monotonically increasing, so we need only evaluate at the upper and lower bounds of the pre-activation values to obtain corresponding bounds for the variables 8,-
We plot the local upper bounds obtained by LiPopt-3 for increasing values of the radius c, the bound for the global constant (given by LiPopt-3) and the lower bound on the local Lipschitz constant obtained by sampling in the e-neighborhood (LBS). We sample 15 random networks and plot the average values obtained. We observe clear gap between both estimates, which shows that larger certified balls could be obtained with such method in the robustness certification applications.
1.10
135
10
01
14
04
3.0
(53
(a) 40 40
(b) 80 x 80
(c) 160 X 160
(d) 320 x 320
Figure 7: Global vs local Lipschitz constant bounds for 1-hidden layer networks
044
022
8.45
025
028
A25
0.33
123
120
(a) 10 x 10 x 10
(b) 20 x 20 X 10
(c) 40 x 40 10
(d) 80 x 80 x 10
Figure 8: Global vs local Lipschitz constant bounds for 2-hidden layer networks
CONCLUSION AND FUTURE WORK
In this work, we have introduced a general approach for computing an upper bound on the Lipschitz constant of neural networks. This approach is based on polynomial positivity certificates and gen- eralizes some existing methods available in the literature. We have empirically demonstrated that it can tightly upper bound such constant. The resulting optimization problems are computationally expensive but the sparsity of the network can reduce this burden.
In order to further scale such methods to larger and deeper networks, we are interested in several possible directions: (i) wewvide-and-oonquue approaches splitting the computation on sub-networks in the same spirit of Fazlyab et al. 2019)) (fi) exploiting parallel optimization algorithms leveraging the structure of the polynomials, (122) custom optimization algorithms with low ow-memory costs such Frank-wole wolfe-type methods for SDP (Yurtsever et al. (009)) as well stochastic handling of constraints (Fercoq et al. 2019)) and (kv), exploting the symmetries in the polynomial that arise from
weight sharing in typical network architectures to further reduce the size of the problems.
ACKNOWLEDGMENTS
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement 725594 time-data) and from the Swiss National Science Foundation (SNSF) under grant number 100021_178865 FL is supported through a PhD fellowship the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. VC acknowledges the 2019 Google Faculty Research Award.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
A. Ahmadi and A. Majumdar. Dsos and sdsos optimization: More tractable alternatives to sum of squares and semidefinite optimization. SIAM Journal on Applied Algebra and Geometry, 3(2):193-230, 2019.
doi: 10.1137/18M1189955 URL httph:: /dcii http://d.....g11111113333
18M1189332
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In Pro- ceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 291-301, Long Beach, California, USA, 09-15 Jun 2019.
PMLRR
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference Machine Learning. volume 70 of Pro- ceedings of Machine Learning Research, pp. 214-223, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally margin bounds for neural networks. In Advances in Neural Information Processing Systems 30, pp. 6240-6249. Curran Associates, Inc., 2017.
Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. In Advances in Neural Information Processing Systems 30, pp. 908-918. Curran Associates, Inc., 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. Proceedings of the 34th International Conference on Machine Learming, volume 70 of Proceedings of Machine Learning Research, pp. 854 163, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Djórk-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUss. arXiv e-prints, art. arXiv: 1511111117200 1.07289, Nov 2015.
Patrick L. Combettes and Shan-Christophe Pesquet. Lipschitz Certificates for Neural Network Struc- tures Driven by Averaged Activation Operators. arXiv e-prints, art. M.Xiv:1903.01011 Mar 2019.
Mahyar Fazlyab, Alexander Robey. Hamed Hassani, Manfred Morari, and George J. Pappas. Effi- cient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks. arXiv e-prints, art. arXiv: 1et::1906..0 1906.44996, Jun 2019.
Olivier Fercoq, Ahmet Alacaoglu, Ion Necoara, and Volkan Cevher. Almost surely constrained con- vex optimization. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1910-1919, Long Beach, Califor- nia, USA, 09-15 Jun 2019. PMLR.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
Bissan Ghaddar, Jakub Marecek, and Martin Mevissen. Optimal power flow as a polynomial opti- mization problem. IEEE Transactions Power Systems, 31(1):539-546, 2015.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of wasserstein gans. In Advances in Neural Information Processing Systems 30, pp. 5767-5777. Curran Associates, Inc., 2017.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning. trained quantization and huffman coding. arXiv preprint 150000151, 2015.
David Handelman. Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math., 132(1):35-62 1988. URL https://prrjeectucldd.oog 443/e (133/uclid..pin 1111//1222889999
Stephen Jose Hanson and Lorien Y. Pratt. Comparing biases for minimal network construction with back- propagatpag In Advances in Neural Information Processing Systems 1, pp. 177-185. Morgan-Kaufmann 1989.
11

---

Published as a conference paper at ICLR 2020
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Conference on Computer Vision and Pattern Recognition, pp. 770-778, 06 2016. doi: 10.1109/CVPR.2216.990
Todd Huster, Cho-Yo Yu Jason Chiang, and Ritu Chadha. Limitations of the Lipschitz constant as a defense against adversarial examples. arXiv e-prints, art. 1rXiv:1807.09971 Jul 2018.
Ming Jin and Javad Lavaei. Stability-certffied reinforcement learning: A control-theoretic perspec- tive. arXiv e-prints, art. arXiv: 10. 1505, Oct 2018.
Masakazu Kojima, Sunyoung Kim, and Hayato Waki. Sparsity in sums of squares of poly- nomials. Mathematical Programming, 103(1):45-622 May 2005. ISSN 1436-4646. doi: 10. 10.10077/110007-0000555544
Jean-Louis Krivine. Anneaux préordonnés. Journal d' "'analyse mathématique, 12:p. 307-326, 1964.
J. B. Lasserre. Convergent Imi relaxations for nonconvex quadratic programs. In Proceedings of the 39th IEEE Conference on Decision and Control (Cat. No.00CH37187) volume 5, pp. 5041-5046 vol.5, Dec 2000. doi: 10.1 D0.1009/CDC.2001..91 .947388.
Jean B Lasserre. Convergent sdp-relaxations in polynomial optimization with sparsity. SIAM Jour- nal on Optimization, 17(3):822-8444 -422, 2006.
Jean Bernard Lasserre. Introduction to Polynomial and Semi-Algebraic Optimization. Cam- bridge Texts in Applied Mathematics. Cambridge University Press, 2015. doi: 10.1017/
10797811
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- learning applied to document recog- nition. Proceedings of the IEEE, 86(1 (6(11))2278-233 Nov 1998. doi: 10.1 17915.77777
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
Jaehyun Park and Stephen Boyd. General heuristics for nonconvex quadratically constrained quadratic programming. arXiv preprint vrXivv:703.07880 2017.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Representations, 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness adversarial examples. In Advances in Neural Information Processing Systems, pp. 10877-10887, 2018b.
Gilbert Stengle. nullstellensatz and positivstellennstzi in semialgebraic geometry, Mathematische Annalen, 207(2):87-97, Jun 1974. ISSN 1432-1807. doi: 10.1007/BF011362449
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems 31, pp. 3835-3844. Curran Associates, Inc., 2018.
H. Waki, S. Kim, M. Kojima, and M. Muramatsu. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM Journal on Optimization, 17(1):18-224 2006. doi: 10. 1771//000663802.
Zizhuo Wang, Song Zheng, Stephen Boyd, and Yinyu Ye. Further relaxations of the sdp approach to sensor network localization. Tech. Rep., 2006.
12

---

Published as a conference paper at ICLR 2020
Tillmann Weisser, Jean B Lasserre, and chy for large scale polynomial optimization with sparsity. Mathematical Programming Compu- tation, 10(1):1-32, 2018
Toh. Sparse-bsos: bounded degree sos hierar-
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 Pro- ceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 5276-5285 Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018, PMIR.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5286-5295, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Eric Wong, Frank Schmidt, and Zico Kolter. Wasserstein adversarial examples via projected Sinkhorn iterations. In Proceedings of the 36th International Conference on Machine Learn- ing. volume 97 of Proceedings of Machine Learning Research, pp. 6808-6817, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring Randomly Wired Neural Networks for Image Recognition. International Conference on Computer Vision, Apr 2019.
Zhengfeng Yang, Chao Huang, Xin Chen, Wang Lin, and Zhiming Liu. A linear programming relaxation based approach for generating barrier certificates of hybrid systems. In John Fitzgerald, Constance Heitmeyer, Stefania Gnesi, and Anna Philippou (eds.). FM 2016: Formal Methods, pp- 721-738, Cham, 2016. Springer International Publishing. ISBN 3--49--89999-6
Yinyu Ye. Approximating quadratic programming with bound and quadratic constraints. Mathemat- ical Programming, 84(2):219-22 Feb 1999. ISSN 1436-4646. doi: 10.100771000079800022 2a.
Alp Yurtsever, Olivier Fercoq, and Volkan Cevher. A caaittiionl-ggradee---aaaaae augmented la- grangian framework. In Proceedings of the 36th International Conference Machine Learning, volume 97 Proceedings of Machine Learning Research, pp. 7272-7281, Long Beach, Califor- nia, USA, 09-15 Jun 2019. PMLR.
Y. Zhang, Z. Yang, W. Lin, Zhu, X. Chen, and Li. Safety verification of nonlinear hybrid systems based on bilinear programming. IEEE Transactions on Computer-Aided Design of Inte- grated Circuits and Systems, 37(11):2768-22 2778, Nov 2018, doi: 00.1099/CAAD2001.888888
13

---

Published as a conference paper at ICLR 2020
A PROOF OF THEOREM
Theorem. Let f be differentiable and Lipschitz continuous function on an open, convex subset X of euclidean space, Let || be the dual norm. The Lipschitz constant of given by
L(f)
sup [VV
(12)
=EX
Proof. First show that L(S)= S suPsex [V]())]..
(5(x) - f(x)) =
VS((1 - +)x + (y) (y - x) dl
Vf((1 -t)x + ty) (y x) dt
[V x). + ty) dt 1ly x11
sup =cx
Vf(=)]+-|ly =
have used the convexity of X.
Now we show the reverse inequality L(f) 2 sup
V (x) |... To this end, we show that for any
positive we have that L(f) 2 supzex [V](()
Let E X' such that [[)](= 2 sup,ex [V(x)]]- e. Because is open, there exists sequence {h& 1 with the following properties:
(ha: vf(=)) [|>]]l\V\=>IIl
2. 2 + h2 E X
3. lim h4 = O.
By definition of the gradient, there exists function d such that lima-40 8(h) 0 and the following holds:
-)=+h)=f(0) (h. + 8(h]]AA)
For our previously defined iterates ba we then have
+ If(( + hx) - f(=) = ||/a|l/ + 8(hx))))))))))) (/xlll
Dividing both sides by ||hæl| and using the definition of L(f) we finally get
f( h&) f(=)
= I(f)) Z
|| 5(h4)
|hal|
I(f) 2 lim
[|]f(=)]l + - [V]
k-000
= I(F) 2 sup [Vf())|
ZEX
14

---

Published as a conference paper at ICLR 2020
B PROOF OF PROPOSITION 1
Proposition. Let fa be a dense network (all weights are nonzero). The following sets, indexed by ...... ; Rdd form valid sparsity pattern for the norm-gradient polynomial of the network fa:
4 = (,)- {.))) there exists directed path from 8(j,)) 8(d-1.5) in Ga}
(13)
Proof. First we show that 4 = I. This comes from the fact that any neuron in the network is connected least one neuron the last layer. Otherwise such neuron could be removed from the network altogether.
Now we show the second property of valid sparsity pattern. Note that the norm- comm-gradient polyno- mial is composed of monomials corresponding to the product of variables in a path from input to final neuron. This imples that if let p; be the sum of all the terms that involve the neuron ((d-1,)) have that p >; Pt. and p; only depends on the variables in 4i-
We now show the last property of the valid sparsity pattern. This is the only part where we use that the network dense. For any network architecture the first two conditions hold. We will use the fact that the maximal cliques of a chordal graph form valid sparsity pattern (see for example Lasserre 2006)).
Because the network is dense, we see that the clique I; is composed of the neuron in the last layer 1,1-1,5) and all neurons in the previous layers. Now consider the extension of the computational
graph G. (V, E) where
È E sl,m) : 1 d 2))
which consists of adding all the edges between the neurons that not in the last layer. We show that this graph is chordal. Let (a1...., a, 01) be a cycle of length at least 4 (r 2 4). notice that because neurons in the last layer are not connected between them in G, no two consecutive neurons in this cycle belong to the last layer. This implies that in the subsequence (a1, 022 03 04, a5) at most three belong to the last layer. A simple analysis of all cases implies that it contains at least two nonconsecutive neurons not the last layer. Neurons not the last layer are always connected in G. This constitutes a chord. This shows that Ga is a chordal graph. Its maximal cliques correspond exactly to the sets in proposition.
15

---

Published as a conference paper at ICLR 2020
C EXPERIMENTS ON RANDOM NETWORKS
LPer
150
3.0
10
12.0
222
123
252
12.3
32.
120
40
40
(b) 80 80
(c) 160 160
(d) 320 320
Figure 9: Lipschitz bound comparison for 1-hidden layer networks
67
Searie
Spursty
Spantr
Searth
(a) x 5 x 10
(b) 10 x 10 x
10
(c) 20 20 X 10
(d) 40 x 40 x 10
Figure 10: Lipschitz bound comparison for 2-hidden layer networks
16


Reviews:
[{"review_id": "ryePC-_y5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors introduce a framework for computing upper bounds on the Lipschitz constant for neural nets. The main contribution of the paper is to leverage the sparsity properties of typical feed-forward neural nets to reduce the computational complexity of the algorithm. Through experiments, the authors show that the proposed algorithm computes tighter Lipschitz bounds compared to baselines.\n\nThe approach proposed in the paper looks interesting. Although the presentation can be made clearer in places. For example, in equation (4), it would be helpful to explicitly state over which parameters the max is taken. There's also a number of small typos that need to be fixed. For example: \"We refer to d as the depth, and we we focus on the case where fd has a single real value as output.\" on page 1.\n\nI found the proposed algorithm and the discussions in Section 2 and 3 interesting, although I am not familiar enough with the literature on polynomial optimization to evaluate whether there is any significantly new idea presented in these sections. I found section 4 very interesting too, and very important towards making the algorithm actually computationally tractable. I have a couple of concerns with the rest of the paper however, which `I describe below:\n\n1. It is nice that upper bounds for the local Lipschitz constant can be incorporated easily into the formulation. I would have liked to see some experiments on evaluating local Lipschitz constants though, and how they compare with other methods, since this is a very popular setting in which such techniques are used nowadays.\n\n2. The paper overall I think would benefit from a better experimental evaluation. It would be interesting to see how much the sparsity pattern in convnets affect results compared to other baselines. It would also be interesting to see how the bound degrades as the network grows bigger, and in particular as the depth increases.\n\nGiven the lack of thorough experiments in the paper, I am giving the paper a borderline rating. I am however willing to increase my score based on discussions with the authors and other reviewers.\n\n===================================\n\nEdit after rebuttal: \nThe latest draft addresses most of my concerns, and I am happy to recommend accepting this paper now.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Skxd_pz5Yr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the problem of estimating the Lipschitz constant of a deep neural network with ELO activation function. The authors formulate the problem as a polynomial optimisation problem, which is elegant. Subsequently, they utilise an LP hierarchy based on the Krivine-Vasilescu-Handelman’s Positivstellensatz and suggest exploiting sparsity therein. The computational results are clearly not sufficient to apply this approach to real-world neural networks, but are still respectable.\n\nSection 3 (Theorem 2) is not original work, as leaving the theorem without a reference would imply: the authors cite Section 9 of Lasserre's 2015 book later, so they are clearly aware of this, and there are many application even within verification, e.g.,\nhttps://link.springer.com/content/pdf/10.1007%2F978-3-319-48989-6_44.pdf\nhttps://ieeexplore.ieee.org/document/8493559\n\nThe suggestions as to the exploitation of sparsity (Section 4) are not original work either. The authors could cite, e.g., JB Lasserre: Convergent SDP-relaxations in polynomial optimization with sparsity (SIAM Journal on Optimization, 2006), as one of the early proponents of the exploitation of sparsity.\n\nIn Section 7:\n-- The claim \"We observed clear improvement of the Lipschitz bound obtained, compared to the SDP method\" is not supported by the results the authors present. \n-- The authors do not present the run-time. This needs to be included, considering they imply that the key improvement over the traditional SDP is that this works with smaller variables and should be faster. \n-- The presentation of the experimental results should be improved, so as to follow the NIPS reproducibility checklist, or at least have error bars at one standard deviation and standard deviation in the table. \n\nOther than that, the paper is well written (modulo Section missing in \"Section 5\" at the top of Section 7), and I would recommend its acceptance. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BklFCPgRKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a general approach for upper bounding the Lipschitz constant of a neural network by relaxing the problem to a polynomial optimization problem. And the authors extend the method to fully make use of the sparse connections in the network so that the problem can be decomposed into a series of much smaller problems, saving large amount of computations and memory. Even for networks that don't have high-level sparse connections, the proposed method can still help to reduce the size of the problem. This paper also compares the proposed LiPopt method with another solution derived from a quadratically constrained quadratic program reformulation. Compared with this method, the LiPopt method can handle cases with more parameters efficiently.\n\nCalculating a TIGHT upper bound of a neural network efficiently is very valuable and useful in many areas in deep learning community. And I really like the potential to use this LiPopt method to upper bound local Lipschitz constant in a given neighboring region, which will be very useful in certificated robustness application, etc..\n\nI also like that the authors present results on networks trained on real-world dataset (MNIST). My only suggestion is that I'd like to see LiPopt's computation time and memory usage compared to its counterparts, as the authors argue the proposed method can fully exploit the sparse connections to reduce the problem size.\n\n=======\nUpdate: I am satisfied with the authors' solid response and would like to raise my score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper improves upper bound estimates on Lipschitz constants for neural networks by converting the problem into a polynomial optimization problem.  The proposed method also exploits sparse connections in the network to decompose the original large optimization problem into smaller ones that are more computationally tractable. The bounds achieved by the method improve upon those found from a quadratic program formulation.  The method is tested on networks with random weights and networks trained on MNIST and provides better estimates than the baselines.

The reviews and the author discussion covered several topics.  The reviewers found the paper to be well written.  The reviewers liked that tighter bounds on the Lipschitz constants can be found in a computationally efficient manner.  They also liked that the method was applied to a real-world dataset, though they noted that the sizes of the networks analyzed here are smaller than the ones in common use.  The reviewers pointed out several ways that the paper could be improved.  The authors adopted these suggestions including additional comparisons, computation time plots, error bars, and relevant references to related work.  The reviewers found the discussion and revised paper addressed most of their concerns.

This paper improves on existing methods for analyzing neural network architectures and it should be accepted.
Decision: Accept (Poster)