A Quantitative Geometric Approach to Neural-Network Smoothness
Authors: Zi Wang
Gautam Prakriya
Somesh Jha
Venue: NeurIPS 2022 Accept (2022)
Keywords: Neural Networks
Semidefinite Programming
Lipschitz Constant

Abstract: Fast and precise Lipschitz constant estimation of neural networks is an important task for deep learning. Researchers have recently found an intrinsic trade-off between the accuracy and smoothness of neural networks, so training a network with a loose Lipschitz constant estimation imposes a strong regularization, and can hurt the model accuracy significantly. In this work, we provide a unified theoretical framework, a quantitative geometric approach, to address the Lipschitz constant estimation. By adopting this framework, we can immediately obtain several theoretical results, including the computational hardness of Lipschitz constant estimation and its approximability. We implement the algorithms induced from this quantitative geometric approach, which are based on semidefinite programming (SDP). Our empirical evaluation demonstrates that they are more scalable and precise than existing tools on Lipschitz constant estimation for $\ell_\infty$-perturbations. Furthermore, we also show their intricate relations with other recent SDP-based techniques, both theoretically and empirically. We believe that this unified quantitative geometric perspective can bring new insights and theoretical tools to the investigation of neural-network smoothness and robustness.

A Quantitative Geometric Approach to Neural-Network Smoothness
Zi Wang University of Disconsin-Madisee zwocs wwsc. edu
Gautam Prakriya The Chinese University of Hong Kong
gautamprakriyaa@aaal com
Somesh Jha
University of Wisconsin-Madiss jhaßcs wisc. edu
Abstract
Fast and precise Lipschitz constant estimation of neural networks an important task for deep learning. Researchers have recently found an intrinsic trade-off between the accuracy and smoothness of neural networks, so training a network with a loose Lipschitz constant estimation imposes strong regularization, and can hurt the model accuracy significantly. In this work, we provide unified theoretical framework, quantitative geometric approach, address the Lipschitz constant estimation. By adopting this framework, we can immediately obtain several theoret- ical results, including the computational hardness of Lipschitz constant estimation and its approximability. We implement the algorithms induced from this quantita- tive geometric approach, which are based on semidefinite programming (SDP) Our empirical evaluation demonstrates that they are more scalable and precise than existing tools Lipschitz constant estimation for -e-petuurbatinns Furthermore, we also show their intricate relations with other recent based techniques, both theoretically and empirically. We believe that this unified quantitative geometric perspective can bring new insights and theoretical tools to the investigation of neural-network smoothness and robustness.
Introduction
The past decade has witnessed the unprecedented success of deep learning in many machine learning tasks (Krizhevsky et al., [217 Mikolov et al. (013). Despite the growing popularity of deep learning, very vulnerable to adversarial attacks (Szegedy (ct al. 2014, Goodfellow et al. 2015 Papernot et al.) 2016). As a result, is important to train neural networks that are robust against those attacks (Madry al. 2018). In recent years, the deep learning community starts to focus on certifiably robust neural networks (Albarghouthi) 2021 Hein
researchers have also found that neural networks
and Andriushchenko 2017 Katz et al. 2017 Cohen al. 2019 Raghunathan et al. 2018 Wang ct al. Leino et al. 2021). One way to achieve certified robustness is to estimate the smoothness of neural networks, where the smoothness is measured by the Lipschitz constant of the neural network.
7017:Cohen
Recent works have found that to achieve both high accuracy and low Lipschitzness, the network has
significantly increase the model capacity (Bubeck and Sellke 2021 This implies that there is intrinsic tension between the accuracy and smoothness of neural networks.
Commonly considered adversarial attacks are the loo and fz-perturbations in the input space. Leino ct al. (2021): Cohen
Cohen et al. (2019) have successfully trained networks with low Lz-Lipschitz constant,
!Our code is available at
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and Huang et al. (2021) trained networks with low local Lipschitzness for &oo pprtuurattinns There are few well-established techniques to train neural networks with low global Lipschitzness for 2s-- perturbations. The techniques for the l2 f2-perturbation do not easily transfer to the - (Leino) al. 202T). One critical step is to measure the Lipschitz constant more precisely and efficiently. Jordan and Dimakis (2020) showed that for ReLU networks, it is NP-hard to approximate the Lipschitz constant for & -perturbations within a constant factor, and proposed an exponential- algorithm to compute the exact Lipschitz constant. However, researchers are interested in more scalable approaches to certify and train networks. In this work, we consider the Formal Global Lipschitz constant (FGL) (See Equation (3), which is roughly the maximum of the gradient operator norm, assuming all activation patterns on hidden layers are independent and possible. FGL is an upper bound of the exact Lipschitz constant and has been used in Raghunathan al. (0118) Fazlyab et al.
2019); Latorre et al. (2020).
We address the Lipschitz constant estimation from the quantitative geometric perspective. Quantitative geometry aims to understand geometric structures via quantitative parameters, and has connections with many mathematical disciplines, such as functional analysis and combinatories (Naor 2013). 3...1. In computer science, quantitative geometry plays a central role in understanding the approximability of discrete optimization problems. We approach those hard discrete optimization problems by considering the efficiently solvable continuous counterparts, and analyze the precision loss due to relaxation, which is often the SDP relaxation (Goemans and Williamson 1995; Nesterov 1998] Alon and Naor 2004). The natural SDP relaxations for the intractable problems usually induce the optimal known polynomial time algorithms (Bhattirrouu al., (022). By adopting the quantitative geometric approach, we can immediately understand the computational hardness and approximability of FGL estimations. Our algorithms on two-layer networks are the natural SDP relaxations from the quantitative geometric perspective.
Latorre et al. (2020) employed polynomial optimization methods the FGL estimation for too- perturbations. Polynomial optimization a very general framework, and many problems can be cast in this framework (Motzkin and Straus 1965 Goemans and Williamson 1995). Therefore, we argue that this is not a precise characterization of the FGL-estimation problem. On the other hand, there are also several SDP-based techniques for FGL estimations. Raghunathan et al. (2018) proposed an SDP algorithm to estimate the FGL for Lo perturbations of two layer networks, and Fazlyab et al. (2019) devised an SDP algorithm to estimate the f--FGL. We will demonstrate the intricate relationships between our algorithms and these existing SDPs on two-layer networks.
Several empirical studies have found that techniques on one tp-perturbations often do not transfer to another ones, even though the authors claim that theory these techniques should transfer (Fazlyab) et al. 2019 Leino et al. 2021). This in-theory claim usually comes from a qualitative perspective. In finte-ddimnssionl space, one can always bound one l, fp-norm from another one, so techniques for one fy-perturbations can also provide another bound for different É ty-perturbations. However, this bound is loose and in practice not useful (Latorre et al.) 2020). Instead, we believe that when transferring techniques from one norm another one, we should consider the quantitative geometric principle: we should separate the -eeeedeet component from the geometry-indepeeddnt one in those techniques, and modify the geometry-deped dependent component accordingly for a different normed space. As we will demonstrate, our whole work is guided by this principle. We hope that our unified quantitative geometric framework can bring insights the empirical hard-to-transfer observations, and new tools to address these issues.
Contributions. To summarize, we have made the following contributions:
1. We provide a unified theoretical framework to address FGL estimations, which immediately yields the computational hardness and SDP-based approximation algorithms on two-layer networks (Section 3
2. We demonstrate the relations between our algorithms and other SDP-based tools, which in return inspires us to design the algorithms for multi-layer networks. This provides more insightful and compositional interpretations of existing works, and makes them easier-to- generalize (Sections 3).
3. We implement the algorithms and name the tool GeoL.I. We empirically validate our theoreti- cal claims, and compare Ge with existing methods to estimate FGI perturrbbaassssss. The result shows that GeoLIP provides a tighter bound (20%-60% improvements) than

---

existing tools on small networks, and much better results than the naive matrix- -ereenooom--paa corm-product method for deep networks, which existing tools cannot handle (Section
2 Preliminaries
Notation. Let [n] (1.....7 .n. For two functions f and 9. o g(x) = f(g(z)) A 0-1 cube is 10,13", and a norm- cube is (-1, 1 nM for some integer n > 0. R+ = [0,, For any vector E IR" diag(v) is n x n diagonal matrix, with diagonal values Let C, (1, (l......
R" be an n-dimensional vector of all I's; and I = diag(en), the identity matrix. Let || denote the tp norm of v. We use y to denote the Hölder conjugate of as a convention, i.e., ; + 1. If e is an operator in the l -pscee the operator norm of is then ||v|l.- Throughout the paper, we consider the nnror of the input's perturbation, and therefore, the norm of the gradient, which acts as an operator on the perturbation. A square matrix X > 0 means that X is positive semidefinite (PSD). Let tr( (X) be the trace of square matrix X. If a, b E R,, let (a, b) be the inner product of a and b.
Lipschitz function. Given two metric spaces (X,dx) and (Y, dy), function f X + Y is Lipschitz continuous if there exists K > 0 such that for all æ1, 22 X,
(f f(x1)) I (dx(2z,51))
The smallest such K satisfying Equation (T), denoted by Ky, called the Lipschitz constant of f. For neural networks, X is in general Nº equipped with the fn-norm. We will only consider the case when
R. In actual applications such as classification task, a neural network has multiple outputs. The prediction is the class with the maximum score. One can then use the margin between each pair of class predictions and its Lipschitz constant to certify the robustness of a given prediction (Raghunathan et al.) 2018 Leino al. (02I). From Rademacher's 's theorem, if f is Lipschitz continuous, then f is is almost everywhere differentiable, and Ky = sup, [V(())ll.
Neural network function. A neural network f R + E is characterized by: f1(x) = a'x+ + bys f((x) = ()) + b,, i = ,,......
where W E R is the weight matrix between the layers, 01 d is the depth of the neural
network, a denotes an activation function, b; E IR is the bias term, and f = fa f.... o f1. Because only consider the R as the codomain of f, Wd gradient of this function is
Rixna is vector. From chain rule, the
f((x)
( (I())) diag (Ja-
Common activation functions, including ReLU (Nair and Hinton 2010), sigmoid functions, and ELU (Clevert et al., 2016) are almost everywhere differentiable. As result, we are interested the supremum operator norm of Equation (2).
However, checking all possible inputs æ infeasible, and common activation functions have bounded derivative values, say (a, b). We are then interested in the following value instead:
I|( diag(v") ................................ diag(v ((ag() E
max
(3)
where is the dimension of each diag(u"). We call this value the formal global Lipschitz constant (FGL) because we treat all activation functions independent but in reality not all activation patterns are feasible. Therefore, this is an upper bound of the true global Lipschitz constant of the neural network. However, it is the value studied in most global Lipschitzness literature (Scaman and Virmaux 20188] Fazlyab et al. 2019: Latorre et al. 2020), and also turns out useful in certifying the robustness of neural networks (Raghunathan et al. 2018 Leino et al. 2021 Pauli et al. 2022). We use -GLL to
denote the FGL for E,- ---peturrbatinn.
In this paper, we focus on the pettuuturbttion on the input, where p == 00 or p Because q the Hölder conjugate of p. we are interested in the value of Equation
when q = (for oc), and q = 2 (for p = 2). Notice that the ReL.Unetwork case, (a, b) is [0, 1]. We will use ReLU-networks as the illustration for the rest of the paper because of the popularity of ReLU in practice and the easy presentation of the -elbe. However, the algorithms presented in this work can be adapted with minor adjustments to other common activation functions.
3

---

Remark 2.1. FGL considers all possible activation patterns on the hidden layers, while some of the activation patterns might be unachievable in reality, Therefore. FGL is an upper bound of the true Lipschitz constant. Notice that the activation pattern induced from an input is also decided by the bias term. Therefore, to find the true Lipschitz constant, one has to incorporate the information from the bias term.
3 Two-layer neural networks
In this section, we consider the two-layer neural network case. We reduce the FGL estimation to the matrix mixed-norm problem. This immediately yields the computational complexity and approximation algorithms for FGL estimations. the appendix, we show that we can consider {0, 1} instead of [0, 1] in Equation (3) for two-layer networks.
Problem description. For a two-layer network where W = W E Raxm and W = IIx", its FGL (as in Equation (3) is ma. || diag(y) (ll where we use y denote oa in this case. we expand the matrix multiplication, it is easy to check that this equals to y0, ||W diag(u))) Let A = W diag(u u), then the is
(0,1)) ||Au|la.
(4)
3.1 FFL estimation
We consider a natural SDP relaxation to Equation (4) when 9 = 1, and analyze the result using the celebrated Grothendieck Inequality, which is fundamental tool in functional analysis.
Mixed-norm problem.
The oo + mixed-norm of a matrix defined as
bo max ||4x||1-
||]||_=]
The mixeddnorm problem appears similar to Equation 44) when g = 1, except for that instead of a norm-l-cube the cube in Equation (4) is 0- 1-cbb. (Alon and Naor (2004) showed that it is NP-hard specifically MAXSNP-hard to compute the co + mixed -orm matrix A, via a reduction to the graph Max-Cut problem. Moreover, Alon and Naor (2004) constructed natural SDP relaxation for the mixed-norm problem:
max (r)
(5)
8.L. X 0, Xa = 1,i E [n mm)
where A is submatrix of B. We provide the detailed derivation of this relaxation in the appendix. In fact, this relaxation admits constant approximation factor. Grothendieck (1956) developed the local theory of Banach spaces, and showed that there exists an absolute value KG such that
Theorem 3.1. For any m. n 2 A E Rxxm and any Hilbert space H, the following holds:
Σ (u, U))H S Kal|A||oo-1. max ((H
where B(H) denotes the unit ball of the Hilbert space.
The precise value of KG is still an outstanding open problem, and it is known that KG < 1.783 Kriv-
iine 1979 Braverman et al., (20TT). The approximation factor of the SDP relaxation Equation (5) Kg. Similar to the mixed-norm problem, we show that the lx FGIL. estimation is MAXSNP- and provide an SDP relaxation, which also admits the ap-apoooinnttion ratio. We provide a detailed explanation why KG is the approximation ratio and how we can view the SDP relaxation geometric transformation in the appendix.
Theorem 3.2. e -FLL estimation MAXSNP-hard.
From 0-1 cube to norm-1 cube. If we can transform the 0-1 cube in Equation 4 to norm- 1 cube, and formulate an equivalent optimization problem, then one can apply the SDP program in Equation 5) to compute upper bound of the FGL. Indeed, we provide cube rescaling technique,

---

and it allows us to construct the SDP for the foc -GL estimation. We provide the full detail of this technique in the appendix, and the result SDP for the -FLL estimation
max (x)
(6)
s.t. ž 0, X = 1, [n + m 1],
where B is a (n + m) (n + + m)) matrix, and B 0 0
0) As a result, we have:
Aen
Theorem 3.3. There exists a polynomial-time approximation algorithm to estimate the -FGL of two-layer neural networks, moreover, the approximation ratio is Kg.
3.2 22-FGL estimation
Scaman and Virmaux (2018) showed that the 22-FGL estimation is NP-hard. qf = in Equation the objective becomes similar to the problem with a PSD weight matrix over a cube, and can be viewed as a generalization of the graph Max-Cut problem. In the quadratic-optimizatin formulation of Max-Cut, the weight matrix the Laplacian of the graph, a special PSD matrix (Goemans and Williamson, 1995). Nesterov (1998) generalized Goemans- Williamson's 's technique and analyzed the case when the weight matrix is PSD, showing that the natural SDP relaxation in this case has a 3 gaappoxximation ratio. This provides a
mixed-nonne problem. This is quadratic optimization
v / appprooxittaooonn algorithm for the 2--FGI. estimation. The approximation ratio comes from similar inequality to the one Theorem 3.1 for F2GL estimation is:
known as the Little Grothendieck Inequality. The SDP
AT c TAAT
AT Acn
max 21
tr(
A
AA
X)
8.1. X 0, Xa 1, +1]
The full derivation is provided in the appendix, and have the following theorem: Theorem 3.4.
There exists polynomial time approximation algorithm to estimate the 2--FGL of two-layer neural networks with an approximation factor V
Remark 3.5. As we have discussed, for two-layer networks, the f,-FGL estimation is essentially the 00 + mixed-norm problem. Indeed the mixed-norm problem is an outstanding topic in theoretical computer science. As discussed in |Bhatiprolu et al. 2018), the constant approximation algorithms if q S 2, and is hard to approximate within almost polynomial factors when g > 2. Because when q > 2, its Hölder conjugate networks, the FGL estimation can much harder for E, perrturbations when < 2.
y mixed norm problem has
2. This implies that for two-layer
Briët et al. (017)) showed that it is NP-hard to approximate the co - mixed-norm problem better than 2 Raghavendra and Steurer 2009) proved that assuming the unique games conjecture (Khot 2002). it is NP- to approximate the co + 1 mixed-norm problem better than Kg. These optimal approximation ratios match our SDP relaxations for FGL estimations accordingly.
Relations to existing SDP works
Before introducing our approach for on FGL estimations, and discuss their relationships with our natural SDP relaxations in Section
networks, we first examine some existing SDP works
-FL estimation. Raghunathan et al. (0018) formulated an SDP that only works for two-layer networks. Theirs is essentially the same as ours in Equation (6) (See the detailed comparison in the appendix). However, we provide rigorous derivation and simpler formulation, and also a sound theoretical analysis the bound, which illustrate more insights to this problem. |Raghunathan et al.) (2018) treated the SDP relaxation as a heuristic to hard quadratic programming problem. We prove that this relaxation is not only a heuristic, but in fact induces an approximation algorithm with a tight bound.
f2IFGL estimation. Fazlyab et al. 2019) proposed LipSDP, another SDP-based algorithm for the f-L estimation problem. Fazlyab et al. (2019) provided several variants of LipSDP to balance the
5

---

precision and scalability, PauiliittylPiiiiiiie et al. (2022) demonstrated that the most precise version of LipSDP, LipSDP-Nor LipsDP-Network, -Newwrkk fails produce an upper bound for 22-FGL. this paper. all the references of LipSDP are to LipSDD- LipSDP appears quite different from Equation (7), we show that LipSDP is dual of Equation to estimate the 22FFLL on two-layer networks. LipSDP for two-layer networks is:
the less precise version. Surprisingly, even though the approach in
min {vE: (- G.A
2abWT <Tm (a bJW
(a+b)WTT) -27 + 0, 20,
where T' = dA) for À E R4; and b are the lower and upper bounds of the activation's derivative.
We will construct a new quadratic program, which we show is equivalent to Equation 4 when 2. and LipSDP is its dual SDP relaxation.
Let the input of the i-th activation node on (vag(v) be yrs and wT be the row vector of W. Hence, y/ w,a. Let Ar Rm be perturbation on z, so Ay: w,Ax. Let Ao(y) R" denote the induced perturbation on diag(y). The constraint from the activation function is An(yl: E [a, 6). in Ay.
other words, Ar(y):
E [a, b). One can write the range constraint
w;Az
(Ao(y); - a (Ao - b w;Ar) S O.
This can be written in the quadratic form:
W Ae
2ab bbb)
W;Ar ) 2 0, Ao(ly)))
Ao(
a +
-2
Vi E [m]].
(8)
Since for the two layer network, [xx un (y), then Aʃ(x) = uA) The objective for 22L (uAa())) The equivalence between this program and Equation estimation is max (w) V (Ar)*
when q 2 is presented in the appendix.
Remark 4.1. Another interpretation for the quadratic program is that we want quantify how the output changes given a data-independent input change. i.e., Ar. In other words, we want to analyze the effect of Ar propagating from the input to the output, with symbolic values rather than actual inputs. The idea is similar to symbolic execution from program analysis (Baldoni et al. 2018).
Duality to LipSDP. Now we will show that LipSDP is the dual SDP to the program formulated above. The dual SDP derivation is of similar form in Ben- Tal and Nemirovski 2001 Ch.4.3.1). Let us introduce variable ( such that < (u
(Az)* 0. In other words,
((Ar)² (w) O.
For each constraint in Equation with A; then
8 let us introduce a dual variable A; 2 0. Multiply each constraint Ar
Ar
(
-22bb we
(a b)).,
(
(AOw)))
(a + b)
-2h
Ao(1)))
2 0,
Vi E [n].
Ax Ao
WT (a+ b)TW
(a (a+b)WTT)) -2T
Ax Ao(y)
Sum all of them, then we have
2 0, where
diag(A) ()) is the n diagonal matrix dual variables AI,...,An
Ar
[T (00
0 -uTw
(Ar
Az Ao(w))
)
Equation (9) can be rewritten as:
2 0. As a result, the dual
program for the new optimization program
min {VS: C.A
--2abTTWT WT {lm (a b)TW
(a (a+b)WTTT) -2T - = 0, A₁ 2 0).
Remark 4.2. In Remark 3.5
we mention that / is the optimal approximation ratio for the do + mixed-norm problem, which matches the approximation ratio in Theorem 3.4 Hence, improving the natural SDP relaxation in Equation 7 can very hard. The duality provides another evidence of HioSDP-Neurony 's correctness, and hints that LipSDP-Netwer the improved variant, may be wrong.

---

4x -FLL estimation for multi-layer networks
For multi-layer neural network, the formal gradient becomes high-degree polynomial, and its no-morm estimation becomes a high-degree polynomial optimization problem over cube, which is in general hard problem (Lasserre) 2015). We provide discussion of the polynomial optimization approach of FGL. estimation in the appendix. Here we provide an SDP dual program the loc -FL estimation inspired by the dual SDP approach in Section The difference is that now consider Loo ex-pperturattion to the input space instead of f2. Hence, the objective becomes
|v)o(v)]
max Az,Ag(y)
||
we add an extra constraint
|| = 1, the above objective becomes
1
max Ar,
(uAr(y) + uAo(y))
(10)
2
The constraints are
T Ao(y)) )
w;Ar
2ab
-(a+ + b)
(a
w;
20, A(x) & 1, Vi [n].] e [m].
(a +bb
2
Ao(y))
T
We can write A(x)) <
1
1
-1
0
Azz 2 0.
Ar./
0
Now let us introduce n + m non-negative dual variables (r, A), where E RT and RT we multiply each dual variable with the constraint and add all the constraints together, will have
T
1==1
Tz (a + b)
Ar (v(
0
-2ab 2abW-WT, Ti (a DJ -27,
Ar
20,
Ao
where Ti diag(7) and T2 diag(A) ()). As result, and obtain the dual SDP for the -FLL estimation:
incorporate the objective Equation (10)
j= Jj
m
0
u
min (5 C,A.T (2
0
2abbW T1 (a + bb (a + 6)
20.A,,T, (11)
u
-Th
Remark 5.1. The SDP programs in Section B are strictly feasible because the identity matrix is positive definite solution. Hence, Slater's condition is satisfied and strong duality holds.
can simply extend the dual program to multiple-layer networks. We first vectorize all the units in the input layer and hidden layers, and then constrain them using layer-wist inequalities to formulate an optimization problem. Let us consider a general d-layer multi-layer network, where W I xn; for i [d - 1], and W' perturbation on the input layer, Az' be the perturbation on the i-th hidden layer, and w be the j-th
Multi-layer extension.
E 1xn,, Let Ar denote the
row vector of W The only difference between two layer networks and multi-layer networks is that we have the additional constraints:
2ab(u)t1))Tun (a ()wb)
(a (a=b)(uft))) -2
Az Aeftt]
A
2 0.
Let A; E R and T; = diag(A;) for i E [d]. Following the similar SDP dual approach, we can add all the constraints together and formulate the following SDP program:
min 1 C.A.
12 (L+ 0, 2, (d]
(12)
where
0
0
2ab(W:)T
(a + b)(W))TT
0
0
L
0
(a + b1
21h 2ab(W2 W W
0
(a bYT.Wd-1
-2Ta
(13)

---

Table I:
FGL estimation of various methods: DGeoLIP and NGeoLIP induce the same values on two layer networks. DGeoLIP always produces tighter estimations than LiPopt and MP do.
Network
DGeoLIP
NGeoLIP
LiPopt
MP
Sample
BruF
2- 2-layer/16 6 units
185.18
185.18 425.04
259.44
578.54
175.24
175.24
2- 2-layer/256 units
425.04
1011.65
2697.38
306.98
N/A
8- 8-layer/64 units per layer
8327.2
N/A
8.237 10"
1130.6
N/A
Table 2: Running time (in seconds) of various tools on lo -GLL estimation: DGeoLIP and NGeoLIP are faster than LiPopt. Notice that the running time is implementation and deteedede
Network
DGeoLIP
NGeoLIP
LiPopt
BruF
2- layer//6 units
28.1
22.3
1572
4.8
2- 1ayer/256 units
976.0
70.9
2690
N/A
8-layer/64 units
329.5
N/A
N/A
E A1k -
5
u
T
0
N
Remark 5.2. If we expand the matrix inequality derived from the compact neural-network repre- sentation in Fazlyab et al. (2019) Theorem 2), we will have exactly the same matrix for network constraints as (Equation (13) the dual program formulation. In other words, we provide compositional optimization interpretation to the compact neural-network representation in LipSDP. With this interpretation, one can extend the SDP to beyond feed-forward structures. such skip connections (He et al. (2016). Notice that if we apply the similar reasoning to the multi-layer network f f2-FGL estimation, we will obtain LipSDP-Neuron.
Evaluation and discussion
The primary goal of our work is to provide theoretical framework, and also algorithms for t estimations on practically used networks. The FGI can be computed using LipSDP. We have implemented the algorithms using MATLAB (MATLAB 2021). the CVX toolbox (CVX Research 2020) and MOSEK solver (ApS) 2019), and name the tool GeoLIP. To validate our theory and the applicability of our algorithms, we want to empirically answer the following research questions:
RQI: Is GeoLIP better than existing methods in terms of precision and scalability?
RQ2: Are the dual SDP programs devised throughout the paper valid?
As we shall see, GeoLIP is indeed better than existing methods in terms of precision and scalability; and the dual SDP programs produce the same values as their natural-SDP-rrlaaxin counterparts.
6.1 Experimental design
To answer RQ1, we will run GeoLIP and existing tools that measure the foc -FGL on various feed- forward neural networks trained with the MNIST dataset (LeCun and Cortes 2010). We will record the computed & -GL to compare the precision, and the computation time to compare the scalability.
To answer RQ2, we will run the natural SDP relaxations for F,- estimations proposed in Section 3 LipSDP for F2I estimation, and the dual program Equation [1] for fos -FGI. on two-layer neural networks, and compare their computed FGLs.

---

Measurements. Our main baseline tool is LiPopt (Latorre et al. 2020). which is an lxx -GL estimation tool D Notice that LiPopt is based on the Python Gurobi solver (Gurobi Optimization. LLC 2022), while we use the MATLAB CVX and MOSEK solver. LiPopt relies on linear programming (LP) hierarchy for the polynomial optimization problem. We use LiPopt-k to denote the k-th degree of the LP hierarchy. BruF stands for an brute-force exhaustive enumeration of all possible activation search, patterns. This is the ground truth for FGL estimations. However, this is an exponential- so we can only run it on networks with a few hidden units. Sample means that we randomly sample 200, 000 points in the input space and compute the gradient norm at those points. Notice that this is a lower bound of the true Lipschitz constant, and thus a lower bound of the FGL. MP stands for the weight- matrix-norm- norm- produpr method. This is a naive upper bound of FGL. We use NGeoLIP to denote the natural SDP relaxations devised in Section B and DGeoLIP to denote the dual SDP Equation (12) for &o -FGI. estimation. Notice that NGeoL.IP only applies to two-layer networks.
We use "_" in the result tables to denote that the experimental setting is not in the scope of the tool's application, and "N/A" to denote the computation takes too much time (> 20 hours).
Network setting. We run the experiments on fulny-connected feed-forward neural networks, trained with the MNIST dataset for 10 epochs using the ADAM optimizer (Kingma and Ba (015). All the trained networks have accuracy greater than 92% on the test data. For two-layer networks, we use 8, 16, 64, 128, 256 hidden nodes. For multiple-layer networks, we consider 3, 7, 8-layer networks, and each hidden layer has 64 ReLU units. Because MNIST has 10 classes, we report the estimated FGL with respect to label 8 as in Latorre et al. (2020), and the average running time per class: we record the total computation time for all 10 classes from each tool, and report the average time per class.
6.2 Discussion
We present selected results in Tables D and 2] and related major discussions here. The full results, more experimental setup and additional discussions can be found in the appendix.
RQ1. In the experiments of LiPopt, we only used LiPopt-2. In theory, if one can go higher in the LP hierarchy in LiPopt, the result becomes more precise. However, in the case of fully- fully-connected neural networks, using degree-3 in LiPopt is already impractical. For example, on the simplest network that we used, i.e., the single-hiddeen-lyer neural network with 8 hidden units, using LiPopt-3, one lox- -GL computation needs least 200 hours projected by LiPopt. As result, for all the LiPopt-related experiments, we were only able to run LiPopt-2. Latoree et al. (2020) pointed out, the degree has have to
to be at least the depth of the network to compute valid bound, for k-layer networks. LiPopt is unable to handle neural networks with more than two layers because this requires LiPopt with degrees beyond 2. Even if we only consider LiPopt-2 on two-layer networks, the running time is still much higher compared to GeoLIP. This demonstrates the great advantage of GeoLIP in terms of scalability compared with LiPopt. we compare LiPopt-2 with GeoLIP on two-layer networks from Table I it is clear that GeoLIP produces more precise results. For networks with depth greater than 2. we can only compare GeoLIP with the matrix-norm- coom-product method. As we can see from all experiments, GeoL.IP's estimation on the FGL is always much lower than MP.
least LiPopt-k
We have also shown that the two-layer network -GL estimation from GeoLIP has theoretical guarantee with the approximation factor KG < 1.783 (Theorem (.3).. If we compare the two-layer network results from GeoLIP and Sampling in Table [ which lower bound of true Lipschitz constant, the ratio is within 1.783. This validates our theoretical claim.
RQ2. In Section 4 we have demonstrated the duality between NGeoLIP and LipSDP for the f2L estimation on two-layer networks, even though the approaches appear drastically different. The experiments show that on two-layer networks, LipSDP and NGeoLIP for f2LF estimations (in the appendix), and DIeoLIP and NG for foe -FL estimations produce the same values. These results empirically validate the duality arguments, and also all the related SDP programs.
SDP relaxation. Applying SDP on intractable combinatorial optimization problem was pioneered by the seminal Goemans- Williamson algorithm for the Max-Cur problem (Goemans and Williamson 1995). For two-layer networks, we have reduced the FGL estimation to the mixed-norm problem, and
2 Another method was proposed by Chen et al. 2020), however, the code is not available and we are not able compare it with GeoLIP.

---

provide approximation algorithms with ratios compatible with the known optimal constants in the corresponding mixed-norm problems. Improving them can be a very hard task. We also provide compositional SDP interpretation of LipSDP-Neurre flaw in LipSDP-Network, our compositional SDP interpretation shows that LipSDP-Neurr
Although Pauli et al. (2022) demonstrated the
correct. In fact, from the compositional SDP interpretation, the program is only constrained by the underlying perturbation geometry and the layer-wise restriction from each hidden unit, so the constraints and objective exactly encode the FGL-estimation problem without additional assumptions. Because often the SDP relaxation for intractable problems gives the optimal known algorithms, we conjecture that GeoLIP and LipSDP are also hard to improve FGL estimations.
Latorre et al. 2020) used polynomial optimization to address the -FLL estimation. We argue that approaching FGL esttmmtitts from the perspective of polynomial optimization loses the accurate characterization of this problem. For example, for two-layer networks, we have provided constant approximation algorithms to estimate FGL.s in both &oo and &2 cases. However, for a general polynomial optimization problem on a cube, we cannot achieve constant approximation. For example, polynomial optimization problem over
the maximum independent set of a graph can be encoded cube (Motzkin and Straus 1965). but the maximum independent set problem cannot be approximated within a constant factor in polynomial time unless P P= NP (Trevisan) 2004).
7 Related work
Chen al. (2200) employed polynomial optimization compute the true Lipschitz constant of
ReLU-networks for Lo -errturrbations and used Lasserre's s hierarchy of SDPs (Lasserre) [200I) to solve the polynomial optimization problem. However, their approach highly tailored to ReLU networks, while ours, like LipSDP, can handle common activations, such as sigmoid and ELU.
Latorre et al. (2020) also proposed estimating this quantity is not the problem studied in our work, and there are tools specifically designed for local perturbations and the Lipschitz constant (Laurel et al. 2022 Zhang et al. 2019).
LiPopt estimate the local Lipschitz constant. However,
Lipschitz regularization of neural networks is an important task, and recent works (Aziznejad et al. 2020; Bungeert et al. [ Gouk et al. [ Krishnan et al.] 2020 Terjek] 2020) have investigated this problem. However, here we study a related but different problem, i.c., Lipschitzness measurement of neural networks. Our work can motivate new Lipschitz regularization techniques.
Conclusion
In this work, we have provided a quantitative geometric framework for FGL estimations, and also algorithms for the -FGL estimation. One important lesson is that when transferring techniques from one perturbations to another ones, we should also transfer the underlying geometry. One future work is to train smooth neural networks using the SDPs proposed in this paper.
Acknowledgments and Disclosure of Funding
The authors thank Vijay Bhattiprolu for introducing recent progress on the mixed-norm problems. The work is partially supported by Air Force Grant FA9550-18-185 (NSF) Grants CCF-FMinF-1836
the National Science Foundation 110otiers-1804648,, 804648, CCF-2046710 10 and CCF-1652140, and ARO grant number W91 17-1-77-- Zi Wang and Somesh Jha are partially supported by the DARPN-GARD problem under agreement number 885000.
IIS-2008559, SaTTC-Frontirs-I
References
Aws Albarghouthi. 2021. Introduction to Neural Network Verification. arXiv:2109.1031 [cs.LG]
Noga Alon and Assaf Naor. 2004. Approximating the Cut-Norm via Grothendieck's Inequality. In Proceedings of the Thirty-Sixth Annual ACM Symposium Theory of Computing (Chicago, II., USA) (STOC '04). Association for Computing Machinery, New York, NY, USA, 72-80.
btttps///oo org/ 101.5/1107755...00777
10

---

MOSEK ApS. 2019. The MOSEK optimization toolbox for MATLAB manual. Version 9.0. http: //docs mosek. wwtpkk.cc.....om 0omm99.0/toolbboxinddzz. html
Shayan Aziznejad, Harshit Gupta, Joaquim Campos, and Michael Unser. 2020. Deep Neural Networks With Trainable Activations and Controlled Lipschitz Constant. IEEE TRANSACTIONS ON SIGNAL PROCESSING 68 (2020), 4688-4699 lattps://doi.
1109 100//TTPPPPPP 2020 3014611
Roberto Baldoni, Emilio Coppa, Daniele Cono D'Elia, Camil Demetrescu, and Irene Finocchi. 2018. A Survey of Symbolic Execution Techniques. ACM Comput. Surv. 51, 3, Article 50 (2018).
Aharon Ben-Tal and Arkadi Nemirovski. 2001. Lectures on Modern Convex Optimization. Soci-
ety for Industrial and Applied Mathematics. https://doi. org 10. arXiv:https:/eepubs.o
http::///ppps......oo///oo//l//e siam.orgg/oo///d//1...// aaXivhhtps.eepubsss...ooodoodd
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani. 2018. Inapproximability of Matrix p->q Norms. Electron. Colloquiium Comput. Complex. 25 ()
Vijay Bhattiprolu, Euiwoong Lee, and Madhur Tulsiani. 2022. Separating the NP-Hardness of the Grothendieck Problem from the citte-Grotthndieckk Problem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Leibniz International Proceedings in Informatics (LIPlcs), Vol. 215), Mark Braverman (Ed.). Schloss Dagstuhl Leitniz-Zentrum für Informatik, Dagstuhl, Germany, 22:1-22:17
attps://doi org. 10. 4230/LIPIcs. ITCS 2022. 22
Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. 2011. The Grothendieck Constant is Strictly Smaller than Krivine's Bound. In 201/ IEEE 52nd Annual Symposium on Foundations of Computer Science. 462-462. attps://ddi..or/10... 1109//F..0..F.F.
2011.77
Jop Briët, Oded Regev, and Rishi Saket. 2017. Tight Hardness of the Non-Commutative Grothendieck 4086
Problem. Theory of Computing 13, 15 (2017), 1-24. https://dbi.orr/// /08.://////...0/////////
0000//0...... toc 2017
v013a015
Sebastien Bubeck and Mark Sellke. 2021. A Universal Law of Robustness via Isoperimetry. In Advances in Neural Information Processing Systems, A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (Eds.). bettps://openrervv/ htt.:/aawwr.ii.oooooooooooooeaa. wtt..//oooorriidd1100s///2/
Leon Bungert, René Raab, Tim Roith, Leo Schwinn, and Daniel Tenbrinck. 2021. CLIP: Cheap Lipschitz Training of Neural Networks. In Scale Space and Variational Methods in Computer Vision, Abderrahim Elmoataz, Jalal Fadili, Yvain Quéau, Julien Rabin, and Loic Simon (Eds.). Springer International Publishing, Cham, 307-319.
Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. 2020. Semialgebraic Optimiza- tion for Lipschitz Constants of ReLU Networks. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., (assaa225033323444c0022222222 Paper pdf
https: http:::://///een///// neur httpppps..cpppppp/////////
Ajnrk-Aréé Clevert Thomas Unterthiner, and Sepp Hochreiter. 2016. Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUss. In 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). http://arxivv org/ Ptrggabe/1555 ats//ab1..022222 07289
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. 2019. Certified Adversarial Robustness via Ran- domized Smoothing. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhut- dinov (Eds.). PMLR, 1310-1320.
mlr, www.s/p9esssooe/e h1197//cohe19.... html
Inc. CVX Research, 2020. CVX: Software for Disciplined Convex Programming, Version 2.2, Build 1148. http:// c/vpr com/ cvx

---

Mahyar Fazlyab. Alexander Robey, Hamed Hassani, Manfred Morari. and George Pappas. 2019. Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, E. Fox, and Garnett (Eds.), Vol. 32. Curran Associates, Inc. https://proceeddggg pdf
neurips. cc/cccppapoo/... hcc/paper/2111 /eleelelliee (00.
Michel X.
Goemans and David P. Williamson. 1995. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. ACM 42, 6 (nov https://doi. org/ 10. 1.0.1144 /111//276//111111 227684
1995), 1115-1145.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining and Harnessing Adversarial Examples. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). attp://aariin wwg/ab/////ooooooooe/gg.oo..aeat 1472
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree. 2021. Regularisation of Neural Networks by Enforcing Lipschitz Continuity. Mach. Learn. 110. (feb 2021), 393-416.
https::/doi.org// 10. 1007
020-00999--0
A. Grothendieck. 1956. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo 8, 1-79 (1956)..
Gurobi Optimization, LLC. 2022. Gurobi Optimizer Reference Manual. htttps://ww.. com
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 770-778.
http://0...rr/110.110/////.. 001.09//VVR.2216..00
Matthias Hein and Maksym Andriushchenko. 2017. Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation. In Proceedings of the 31 International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS' I7). Curran Associates Inc., Red Hook, NY, USA, 2263-2273.
Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. 2021. Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds. In Thirty-Fifihh Con- ference on Neural Information Processing Systems.
FTE28RYJ5PC
Matt Jordan and Alexandros G Dimakis. 2020. Exactly Computing the Local Lipschitz Constant of ReLU Networks. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 7344-7353. huttps://proceedinngg wtwprocceddnngs..erri...... nwwrine.rccccccooo http://i....oarps...o.ppp/////pp wttpppaap/p//22///11eeee/
pdf
Guy Katz, Clark Barrett, David I.. Dill, Kyle Julian, and Mykel J. Kochenderfer. 2017. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. Computer Aided Verification, Rupak Majumdar and Viktor Kunčak (Eds.). Springer International Publishing, Cham, 97-117.
Subhash Khot. 2002. On the Power of Unique 2-Prover 1-Round Games. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing (Montreal, Quebec, Canada) (STOC '02). Association for Computing Machinery, New York, NY, USA, 767-775. https
7doo. otwpi..rg/11... 1145 5505550999077000177
Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). http
/ //arxiv.. org/ /abb/ 6980
Vishaal Krishnan, Abed AlRahman AI Makdah, and Fabio Pasqualetti. 2020. Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing. In Proceedings of the 34th International Conference on Neural Information Processing Systems (Vancouver, BC, Canada) (NIPS'20). Curran Associates Inc., Red Hook, NY, USA, Article 917, 12 pages.
12

---

J.L. Krivine. 1979. Constantes de Grothendieck et fonctions de type positif sur les sphères. Advances in Mathematics 31, 1 (1979), 16-30. https://doi.org// (1000000000000000000177770000110
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2017. ImageNet Classification with
Deep Convolutional Neural Networks. Commun, ACM 60, (may 2017), 84-90. https
//doi. otgeii.rg11... 1000001115/336688
Jean B. Lasserre. 2001.
Global Optimization with Polynomials and the Problem of Mo- ments. SIAM Journal on Optimization 11,3 3 (2001), 796-817. https://doi.org/ ott.doi..rrg/..111.77..
$1052623400366802 ar wtw..ittps///doi.or//.......1 httpp////.....111111000200000000
Jean Bernard Lasserre. 2015. An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press. https: org/ 10. 1017 1017/0809781100447228
Fabian Latorre, Paul Rolland, and Volkan Cevher. 2020. Lipschitz constant estimation of Neural Networks via sparse polynomial optimization. In International Conference on Learning Represen- wttp://www.ttoooummmooooeeoe - Je4 xSFDB
tations.
Jacob Laurel, Rem Yang, Gagandeep Singh, and Sasa Misailovic. 2022. for Static Analysis of Clarke Jacobians. Proc. ACM Program. Lang. 6, POPL, Article 56 (jan 2022), 30 pages. lttps://doi.org//
Dual Number Abstraction
1144/34997118
Yann LeCun and Corinna Cortes. 2010.
MNIST handwritten digit database.
(2010). http: /ttt://yaan. /ann lecun. wwt.eccoo/eeieeeeee com/exdb/mmist.
Klas Leino, Zifan Wang, and Matt Fredrikson. 2021. Globally-Robust Neural Networks. In Interna-
tional Conference on Machine Learning (ICML).
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, 2018. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations. httpp:://openrevieu
http:/arwweeeeeeeeeeoooorrn/aaa. net/fforumidd=:22IBBZZ
MATLAB. 2021. 9.1 1.0. 1837725 (b202/b) Update 2. The Math Works Inc., Natick, Massachusetts.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado. and Jeffrey Dean. 2013. Distributed Representations of Words and Phrases and Their Compositionality. Proceedings of the 26th International Conference Neural Information Processing Systems Volume (Lake Tahoe, Nevada) (NIPS' 13). Curran Associates Inc., Red Hook, NY, USA, 3111-3119.
T. S. Motzkin and E. G. Straus. 1965. Maxima for Graphs and New Proof of a Theorem of Turán. Canadian Journal of Mathematics 17 (1965), 533-540. CJM-1965-
https://doi. hwl.ddi.orrggoo org/ 10. 4153/
Vinod Nair and Geoffrey E. Hinton. 2010. Rectified Linear Units Improve Restricted Boltzmann Machines. In Proceedings of the 27th International Conference on International Conference on Machine Learning (Haifa, Israel) (ICMI.' 10). Omnipress, Madison, WI, USA, 807-814.
Assaf Naor. 2013. Quantitative geometry.
Proceedings of the National Academy of Sci- 10r./10.1073/paas 1320388110
ences 110, 48 (2013), 19202-19205. http:://wwwwwp.ooaoooo/////////a
Yu Nesterov. 1998. Semidefinite relaxation and nonconvex quadratic optimization. Optimiiatiiin Meth-
ods and Software 9, 1-3 (1998), 141-160. httpps://dii. http://ooo..rr////// org//0.. http://..11000155551111 1000/055579988805000 /rtpt:/ss////oi.o//////o// org/ 10. 11000///0557799990005050000
arXiv.https://doi.org
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredríkson, Z. Berkay Celik, and Ananthram Swami. 2016. The Limitations of Deep Learning in Adversarial Settings. 2016 IEEE Euro-
pean Symposium on Security and Privacy (EuroS& P). 377-387. https://doi. www.o0..11111
EuroSP 2016.0266 36
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. 2022. Training Robust Neural Networks Using Lipschitz Bounds. IEEE Control Systems Letters 6 (2022), 121-126.
httpss:/doi.. org/ 1109/LCSYs 2021. 3050444
13

---

Prasad Raghavendra and David Steurer. 2009. Towards Computing the Grothendieck Constant. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (New York, New York) (SODA '09). Society for Industrial and Applied Mathematics, USA, 525-534.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. 2018. Certified Defenses against Adversarial Examples. In International Conference on Learning Representations. htttps://openreveer
net/forrum?dd-Bys4aa Rb
Kevin Scaman and Aladin Virmaux. 2018. Lipschitz. Regularity of Deep Neural Networks: Analysis and Efficient Estimation. In Proceedings of the 32nd International Conference on Neural Informa- tion Processing Systems (Montréal, Canada) (NIPS' 18). Curran Associates Inc., Red Hook, NY, USA, 3839-3848.
Christian Szegedy, Wojciech Zaremba. Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014. Intriguing properties neural networks. In 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). http: //rxiv//xxxvvv/// wwgg//b///aa 6199
Dávid Terjék. 2020.
Adversarial Lipschitz Regularization. In International Conference Learning Representations. hattps://peenreviee..n www.://wwnttttooonddddddiedee httpss//ppaareereee..e//ooorrddo DDrrtD
Luca Trevisan. 2004. arXiv:cs/0409043 [cs.CC]
Inapproximability of Combinatorial Optimization
Problems.
Zi Wang, Aws Albarghouthi, Gautam Prakriya, and Somesh Jha. 2022. Interval Universal Approxi- mation for Neural Networks. Proc. ACM Program. Lang. 6, POPL, Article 14 (jan 2022), 29 pages.
https://doi. org/ 10. 1145/3498675
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh. 2019. RecurJac: An Efficient Recursive Algorithm for Bounding Jacobian Matrix of Neural Networks and Its Applications. Proceedings of the AAAI Conference on Artificial Intelligence 33, 01 (Jul. 2019), 5757-5764. https:://da
org 10. w1009//aaaa.. v33101. 33015757
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] Our main claims in the abstract and introduction accurately reflect the paper's contributions and scope. In particular, we listed our con- tributions in Section section in the paper.
| and forward referenced each contribution to the corresponding
(b) Did you describe the limitations your work? [Yes] We clearly defined what the quantity to measure and what the network is in Section 2 and what the assumptions are for each theorem in Section 3
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discussed them in the appendix.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read the ethics review guidelines. Because our work is to measure the smoothness of neural networks (see Sections I [) and we only used the standard MNIST dataset (see Section 6.1 the paper conforms guidelines.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We clearly defined the quantity to measure and the network structures in Sections 2 to
(b) Did you include complete proofs of all theoretical results? [Ys]] We provided important intuition and ideas the main paper (see Sections to 5) and included complete proofs in the appendix.
3. If you experiments...
14

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We included the code, data, and instructions as URI..
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We included major experimental setting in Section 6.1 and detailed specification in the appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [N/A] Our experiments are deterministic. Given neural network, our algorithm always returns the same result.
(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] This provided in the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] In terms of dataset, only used the standard MNIST, and cited the creators. All the tools used in the paper were properly cited. See Section 6. and the appendix.
(b) Did you mention the license of the assets? [Yes] See the appendix.
(c) Did you include any assets either in the supplemental material or as URL? [Yes] We included our code as a URL.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "oZ9eIBt2EKX", "reviewer": "Reviewer_YiVe", "summary": "In this paper the authors propose a new tool to estimate an upper bound on the Lipschitz constant of ReLU based feed forward networks. They focus on Lipschitz constant for L-infinity norms and L2 norms. The computation of the upper bound is based on SDP relaxations of the original problem, a standard approach of the literature. \n\nFor L-infinity, as said by the authors, they \"provide a rigorous derivation and simpler formulation, and also a sound theoretical analysis of the bound, which illustrate more insights to this problem\" compared to the work of Raghunathan et al. (2018). Whereas for for L2-bounds they \" show that LipSDP is dual of Equation (7) to estimate the ℓ2-FGL on two-layer networks\".\n\nFinally the release a software, GeoLip, that implements the SDP of interest for multil-layers neural networks (for l-infinity) and 2-layers neural networks (for l2). Not only the upper bound is improved compared to concurrent methods, but it is even cloaser to the lower bound obtained by sample or brute force by a small factor, even on deep networks. Moreover the running time is competitive even on those deep networks.", "questions": "l 125 : \"However, the algorithms presented in this work can be adapted with minor adjustments to other common activation functions.\"\nDoes it also work with non elementwise activation functions ? In this case the diag(y) is no longer diagonal. Is it a simple way to adapt the method to arbitrary diag(y) ?\n\nFrom my limited understanding of the topic, I have two more naive (related) questions.\n\n* For multi-layers ( i.e > 2) neural networks , do you have any theoretical guarantees like the ones of theorems 3.3 and 3.4 ?\n* experiments on l2 norms for multi-layers neural networks are lacking. Is it because the duality result of section 4.1 does not extend further than the case of two-layers networks ?", "limitations": "Every result is clearly stated along with its hypothesis. The only part that could be subject to caution is the the running time of their solver, which might unfairly benefit from better software than other SDP based relaxations of literature, as acknowledged by the authors: \"Notice that the running time is implementation and solver-dependent\".", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper makes a clear theoretial contribution by posing rigorously posing the problem. The link the Grothendieck inequality is very interesting and establish a clear bound toward algorithms must tend. The link between dual formulation (7) and previous work LipSDP \nis interesting. Claims in all theorems 3.2 3.3 and 3.4 seem to be significant contributions.\n\nThe SDP are clearly specified which allows independent implementation, and easier reproducibility. \n\nThe speed and quality of the bounds of GeoLip software, whose code is made public, is very convincing and is validating theoretical claims.\n\nThe paper is well written, I learned a lot about this topic with which I am unfamiliar.\n\nWeaknesses:\n\nfor reader unfamiliar with the topic some notations are a bit harsh: it took me some time to understand the motivation behind the definition of two-layers networks (l 135) : no bias since it does not play any role in computation of the upper bound (only in the pattern of activations between true Lipschitz constant and the FGL). diag(y) the pattern of activations, and u the weight of the last layer (with the NN seen as a function from R^n to R)\n\nminor/typo: a parenthesis is lacking in equation (2)\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": "UEd1w89AlHM", "reviewer": "Reviewer_TC4r", "summary": "The article tackle the estimation of the Lipschitz constant of a neural network for norms $p \\in \\{ 2, \\infty \\}$. The authors rely on previously existing SDP techniques and propose new formulations that give new theoretical insights on Lipschitz estimations.\nIndeed, the authors bound the approximation of the polynomial SDP relaxation, and provide formulation for norms $2$ and $\\infty$.\nThe theory is developed for NN with one hidden layer and then extend to the general case, giving a new algorithm called GeoLip.\nFinally, the paper provide experimental results that shows that GeoLip outperforms in accuracy and time previous state of the art methods on multi-layers straightforward neural networks.", "questions": "Where does the name 'GeoLIP' comes from?\n\nIn the experimental section, are NGeoLIP results taking into account the approximation bound in order to be upper-bounds?\n\nIt would be interesting to show an example in which NGeoLIP and DGeoLIP give different bounds in order to better assess the advantage of using a (fast) approximation algorithm.\n\nWould it be possible to extend the current approach to \"much bigger\" feed-forward network such as CNN or residual nets? It seems it is a difficult question as is, but would specific SDP solving strategies exploit the characteristics of these operations instead of their matrix form (which would make it intractable)?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clear, well written and properly motivated. The other approach in the literature are well discussed and the paper is honest at comparing itself. Overall, I really enjoyed reading this paper.\n\nIn all generality, the dual of $\\ell^\\infty$ is ill-defined (l120) and requires some more hypothesis, even though it does not matter here.\n\nl131:\n    In the problem description describe what is $y$ (one line it is $\\sigma$, the next one it is $\\sigma'$ if I get it) and explain the simplification made from the definition of neural network above (no bias).\n    Use notations defined before, what is y here?\n    Could we write f(x) = W2 sigma (W1 x), which would then reduce to eq(4) directly thanks to eq(3), while preserving the notations introduced before.\nl147: ref for the majoration of $K_G$ and its link to eq (5).\n\n\n* Conventions\n\nGlobally, why upper indices? In the paper it seems that lower indices should be enough and this would make the paper even clearer.\n\n* Typos:\n    - l92: \"X [is] positive semidefinite\";\n    - l88,92,146: Sentences beginning with a symbol;\n    - l103: no diag in the equation;\n    - l109: almost everywhere (no parenthesis);\n    - l112: say.\n\nCheck the end of sentences in particular after formulas as the punctuation is very often missing or incorrect (e.g. sentence finishing with a ','). In particular in the Appendix where the punctuation is chaotic.\n\nReferences: many references are incomplete (lacks conference/journal)", "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": "3qDyjcn06tx", "reviewer": "Reviewer_xMmc", "summary": "This paper proposed a new method for estimating the Lipschitz constant (more specifically, the ($\\ell^p$-) Formal Global Lipschitz (FGL) constant) of DNNs.\nFirst, this paper analyzed two-layer ReLU-DNNs and showed that $\\ell^{\\infty}$-FGL estimation is MAXSNP-hard (Theorem 3.2). Then, by relaxing the FGL-estimation problem and reducing it to SDP, this paper derived a polynomial algorithm with an approximation ratio $K_G$ (Theorem 3.3) for general $p=\\infty$ and $\\sqrt{\\frac{\\pi}{2}}$ for $p=2$ (Theorem 3.4).\nNext, the $\\ell^p$-FGL estimation problem of two-layer NNs was formulated as the maximization of perturbation of intermediate units with respect to that of the input. Then, this paper showed that this formulation is equivalent to the first formulation (l.211) and is dual to LipSDP (l.212--220) when $p=2$. In addition, this paper extended it to multi-layer NNs.\nFinally, this paper evaluated the proposed method numerically and claimed that the proposed method performed tighter estimation than existing methods for the $\\ell^{\\infty}$-estimation problem of two-layer and multi-layer DNNs.", "questions": "- l.103: $f_i(x)=W^i\\mathrm{diag}(\\sigma(f_{i-1}(x))) + b_i$ → I think $\\mathrm{diag}$ is not needed here.\n- l.107: We do not usually use $\\prod$ for matrix multiplications, which are non-commutative.\n- l.160: Although we can understand the meaning of the term \"approximation ratio\" intuitively, I would suggest writing its mathematical definition explicitly since it is used in mathematical statements.\n- l.169 (7): $A\\cdot B$ is undefined.\n- l.209: $f(x) = u\\sigma(x)$ → $f(x) = u\\sigma(Wx)$ ?\n- l.563: I was not aware that $x$ in l.138 takes value in {-1, 1}^n. I suggest writing the range of $x$ more explicitly. I think l.563 does not hold in general (at least without any assumption). We should have:\n\n\\max_{x\\in \\{-1, 1\\}^n} \\|Ax\\|_{1} = \\max_{x\\in \\{-1, 1\\}^n, , y\\in \\mathbb{R}^m, \\|y\\|_{\\infty}=1} \\langle Ax, y\\rangle\n\nSo, I am wondering why we can restrict the range of $y$ to {-1, 1}^{m}", "limitations": "As far as I have checked, this paper did not discuss the proposed methods' limitations. However, the proposed method (1) only applies to ReLU-DNNs and (2) has no theoretical guarantees for multi-layer NNs. Therefore, it is desirable to discuss such limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- NGeoLip proposed in this paper has theoretical guarantees for the FGL-estimation problem of two-layer NNs.\n- DGeoLIP proposed in this paper applies to multi-layer NNs, while competitive methods are limited to two-layer NNs.\n- SDP allows a unified approach to $\\ell^2$-FGL and $\\ell^\\infty$-FGL.\n\nWeaknesses\n\n- This paper is intended to apply the Lipshitz constant estimation to mitigate the vulnerability against adversarial attacks. However, this paper did not experimentally evaluate the effectiveness of the proposed methods in adversarial attacks.\n- There is room for discussion on whether the proposed method sufficiently demonstrates its effectiveness (either theoretically or empirically) to the estimation problem in the multi-layer settings.\n- There is room for improvements in the organization of the paper (see Clarity section).\n\n\nOriginality（Novelty）\n\n- As this paper mentioned, existing literature employed the idea of reducing the Lipschitz constant estimation problem to SDP (l.55). However, this paper adopted this idea differently and proposed different algorithms.\n- The authors claimed their work is guided by the principle that we should separate geometry-dependent and independent components. The authors think that this is a crucial idea underlying this paper. However, it was not clear to me how this principle works. For example, in Sections 3.1 and 3.2, $\\ell^\\infty$-FGL and $\\ell^2$-FGL were first reduced to the mixed-norm problem and then were analyzed separately. In this example, is it correct to understand that the reduction to the mixed-norm problem is the geometrically-independent part? I suggest the authors write how they applied this principle to actual algorithms. \n\n\nQuality（Soundness）\n\n- As far as I have checked, the mathematical statements and proofs are correct all in all.\n- The details of the experimental setup are described in the Appendix. I can confirm the validity of the experiment.\n- l.144: On which does the constant $K_G$ depend? Does $K_G$ depend on the Hilbert space $H$?\n\n\nClarity（Presentation）\n\n- There is room for improvement in the organization of the paper. However, I think it does not significantly impact the paper's evaluation because I expect the authors can correct it quickly.\n- I found Section 3.1 to be a bit difficult to read. Specifically, this section (1) explained the SDP relaxation for the matrix-norma problem (l.140--148), (2) changed the topic to the problem without relaxation and showed its hardness (l.149--152), and (3) went back to the problem with relaxation (l.153--169). Therefore, I suggest reconsidering the order of the three.\n- I think the content of Section 4.1 should be in Section 3 rather than Section 4 since it is about two-layer NNs. Raghunathan et al. (2018), which applied two-layer NNs, is compared to eq. (6) in Section 3.1. Also, LipSDP and LipSDP-network appeared in Section 4.1. is compared with eq. (7) in Section 3.2.\n\nSignificance\n\n- For two-layer NNs, this paper showed the theoretical and empirical effectiveness of the proposed methods well.\n- For multi-layer NNs, the DGeoLIP does not have theoretical guarantees. In addition, it is not better than the baseline method by sampling (Table 1). Therefore, I have a question about the effectiveness of the proposed method for multi-layer settings.\n- This paper intends to apply the estimation of the Lipschitz constant to mitigate the vulnerability of NNs to adversarial attacks. However, the numerical experiments are only performed on the pure Lipschitz constant estimation problem. Therefore, this paper would be more significant if it could show that the proposed method is effective against adversarial attacks in some way.", "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": "1RefYRy8i2g", "reviewer": "Reviewer_xmVx", "summary": "The paper deals with estimating the Lipschitz constants of neural networks, aiming to unify different approaches based on semidefinite programming (SDP). More precisely, the authors would like to estimate the \"formal global Lipschitz constant\" (FGL) which is an upper-bound of the actual Lipschitz constant that's however sharper than the naive product of the norms of all weight matrices. They consider FGL estimation for two layer networks in the $\\ell_\\infty$ and $\\ell_2$ topologies and also outline FGP estimation for multi layer networks. Furthermore, they show that some existing SDP based models are duals of the FGP problem. In their numerical results section the authors compare their formulations to some other methods which estimate the Lipschitz constant, like dual SDP problems or brute force methods.\n\n########POST-REBUTTAL#########\n\nSince there seems to be relatively strong support for the paper, I increase my score to 5 and ask the authors improve the organization of the paper.", "questions": "I have a couple of questions and remarks that should be addressed: \n\n- p.3, l.103: I think the $\\operatorname{diag}$ operator shouldn't be part of the forward pass of the network. Is this a typo?\n- p.3, l.112, eq. (3): I guess that the matrices $W^i$ for $i=2,\\dots,d-1$ should also appear in this formula, right?\n- p.3, l.122: an interval of the form $[a,b]$ can never coincide with the set $\\lbrace 0,1\\rbrace$.\n- p.3, l.131: I don't understand why $f(x)$ has this form. This is linear in $x$. Also: what's $y$ in $\\operatorname{diag}(y)$?\n- p.7, l.242: same thing here\n- In general, the presentation of sections 3 and 4 is suboptimal and lacks a golden thread.\n- The numerical results in Table 1 seem to suggest that sampling is the best way to estimate the Lipschitz constant. Maybe you should compare your methods with sampling based Lipschitz constant estimation methods like for instance [2].\n- Given that Lipschitz regularization of neural networks is a very active field, the related work section and introduction does not paint a clear picture of the different approaches out there, such as e.g. the articles [1-5].\n\n[1] Aziznejad, S., Gupta, H., Campos, J., & Unser, M. (2020). Deep neural networks with trainable activations and controlled Lipschitz constant. IEEE Transactions on Signal Processing, 68, 4688-4699.\n\n[2] Bungert, L., Raab, R., Roith, T., Schwinn, L. and Tenbrinck, D., 2021, May. CLIP: Cheap Lipschitz training of neural networks. In International Conference on Scale Space and Variational Methods in Computer Vision (pp. 307-319). Springer, Cham.\n\n[3] Gouk, H., Frank, E., Pfahringer, B., & Cree, M. J. (2021). Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, 110(2), 393-416.\n\n[4] Krishnan, V., Makdah, A., AlRahman, A., & Pasqualetti, F. (2020). Lipschitz bounds and provably robust training by Laplacian smoothing. Advances in Neural Information Processing Systems, 33, 10924-10935.\n\n[5] Terjék, D. (2019). Adversarial lipschitz regularization. arXiv preprint arXiv:1907.05681.\n\n\n\n", "limitations": "To my mind, a negative societal impact cannot be expected and is also not discussed. Also there is a discussion section, the possible shortcomings (and advantages) of the proposed method over sampling type methods for estimating the Lipschitz constant is not discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The numerical results seem to indicate that the presented method computes the same estimate for the Lipschitz constant as its dual SDP variants, however, in shorter time. Furthermore, it compares favorably against the chosen baseline method LiPopt and brute force estimatation. \n\nWeaknesses: I find the paper pretty poorly written and it's not clear what exactly the contribution or the novelty is. The theoretical part of the paper is relatively ad hoc. Furthermore, the numerical results are not entirely conclusive, see \"Questions\" further down. ", "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