Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations
Authors: Patricia Pauli
Aaron J Havens
Alexandre Araujo
Siddharth Garg
Farshad Khorrami
Frank Allgöwer
Bin Hu
Venue: ICLR 2024 poster (2024)
Keywords: Neural Networks
Semidefinite Programming
Lipschitz Constant Estimation
Primary area: general machine learning (i.e., none of the above)

Abstract: Recently, semidefinite programming (SDP) techniques have shown great promise in providing accurate Lipschitz bounds for neural networks. Specifically, the LipSDP approach (Fazlyab et al., 2019) has received much attention and provides the least conservative Lipschitz upper bounds that can be computed with polynomial time guarantees. However, one main restriction of LipSDP is that its formulation requires the activation functions to be slope-restricted on $[0,1]$, preventing its further use for more general activation functions such as GroupSort, MaxMin, and Householder. One can rewrite MaxMin activations for example as residual ReLU networks. However, a direct application of LipSDP to the resultant residual ReLU networks is conservative and even fails in recovering the well-known fact that the MaxMin activation is 1-Lipschitz. Our paper bridges this gap and extends LipSDP  beyond slope-restricted activation functions. To this end, we provide novel quadratic constraints for GroupSort, MaxMin, and Householder activations via leveraging their underlying properties such as sum preservation. Our proposed analysis is general and provides a unified approach for estimating $\ell_2$ and $\ell_\infty$ Lipschitz bounds for a rich class of neural network architectures, including non-residual and residual neural networks and implicit models,  with GroupSort, MaxMin, and HouseHolder activations. Finally, we illustrate the utility of our approach with a variety of experiments and show that our proposed SDPs generate less conservative Lipschitz bounds in comparison to existing approaches.

Published as a conference paper at ICLR 2024
NOVEL QUADRATIC CONSTRAINTS FOR EXTENDING LIPSDP BEYOND
ACTIVATIONS
Patricia Pauli +1
Aaron Havens
Alexandre Araujo
Siddharth Garg
Farshad Khorrami 3
Frank Allgöwer
Bin Hu 2
Institute for Systems Theory and Automatic Control, University of Stuttgart
2 ECE & CSL. University of Illinois Urbana- Chaan--hamppign
3 ECE, New York University
Corresponding author. E-Mail: catricia.paull @ iis..ni-stuttgarr..e
ABSTRACT
Recently, semidefinite programming (SDP) techniques have shown great promise providing accurate Lipschitz bounds for neural networks. Specifically, the LipSDP approach (Fazlyab al., 2019) has received much attention and provides the least conservative Lipschitz upper bounds that can be computed with polynomial time guarantees. However, one main restriction of LipSDP that its formulation requires the activation functions to be restrrest on [0. 1]. preventing its further use for more general activation functions such as GroupSort, MaxMin, and Householder. One can rewrite MaxMin activations for example However, a direct application of LipSDP to the resultant residual ReLU networks is conservative and even fails in recovering the well-known fact that the MaxMin activation 1-Lipschitz. Our paper bridges this gap and extends LipSDP beyond slope-restricted activation functions. To this end, we provide novel quadratic constraints for GroupSort, MaxMin, and Householder activations via leveraging their underlying properties such sum preservation. Our proposed analysis general and provides a unified approach for estimating & and loo Lipschitz bounds for rich class of neural network architectures, including non-residual and residual neural networks and implicit models, with GroupSort, MaxMin, and Householder activations. Finally, we illustrate the utility of our approach with a variety of experiments and show that our proposed SDPs generate less conservative Lipschitz bounds comparison existing approaches.
residual ReLU networks.
INTRODUCTION
For neural network models, the Lipschitz constant key sensitivity metric that gives important implications properties such as robustness, fairness, and generalization (Hein & Andriushchenko, 2017; Tsuzuku et al., 3018; Salman et al., 2019; Leino et al., 2021; Huang et al., 2021; Lee et al.,
2020; Bartlett et al., 2017: Miyato et al., 2018; Farnia al., 2019; Li et al., 2019; Trockman & Kolter,
2021; Singla & Feizi, 2021; Xu et al., 2022: Yu et al., 2022; Meunier et al., 2022: Prach & Lampert,
2022). Since the exact calculation of Lipschitz constants for neural networks is NP-hard in general
(Virmaux & Scaman, 2018; Jordan & Dimakis, 2020), relaxation techniques are typically used to compute related upper bounds (Combettes Pesquet. 2019; Chen et al., 2020; Latorre al., 2020; Fazlyab et al., 2019; Zhang et al., 2019). A naive Lipschitz bound for a neural network is given by the product of the spectral norm of every layer's weight (Szegedy al., 2013), yielding quite conservative bounds for multi-layer networks. To provide tighter bounds, Fazlyab et al. (2019) introduced LipSDP, a semidfeinite programming (SDP) based Lipschitz constant estimation technique, that provides state-of-the-an &2 Lipschitz bounds in polynomial time. Since its introduction, LipSDP has had broad impact in many fields, e.g., Lipschitz constant estimation (Hashemi et al., 2021: Shi et al., 2022) and safe neural network controller design (Brunke al., 2022; Yin al., 2021). It inspired many follow-up works, extending the framework to more general network architectures (Pauli et al., 2023a) and loo bounds (Wang al., 2022). Beyond Lipschitz constant estimation, many works developed

---

Published as a conference paper at ICLR 2024
training methods for Lipschitz neural networks based on LipSDP (Pauli et al., 2021; 2023b; Araujo et al., 2023; Revay et al., 2020; Havens et al., 2023; Wang & Manchester, 2023).
One important assumption of the LipSDP formulation is that it requires the activation functions to be slope-restricted. Recently, new activation functions have been explored that do not have this property. Especially, the MaxMin activation function (Anil al., 2019) and its generalizations GroupSort and the Householder activation function (Singla et al., 2022) have been popularized for the design of Lipschitz neural networks and have shown great promise as a gradient norm preserving alternative to ReLU, tanh, or sigmoid (Leino et al., 2021; Huang et al., 2021; Hu et al., 2023b; Cohen et al.. 2019). MaxMin can equivalently be rewritten as residual ReLU network, enabling a LipSDP- based analysis based on the slope-restrictin property of ReLU. However, as we will discuss in our paper, this description too conservative to even recover the well-known fact that MaxMin is 1-Liischittz. This creates an incentive for us to develop tighter quadratic constraints to obtain better Lipschitz bounds beyond slope-restricted activations. Consequently, in this paper, we explore the characteristic properties of MaxMin,, GroupSort, and Householder activations to develop novel quadratic constraints that are satisfied by these activations.
Based on our new quadratic constraints, our work is the first one extend LipSDP beyond slope- restricted activations, providing accurate Lipschitz bounds for neural networks with MaxMin,, Group- Sort, Houscholder activations. More specifically, quadratic constraints are also the first ones for sum-preserving elements. Along with our extension of LipSDP new classes of activation functions, we present unified approach for SDP-based Lipschitz constant estimation that covers a wide range of network architectures and both &g and &oo bounds. Our work complements the existing SDP-based methods in (Fazlyab al., 2019; Wang et al., 2022: Araujo et al., 2023; Pauli et al., 2023a; Gramlich et al., 2023b; Revay et al., 2020; Havens et al., 2023; Wang & Manchester, 2023) and further shows the flexibility and versatility of SDP-based approaches, involving the Lipschitz analysis of residual and non ros-resilaal networks and implicit learning models with slope-restricted or gradient norm preserving activations.
use that GroupSort is sum sum- preserving and our
Notation. We denote the set of real n-dimensional vectors (with non-negative entries) by R (RC). the set of m x n-dimennional matrices by Rm and the set of n-dimensional diagonal matrices with non-negative entries by D We denote the n x n identity matrix by In and the n-dimensional all ones vector by 1,, Given any vector E R" we write diag(=) for diagonal matrix whose (i, i)-th entry is equal to the i-th entry of æ. Clearly, 1,, is just the sum of all the entries of a. We also use bikdiag((X, X..... .xx) to denote blockdiagonal matrix with blocks X1, X2, ......, Xn. Given two matrices A and B, their Kronecker product is denoted by A @ B. A function & R + is
slope-restricted on [a, 3] where 0 S a < B co if a x) S (oy) p(x)= S Bly x) Yx, y E R. A mapping ø R > R" is restecret on [a, B8] if each entry of á is slope-restricted on (a, .3.
2
PRELIMINARIES
2.1 LIPSCHITZ BOUNDS FOR NEURAL NETWORKS: A BRIEF REVIEW
In this section, we briefly review the original LipSDP framework developed in Fazlyab et al. (2019). Suppose we are interested in analyzing the Eg + Eg Lipschitz upper bounds for the following standard 1-layer feed-forward neural network which maps an input x to the output fz):
= I, x² +WW + bi) i = 1,...,/-11 1, fo(x) = Wia' + bz
Here W2 E X and b, E mT denote the weight matrix and the bias vector at the i-th layer, respectively. Obviously, we have x E 0 and fe(x)) E I and we collect all characterizing weight and bias terms in = (,, by i=1- The goal is to obtain an accurate Lipschitz bound > 0 such that (=) - fo(u)lla L vll2 Vx, y R holds.
!
Spectral norm product bound for @ being 1- 1-Lipschitz. If the activation function á is L-Lipschitz, then one can use the chain rule to obtain the trivial Lipschitz bound L = II'm, ||Willa (Szegedy et al., 2013). In other words, the product of the spectral norm of every layer's 's weight provides a simple Lipschitz bound. This spectral norm bound can be efficiently computed using the power iteration method, and the assumption regarding ó being 1 1-Lipschitz is quite mild, i. e., almost all activation functions used in practice, e.g., ReLU and MaxMin, satisfy this weak assumption. The downside is
2

---

Published as a conference paper at ICLR 2024
that the spectral norm bound yields conservative results, e.g., ReLU is not only I-Lipschitz but also slope-restricted on [0, 1], which is exploited in more advanced SDP-based methods.
LipSDP for é being slope-restricted on [0, 1]. If the activation ø is slope-restricted on [0, 1] in an entry-wise sense, as satisfied, e.g., by ReLU, sigmoid, tanh, one can adopt the quadratic constraint framework from control theory (Megretski & Rantzer, 1997) to formulate LipSDP for improved
Lipschitz analysis (Fazlyab et al., 2019). Given (W; by) b define (A, B) as
W1
0
0
0
0
1m1
0
0
0
2
0
122
A
0
Wi-1
Inz
to write the neural network (1) compactly as Bx Φ(Ar + b) with x
b = [6] ... ...6]]]]] ...6'''' Based on (Fazlyab et al., 2019, Theorem 2), if there exists a diagonal positive
semidefinite matrix T e D", where Ei=1 1 n2 such that the following matrix inequality holds!
plng
0
A B
O T 2T
A B
0
0
30, 00
(2)
T
W W
then the neural network (1) with @ being slope-restricted on [0. is /p-Lipschitz the &g -> l sense, i.e., [l) - (1))l2 I /pllz vllz Va, E "o Minimizing over the decision variables (p, ()) subject to the matrix inequality constraint (2), i.e.,
min p.TED
t. (2),
convex program and exactly the so-called LipSDP, which, in comparison the spectral norm bound, leads to improved Lipschitz bounds for networks with slope-restricted activations (e.g. ReLU).
SDPs for Loo perturbations. Wang et al. (2022) developed an extension of LipSDP to find Lipschitz bounds for neural networks with slope-restricted activations in the foo - & sense. Specifically, suppose fo is scalar output, and the SDPs in Wang et (2022) can be used find such that [Ja(z) fo(v) < L|xx= y/loo Va, E R See Wang et al. (2022) for more details.
2.2 GROUPSORT AND HOUSEHOLDER ACTIVATIONS
Recently, there has been growing interest using gradient norm preserving activations, particularly MaxMin, to design expressive Lipschitz neural networks (Tanielian & Biau, 2021) that are used, e.g.. in the fields of robust neural networks and learning-
control, cmp. Appendix for details. MaxMin is special case of the GroupSort actívation that we define as follows (Anil et al., 2019). Suppose Φ : R - R. is a GroupSort activation. What & does is separating the n preactivations into N groups each of size Ng. i.e.,
Nng, and sorting these groups in ascending order before combining the outputs to a vector of size n. GroupSort encompasses two important special cases: MaxMin (ny 2) and FullSort (ny = n). Another gradient norm preserving activation that also generalizes MaxMin is the Householder activation @ IR" R" that is applied to subgroups
n (Singla al., 2022)
x
x 0
(xx)
(In, 2o Ja
UT <
for all V : ||l||2 1. The parameter v can hence be learned during training and the choice v2 Mg 2 recovers MaxMin.
Using that the GroupSort and the Householder activation are 1-Lipschitz (Anil et al., 2019; Singla al., 2022), the spectral norm bound can still be utilized. However, GroupSort and Householder not slope-restricted on (0, 1]. Therefore, LipSDP cannot directly be applied to this case. Our work aims extending LipSDP and its variants beyond slope-restricted activation functions.
'The original work in Fazlyab et al. (2019) uses more general block parameterization of However. pointed out in Pauli et al. (2021), (Fazlyab al., 2019, Lemma 1) is actually incorrect, and one has use diagonal matrices T instead.

---

Published as a conference paper at ICLR 2024
3 MOTIVATION AND PROBLEM STATEMENT
Motivating Example. One may argue that MaxMin activations can be rewritten as residual ReLU networks
x1
0
1
([-)
-1
MaxMin
0
1
22
+
-1
ReLU
Ho+ ReLU (Wx).
(3)
Using that ReLU is slope-restricted, one can then formulate SDP condition
HHC | .
I 0
W
0 I
O T
T
W
0 1
(4)
G
0
-2T
that implies /p-l.ipschizzees of the MaxMin activation function. The proof of this claim is deferred Appendix C.1. Minimizing & over (p. 7) subject matrix inequality (4) yields p 2. This shows that applying LipSDP to the residual ReLU network equivalent to MaxMin too conservative to recover the well-known fact that MaxMin is L-Lipschitz. To get improved Lipschitz bounds, necessitate more sophisticated qudratic constraints for MaxMin and its generalizations GroupSort and Householder, which we derive in the next section.
Problem statement. In this paper, we are concerned with Lipschitz constant estimation for neural networks with MaxMin, GroupSort, and Householder activations. We give brief preview of our approach here. Similar to LipSDP, we also follow the quadratic constraint approach from control theory (Megretski & Rantzer, 1997) to obtain a matrix inequality that implies Lipschitz continuity for neural network. We provide more details on the quadratic constraint framework in Appendix B. Notice that the matrix inequality (2) used LipSDP is a special case
p
0
0
A B
X
3 0,
(5)
W, Wi
with X = [ _T for [0, 1|-slope-restricted activations.
Developing proper choice of X beyond doing so, we explore the input-output properties of GroupSort and Householder activations to set up X such that the matrix inequality (5) can be modified give tfate-of-the-art Lipschitz bounds for neural networks with important and popular activations that are not slope-restricted.
restricted activations is the goal of this paper. In
4 MAIN RESULTS: SDPs FOR GROUPSORT AND HOUSEHOLDER ACTIVATIONS
In this section, we develop novel SDPs for analyzing Lipschitz bounds of neural networks with MaxMin. GroupSort, and Householder activations. Our developments are based on non-trivial constructions of quadratic constraints capturing the input-output properties of the respective activation function and control-theoretic arguments (Megretski & Rantzer, 1997).
4.1 QUADRATIC CONSTRAINTS FOR GROUPSORT AND HOUSEHOLDER ACTIVATIONS
First, we present quadratic constraints characterizing the key input-output properties, i.e., 1-Lipschitz- ness and sum preservation, of the GroupSort function. Our results are summarized below.
Lemma 1. Consider a GroupSort activation Φ R." + R with group size Ng. Let
Given
ng
any x RN and 7, v, 7 E RNN the following inequality holds for all x. y E R
x y (xx) - o(y)
T - 25 P+
2 0,
(6)
P+S
-T- 2P
((x)) x
where ST P) are given as
T diag(A) ② In, + diag(?) @ (1n, 1,,)
P = diag(v) 2 (1n, (T)),
(7)
S diag(r) (1,, n.
4

---

Published as a conference paper at ICLR 2024
All the detailed technical proofs are deferred to Appendix C. To illustrate the technical essence, briefly sketch a proof outline here.
Proof sketch. Let E; denote N-dimensional unit vector whose i-th entry is and all other entries are O. Since GroupSort preserves the sum within each subgroup, (e, @ In, )z = (ef @ 1,, )((x)
holds for all = I,...,... N. This leads to the following key equality:
(x - 3) ((eee)) @ (In, M= 9) = (6(z) - ((v)) ((ere) ) ) (In, In, (d(()) o(y))
= (d(x) -(v)) ((ere,) ) @ (In, 1n, (z y) = v) ((ere) @ (Ing 1,, (d(x)) - <(v)),
which can be used to verify that (6) is equivalent to
I y - ((x)-
diag(A)
Ing
1 [(xx) | y (v)
2 0.
(A) @ I.
Finally, the above inequality holds because the sorting behavior each subgroup is 1 1-Lipschitz, i.c. II(e, @ In,)(z v) 2 lI(e, In()((()) ((v)) for all i == 1.....N. N.
Based on the above proof outline, we can see that the construction of the quadratic constraint (6) relies the key properties that the sorting in every subgroup is 1 1-Lipschitz and sum- cum-preervvngg This significantly different from the original sector-bounded quadratic constraint for slope-restricted nonlinearities in Fazlyab et al. (2019).
In the following, we present quadratic constraints for the group-wise applied Householder activation. Lemma 2. Consider Householder activation & R - R with group size ng. Let N "g"
Given any À E R. and E TR-,, the inequality (6) holds for all x, E TR" where (T, S, P) are given
T diag (A) @ In + diag(n) @ (In, - -v vv
P diag(v) @ (Ln, ve ))
S == diag(T) @ (In, vo ).
Using the novel quadratic constraint (6) with (T, S, P) either defined as in (7) or in (8), we can formulate a SDP subject to (5) with X being set up X constant of a GroupSort/Househllder neural network. We will discuss such results next.
T=-2 28 P+8 estimate the Lipschitz -T-
4.2 lg + lg LIPSCHITZ BOUNDS FOR GROUPSORI/HOUSSHOLDEE NEURAL NETWORKS
Based on Lemmas and we develop a new SDP condition analyze neural networks with GroupSort and Householder activations. To this end, we establish the following result.
Theorem 1. Consider the l-layer connecco neural network (1), where is GroupSort (House- holder) with the same group size ng in all layers. Let N = Σizl ni be the total number of groups. If Rh
there exist > 0, X E R.N, and U E RNN such that the following matrix inequality holds
pI
A B
T 2S
P+S -T
A
0
0
(,P.P.S,T)
0,
(9)
P+S
2P
B
W, WJ
where (T, S, P) are defined by (eq. (8)), then (1) /p-Lipschitz in the lg + lg sense.
The proof of the above result based on standard quadratic constraint arguments and is included in Appendix C.4. Based this result, the solution vp of the SDP
min P s. M(p, T, T) P.T.S.P
(10)
gives an accurate Lipschitz bound for neural networks with GroupSort or Householder activations. In our practical implementation, we S P 0 for improved scalability, i.e.. reduce the number of decision variables and to exploit the structure of the constraint (9). See Appendix D. for details. Empirical tests indicate that the choice S P 0 yields the same results as without this consraint. In what follows, we discuss several important aspects of SDP-base Lipschitz constant estimation for GroupSort and Householder activations.
5

---

Published as a conference paper at ICLR 2024
Simplifications for the single-layer neural network. If the neural network is single-layer, i.e., fo(r) = W2 b1) + by with & being GroupSor/Houscholder with group size nlg we can simplify our SDP condition (9)
WTTW: pl - W2 3 30,
0
setting S = - 0 discussed before. One can compare the above result to its LipSDP counterpart (Fazlyab et al., 2019, Theorem 1) and realize that the only main difference is that Lemma 1 is used to replace (Fazlyab et al., 2019, Lemma for setting up X.
MaxMin activations. In practice, MaxMin is typically used where n2 2. In this case, the number of the decision variables used to parameterize T is exactly Σ 14. This is consistent with LipSDP, which uses the same number of decision variables to address slope-restricted activations.
GroupSort and conn-consta weights. GroupSort activations are oftentimes used in combina- tion with gradient norm preserving layers. For this special case the Lipschitz constant is tight and hence there no need for Lipschitz constant estimation. However, many MaxMin neural networks are trained without weight constraints they have shown to be prohibitive in training (Leino et al., 2021; Hu al., 2023b; Huang et al., 2021; Cohen et al.. 2019). For such neural networks our approach provides more accurate Lipschitz bounds than existing approaches.
Adaptions to convolutional neural networks. Theorem can be extended to convolutional neural networks using ideas from Pauli et al. (2023a); Gramlich et al. (2023b). The key idea in (Pauli al., 2023a; Gramlich et al., 2023b) is the formulation of convolutional layers via state space representation, which enables the derivation of non-sparse and scalable SDPs for Lipschitz constant estimation for convolutional neural networks. We briefly streamline the method in Appendix F.2.
4.3 lo - l LIPSCHITZ BOUNDS FOR GROUPSORT/HOUSSOOLDDO NEURAL NETWORKS
In this section, we will combine Lemmas 1 and 2 with the results in Wang al. (2022) to develop SDPs for the too + ε analysis of neural networks with GroupSor/Houscholder activations. Similar to Wang al. (2022). we assume that fa( has scalar output. Suppose ó is GroupSor/Householdde activation with group size ng. We are interested in calculating L such that (f) fe(y) S L| y/ Var, y Ro It well known that the lx - f Lipschitz bounds via some standard scaling argument based on the equivalence of norms. However, such naive approach is conservative in practice (Latorre et al., 2020). In this section, we develop novel SDPs for more accurate calculations of too + L Lipschitz bounds.
& Lipschitz bounds can be transferred into
Single-layer case. For simplicity, we first discuss the single-layer network case, i. e., fo(x) W2o(W1æ + b1) + b2 with o being GroupSor/Houscholderr with group size Ng. Since the output fo(r) is assumed to be a scalar, we have W2 E R lxxi, Obviously, the tightest Lipschitz bound is given by
Liin = max (z((z) - fo(
(11)
I - 2o1
Then for any 2 Luin, we will naturally have lfo(z) - fo(y)) S L||x y/l Vz, y. Based on Lemma 1, one upper bound for Lmin is provided by the solution of the following problem:
W2Av1
WrAr
- 2S
P+S
Wr
max Ss
| 1oo
s.t.
Au
P+S S
-T
2P
Av
20,
(12)
where Ar <WWr + b1) 6(W1 + b1). Ar x and (T,S, P) are given by (7) with some V, T E RN, A E R.Y A similar argument has been used in (Wang et al., 2022, Section 5). The difference here is that the constraint in the optimization problem (12) is given by our new quadratic constraint specialized for GroupSort/Housholdeer activations (Lemma 1/2). We note that if we scale Ar and Au with some common factor, the constraint in problem (12) is maintained due to its quadratic form, and the objective ratio remains unchanged. Hence the problem (12) is scaling-invariant, making it equivalent to the following problem (the absolute value in the objective is removed since scaling Av with -1 does not affect feasibility)
[W Au
T 28
P+S
W1 Av 2 0,
max WGAv s.t. Ar,Ae
|| 1.
P+S
-T 2P

---

Published as a conference paper at ICLR 2024
A simple upper bound for the above problem is provided by replacing the equality constraint with an inequality || I 1. Therefore, we know Lmin can be upper bounded by the solution of the
following problem:
Ax
(T W
(P+++ -T - 2P
Az Au
max W2 s. Ar
N 0, || S 1. (13)
Au
S)W
can be equivalently rewritten the following quadratic constraints (e] Az)² < 1 for j -...., no (Wang et al., 2022). Now we introduce the dual variable jA E IR4
Finally, note that ||
and obtain the following SDP condition (which be viewed the dual program of (13)).
Theorem 2. Consider single-layer neural network described by fo(x) = W20 Wix + b1) + b2.
where Φ Rd1 TR is GroupSort (Householder) with group size ng. Denote N
21, Suppose
there exist p > 0, T.M. E ERN, , X E EN,, and μ E R+ such that
1 0
2p
W2
WT - Q
(T S)
30,
(14)
W
(P+SWWi
-T-21
where P) are given by (7) (eq. (8)), and Q == diag(u). Then lfo(z) - fo(u)) - p|l x1 Vx, E R
Multi-layer case. The above analysis can easily be extended to address the multi-layer network case with GroupSord/Houshhlldr activations. Again, adopt the setting in Wang al. (2022) and choose 1. By slightly modifying the above analysis, we then obtain the following result.
Theorem 3. Consider the E-layer feedforward neural network (1), where é is GroupSort (House-
holder) with group size ng in all layers. Let N E. be the total number of groups. Suppose
there exist > 0, N.V. E RN,, X E R,,, and μ E R4 such that
1
2p
Wi
0 0
A
T 25
P+S
0 1
0
Q
0
M(,
+
0,
B
P+S -T - 2P
B
:
W
0.
(15)
where (T, S, P) are given by (7) (eg. (8)), and Q = diag(u). Then (fo(z) So(u)l S p||x Val E R.
Minimizing subject to the constraint (15) yields SDP problem. For sarge-scale implementations. we again set S = and implement the SDP as specified Appendix D.2 to solve it more
efficiently. Based on preliminary testing, this implementation does not introduce conservatism over the original SDP formulation with non-zero (S,P).
4.4 FURTHER GENERALIZATIN RESIDUAL. NETWORKS AND IMPLICIT MODELS
In this section, briefly discuss how our quadratic constraints in Lemmas I and 2 can be used to generalize various existing SDPs to handle residual networks and implicit learning models with MaxMin, GroupSort, and Householder activations. Due space limitations, keep our discussion brief. More details can be found in Appendix F.
Residual neural networks.
We consider a residual neural network
d0 x, o¹ = - G.o(Wa be) i= i. fo(x) =
(16)
referring the reader to Appendix F.1 for the single-layer case. Suppose @ is GroupSor/Houucholder with the same group size ny for all layers. For simplicity, we define the matrices À and B as
W1
0
0 I
0
W2
W2G1
0
0
0
Ing
-=
B
W WIG1
WIG-1
0
7

---

Published as a conference paper at ICLR 2024
Table 1: This table presents the results of our LipSDP-NSR method on several feed-forward neural networks with MaxMin activations trained on MNIST with more than 96% accuracy, using &g adversarial training. We compare against several metrics which are described in detail in Section The computation time in seconds is shown in parentheses and included in Appendix D.3 for the naive bounds. Similar to Wang et al. (2022), we report the box. bounds with respect to label to consider scalar outputs.
Made
4
(ustts
lyari
Somple
LipSDP-NSR
LipSDP-RR
Sample
LipSDP-NSR
LiSSDP-R
MP
15 usits
20.95
22,02
22.59
(54)
23.02
(15)
23.46
142.42
153.22
202.62
(94)
207.3
(34)
552.52
543
2-kayer
units
unii
63.35
$4.54
$7.95
72.77
36.15
(160)
(86)
14.31
40.25
(24)
(22)
43.4h
13.5%
653.0
307.9
11891
366-6
855.50
(147)
(1328)
5703
401.5
(44)
(35)
2005.6
1074
3572
1140
55,44
70.87
(182)
72.18
9000
10588
(236)
1033.1
(77)
19644
Skkyer
units
232,21
106-55
386.81
204.55
(360)
623
1
(225)
(66)
520.73
20..1
2157.32
952.88
2009
63795
(150)
43811
$521.3
(135)
(419)
6586.
10831
133710
S0ATE3
snits
113.34
401.05
(380
10785
(175)
780
813.55
4305
(121))
6131.1
(376)
11229
2.01
8.kgee
258.35
(1:18
(1426)
1241
2147.64
75
(188)
1.366-004
(2495)
19995
4355-00
245
307.06
643.07
414
1845 11
9156
(759)
17904
1150-49
unils
267.32
17432
(643
75465
1693 69
1-8991445
(78)
4.5611405
2.256-13
16-taeer
units
533.85
25412
(1399
NE384
2037 21
1,90076608
(150)
0.35588-055
1.000:-15
$36.04
(200)
1,90995005
0,79541-405
to compactly describe the model (16) as Bx = o(Ax + 6) with b [b] ..666]]]] Then we obtain the following theorem.
Theorem 4. Consider the multi- residual network (16), where o is GroupSort (Householder)
with the same group size R2 for all layers. Define N = Ex n4 7, RN and X E I.Y. such that
Suppose there exist p > 0,
ng
Ln G
G1 G
G.
G
A B
T - 25
P+S
A B
P+S
-P
+
I 00
(17)
GT
G
G GL
where (T,S, P) are given by (7) (eq. (8)). Then (16) is /p-Lipschitz in the lo -> lg sense.
From empirical studies we know that, when implementing the SDP, we can either set S = or P 0 (but not both), yielding the same SDP solution with non-zero (S, P).
Implicit learning models. With our proposed quadratic constraints, we can also formulate SDPs for the Lipschitz analysis of implicit models with GroupSort/ousccollde activations. When the activa- tion function is slope-restricted on [0, 1]. SDPs can be formulated for the Lipschitz analysis of both deep equilibrium models (DEQs) (Bai et al., 2019) and neural ordinary differential equations (Neural ODEs) (Chen et al., 2018). For example, a variant of LipSDP has been formulated in (Revay et al., 2020, Theorem to address the Lipschitz bounds of DEQs with [0, 11-slope-restricter activations based on the quadratic constraint in (Fazlyab et al., 2019, Lemma 1). When GroupSort/Househh used, we can easily modify the result in (Revay al., 2020, Theorem 2) obtain new SPD for activations via replacing the slope-restricted quadratic constraints
DEQs with SroupSort/Hosscholde with (6) Lemma 1/2. Similar results can also be obtained for neural ODEs. Due to the space limit, we defer the detailed discussion of such extensions to Appendices F.3 and F.4.
NUMERICAL EXPERIMENTS
In this section, we present numerical results demonstrating the effectiveness of our proposed SDP, whose solution we denote by LipSDP-NSE Additional numerical results including experiments on residual neural networks are included in Appendix E. Code to reproduce all experiments is provided at https://// //i thub. com/
/CCsa MaxMin. Following the same experimental setting as Wang al. (2022), we evaluate our approach on several MaxMin neural networks trained on the MNIST dataset (LeCCun & Cortes, 2010) and compare LipSDP-NSR to four other measurements:
The sampling approach computes the norm of the gradient (or the Jacobian) 200k random samples from the input space. This measurement easy to compute and provides a lower bound on the true Lipschitz constant.
Sample:
8

---

Published as a conference paper at ICLR 2024
Formal global Lipschitz (FGL): This metric is computed by iterating over all (including infeasible) activation patterns. Despite being an upper bound on the true Lipschitz constant, this value is accurate. However, it can only be computed for small networks it is exponential-time search. We provide computation details for FGL. on GroupSort networks below.
LipSDP-RR We formulate MaxMin activations as residual ReLU networks (3) and solve SDP using slope-restrictin quadratic constraints.
Equivalence of Norms (Norm Eq.): This bound on the lo <x--Lipschizz bound is obtained using the equivalence of norms, i. e.e., yno f2-LipSDP-NSR.
Matrix-Product (MP): Naive upper bound of the product of the spectral norms of the weights.
Implementation details of FGL. As shown in Virmaux & Scaman (2018), based on Rademacher's theorem, if f is Lipschitz continuous, then f is almost everywhere differentiable, and Ly = sup, || fl From this result and based on the chain rule, we can write the Lipschitz con- stant of the network f as
Ls sup [WVVV (o(]()))Wlll
(18)
where é is the GroupSort activation with group size n, and fi(x) = Wiri-1+ i- 1,..,,
Given that GroupSort is simply a rearrangement of the values of the activation, the Jacobian (e( is a permutation matrix. Let Pn, be the set of permutation matrices of size ng x ng. N "y us define the set of GroupSort permutations:
and let
pn, (blkdiag( Pi..... PN) PI..., PN E Pny)
(19)
Following the same reasoning Wang al. (2022) and Virmaux & Scaman (2018), we can upper bound T,f as follows:
WiP Piwill, (.................. FGL.
S max
(20)
P PLIEP...
Implementation details of LipSDP-NSR discussion of the results. We solve problem (10) and an SDP that minimizes p subject to (15), using YALMIP (Löfberg, 2004) with the solver Mosek (MOSEK Aps, 2020) in Matlab on a standard i7 note book. Our results and the other bounds are summarized in Table 1. For all networks, LipSDP-NSE clearly outperforms MP and the equivalence of norms bound. More detailed discussions are given in Appendices D and E.
Limitations. SDP-based Lipschitz bounds are the best bounds that can be computed in polynomial time. One limitation is their scalability large neural networks that has been tackled by structure exploiting approaches (Newton & Papachristodoullu, 2023; Xue et al., 2022; Pauli et al., 2023a). Our implementation incorporates such approaches and we provide implementation details Appendix D. In addition, we see potential that new SDP solvers or tailored SDP solvers (Parrilo, 2000; Gramlich al., 2023a) will mitigate this limitation in the future. Finally, the concurrent work in Wang et al. (2024) has developed the exact-penalty form of LipSDP for the seope-restricted activation case, enabling the use of first-order optimization methods for scaling up the computation. We believe that the argument in Wang et al. (2024) can be modified to improve the scalability of our proposed SDP conditions.
CONCLUSION
We proposed SDP-based method for computing Lipschitz bounds of neural networks with MaxMin, GroupSort and Householder activations with respect to &-- and -e--perurrbatios. To this end, we derived novel quadratic constraints for GroupSort and Householder activations and set up SDP conditions that generalize LipSDP and its variants beyond the original slope-restricted activation setting. Our analysis method covers a large family of network architectures, including residual, non-residual, and implicit models, bridging the gap between SDP-based Lipschitz analysis and this important new class of activation functions. Future research includes finding specific quadratic constraints for other general activation functions and nonlinear parts in the neural network.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
P. Pauli and F. Allgöwer are funded by Deutsche Forschungsgemeinschatt (DFG, German Re- search Foundation) under Germany's Excellence Strategy EXC 2075 390740016 and under grant 468094890. A. Havens and B. Hu are generously supported by the NSF award CAREER-2048 the AFOSR award TA9550-23-1-07333 and the IBM/IIDAI award 1 110662-01. A. Araujo, S. Garg, and F. Khorrami are supported in part by the Army Research Office under grant number W91 21-1-0155 and by the New York University Abu Dhabi (NYUAD) Center for Artificial Intelligence and Robotics, funded by Tamkeen under the NYUAD Research Institute Award CGO10. P. Pauli also acknowledges the support by the Stuttgart Center for Simulation Science (SimTeeh) and the support by the International Max Planck Research School for Intelligent Systems (IMPRS-IS).
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In International Conference on Machine Learning, pp. 291-301. PMLR, 2019.
Alexandre Araujo, Aaron Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. A unified algebraic perspective on Lipschitz neural networks. In International Conference Learning Representations, 2023.
Anil Aswani, Humberto Gonzalez, Shankar Sastry, and Claire Tomlin. Provably safe and robust learning-baat -based model predictive control. Aulomatica, 1965):111-1122 1226, 2013.
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, 32, 2019.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaiizee margin bounds for neural networks. In Advances in Neural Information Processing Systems, 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, pp. 908-918.70 2017.
Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning in robotics: From learning-based control to safe reinforcement learning. Anmual Review of Control, Robotics, and Autonomous Systems, 5:41 5:411-444, 2022.
Joaquin Carrasco, Matthew Turner, and William P Heath. Zames-fal multipliers for absolute stability: From o' shea' contribution to convex searches. European Journal of Control, 28:1-19, 2016.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018.
Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimization for Lipschitz constants of relu networks. Advances in Neural Information Processing Systems, 33: 19189-19200, 2020.
Jeremy EJ Cohen, Todd Huster, and Ra Cohen. Universal Lipschitz approximation bounded depth neural networks. arXiv preprint arXiv: 1904.04861, 2019.
Patrick L Combettes and Jean- Lean-Christophe Pesquet. Lipschitz certificates for neural network structures driven by averaged activation operators. arXiv, 2019, 2019.
Filippo Fabiani and Paul J Goulart. Neural network controllers for uncertain linear systems. arXiv preprint arXiv:2204.1333 13209, 2022.
Farzan Farnia, Jesse Zhang, and David Tsc. Generalizable adversarial training via spectral normaliza-
tion. In International Conference on Learning Representations, 2019.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of Lipschitz constants for deep neural networks. 2019.
10

---

Published as a conference paper at ICLR 2024
Mahyar Fazlyab, Manfred Morari, and George Pappas. Safety verification and robustmess analysis of neural networks via quadratic constraints and semidefinite programming. IEEE Transactions on Automatic Control, 2020.
Dennis Gramlich, Tobias Holicki, Carsten W. Scherer, and Christian Ebenbauer. A structure exploiting sdp solver for robust controller synthesis. IEEE Control Systems Letters, 7:1831-1836, 2023a. doi:
N0011099LCSSS.2233322733
Dennis Gramlich, Patricia Pauli, Carsten W Scherer, Frank Allgöwer, and Christian Ebenbauer. Convolutional neural networks as 2-D systems. arXiv preprint arXiv:2303.0304/ 2023b.
Navid Hashemi, Justin Ruths, and Mahyar Fazlyab. Certifying incremental quadratic constraints for neural networks via convex optimization. Learning for Dynamics and Control, pp. 453-853. PMLR, 2021.
Aaron J Havens, Alexandre Araujo. Siddharth Garg, Farshad Khorrami, and Bin Hu. Exploiting connections between Lipschitz structures for certifiably robust deep equilibrium models. In Advances in Neural Information Processing Systems, 2023.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. Advances in Neural Information Processing Systems, 30, 2017.
Kai Hu, Klas Leino, Zifan Wang, and Matt Fredrikson. A recipe for improved certifiable robustness: Capacity and data. arXiv preprint arXiv:2310.0251.. 2023a.
Kai Hu, Andy Zou, Zifan Wang. Klas Leino, and Matt Fredrikson. Unlocking deterministic robustness certification on imagenet. In Thirty-sevente Conference on Neural Information Processing Systems, 2023b. URL https:t////.. oppnnevview net / forum? id=SHyVaMGTO4,
Yujia Huang, Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local Lipschitz bounds. Advances Neural Information Processing Systems, 34:22745-227555 2021.
Ming Jin and Javad Lavaei. Stability-certiffed reinforcement learning: A control-theoretic perspective. IEEE Access, 8:229086-229100, 2020.
Matt Jordan and Alexandros G Dimakis. Exactly computing the local Lipschitz constant of ReLU networks. In Advances in Neural Information Processing Systems, pp. 7344-7353. 2020.
Chung-Yau Yao Kao and Anders Rantzer. Stability analysis of systems with uncertain time-varying delays. Automatica, 43(6):959-977) 2007.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. International Conference on Learning Representations, 2020.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
Sungyoon Lee, Jaewook Lee, and Saerom Park. Lipschitzecertffiable training with a tight outer bound. In Advances in Neural Information Processing Systems, pp. 16891-16902, 2020.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference Machine Learning, 2021.
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Heen- Jacobsen. Preventing gradient attenuation in Lipschitz constrained convolutional networks. In Advances in Neural Information Processing Systems, 2019.
J. Löfberg Yalmip A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
Max Losch, David Stutz, Bernt Schiele, and Mario Fritz. Certified robust models with slack control and large Lipschitz constants. arXiv preprint MiXx:2309006166 2023.

---

Published as a conference paper at ICLR 2024
Alexandre Megretski and Anders Rantzer. System analysis via integral quadratic constraints. IEEE Transactions on Automatic Control, 42(6))819-83) 830, 1997.
Laurent Meunier, Blaise Delattre, Alexandre Araujo, and Alexandre Allauzen. A dynamical system perspective for Lipschitz neural networks. In International Conference on Machine Learning, pp- 15484-15500. PMLR, 2022.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. International Conference on Learning Representations, 2018.
MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 9.2.5, 2020.
Matthew Newton and Antonis Papachristodoulou. Exploiting sparsity for neural network verification. In Learning for Dynamics and Control, pp. 715-727. PMLR, 2021.
Matthew Newton and Antonis Papachristodoulou. Sparse polynomial optimisation for neural network verification. Automatica, 157:111233, 2023.
Pablo A. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. Training robust neural networks using Lipschitz bounds. IEEE Control Systems Letters, 1:1-11 2021.
Patricia Pauli, Dennis Gramlich, and Frank Allgöwer. Lipschitz constant estimation for 1d convolu- tional neural networks, In Learning for Dynamics and Control Conference, pp. 1321-1332. PMLR, 2023a.
Patricia Pauli, Ruigang Wang. Ian R Manchester, and Frank Allgöwer. Lipschitz-bounded ID convolutional neural networks using the Cayley transform and the controllability Gramian. arXiv preprint arXiv:2303. 11835, 2023b.
H. Pfifer and P. Seiler. Integral quadratic constraints for delayed nonlinear and parameter-varying systems. Automatica, 56:36 -3,,,6433000 2015.
Bernd Prach and Christoph H Lampert. Almost-orthogonal layers for efficient veneral-purpont Lipschitz networks. In Computer Vision-ECCV 2022: 17th European Conference, 2022.
Max Revay, Ruigang Wang, and lan R Manchester. Lipschitz bounded equilibrium networks. arXiv preprint arXiv:2010.01732 2020.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, 2019.
Guanya Shi, Xichen Shi, Michael O' O'Connell Rose Yu, Kamyar Azizzadenesheli, Animashree Anandkumar, Yisong Yue, and Scon-Jo Chung. Neural lander: Stable drone landing control using learned dynamics. 2019 international conference on robotics and automation (icra), pp- 9784-9790. IEEE, 2019.
Zhouxing Shi, Yihan Wang, Huan Zhang, J Zico Kolter, and Cho-Jui Hsieh. Efficiently computing lo- Lipschitz constants neural networks via bound propagation. Advances in Neural Information Processing Systems, 35:2350-2366 -2644, 2022.
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference on Machine Learning, 2021.
Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on CIFAR-10 and 10FAR-100. In International Conference Learning Representations, 2022.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint 131. 2013.
Ugo Tanielian and Gerard Biau. Approximating Lipschitz continuous functions with groupsort neural networks. In International Conference Artificial Intelligence and Statistics, pp. 442-450, 2021.
12

---

Published as a conference paper at ICLR 2024
Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In Interaational Conference on Learning Representations, 2021.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems, 2018.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
Ruigang Wang and lan Manchester. Direct parameterization of Lipschitz- deep networks. In International Conference Machine Learning, pp- 30093-3611111 --19903-.10... PMLR, 2023.
Zi Wang, Gautam Prakriya, and Somesh Jha. A quantitative geometric approach neural-network smoothness, In Advances in Neural Information Processing Systems, 2022.
Zi Wang. Bin Hu, Aaron J Havens, Alexandre Araujo, Yang Zheng, Yudong Chen, and Somesh Jha. On the scalability and memory efficiency of semidefinite programs for Lipschitz constant estimation of neural networks. In International Conference on Learning Representations, 2024.
Xiaojun Xu, Linyi Li, and Bo Li. Lot: Layer-wise orthogonal training improving 12 certified robustness. Advances in Neural Information Processing Systems, 2022.
Anton Xue, Lars Lindemann, Alexander Robey, Hamed Hassani, George J Pappas, and Rajeev Alur. Chordal sparsity for Lipschitz constant estimation of deep neural networks. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 3389-3396. IEEE, 2022.
He Yin, Peter Seiler, and Murat Arcak. Stability analysis using quadratic constraints for systems with neural network controllers. IEEE Transactions on Automatic Control, 67(4)) 2021.
Wallace Tan Gian Yion and Zhe Wu. Robust machine learning modeling for predictive control using Lipschitz-constrained neural networks. Computers & Chemical Engineering, pp. 108466, 2023.
Tan Yu, Jun Li, Yunfeng Cai, and Ping Li. Constructing orthogonal convolutions in an explicit manner. In International Conference on Learning Representations, 2022.
Huan Zhang, Pengchuan Zhang, and Cho- Jui Hsieh. Recurjac: An efficient recursive algorithm for bounding Jacobian matrix of neural networks and applications. Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
13

---

Published as a conference paper at ICLR 2024
A APPLICATIONS OF MAXMIN NEURAL NETWORKS
GroupSort and Houscholder activations have been introduced as gradient-norm preserving activa- tion functions. This convenient property lead to the use of neural networks with GroupSort and Householder activations to fit Lipschitz functions (Anil et al., 2019; Tanielian & Biau, 2021; Cohen et 2019) and to design robust neural networks (Singla et al., 2022; Huang et al., 2021). Using MaxMin neural networks, Huang et al. (2021); Leino et al. (2021); Hu et al. (2023b;a); Losch et al. (2023) provide state-of-the-art verified-robust accuracy, that they compute based on information of the Lipschitz constant and the prediction margin of the trained networks.
Another application of Lipschitz neural networks is in learning-based control with safety, robustness and stability guarantees (Aswani et al.. 2013; Berkenkamp et al., 2017; Jin & Lavaei, 2020; Shi al., 2019; Fabiani & Goulart, 2022; Yion & Wu, 2023), for example using MaxMin activations (Yion & Wu, 2023). LipSDP for MaxMin can potentially reduce the conservatism in the stability and robustness analysis of such MaxMin network controllers.
B THE QUADRATIC CONSTRAINT FRAMEWORK
The quadratic constraint framework stems from the control community and was developed starting in the 1960s (Megretski & Rantzer, 1997). In the control literature, quadratic constraints are used to abstract elements of a dynamical system that cause trouble in the analysis, e.g., nonlinearities, uncertainties, or time delays. This abstraction then enables the analysis of systems which include such troublesome elements. The quadratic constraint framework is generally applicable, as long as the troublesome element can be abstracted by quadratic constraints. For example, Kao & Rantzer (2007) introduce quadratic constraints for so-called difffe--iffereee"" operator to describe varying time delays, Pfifer& & Seiler (2015) use geometric interpretation to derive quadratic constraints for delayed nonlinear and parameter-varyinn systems, and Carrasco et al. (2016) summarizes the development of Zames-Falb multipliers for restrreet nonlinearites based on frequency domain arguments. All previous papers on LipSDP borrow existing quadratic constraints for cestrcrettricted nonlinearities from the control literature that are not satisfied by MaxMin, GroupSort, and Householder activations. This being said, our paper the first that successfully derives quadratic constraints for GroupSort and Houscholder activations, and further, we are the first to formulate quadratic constraints for sum-preserving elements. The idea we used to derive these quadratic constraints is creative in the sense that it is very different from all the existing quadratic constraint derivations in the large body of control literature. The difficulty in deriving new quadratic constraints lies in identifying properties and characteristics of the troublesome element, in our case multivariate nonlinearity GroupSort or Householder, that can (i) be formulated in a quadratic form and (ii) whose quadratic constraint formulation is tight and descriptive enough lead to improvements in the analysis. Please see Appendices C.3 and C.3 for the technical details of our derivation. We use our novel quadratic constraints to solve the problem of Lipschitz constant estimation. However, the modularity of the quadratic constraint framework allows to, as well, address different problems, e.g., safety verification of MaxMin neural network similar to (Fazlyab et al., 2020; Newton Papachristodoulou, 2021) or the stability of feedback loop that includes MaxMin neural network, as done in (Yin et al., 2021) for slope-restricted activations.
C TECHNICAL PROOFS OF MAIN RESULTS
C.1 PROOF FOR MOTIVATING EXAMPLE
In Section 3, we claim that the matrix inequality (4) implies V/-Lipschitzness for the residual ReLU network that we obtained from rewriting MaxMin. In the following, we prove this claim. We left and right multiply (4) with (x y)" (ReLU(Wz) - ReLUUWy)) and its transpose, respectively. and obtain
z ReLU 2) - ReLU((W))
]
I
0
pl
0
0]
I yy ReLU(Wx)) - ReLU
H
G
0
-1
и
W
0
[
T.
[W
z y ReLU(WZz) - - ReLU(Wy)
ReLU(Wxz) - RReLLRW)))
0
I
T
-2T
0
I
14

---

Published as a conference paper at ICLR 2024
This inequality can equivalently be rewritten as
p(x T)(( (xr y) Hæ + G G))L Hy - G (H GRelWW) Hy GR
MaxxMiu(z)
We Wy Re. ReLu(W w
T 27
Wx Wy RoLUU(W) Reluww))
which we in turn equivalently state
p||
ull2
|| MaxMin(x) MaxMin(y)13
Wx Wy I
0 T
T -27
Wz Wy ReLUU(Wx) - ReL.U(W)) 20,
Re) - ReLU(Wy))
where the last inequality holds due [0, r-sstope-restrictionn of ReL.U, emp. (Fazlyab al., 2019, Lemma 1). This yields vpll - yll2 2 ||axMin(r) - MaxMin(y)lla. which completes the proof.
C.2 PROOF OF LEMMA
Let 6, denote N-dimensional unit vector whose i-th entry is and all other entries Since GroupSort preserves the sum within each subgroup, we must have e," & 1 x = e, @ 1 o(x) for all é = ,....,,.. N. This leads to the following key equality:
(r- u) v) ((Gse] @ (In, 1,, (r v) = (6(x) <(v)) ((ere) 2 (In, 1,, ()(()) - x(v)) = (ő(x) ((n)) ((Gre]) @ (In, (T,11,))( (--)))
- ()]
((ete) @ (In, T7, (d(x) - <(y)).
Therefore, we can introduce conic combinations of the subgroup constraints and obtain the following quadratic equalities:
diag(n) @ (1n, (T,
x y (xx) - Q(v)
I y
0,
diag(r) & (In, 1T,
((x)) - Φ(v)
y (xx) {1))
0 diag(v) @ (1n, 1T,))
diag(v) 2 (Ing 1T,)
I - y
0.
-2 diag(r) (v) @ (In, 1ng]
(xx) - =6())
- diag(T) (T) (1n, 17,) diag(r) (T) Ø (1n, 1
diag(? (T) 2 (1ng )T,)
x y p(x) -(v)
I- y (dx)) 2(v)
0.
By these equalities, (6) is equivalent to
x - (bx) ((v)
]
1 x y diag ()) @ In. diag(A) In xxxx) (v))
0
2
(C.1)
We can easily see that (C.1) holds because the sorting behavior in each subgroup is 1-Lipschitz i.e. lle] @ In (ar - 1| > lle] & In, (Ø(x) Φ(v)) 1 for i = 1,.... N. Hence, we have verified that the GroupSort/MaMMin activation satisfies the quadratic constraint (6).
C.3 PROOF OF LEMMA 2
First, we prove that the Householder activation satisfies three key equalities on each subgroup and then we discuss the I-Lipschitz of Householder activations. The first key equation is
- ((x)-<(v)) (In, vu vu (o(z)) d())) (x y) (In, vv T (x ((x-w/ v).
We distinguish between the cases (i) d(x) = x. Q(y) = (ii) x(z) = (Ln 2vv 2er Φ(v) = (In 2cv }y, and (iii) ((x) x, d(v) (1 - 2vv )y that without loss of generality corresponds to (bxx) (Tn, 20u )ar, Φ(v) y-
15

---

Published as a conference paper at ICLR 2024
(i (d(x) o(y)) ( (In ())()))))))))))))))))))))))))) -(v)) = (x y) 2w vv=)xx y) holds trivially.
(ii) (d(x)) <(y)) T (In, - w (b(()) - <(y))
= (x 8) (In,, 20v ) pu [ 2v0 (x - 4)
= (x- y) 7) (In, -vv (x - y) -4(x 142x(11) -yy vo' (Ing - vo ((--))= + 4(x v) T "ve" T
(u-y)
we )oo' (x y) (x y) vo (x y) holds, using that wo T (In₂ vv )oe vo
wo 0.
(iii) (6(x) o(y)) T (Ing we (d(x)) - p(v))
(x (In, 2vv )y) (Ing vv )x (Ing 200 )y
((x - y) + 200 T 8) T (Ing v0 ) ((x y) 2vu y)
= (x - y) (In, - vv )xx - y) 1(x 3) (Ing 00 joo youTy= y 4y T ov (In, - vu )oo' To
holds, again using that (In, ve T )oe' vu vo = 0.
Next we prove that the Householder activation satisfies the equation
(δ(x) - <(v)) (In - -e )x=)(x= [ u) = (x y) T (Ing vv ) - 9),
again considering the three cases (i), (ii) and (iii).
i (δ(x)) d(v)) ([,, vo (x u y) = (x - u) (Ing vv -v0))x y) holds trivially.
(i) (ó(x) <(y)) T (Ln - -v (I y)
(x y) [(n, - -200 (Ing vv )xx - 8)
= (x y) T(m(m, 3rv + 2vr wo (x y)
(x -) T(m(,, vv
vv (x - y) holds.
(ii) (ő(x) <(y)) T (In, vv vv )r y)
(x y (In, - 2cv (I,, vv [xx - 8)
= {I y) [[In, vv (x: - y) - 2y vu (Ing - vv To (x - 3)
(x y) (Ln, ve (x - y) using that ve' (In, vo vu - vw = 0.
Accordingly, we show that the Householder activation function satisfies
(Ø(x) - (dy)) (In, - co (((()) d())) = (x - 3) (In, - vu (((z)) - o(y))
() (ő(x) o(v)) ((n)))((n)) - ve (oll)) <bv)) (Ø(x) -(1)) (Kn ov )x y) holds trivially.
(i) (d(x) o(y)) T (Ln, vv
(d(()) (
- o(v))
(xr - -y) T(mn - -2vv )[ vu (p(x) -v))
= (x b) T(Tn,,, 3rv + 2vc un (0(x) - 2(v))
= (x y)T(In, ve (0(x)) )())) holds.
(ii) (d(x) d(y)) (Ln, vv (d(() - o(v))
(x y (In, - 2cv [I -v (0(x)- - dyy)
= (x y) (In, vu (x - y) - 2y vv (Ln, vu (0(x) - x(y))
(x v) [[n,, ve (d(x) d(y)), using that vv T (In, - vu = vo vo 0.
Therefore, we can introduce conic combinations of the subgroup-wise constraints and obtain the following quadratic equalities:
x diag(?) (1n, IT) p(x) (vv)
I = 0.
diag(7) @ (1ng inn diag(v) 2 (1n, IT,) 2diag(v) 2 (Ing
ddx)) 2(v)
I d(x) - x(v)
= 0,
(xx) {1v)
diag(v) @ (In, IT,)
2 diag(()) (T) 1 (1n, 1T)) diag(T) 2 (1ng mg
y
I
= 0.
(xx) (1r)
diag(T) @ (1n, 1T
((x) - ((v)
16

---

Published as a conference paper at ICLR 2024
By these equalities, (6) is equivalent to I (xx) - [(v)] ] diag(2A (A) 60 I,,
0 diag(A) Ln (0xx) (1y)
11 x - y
2 (C.2)
The Householder activation is gradient norm preserving by design as / and - 2v0 have only singular values 1. Accordingly, is 1-Lipschitz, i.e., | 2 [l0(z) eyyll holds and inequality (C.2) is conic combination of the Lipschitz property.
C.4 PROOF OF THEOREM 1
We want to prove that (9) implies (z) set x. and yd y. Then we define
fo(u)l & p||.
vll2 for any æ, y RR", To do this, we
x²
y
x
y
(C.3)
where x.¹ ((,,'' b.) and y² (x- 1--y7 y)T and its transpose, respectively. This leads to
<(Way' + b,).
Now we left and right multiply (9) with
T 2S P +
P S
A
y)
xx
y)
B
S
-T - 2P
B
pTnno
0
0
+(x yx-y))
(x - y) S 0,
W, W2
which can be rewritten
p(x"
Txx 00)
(x (.-))W7 Wi(x 1
Ax Ay
T 28
P+S
Ax Ay [o(Ax b) o(Ay b)
(C.4)
6(AA b) - (y + bb] where TT_ = [b1 by T
P+
-T-2P 2P
by b. Based on Lemma (Lemma 2), the right side of (C.4) is
guaranteed be negattgaeive. Therefore, we have
p(2" - y²) (x" 9²) - - W,, Wi(x 3/ 2221)20. 0.
Noting that fo(x) fo(u) = Wiot + bi -Wigt- - bi Wi(xt-1- y² and ~. y0 = we finally arrive at
[[((z)) fo(v)l13 s p||x - -v1
This completes the proof.
C.5 PROOF OF THEOREM 2
This theorem considers a single-layer neural network fo(x) = W22(W1z b1) +2 with fo(x) e R. Given x0, y Roa, set x! 6(W,z + b2), and y' @Way + b1). We left and right
multiply (14) with (I O
(x (x'-y') T and its transpose, respectively, and obtain
2p
0 WT (T - 21 Q
W₂ WT S)
1 x y
< 0,
(C.5)
y
W₂ T
+ S)
-T-2P
xt1 y
which is equivalent to
no
2p 22 - - >
Σ
Mi(1 - -
i=1
W1 ) 6(W120 + b1) - @(W130 +b1)
-S P+S S
P+S
Wi(2 - -1²)
-T -2
@WW1 + +b1 oWW2 +
(C.6)
17

---

Published as a conference paper at ICLR 2024
where 6; is the i-th entry of the vector (z >²) Given that we aim to find some that solves problem (13), we consider only pairs of r² y² x , that satisfy the constraints in (13). Based on these constraints, the right hand side of (C.6) has to be non-negative. This means that must have 2 W2(22 y²). Therefore, provides an upper bound for the objective of problem (13), and we have p 2 Limin- This immediately leads to the desired conclusion.
C.6 PROOF OF THEOREMS 3
Let (x, y) be defined by (C.3), We left and right multiply (15) with [1 (x (x and its transpose, respectively, and obtain
(x y)
A B
T- P+S
P+S
A
(x
y)
-
B
1
2p
Wi
1 (x - y)
0
0
1
+
S 0,
[x - y)
W1
0
which is equivalent to
ng
2p -8-2111 2Wi(=
1 2
Σ
14(1 67)+
i=1
(C.7)
Ax Ay
T 2S P
P+S
Ax Ay
6(Ax + +b (y + b)
-T-2P 2P
((Ax + b) o Ay + 6)
where 1 = bb
b2
b J. and 6e is the i-th entry of the vector (0.0 - yO). Following
the same arguments in Section C.5, we can show 2 Wi(x - -y- which leads to the desired conclusion.
C.7 PROOF OF THEOREM 4
Given x² E R" let (x') be defined by (16). Similarly, given y0 R we can calculate the output of the multi-layer residual network based on the recursion y² y + G,o(W,''
b,).
We define 3 o(W,ri=1 + b,) for i = 1, ...,.. Then we have x² - + G for i =
1, ... Via setting 300 x², we can unroll this recursive expression to obtain the following relationship:
x² +
G
Therefore, we have 3 = ((W,(1 + Σ k= GRan) + b:) for i = 1,....h.
Similarly, we define 5 6(W,)' -1 + b.). We must have j = 6(W.(5" + +E= Gxazt) + b:) for
i= I. Next, we define
b1
y
62
y
(C.8)
Then it straightforward to verify Bx Φ(Ax + b) and Bý
ó(A + b). This leads to
B(x 3) Φ1 AA b) - ②5A b)
(C.9)
18

---

Published as a conference paper at ICLR 2024
Now we left and right multiply (17) with (x y) and its transpose, respectively, and obtain
A B
-2 P S
P+5
A
(R ()
(x
9)
-T 2P
B
[11 P no
G₁
G¹
G
G
G
+ (3x y)
(x-5) S
:
G
G
c
which can be combined with (C.9) to show
p||35 - 50 ||:00
g +
Ga - -0)11
k=1
(C.10)
A Aÿ
T
25 S
P+S
A Aÿ ((x
[o(Āx -)- 6 Aý + b)]
P+
-T
(A +b)
Based on Lemma 1/Lemma we know the right side of (C.10) must be non-negative. Therefore, we have
|: 8
Ga 51 S vpli -
k=1
Recall that we have - y 1 800 and fo(x) ff(y) = o - 30 Eb Gx -1)). Hence
we have (x)) fo(v) 12 S vplz - vll2, which completes the proof.
D IMPLEMENTATION DETAILS FOR IMPROVED SCALABILITY OF THE SDP
is well-known that SDPs run into scalability problems for large-scale problems. To improve the scalability of the proposed SDPs for Lipschitz constant estimation, efforts have been made exploit the structure of the matrix that characterizes the SDP condition, using chordal sparsity (Newton & Papachristodoulou, 2023; Xue et al., 2022) or layer-by-layer interpretations (Pauli et al., 2023a). We incorporated these tricks in our implementations. In the following, we present details on our practical implementations of the SDPs based on Theorem and Theorem 3 and address some additional tricks to trade off efficiency and accuracy of the SDP.
D.1 PRACTICAL IMPLEMENTATION FOR SDP BASED ON THEOREM 1
To enhance computational tractability in large-scale problems, it is desirable to formulate layer-wise (Pauli et al., 2023a; Xue et al., 2022). To
SDP conditions rather than the sparse end-to-end make such simplifications, we set v/ = and T = O, which does not change the final solution of the above SDP for feedforward neural networks in (1). Therefore, can just set P 0. (1..
Further, we denote T, = >r + 71(,, IT,,), IT,)), which yields can equivalently be stated as
Then, (9)
blkdiag(W; TWW, TTW,W,WW,
T2W, Ti,..., W, W, T7-1) 30
(D.1)
Consequently, we can implement a set of I SDP constraints, using the blocks in the matrix in (D.1), rather than using the large and sparse condition (9). This idea follows along the lines of Newton & Papachristodoulou (2023); Xue et al. (2022), where the sparsity pattern of the block-tridiagonal LMI in Fazlyab et al. (2019) is exploited. The decomposition of the matrix in (D.1) is straightforward due to its even simpler block diagonal structure. Specifically, setting To pl, we solve the SDP
min P s. W,T.W, To 0, W.W222 31 P.
Wi_ Wi-1 Ti-1 30 (D.2)
D.2 PRACTICAL IMPLEMENTATION FOR SDP BASED ON THEOREM 3
We argue accordingly for foc Lipschitz bounds based on Theorem 3. Minimizing p subject to (15)
yields a SDP problem. For large-scale implementations, set S P 0, which reduces the
19

---

Published as a conference paper at ICLR 2024
number of decision variables without affecting the solution. Further, reorder rows and columns of the matrix in (15) by a similarity transformation. The rearranged version of the matrix in (15) has dlock-diagonal structure that leads to the following decoupled conditions with To Q:
Ti-1 W
W 2j=1
T W, 7WW; = 0, i 1,....--11
(D.3)
2p
This yields set of non-sparse constraints such that the resulting SDP can be solved in more efficient way.
D.3 TRADE-OFF BETWEEN ACCURACY AND COMPUTATIONA EFFICIENCY
In Section 5, we focus the computation times of the SDP-based methods. For completeness and to discuss the trade-off between accuracy and computational efficiency, we include computation times for the naive lg bounds FGL in this section. This involves the lower bound from sampling and the matrix product bound for all models analyzed in Table
Table 2: This table presents the computation times in seconds of all naive & bounds for the neural networks used Table 1: the sample bound evaluated on 200k samples, the FGL bound, and the matrix product bound. See Section 5 for details the bounds.
Model
L2
(units per layer)
Sample
FGL
MP
16 units
12.02
4.54
6.16
32 units
13.08
81.92
5.33
2-layer
64 units
12.84
3.95
128 units
12.61
3.6
32 units
13.18
5.43
5-layer
64 units
14.83
5.68
32 units
14.14
5.57
64 units
14.27
5.6
8-layer
128 units
14.15
9.85
256 units
13.74
9.3
32 units
23.28
7.64
18-layer
64 units
21.09
9.22
128 units
19.48
4.9
The computation of the matrix product bound (MP), while naive, is quite fast, taking less than 10 for all our models. provides reasonably accurate bounds when the number of layers is small, but becomes very loose for deep neural networks. LipSDP-NSR is comparison computationally more expensive, while providing significantly tighter bounds, cmp. Table 1. The computation of lower bound by sampling (Sample) takes between 12 and 23 on our models, which is also comparably cheap. This bound is not helpful in further verification steps but it gives an idea on the range in which the true Lipschitz constant lies. Finally. it may seem surprising at first that the computation of FGL can be computed comparably fast to LipSDP-NSH for the small models 2FC-16 and 2FC-32. However, due to the exponential complexity of this approach it becomes intractable for all larger models.
D.4 FURTHER TRICKS TO TRADE OFF EFFICIENCY AND ACCURACY OF THE SDP
Considering less decision variables per layer, emp. the variants LipSDP-Neume and LipSDP-Layer in Fazlyab et al. (2019), can be used to trade off efficiency and accuracy of the SDP.
LipSDP-NSR-Neuron-2 decision variables per group (as implemented in problem (D.2))
L-ipDD--NSR-Neuro--1 decision variable per group (7: 0, 1,...,
20

---

Published as a conference paper at ICLR 2024
Table This table presents additional results of our LipSDP-NSR method on several feed-forward neural networks trained on MNIST with more than 96% accuracy. The first table describe the result with classic training while the second table describes the results for foe adversarial training. We use the same setting as described in the paper.
Model
E
loyer)
Sample
FGL
LipSDE-NSR
MP
Sample
FGL
LiSSDPNNS
Norm Eq.
MP
Clasde Truining
unit
21.18
21:39
(76)
22.86
147.61
(149)
599.04
2-1ayer
32 units
units
20.40
17:51
20,
21.09
20.34
(279)
(152)
22.67
23.65
212.23
196.21
202.78
500.21
244.14
(425)
(220)
590.43
569.55
1164.53
782 252.25
128 unlss
16.25
19.07
(673)
21.94
179.04
257.00
(650)
533.86
1359:68
5 Jayer
64 unlls
units
107.46
101.04
176.99
132.48
(130)
(359)
250.15
166.25
1073.68
$70.29
2671.64
1688.85
(271)
(583)
4947.
5709.43
2.632405
2.96e-05
units
118.00
414.02
(188)
711.15
1353.52
5134,45
(266)
11592
1.36e-07
8 Jayer
128 uniis
uniss
$1.59
98.33
205.65
246.35
(357)
(595)
405 13
318.68
863.88
701.12
2516.24
3620.96
(294)
(912)
6897 82
5702 34
1.01ce088
3.6024077
256 units
34,83
149.0
(1337)
225 18
425.83
2133.17
(2256)
4197.25
4.22c+08
uniss
258.22
1A5cx04
(270)
7.70g4444
2335,92
1.52e405
(285)
4.06ce
2.H5ce13
18-layer
units
361.36
4.77c+00
(496)
2,05
1677.43
7.13ev05
(559)
1.34
4.03ce15
128 unils
150.60
5.56c405
(1047)
8.734406
1457.68
5, 5.704406
(1331)
1 1.5c4407
9.35c417
Adversorial trsining
18.30
14.70
15.04
17:47
92.90
421.12
255.70
3-layer
15.73
15.88
17.86
(242)
444.64
453.64
(559)
1245.44
2387.62
S-layer
62.62
(138)
(138)
596213.27
0.
(155)
1298.9
9146349
layer
138
133.30
(634)
1073.40
$309.5
12020.85
6000+0
256
176.81
694.33
(1535)
1132.61
1743.15
(7573)
19441.21
1.000+09
344.79
37785
1508.21
R0042
1.54
layer
210.53
10518
(426)
1396.26
57044
(565)
380.77
15440
(922)
2194.38
16608E+0
(1119)
LipSDP-NSR-Layer-2: 2 decision variables per layer (A1 = x22 -.. A1, 71 = 122
= 7N)
LipSDP-NSR-Laye-1 1 decision variable per layer (A1 = _... do. 71 722 ... YN = 0, equivalent to norm of weights)
Another trick is to split a deep neural network in subnetworks. The product the Lipschitz constants of the subnetworks yields a Lipschitz bound for the entire neural network.
E ADDITIONAL NUMERICAL RESULTS AND DISCUSSIONS
In Table 3, we present additional results on neural networks with the same architectures as in I that were also trained on the MNIST dataset. The upper half of Table 3 states results from classic training and the lower half from &or adversarial training.
E. MORE DISCUSSIONS ON THE NUMERICAL RESULTS IN THE MAIN PAPER
For all the models in Tables I and 3, we observe that LipSDP-NSR provides tighter Lipschitz bounds than the norm product of the weight matrices. For small neural networks, e.g., the 2-layer network with 16 units, the deviation of LipSDP-NSR to the true Lipschitz constant under the &, perturbation is especially small. We note that the computation time increases polynomial time with the number of units and decision variables. Due to the convenient biock-wise implementation of the SDP conditions, we observe good scalability of LipSDP-NSR to neural networks with an increasing number of layers, being able to handle 18-layer neural networks. In comparison to LipSDP-RR, LipSDP-NSK shows tighter bounds especially for larger neural networks and its computational advantages also become apparent for larger neural networks. Table shows that for small neural networks LipSDP- RR provides comparable bounds to LipSDP-NSR and is even evaluated faster. But for larger neural networks. the bounds of LipSDP-RA are much looser and the computation time blows up. For all models, the computation time required to solve the SDP for the l, bounds is slightly faster than the lo case. This is expected the constraints in (D.3) include larger SDP condition for the last layer
21

---

Published as a conference paper at ICLR 2024
than problem (D.2) and additional decision variables μr. We note that our lo bounds not only significantly smaller than the & bounds of the matrix norm product but also notably smaller (roughly by factor 2) than the bounds computed via lg Lipschitz bounds and the equivalence of norms.
E.2 EXTRA NUMERICAL RESULTS RESIDUAL NEURAL NETWORKS
In this section, we present numerical results of LipSDP-NSR on residual neural networks as introduced in Section 4.4. The first and the last layer of our l-layer residual neural networks are linear layers and the fully residual part consists of the remaining - layers. In our examples, we choose G; I in all residual layers. We compare our bounds to a sampling-basee where for the i-th residual layer the Lipschitz constant bounded by + [[G:|l/|WW | To compute LipSDP-NSR, we analyze the fully residual part of the neural network using SDP based on (4), Then we multiply the result with [W ||]ll] to obtain a bound for the entire network. We state the results for the choice P + 0 and 5 = well as for P = S in (17).
lower bound, and the matrix product,
Our results are summarized in Table 4. We observe that LipSDP-NSR provides more accurate Lipschitz bounds than the matrix product. The SDP condition (17) is non-sparse and in this case, it is non-trivial to break down the constraint (17) into multiple smaller constraints. This is reflected in the computation time of the SDP solution. The computation times for small residual networks lower than for small feed-forward networks, but they increase more drastically for larger residual neural networks. Comparing the results for P & O, in (17), we notice that the computation times are lower for the reduced number of decision variables (P 0), yet the accuracy of the Lipschitz bound worse for P
and the ones for P S 0. respectively,
0.
Table 4: This table presents the results of our LipSDP-NSR method on several residual neural networks trained on MNIST with more than 90% accuracy. We compare against several metrics which are described in detail in Section 5. For LipSDP-NSR, we state results choosing P o 0 and S = 0 as well choosing P S 0 in (17).
l
Model
(units per layer)
Sample
LipSDP-NSR
MP
P 0,
S
500
p
8=0
32 units
15.33
29.75
(2)
33.04
(1)
55.64
5-layer
64 units
14.28
31.40
(21)
34.64
(11)
53.25
32 units
8.99
21.34
(18)
22.98
(7)
46.60
8-layer
64 units
8.34
17.88
(371)
18.52
(115)
35.76
128 units
7.82
17.68
(4629)
18.14
(2112)
34.90
ADDITIONAL NETWORK ARCHITECTURES
F.1 SINGLE-LAYER RESIDUAL NETWORK WITH GROUPSORT/HOOUSHOODDEE ACTIVATIONS
For completeness, address the special case of single-layer residual neural network. Consider single-layer residual network model
fe(x) HAT Gio(Wi b1).
(F.I)
If ó is 1-Lipschitz, will typically use triangle inequality obtain the Lipschitz bound || ||| |[G |1 However, this bound can quite loose. If o slope-restricted on [0, 1). a variant of LipSDP (Araujo al., 2023, Theorem 4) provides improved Lipschitz bounds. Similarly, if is
GroupsSot/Householle we can apply Lemma to generalize (Araujo et al., 2023, Theorem 4) as follows.
Theorem F.1. Consider a single-layer generalized residual network (FII,, where à R - R is GroupSort (Householder) with group size ng. Denote N 21, Suppose there exist p 0. ng
22

---

Published as a conference paper at ICLR 2024
7, RY X R
such that
I H1 G1
pl
I H2
ai =
- 25] (T (T
{ -T
(F:2)
where (T,S,P) P) are given by equation (7) (equation (8)). Then fo is /p-Lipschitz the lo - l sense.
Proof. Given x. . E R we set x' = @WW1r + b1), and y² - o(Wiy +b1). We left and right
multiply (F.2) by [a - - (xt - and its transpose respectively, and obtain
P| 1 1111(22 yy Gi(z'-y')ll y
Wi(x0 - 18)
]
T
P+S ] P
Wi(x -y 6(W,>> + +b,) - o + b1)
6 2000 + b1) oW bi)
- 2P]
(F.3)
Based on Lemma 1, we know the left side of (F.3) is non-negative. Therefore, the left side of (F.3) is also non-negative. This immediately leads to the desired input-output bound.
F.2 CONVOLUTIONAL NEURAL NETWORKS WITH GROUPSORT//HOUSEHOLLEE ACTIVATIONS
All results for fully connected neural networks Section can also be applied to convolutional neural networks, unrolling the convolutional layers as fully connected matrices based Toeplitz matrices. For efficiency and scalability, SDP-based Lipschitz constant estimation has been extended to exploit the structure in convolutional neural networks (CNNs) (Pauli al., 2023a; Gramlich et al., 2023b). In particular, they use state space representation for convolutions that enables the formulation of compact SDP conditions. Combining those results with our newly derived quadratic constraint (6), we can extend our Lipschitz analysis to address larger-scale convolutional neural networks with GroupSort/Hosehollo activation functions. In this section, we briefly streamline this extension and refer the interested reader Gramlich et al. (2023b) for details.
Similar to the previous case where we modify the choice of the matrix X the original LipSDP constraint (10) to derive LipSDP-NSR, cmp. Section 3, can adapt the SDP condition in Gramlich et al. (2023b) to address CNNs with GroupSort/ousshollder activation functions via modifying a corresponding matrix using Lemma 1 Lemma 2. Specifically, setting (Q" S R") in (Gramlich et al., 2023b. Theorem 5) as Q" = T 28, S P + S. and R" = - 2P with (T, S, P) given by (7)(8) immediately leads to the modified SDD condition for Lipschitz constant estimation of CNNs with GroupSor/Householder activation functions.
F.3 DEEP EQUILIBRIUM MODELS WITH GROUPSORT//OUSSEOODDO ACTIVATIONS
In contrast to explicit feed-forward networks, we may also consider implicit learning models. In this section, we consider the so-called deep-equilibrium models (DEQ) (Bai et al.. 2019). Given imput Ra, the DEQ output is obtained by solving a nonlinear equation for the hidden variable e R4.
(WW + Ux bz), y Wo + by:
(F.4)
where W E pdxdd U E Rdxx ; W, E goxd by E Rd and by E R are the model parameters to be trained. Previously, SDP-based Lipschitz bounds for DEQs have been obtained for the case where is slope-restricted on [0, 1] (Revay et al., 2020). Here we will extend these results to the case where ø a GroupSort/Househllder activation function.
The DEQ model (F.4) is well-posed if for each input E R" there exists a unique solution 2 Rd satisfying (F.4). First, we leverage the incremental quadratic constraint in Lemma derive sufficient condition that ensures the DEQ (F.4) to be well-posed.
Theorem F.2. Consider the DEQ (F.4), where ó Idd + Rd is GroupSort (Householder) with group size Ng. Denote N d. If there exist X E R.Y. 7, M, E RRN and IT > O such thut
-III II
- 2 (P+
WTPP -0,
(F.5)
II
0
-T 2P
where (T, P) are defined by equation (7) (equation (8)), then the DEQ (F.4) is well-posed.
23

---

Published as a conference paper at ICLR 2024
Proof. If we show that the following ODE with any fixed x E R has unique equilibrium point
d dt (t) = = + @(Wz(t) + Ur b.).
(F.6)
then (F.4) is guaranteed to be well-posed. We will show that the condition F.5 guarantees that the ODE (F.6 converges globally to unique equilibrium point via standard contraction arguments. Obviously, the GroupSort/ouusholle
activation function Ø is a continuous piecewise linear mapping by nature, and hence the solutions of (F.6) well defined. Then define the difference of two arbitrary trajec- tories of DEQ (F.6) as Az(t) == xt) - 2²(t) E Rd. In general, we allow ztt) and ='(t) are generated by ODE (F.6) with different initial conditions. Next,
define V (t)(t)) == Az(t) [t). Here, V can be viewed as a weighted &2 norm, i.e., V (Az(t)) = (Az(t), (z where (--) denotes the WI-weighted inner product. For simplicity, we also denote vz (1) == (tz(t) + Ux 6). If (F:5) holds, then there exists a sufficiently small positive number such that the following non-strict matrix inequality also holds:
2 - II II +
WT
1 0.
(F.7)
11
0
(P+
-
Based on the above matrix inequality, we immediately have
=(t) (t) - (1)
-100=+#00 -()))=(())
=1) -2(1 e
]
π
=(t) =1()) (t( -0- (t)
II
0]
(0(00- =(( - 2(()
WT -S)
WT S)]
=(1) 2'(1)
+ (=(() - -=(00) (z) (t)
S.
S)W
-T- 2P
(2(()) ve-(1))
(F88
is easy to verify that the first term on the left side of (F.8) is equal to V (A=(1)) + 2 (A=( In addition, by Lemma I/Lemma 2, the second term on the left side of (F.8) is guaranteed to be non-negative due to the properties of d. Therefore, we must have
d V (Az(t)) + 2cV (Az(t)) S.
dt Now can easily see that (F.6) is contraction mapping with respect the Il-weighted & norm. The contraction rate is actually exponential and characterized by c. Since the flow map of our ODE is continuous and time-invariant existence and uniqueness of the equilibrium point for (F.6). This immediately leads to the desired conclusion.
directly apply the contraction mapping theorem to prove the
Similar to Revay et al. (2020), it is possible to simplify the matrix inequality condition in Theorem F.2 via the KYP lemma and frequency domain inequalities. Such developments are straightforward and omitted here. Given that the DEQ (F.4) is well-posed, we can combine the arguments in Revay et al. (2020) with Lemma obtain the following SDP conditions for analyzing the Lipschitz. bounds of DEQ with GroupSort/MaxMin activations.
-ogmanny-domain
Theorem F.3. Consider the DEQ (F.4) with & being GroupSort with group size ng. Suppose (F.4) is well-posed, and denote N d.
If there exist E TREN, E RN,, u E TR. and T E RRN such that
ny"
W.T.W W. 0
O LUT
WT
1PPS
T 2S
P+S
W
U
+
30
(F.9)
-pi|
P+S
-T -
1
0
where (T, S, P) are defined by equation (7) (equation (8)), then (F.4) is /p-Lipschitz x to y in the le lg sense.
Proof. Given x and x', denote the corresponding hidden DEQ variables as 2 and '', respectively. Based on (F.9), we immediately have
W
W. 0
o
x
pT
x'
(F.10)
zz
W
I
2S)
(P+S)
[W U
< 0.
x'
UT
0
(P+
-T- 2P
0
r x'
24

---

Published as a conference paper at ICLR 2024
Based on (F.4) and Lemma 1/Lemma 2, the second term the left side of (F.10) has be non- negative. Therefore, the first term on the the left side of (F.10) has to be non non-positive. Then we must have
| + by (W + b,)ll2 S vpll= x' 112.
which directly leads to the desired conclusion.
In Revay et al. (2020), SDPs that certify Lipschitz continuity have been used derive parameteriza- tions for DEQs with preseribed Lipschitz bounds. In a similar manner, our proposed SDP conditions can be used for network design. Further investigation needed address such research directions in the future.
F.4 NEURAL ODE WITH GROUFSORT/HOUUSEOODDDO ACTIVATIONS
In this section, we extend our approach to address another family of implicit learning models, namely neural ODEs (Chen et al., 2018). The neural ODE architecture be viewed as continuous-time analogue of explicit residual networks. Consider the following neural ODE:
(t) = fo(2(t). = Go (W)=(t) + Wit + bo) + bi z = x E R.;
(F.11)
dt
where fo: R R RR.h is non-autonomous vector field parameterized as neural network with trainable parameters A = (G, W. W1, bu, bj) and GrouppSort/ousehho activation ø. The input æ to the neural ODE is used as the initial condition, and the output is just the solution of the resultant initial value problem at some final time t > 0.
Since Sa is globally Lipschitz continuous in z and I, we get well-defined flow map o6 R R
which yields the following formula
$ (x)) 2(t) = x L fo(=(s)ssdds
For simplicity, we fix 1 = 1 and consider the neural ODE to be the map + that takes the input z(0) to the final output z(1) (f(x)). We can use Lemma 1/Lemma 2 to calculate Lipschitz bounds for the neural ODE flow map @ as follows.
Theorem F4. Consider the neural ODE according to (F.11), where o R R" is GroupSort (Householder) with group size ng. Denote N n. Suppose there exist > NN such that
O, X X IN Y, V
ng
-ol GT
(T- w S)W [
(P
30,
(F.12)
-T -T-2P
where (T, PT) are given by equation (7) (equation (8)), then the neural ODE flow map $ is expps/t) in the lg + b2 sense.
Proof. Given two inputs x and x', we denote the corresponding trajectories as z(() and et()). respectively. Then define the difference of these two trajectories Az(t) := z(t) - 2'( E l². In addition, we define V (Az(t)) == [t)ll and (t()) = o(Woz(t) + Wit bo). Based on condition (F.12), immediately have
=())) 21(1) (t) (t)
-ol o)
x(t) (t) (=(() (t)
GT
+ 10 1000=110 =())
1
(P 5)]
=(()) 2(1)
vz(() - (2)
SP
-T- 2P
(2(()) - (t)
< 0. (F.13)
It is easy to verify that the first term on the left side of (F.13) is equal to 4 V (Az((tt)) - PV (t)(
de
In addition, by Lemma 1 (Lemma 2), the second term on the left side of (F.13) is guaranteed to be non-negative for any t. Therefore, the following inequality holds for all t 2 0:
d v (A=(1)) S pV (A=(1))
di
25

---

Published as a conference paper at ICLR 2024
Finally, integrating V up to time 1 yields
(() ()(x') I| [|x(1) - ='(1)l22 S exp(p/2)||= ='112.
which completes our proof.
26


Reviews:
[{"review_id": "0JzgUCeEAP", "reviewer": "Reviewer_ykPt", "summary": "This paper considered the problem of estimating the Lipschitz constant of neural networks with different kinds of activations that are not slope-restricted. Particularly, the authors investigated multi-layer (residual) networks applied with the GroupSort and Householder activations. The paper followed the idea of thge LipSDP formulation of the Lipschitz parameter estimation problem, and the main contribution is that the authors devised a new quadratic constrained that can deal with GroupSort and Householder which are not slope-restricted. In addition, the authors conducted empirical experiments which showed that the new formulation with quadratic cosntraints outperforms traditional matrix-product algorithms in terms of the accuracy of the estimated Lipschitz parameter.", "questions": "How does the new formaulation compare to the original LipSDP for MaxMin networks in terms of computational efficiency/runtime?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is written clearly and the authors provided useful intuiation.\n\nThe new quadratic constraints enabled us to estimate the Lipschitz constants of neural networks with GroupSort or Householder activations with higher accuracy compared to traditional algorithms.\n\nIn addition, the authors considered both $\\ell_2$ and $\\ell_\\infty\\to\\ell_1$ lipschitz constants.", "weaknesses": "The result seems to be weak since the quadratic constraints only applied to 2 specific activations. It would be more interesting if it can be applied to a class of activaitons.", "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": "", "extra_scores": {}}, {"review_id": "V0l2lUxM5P", "reviewer": "Reviewer_8tsi", "summary": "This paper presents new semi-definite programs for computing upper-bounds on\nthe Lipschitz constants of deep neural networks with gradient-preserving\nactivations.  The authors derive new quadratic constraints which extend the\nstate-of-the-art LipSDP framework to Lipschitz estimation with the GroupSort,\nMaxMin, and Householder activation functions; these activations were previously\nnot covered by LipSDP since they do not satisfy the slope-restricted property.\nThe authors then extend their approach to compute Lipschitz constants in the\n$\\ell_\\infty$ norm and show how to apply their results to neural networks with\nresidual connections. Experiments confirm the empirical performance of the\nproposed SDPs.", "questions": "As noted above, I am not a expert on Lipschitz constant estimation for neural\nnetworks nor have I made use of algorithms from this area. Given this, can the\nauthors please provide additional details on why the GroupSort and Householder\nactivations are of particular interest for Lipschitz constant estimation? Since\nthese activations are the exclusive focus of the paper, I feel there must be an\nimmediate desire from the community to solve this problem in practice for\nthe paper to have a significant impact.\n\nI would also appreciate it if the authors could provide running times for the\nnaive estimation strategies in Table 1; this well help contextualize the cost\nof LipSDP-NSR and clarify the trade-off between accuracy and compute time. \n\nFinally, perhaps the authors can comment on the difficulty of deriving\nthe quadratic constraints for the SDPs. This will help me understand the novelty\nof the theoretical contributions.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is an interesting submission which extends the existing LipSDP framework\nfor estimating Lipschitz constants of neural networks to new activation\nfunctions. The authors use the quadratic constraint approach from control\ntheory to obtain polynomial-time algorithms for the GroupSort and Householder \nactivations (these generalize the MaxMin activation). As only naive estimation\napproaches previously existed for these activations, this contribution is fairly\nstrong and represents the major strength of this paper.\n\nOther notable strengths are the following:\n\n- The proposed SDPs yield upper-bounds for small networks which are close to\n    those obtained by brute-force search over the activation space, particularly\n    for the $\\ell_2$-norm. Moreover, the bounds are much tighter than those\n    obtained using operator norms.\n\n- The methodology is presented clearly and the manuscript is polished.", "weaknesses": "The major limitation of this work is the restriction to Householder and\nGroupSort activations. The utility of extending the LipSDP framework to these\nactivation depends directly on the how interesting the problem of Lipschitz\nestimation is for neural networks using these architectures. While the authors\nstate that such activations are becoming popular for the design of Lipschitz\nneural networks, no concrete examples are provided. I am also concerned about\nthe following:\n\n- The basic idea of LipSDP was developed by Fazlyab et al. (2019) while the \n    extension to estimation in the $\\ell_\\infty$ norm is from Wang et al. (2022).\n    The main theoretical contribution of this work is to develop new quadratic\n    constraints which fit into those frameworks, rather than build significantly\n    on top of them. Thus, the paper may be somewhat incremental in nature.\n\n- The authors do not provide the computation time for the naive baseline method\n    for approximating Lipschitz constants based on operator norms (MP),\n    so it is not clear what the trade-off between computation and accuracy is\n    for the proposed method.\n\nI am hesitant to recommend this submission for acceptance without additional \nevidence that the Householder and GroupSort activations are of practical\ninterest for Lipschitz estimation (see \"Questions\").\nMoreover, this paper is outside of my research area so it is difficult for me\nto judge its theoretical novelty; I did not check the proofs for correctness\nfor the same reason. Given this, and the smaller issues raised above, I am\n on the fence regarding this submission.", "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": "", "extra_scores": {}}, {"review_id": "uTxUeZTGIT", "reviewer": "Reviewer_pJPd", "summary": "This paper extends the method of estimating the Lipschitz constant of a neural network using semidefinite programming (SDP) to the networks with non-slope-restricted activations functions such as GroupSort, Maxmin, and Householder. The SDP formulations are proposed for estimating $l_2$ and $l_\\infty/l_1$ Lipschitz constants for various network architectures.", "questions": "1. How frequently are GroupSort, Maxmin, and Householder being used in practice? If they are not so popular, why we are studying LipSDP for them?\n2. This is merely a comment. The results would be more interesting and valuable if using GroupSort, Maxmin, and Householder activations have some implicit bias towards having an NN with a smaller Lipschitz constant.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. well-written, easy to follow even for a non-expert.\n2. The extension of LipSDP to GroupSort, Maxmin, and Householder activations is new.", "weaknesses": "The main concern I have is that this paper seems to be an extension of two works Fazlyab'19 and Wang'22 to the case of having sum-preserving activations like GroupSort, Maxmin, and Householder, which seems incremental.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)