A Unified Algebraic Perspective on Lipschitz Neural Networks
Authors: Alexandre Araujo
Aaron J Havens
Blaise Delattre
Alexandre Allauzen
Bin Hu
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Deep Learning
Lipschitz neural networks
Robustness

Abstract: Important research efforts have focused on the design and training of neural networks with a controlled Lipschitz constant. The goal is to increase and sometimes guarantee the robustness against adversarial attacks. Recent promising techniques draw inspirations from different backgrounds to design 1-Lipschitz neural networks, just to name a few: convex potential layers derive from the discretization of continuous dynamical systems, Almost-Orthogonal-Layer proposes a tailored method for matrix rescaling. However, it is today important to consider the recent and promising contributions in the field under a common theoretical lens to better design new and improved layers. This paper introduces a novel algebraic perspective unifying various types of 1-Lipschitz neural networks, including the ones previously mentioned, along with methods based on orthogonality and spectral methods. Interestingly, we show that many existing techniques can be derived and generalized via finding analytical solutions of a common semidefinite programming (SDP) condition.  We also prove that AOL biases the scaled weight to the ones which are close to the set of orthogonal matrices in a certain mathematical manner. Moreover, our algebraic condition, combined with the Gershgorin circle theorem, readily leads to new and diverse parameterizations for 1-Lipschitz network layers. Our approach, called SDP-based Lipschitz Layers (SLL), allows us to design non-trivial yet efficient generalization of convex potential layers.  Finally, the comprehensive set of experiments on image classification shows that SLLs outperform previous approaches on certified robust accuracy. Code is available at https://github.com/araujoalexandre/Lipschitz-SLL-Networks.

Published as a conference paper at ICLR 2023
A UNIFIED ALGEBRAIC PERSPECTIVE ON LIPSCHITZ NEURAL NETWORKS
Alexandre Araujo'!, Aaron Havens Blaase Delattre Alexandre Allauzen and Bin Hu?
INRIA, Ecole Normale Supérieure, CNRS, PSL University, Paris, France
CSL & ECE, University of Illinois Urbana-Champaign, IL, USA
3 Miles Team, LAMSADE, Université Paris-Dauphine, PSL University, Paris, France Foxstream, Vaulx-en- Velin, France
ESPCI PSL, Paris, France
ABSTRACT
Important research efforts have focused on the design and training of neural net- works with controlled Lipschitz constant, The goal is increase and sometimes guarantee the robustness against adversarial attacks. Recent promising techniques draw inspirations from different backgrounds design I-Lipschitz neural net- works, just to name few: convex potential layers derive from the discretization of continuous dynamical systems, Mimost-Orhooonal--Eee method for matrix rescaling. However, it is today important to consider the re- cent and promising contributions in the field under a common theoretical lens to better design new and improved layers. This paper introduces novel algebraic perspective unifying various types of 1-Lipschitz neural networks, including the ones previously mentioned, along with methods based on orthogonality and spec- tral methods. Interestingly, we show that many existing techniques can be derived and generalized via finding analytical solutions of common semidefinite pro- gramming (SDP) condition. We also prove that AOL biases the scaled weight to the ones which are close to the set of orthogonal matrices in certain mathemat- ical manner. Moreover, our algebraic condition, combined with the Gershgorin circle theorem, readily leads new and diverse parameterizations for 1-Lipschitz network layers. Our approach, called SDP-based Lipschitz Layers (SLL), allows us to design non-trivial yet efficient generalization of convex potential layers. Fi- nally, the comprehensive set of experiments on image classification shows that SLLs outperform previous approaches on certified robust accuracy. Code is avail- able at gi github. com/araaaaaaoo com/arrauoaaeexndde hwweaaannnreeiieiiiieeeaaee Lipschit chitteite SLL--LL- Wewoos......
proposes a tailored
INTRODUCTION
The robustness of deep neural networks is nowadays a great challenge establish confidence in their decisions for real-life applications, Addressing this challenge requires guarantees on the sta- bility the prediction, with respect to adversarial attacks. In this context, the Lipschitz constant of neural networks is key property at the core of many recent advances. Along with the margin of the classifier, this property allows us certify the robustness against worst-case adversarial perturba- tions. This certification is based on a sphere of stability within which the decision remains the same for any perturbation inside the sphere (Tsuzuku al., 2018).
The design of 1 1-Lipschitz layers provides a successful approach to enforce this property for the whole neural network. For this purpose, many different techniques have been devised such as spec- tral normalization (Miyato al., 2018; Farnia et al., 2019), orthogonal parameterization (Trockman et al., 2021; Li et al., 2019; Singla et al., 2021; Yu et al., 2022: Xu et al., 2022), Convex Potential Orterst-OOtooonnlloo
Layers (CPL) (Meunier et al., 2022), and While all these techniques share the same goal, their motivations, and derivations can greatly differ,
(AOL) (Prach et al., 2022).
Equal contribution.

---

Published as a conference paper at ICLR 2023
delivering different solutions. Nevertheless, their raw experimental comparison fails to really gain insight into their peculiar performance, soundness, and in the end their possible complementarity. Therefore question acts as a barrier for an in-depth analysis and future development:
Are there common principles underlying the developments of I-I.ipschizz Layers?
In this paper, we propose novel perspective answer this question based on a unified Semidefinite Programming (SDP) approach. We introduce a common algebraic condition underlying various types of methods like spectral normalization, orthogonality- key insight is that this condition can be formulated as a unifying and simple SDP problem, and that the development of I-Lipschitz architectures systematically arise by finding "analytical solutions" of this SDP. Our main contributions are summarized as follows.
methods, AOL, and CPL. Our
We provide a unifying algebraic perspective for 1-Lipschitz network layers by showing that exist- ing techniques such as spectral normalization, orthogonal parameterization, AOL, and CPL can all be recast as a solution of the same simple SDP condition (Theorem and related discussions). Consequently, any new analytical solutions of our proposed SDP condition will immediately lead to new I-Lipschitz network structures.
Built upon the above algebraic viewpoint, we give a rigorous mathematical interpretation for AOL explaining how this method promotes "almost orthogonality" in training (Theorem 2).
Based on our SDPs, new family of 1-Lipschitz network structures termed as SDP-based Lips- chitz layers (SLL) has been developed. Specifically, we apply the Gershgorin circle theorem to obtain some new SDP solutions, leading to non-trivial extensions of CPL (Theorem 3). We derive new SDP conditions to characterize SLL in very general form (Theorem 4).
Finally, we show, by comprehensive set of experiments, that our new SDP-based Lipschitz layers outperform previous approaches on certified robust accuracy.
Our work inspired by Fazlyab al. (2019) that develops SDP conditions for numerical estimation of Lipschitz constants of given neural networks. A main difference is that we focus on "analytical SDP solutions" which can be used to characterize I-Lipschitz network structures.
2 RELATED WORK
In recent years, certified methods have been central to the development of trustworthy machine learning and especially for deep learning. Randomized Smoothing (Cohen et al., 2019; Salman al., 2019) is one of the first defenses offer provable robustness guarantees. The method simply extends a given classifier by the smart introduction of random noise to enhance the robustness of the classifier. Although this method offers an interesting level of certified robustness, it suffers from important downsides such as the high computational cost of inference and some impossibility results from information-theory perspective (Yang et al., 2020; Kumar et al., 2020).
Another approach to certify the robustness of classifier is to control its Lipschitz constant (Hein et al., 2017: Tsuzuku et al., 2018). The main idea is to derive a certified radius in the feature space by upper bounding the margin of the classifier. See Proposition I of Tsuzuku et al. (2018) for more details. This radius, along with the Lipschitz constant of the network can certify the robustness. In order reduce the Lipschitz constant and have non-trivial certified accuracy, Tsuzuku et al. (2018) and Leino et al. (2021) both upper bound the margin via computing a bound on the global Lipschitz constant, however, these bounds have proved to be loose. Instead of upper bounding the global Lipschitz constant, Huang et al. (2021b) leverages local information to get tighter bound on the Lipschitz constant. On the other hand, other works, instead of upper bounding the local or global Lipschitz, devised neural networks architecture that are provably I-Lipschitz. One of the first approaches in this direction consists of normalizing each layer with its spectral norm (Miyato et al., 2018; Farnia et al., 2019). Each layer is, by construction, 1-Lipschitz. Later, a body of research replaces the normalized weight matrix by an orthogonal matrix. improves upon the spectral normalization method by adding the gradient preservation (Li et al., 2019; Trockman et al., 2021: Singla et al., 2021; Yu et al., 2022; Xu et al., 2022). These methods constrain the parameters by orthogonality during training. Specifically, the Cayley transform weights (Trockman et al., 2021) and, in a similar fashion, SOC (Singla et al., 2021) parameterizes their layers with the exponential of skew symmetric matrix making it orthogonal. To reduce cost,
be used to constrain the
2

---

Published as a conference paper at ICLR 2023
Trockman et al. (2021), Yu et al. (2022), and Xu al. (2022) orthogonalize their convolutional kernel in the Fourier domain.
More recently, work by Meunier et al. (2022) has studied Lipschitz networks from dynamical system perspective. Starting from the continuous view of residual network, they showed that the parameterization with the Cayley transform (Trockman al., 2021) and SOC (Singla et al., 2021) correspond respectively to two specific discretization schemes the continuous flow. Furthermore, a new layer is derived from convex potential flows to ensure the 1-Lipschitz property":
= x
W
Wo +),
(1)
where || is the spectral norm of the weight matrix W and a is the ReLU activation function. In general, the training of orthogonal layers can be expensive. The Cayley approach involves matrix inversion, and the implementation of SOC requires either an SVD or an iterative Taylor expansion. The C approach can be more efficient, although the computation of [W]]2 still needed.
A recent work, Momoos-Orthogonll-ae a new normalization which makes the layer I-Lipschitz by favoring orthogonality. The fully- connected AOL layer is defined as W Dæ + b where D is diagonal matrix given by?:
(AOL) (Prach et al., 2022) came up with middle ground:
D diag
E, I (WWT)
They demonstrated that this layer is 1 I-Lipschitz and they empirically show that, after training, the Jacobian of the layer (with respect to x) almost orthogonal, hence facilitating the training.
Another source of inspiration is the application of convex programs for robustness certification of neural networks (Wong et al., 2018; Raghunathan et al., 2018; Fazlyab et al., 2019; Revay et al., 2020; Fazlyab et al., 2020; Wang et al., 2022). The most relevant work is Fazlyab et al. (2019), which leverages the quadratic constraint approach from control theory (Megretski et al., 1997) to formulate SDPs for estimating the global Lipschitz constant of neural networks numerically. It is possible to solve such SDPs numerically for training relatively small Lipschitz networks (Pauli et al., 2021). However, due to the restrictions of existing SDP solvers, scalability has been one issue when de- ploying such approaches to deep learning problems with large data sets. Our focus is on the design of Lipschitz network structures, and we avoid the scalability issue via solving SDPs analytically.
BACKGROUND
Notation. The x n identity matrix and the X n zero matrix are denoted as In and O,, re- spectively. The subscripts will be omitted when the dimension is clear from the context. When a matrix P negative semidefinite (definite), we will use the notation P < (<)0. When a matrix P is positive semidefinite (definite), we will use the notation P > (>)0. Let denote the vector whose i-entry is 1 and all other entries are Given collection of scalars {a:)= we use the notation diag(a;) (a:) to denote the n x n diagonal matrix whose (i, i)-th entry is a, For a matrix A, the following notations AT. || 2|. tr(A), miin (A), ||A|]e. p. and p( ()) stand for its transpose, largest singular value, trace, smallest singular value, Frobenius norm, and spectral radius, respectively.
Lipschitz functions. A function f R + R is L-Lipschitz with respect to the & norm iff it satisfies [I - (w)ll < L|| - yll for all x,y E R", where ||-I| stands for the l2 norm. An important fact is that the robustness of neural network can be certified based on its Lipschitz constant (Tsuzuku et al., 2018). In this paper, we are interested in the case where L we consider the training of I-Lipschitz neural networks. If each layer of a neural network is 1- Lipschitz, then the entire neural network is also I-Lipschitz. The Lipschitz constant also satisfies the triangle inequality, and hence convex combination will preserve the 1-Lipschitz property.
Specifically,
Matrix cones: Positive semidefiniteness and diagonal dominance. Let S" denote the set of all x n real symmetric matrices. Let ST. S be the of all x symmetric positive semidefinite
We reverse the transposition from the original layer to have a consistent notation in the rest of the article. For simplicity, we assume all the columns of W have at least one non-zero entry. Then (2) is well defined.
3

---

Published as a conference paper at ICLR 2023
matrices. It is well known that St is closed-pointed convex in S With the trace inner product, S is also self-dual. Consider two symmetric matrices A and B such that A > B S", then we have A B E S and (r - B) provides distance measure between A and B. In addition, we have || - B S tr( A - B). Finally, the set of all n x n real symmetric diagonally dominant matrices with non-negative diagonal entries is represented by D It is known that D forms a closed, pointed, full cone (Barker et al., 1975). Based on the Gershgorin circle theorem (Horn et al., 2012), we know D S is also known that D is smaller than S (Barker al., 1975). For any A E D", we have AH 2 Σn |Ayl. It is important to require Aü 2 0, and the set of real symmetric diagonally dominant matrices not a cone by itself.
4 AN ALGEBRAIC UNIFICATION OF 1-LIPSCHITZ LAYERS
In this section, present unified algebraic perspective for various I-Lipschitz layers (Spectral Normalization, Orthogonalization, AOL, and CPL) via developing a common SDP condition char- acterizing the Lipschitz property. Built upon algebraic viewpoint, also present new mathe- matical interpretation explaining how AOL promotes orthogonality in training.
4.1 THE UNIFYING ALGEBRAIC CONDITION
First, we present an algebraic condition which can be used to unify the developments of existing techniques such as SN, AOL, and CPL. Our main theorem is formalized below.
Theorem 1. For any weight matrix W E Rmxx, if there exists nonsingular diagonal matrix T such that WWW - T - 0, then the two two following statements hold true.
1. The mapping g(x) = WT $ b 1-Lipschitz.
2. The mapping h(x) -------25 2w oooo (W +b) is 1-Lipschitz if is ReLU, tanh sigmoid.
The proof of the above theorem and some related control-theoretic interpretations the appendix. This theorem allows us to design different I-L-iscchitz layers just with various choices of T, in two important cases: for linear transformation with Statement 1, as well as for residual and non-lincar block with Statement Moreover, for any given weight matrix W, the condition WTW < T is linear in T, and hence be viewed as SDP condition with decision variable T. To emphasize the significance for designing I-Lipschitz layers by choosing specific T for the SDP condition WW < T. The 1-Lipschitz property is then automatically obtained.
provided in
this theorem, we propose to derive existing methods used
Spectral Normalization (SN) corresponds to an almost trivial choice if we notice that WTW 3 W I [ T. Hence with T [[W|T, we build the SN layer ((x) = WT-1p 1r - [W1, W
The Orthogonality- parameterization is obtained by setting T I and enforcing the equality W WTW T = I. Then obviously g(z) = W r + bs I-Lipschitz.
WTT))))) With this choice, we have T WTW n C ST, hence W W T. Then Statement in Theorem implies that the AOL layer, written as g(x) = WT 2x + b, is I-Lipschitz."
AOL formula can be derived by letting T = diag Σ
CPL follows the same SN choice T = || [ but with Statement 2 of Theorem 1. Hence we derive a different function h(x) x TWT3
W (W +b) which is also I-Lipschitz.
The above discussion illustrates the benefit of expressing all these methods within the same the- oretical framework, offering us new tool to characterize the similarity between different meth- [[]]| The difference be-
ods. For instance, SN and CPL share the same choice of tween them is which statement is used. Hence CPL can be viewed as the "residual version" of
FFor ease of exposition, our main paper always assumes that all the columns of W have at least one non- entry such that (2) is well defined. To drop this assumption, we use variant of Theorem which replaces the SDP condition with bilinear matrix incquality condition. We will discuss this point in the appendix.
4

---

Published as a conference paper at ICLR 2023
SN. Clearly, the residual network structure allows CPL address the gradient vanishing issue more efficiently than SN. With the same approach, we can readily infer from our unified alge- braic condition what are the "residual" counterparts for orthogonality-base basee parameterization and AOI. For orthogonality-based parameterization, if we enforce WTW W = T == T via methods such SOC and ECO, then the function h(x) x 2Wo(WT. + b) is I-Lipschitz (by State-
IW [WTW,;)) then the function ment 2 in Theorem 1). Finally, if we choose T diag |
(WT oW b) is also I-Lipschitz. Therefore it is straight- forward to create new classes 1-Lipschitz network structures from existing ones.
h(x)= = x - 2W diag -
Another important consequence of Theorem 1 is about new layer development. Any new nonsingu- lar diagonal solution for the SDP condition WTW 3 immediately leads to new 1-L-pschitz network structures in the form of g(x) WT- + b h(x) = x - 2WT x + b). There- fore, the developments of 1-Lipschitz network structures be reformulated finding analytical solutions the matrix inequality W W W = T with nonsingular diagonal T. As a matter of fact, the Gershgorin circle theorem can help improve the existing choices of ' in a systematic way. In Section 5, we will discuss such new choices of 7 and related applications to improve CPL. At this point, worth noticing that to develop deep Lipschitz networks, important to have analytical formulas of T. The analytical formula of T will enable a fast computation of WT & or WT-1
Theorem 1 is powerful in building a connection between I-Lipschitz network layers and the alge- braic condition WTW T. Next, we will look closer at this algebraic condition and provide new mathematical interpretation explaining how AOL generates "almost orthogonal" weights.
The proof of Statement 2 in Theorem I relies on (Fazlyab et al., 2019, Lemma 1), which requires the activation function a to be slope-restricted on [0, 1]. Therefore, Statement 2 cannot be applied to the case with being the GroupSort activation function (Anil et al., 2019). In contrast, Statement can be used to build neural networks with any activation functions which are I-Lipschitz
Remark 1.
funcction
4.2 A NEW MATHEMATICAL INTERPRETATION FOR AOL
In Prach et al. (2022), it is observed that AOL can learn "almost orthogonal" weights and hence overcome the gradient vanishing issue. As a matter of fact, the choice of T' used in AOL is optimal in specific mathematical sense as formalized with the next theorem.
Theorem 2. Given any W mRx which does not have zero columns, define the set T [T: iss nonsingular diagonal, and T - WTW E DD). Then the choice of for the AOL method actually satisfies
T diag(
W WTWW
arg min (rl 3 3T arg min T WT 1|| TET
TET
We defer the proof for the above result to the appendix. Here we provide some interpreta- tions for the above result. Obviously, the quantity - - [|]F provides mea- sure for the distance between the scaled weight matrix WT-3 and the set of n orthogo- nal matrices. If ||T à WTTTT [|]F O, then the scaled weight WT- is orthogonal. If -
F|| is small, means that WT-1 2 "almost orthogonal" and close to the set of orthogonal matrices. Since we require WWW - T < O, we know that / - 7- TTTW- is a positive semidefinite matrix, and its trace provides an alternative metric quantifying the distance between WT- and the set of orthogonal matrices. Importantly, we have the following inequality:
IT i WT AllF s tr(1 T W WWT
FFr(--T-1WTW7-1 is small, then WT-WWTTT to the set of orthogonal matrices. Therefore, one interpretation for Theorem 2 is that among all the nonsingular diagonal scaling matrices 7' satisfying
T|| is also small, and WT is close
W 1 E D", the choice of T used in AOL makes the scaled weight matrix WT-$ & the closest to the set of orthogonal matrices. This provides new mathematical explanation of how AOL can generate "almost orthogonal" weights.
5

---

Published as a conference paper at ICLR 2023
One potential issue for AOL is that D is typically much smaller than S and the condition T WTW E D may be too conservative compared to the original condition T WTW E St in Theorem 1. If we denote the set T = {T : T is nonsingular diagonal, and T - W E S } then we have arg mrg tr(I T W WT S arg minrer tr - T WTWT -), and arg m - WT - F I arg minrer|l?- W /|/.. This leads to inter- esting alternative choices of T which can further promote orthogonality:
= arg min| W WT TET
I||F or T arg min tr(l - T W WTW
(3)
TET
Although (3) may be solved as convex programs on small toy examples, it is not practical to use such choice of T for large-scale problems. It is our hope that our theoretical discussion above will inspire more future research on developing new practical choices of T for promoting orthogonality.
5 EXTENSIONS OF CPL: THE POWER OF GERSHGORIN CIRCLE THEOREM
In this section, we extend the original CPL. layer (5) a new family of I-Lipschitz network struc- tures via providing new analytical solutions to our condition WTW 3 T. We term this general family of layers as SDP-based Lipschitz layers (SLL), since the condition W W < T can be viewed as an SDP for the decision variable T. First of all, we extend the existing CPL (Eq. (1)) via applying more general choices of T with Theorem 1. From the discussion after Theorem 1, already know that we can the choice of T = diag ( [WTW);)) to replace the original choice T = ||W Il In this section, we will strengthen CPL via an even more general choice of T, which is based on a special version of Gershgorin circle theorem. Specifically, we will apply (Horn et al., 2012, Corollary 6. 6.) to show the following result.
Theorem 3. Let W be the weight matrix. Suppose T is a nonsingular diagonal matrix. If there exists some diagonal matrix Q with all positive diagonal entries such that (T QWTQQ is real diagonally dominant matrix with diagonal entries being all positive, then T 2 W, and the function h(x) = x - 2WT o (WT x + b) is I-Lipschitzfor for a being ReLU, tanh or sigmoid.
We defer the proof of this result to the appendix. If we choose Q = L, the above theorem just recovers the choice of I' used in AOL, i.c. T diag(E; j= (WTWlys). However, it is expected that the use of more general Q will allow to train less conservative 1-Lipschitz neural network due to the increasing expressivity brought by these extra variables. We will present numerical results to demonstrate this. We also emphasize that (T QWTWQ=1) is typically not a symmetric matrix and hence is not in D even when it only has non neg-nteaaive eigenvalues. However, this does not affect our proof on the positive-emmidefniiness of (T WT)..
Application of Theorem 3. entry of QWTWQ-I equal (WTW), W))g;;/9 Hence we can just set the diagonal entry of T
We can parameterize Q diag(g:) with q; > O. Then the (i. -)th
(W W We/g///ll Σ
W Who
Dj 4
This leads to our new choice of T = diag(E)- Wls9//.).. Notice that the layer function Mxx) x x 2 x++b) has a residual network structure. Hence it is expected that vanishing gradient will not be an issue. Therefore, we can simultancously optimize the training loss over W and {q, J. We will present a numerical study to demonstrate that such training approach will allow us to generate competitive results on training certifiably robust classifiers.
SDP conditions for more general network structures. It is also worth mentioning that the SDP condition in Theorem I can be generalized to address the following more general structure:
h(())= = Hx + Go x xx++0 +b,,
(5)
where H and G will be determined by the weight W in some manner, and the matrix dimensions are assumed to be compatible. we choose H- and G = -2WT-1 then (5) reduces to the residual network structure considered in Theorem 1. There are many other choices of (H, G) which can also ensure (5) to be I-Lipschitz. Our last theoretical result is a new SDP condition which generalizes Theorem and provides more comprehensive characterization of such choices of (H, G).

---

Published as a conference paper at ICLR 2023
Table 1: This table presents the natural, provable accuracy well the number of parameters and training time several concurrent work and our SLL networks CIFARIO dataset. results for SLL networks are the result of the average of trainings.
Natural Accuracy
Provable Accuracy (e)
Number of Parameters
Time by Epoch
Models
1
GloRo (Leino 2021)
77.0
58.4
8M
Local-Lip-BB (Huang
77.4
60.7
39.0
20.4
2.3M
Cayley Large (Trockman et al., 2021)
74.6
61.4
46.4
32.1
21M
30
SOC 20 (Singla et 2021)
2021)
78.0
62.7
46.0
30.3
27M
52
SOC+ 20 (Singla al. 20226)
76.3
62.6
48.7
36.0
27M
52
CPL XL (Meunier
2022)
78.5
64.4
48.0
33.0
236M
163
AOL Large (Prach et al., 2022)
71.6
64.0
56.4
49.0
23.7
136M
64
SLL Small
71.2
62.6
53.8
45.3
20.4
41M
20
SLL Medium
72.2
64.3
56.0
48.3
23.9
78M
35
SLL Large
72.7
65.0
57.3
49.7
25.4
118M
55
SLL X-Large
73.3
65.8
58.4
51.3
27.3
236M
105
Theorem 4. Let be the neuron number. For any non-negative scalars {M define
A = diag(A1 ,2...., An).
(6)
Suppose the activation function is ReLU tanh sigmoid. there exist non-negative scalars {>r)==1 such that the following matrix inequality holds
T- HTTH -HTG WA
2A G
then the network layer (5) is 1-Lipschitz, i.e., [[((z) h(y] S o yll for all (z, y).
The above theorem be proved via modifying the argument used in Fazlyab al. (2019, Theo- rem 1yt and we defer the detailed proof to the appendix. On one hand, if we choose H = 0, then our condition (7) reduces
variant of Theorem in Fazlyab al. (2019). $ On the other hand, for residual network structure with // L, we can choose 7 2A and G -WA = 2 reduce (7) to our original algebraic condition T > WTW Therefore, Theorem provides connection between the SDP condition in Fazlyab et al. (2019) and our proposed simple algebraic condition in Theorem 1. It is possible to obtain new 1-Lipschitz network layers via providing new analytical solutions to (7). It is our hope that our proposed SDP condition (7) can lead to many more 1-Lipschitz network structures in the future.
EXPERIMENTS
In this section, we present comprehensive set of experiments with 1-Lipschitz neural networks based on our proposed SDP-based Lipschitz Layer. More specifically, we build I-Lipschitz neural networks based on the following layer:
(xx) 2W diag
Σ [ W/lll//g//
o xb)).
where W is parameter matrix being either dense or a convolution, {q:} forms diagonal scaling matrix as described by Theorem 3, and a--) the ReLU nonlinearity function. We the same architectures proposed by Meunier et al. (2022) with small, medium, large and xlarge sizes. The architecture consists of several Conv-SLL and Linear-SLL. For CIFAR-100, we use the Last Layer Normalization proposed by Singla et al. (2022h) which improves the certified accuracy when the number of classes becomes large. Note that the layer presented in Equation (8) can be easily im- plemented with convolutions following the same scaling as in Prach et al. (2022). Our experiments focus on the impact of the Lipschitz layer structures on certified robustness. This complements recent study other aspects (e.g. projection pooling) of robust networks (Singla et al., 2022a).
As commented in Pauli et al. (2021), such a modification works as long as A is diagonal.
To this connection, (o, W W = (0, 1, W., G) in Theorem I of Fazlyab (2019).

---

Published as a conference paper at ICLR 2023
Table This table presents natural and provable accuracy of several concurrent works and our SLL net- works on CIFAR 100 and TinylmageNet datasets, SLL. networks are averaged of 3 trainings.
Natural Accuracy
Provable Accuracy (E)
Datasets
Models
36 255
T2 255
108 255
Cayley Large (Trockman al., 2021)
43.3
29.2
18.8
11.0
SOC 20 (Singla 2021)
48.3
34.4
22.7
14.2
SOC+ 20 (Singla et al., 2022b)
47.8
34.8
23.7
15.8
CPL XL
(Meunier et al., 2022)
47.8
33.4
20.9
12.6
AOL Large (Prach et ol., 2022)
43.7
33.7
26.3
20.7
7.8
CIFARI00
SLL Small
44.9
34.7
26.8
20.9
8.1
SLL Medium
46.0
35.5
27.9
22.2
9.1
SLL Large
46.4
36.2
28.4
22.7
9.6
SLL X-Large
46.5
36.5
29.0
23.3
10.4
GloRo (Leino 2021)
35,5
22.4
Local-Lip-B (+MaxMin) (Huang et al., 2021b)
36.9
23.4
12.7
6.1
0.0
SLL Small
26.6
19.5
14.2
10.4
2.9
TinylmageNet
SLL Medium
30.4
22.3
15.9
11.6
3.0
SLL Large
31.3
23.0
16.9
12.3
3.3
SL. X-Large
32.1
23.2
16.8
12.0
3.2
Details on the architectures & Hyper-parameters. Table 3 describes the detail our Small, Medium, Large and X-Large architectures. We trained our net- works with a batch size of 256 over 1000 epochs with the data augmentation used by We use an Adam opti- mizer (Kingma et al., 2014) with 0.01 learning rate and parameters 31 and 83 equal to 0.5 and 0.9 respectively and no weight decay. We use piecewise triangular learning rate scheduler to decay the learning rate during training. We use the CrossEntropy loss as in Prach al. (2022) with a temperature of 0.25 and an offset value 3 3.2.
Table SLL architecture used for experiments is inspired by Meunier el al..
5
M
XI.
Conv-SLL
20
120
Channels Linear-SLL
45
60
70
10
15
Linear Features
2048
2048
4096
4096
Results in terms of Natural and Certified Accuracy CIFARI0/100. First, evaluate our networks (SLL) on CIFARIO and CIAFR 100 and compare the results against recent I-Lipschitz neural network structures: Cayley. SOC, SOC+, CPL and AOL. We also compare SLL with two other Lipschitz training approaches (Leino et al., 2021; Huang et al., 2021b), which do not guaran- tee prescribed global Lipschitz bounds during the training stage. Table presents the natural and certified accuracy with different radius of certification on CIFAR10. For fair comparison, param- eter number and training time per epoch for each method are also added Table Results on CIFAR 100 are included in Table 2. We can see that our approach outperforms existing 1-Lipschitz architectures including AOL and CPL on certified accuracy for all values of E. We also observe that SLL-based 1 1-Lipschitz neural networks offer good trade-off among previous approaches with respect to natural and certified accuracy. A detailed comparison is given below.
Ad Advantages of SLL over Cayley/SOC. In general, it difficult to compare the expressive power of non-residual and residual networks. Hence we do not claim that with the same model size, SLL is more representative than Cayley or SOC which are not residual networks in the first place. However, we believe that the current choice T in SLL is very easy calculate and hence leads to scalable approach that allows us to train very large models with a reasonable amount of time. For illustrative purposes, consider the comparison between SLL and Cayley in Table 1. We can see that SLL Small has more parameters than Cayley Large (41M vs. 21M) while being faster to train. Indeed, the Cayley approach involves computing expensive orthogonal projection (with a matrix inverse), while SOC requires to the computation of several convolutions at training and inference (from 6 to 12) to compute the exponential of a convolution up to a desired precision. Hence the training time epoch for Cayley Large and SOC is actually longer than SLL Small. While being faster to train SLL Small still outperforms Cayley Large and SOC for all three values of general, we think it is fair to claim that our approach is more scalable than previous approaches based on orthogonal layers, and allows the use larger networks which leads to improvements in certified robustness.
8

---

Published as a conference paper at ICLR 2023
Table 5:
The table describes the empirical robustness of our SLL-based classifiers CIFARIO CIFARIOO datasets. The empirical robustness is measured with AutoArtacks. results are the average of models.
CIFAR10 AutoAttack (E)
CIFAR100 -AttoAttack (E)
Models
36
108
72
255
255
255
255
255
255
SLL Small
68.1
62.5
56.8
35.0
40.7
35.2
30.4
17.0
SLL Medium
69.1
63.8
58.4
37.0
41.5
36.4
31.5
17.9
SLL Large
69.8
64.5
59.1
37.9
42.1
37.1
32.6
18.7
SLL X-Large
70.3
65.4
60.2
39.4
42.7
37.8
33.2
19.5
Advantages of SLL over AOL/CPL. With careful tuning of the offset value, SLL outperforms AOL for all values of We experiment with several offset values: /2, 3/2 22 and 2v2. The detailed results for all these different offset values are deferred to Table 6 in the appendix. In general, the offset value offers a trade-off between natural accuracy and robustness, thus, by choosing the offset value properly, SLL Large already achieves better results than AOL Large (notice that the training time per epoch for these two is roughly the same). SLL X-Large has even more improvements. We can also see that SLL Large outperforms CPL XL for all values of while being faster to train. For larger value of e, the gain SLL over CPL remarkable (over 10%).
Results on TinylmageNet. We have also implemented SL.. on TinylmageNet (see Table 2). Previously, other I-Lipschitz network structures including SOC, Cayley, AOL, and CPL have not been tested on Tmnylmag,Net, and the state-of-the- art approach TinyImageNet is the local Lipschitz bound approach (Huang et al., 2021a). We can see that SLL signif- icantly outperforms this local Lipschitz approach for larger values of & (while generating similar results for the small case). Notice that the local Lipschitz approach (Huang al., 2021a) is quite different from other 1-Lipschitz network methods in the sense that it has no guar- antees on the Lipschitz constant of the resultant network and hence does not generate 1-Lipschtiz networks in the first place. Furthermore, given that this approach does not guarantee Lipschitz bound during training, a lot more computation needs to be performed during inference, making the certification process very time consuming. Table 4 describes the inference time on TinylmageNet for this local Lipschitz approach and SLL X-large.
Table Inference time Local-Lip- and SLL X-Large on the full Tinylm- ageNet validation with 4 GPUs.
Models
Inference Time
Local-Tip-B
41 min 8 sec
SL. X-Large
Results on Empirical Robustness. We also provide results of our approach on empirical robust- ness against an ensemble of diverse parameter-free attacks (i.e, AutoArtacks) developed by Croce et al. (2020b). Table 5 reports the empirical robustness accuracy for different levels of perturbations. Although AutoAttacks is a strong empirical attack consisting of an ensemble of several known at- tacks: APGDCE- APGDDLR. FAB (Croce et al., 2020a) and Square (Andriushchenko et al., 2020). We can observe that the measure robustness is high and well above the certified radius. Indeed, on CIFARI0 10, observe robustness "gain" of up to 4.5%, 9.6%, 14. 1% and 21.7% for respectively, 36, 72, 108 and 255 e-perturbations.
CONCLUSION
In this paper, we present a unifying framework for designing Lipschitz layers. Based on novel algebraic perspective, we identify a common SDP condition underlying the developments spectral normalization, orthogonality-basee methods, AOL, and CPL. Furthermore, we have shown that AOL and CPL can be re-derived and generalized using our theoretical framework. From this analysis, introduce family of SDP-based Lipschitz layers (SLL) that outperforms previous work. In the future, it will be interesting to investigate more expressive structures of T and extending our contributions address multi-layer neural networks.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was performed using HPC resources from DENCI-IDRIL (Grant 2021-AD01101 1011219911399 and funded by the French National Research Agency (ANR SPEED-20- SEEED-20--E23-000 CO-CEE2-0025). A. Havens and B. Hu are generously supported by the NSF award CAREER-2048168.
REFERENCES
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square at- tack: a query-efficient black-box adversarial attack via random search. In European Conference Computer Vision, 2020.
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In Inter- national Conference Machine Learning, 2019.
George Barker and David Carlson. Cones of diagonally dominant matrices. Pacific Journal of Mathematics, 57(1):15-32, 1975.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, 2019.
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In International Conference on Machine Learning. PMLR, 2020a.
Francesco Croce al. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning, 2020b.
Farzan Farnia, Jesse Zhang, and David Tse. Generalizable adversarial training via spectral normal- ization. In International Conference on Learning Represenlations, 2019.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Mahyar Fazlyab, Manfred Morari, and George Pappas. Safety verification and robustness analysis of neural networks via quadratic constraints and semidefinite programming. IEEE Transactions on Automatic Control, 2020.
Matthias Hein and Maksym Andriushchenko. Formal guarantees the robustness of classifier against adversarial manipulation. Advances in neural information processing systems, 30, 2017.
R.A. Horn and C.R. Johnson. Matrix Analysis. 9781 139788885.
Cambridge University Press, 2012. ISBN
Yujia Huang, Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar. Training certifi ably robust neural networks with efficient local lipschitz bounds. In Advances in Neural Informa- tion Processing Systems, 2021a.
Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. Training certifi- ably robust neural networks with efficient local lipschitz bounds. Advances Neural Information Processing Systems, 14-27755-227577 2021b.
Diederik Kingma et al. Adam: A method for stochastic optimization. In International Conference for Learning Representations, 2014.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. International Conference on Machine Learn- ing, 2020.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robut neural networks. In International Conference Machine Learning, 2021.
10

---

Published as a conference paper at ICLR 2023
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Joern-Henrl Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. In Advances in Neural Information Processing Systems, 2019.
A. Lur'e e and V. Postnikov. On the theory of stability of control systems. Applied mathematics and mechanics, 8()):266-248, 1944.
A. Megretski and A. Rantzer. System analysis via integral quadratic constraints. IEEE Transactions on Automatic Control, 42:819-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, 2022.
Takeru Miyato, Toshiki Kataoka, Masamori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. Training robust neural networks using lipschitz bounds. IEEE Control Systems Letters, 6:121-126, 2021.
Bernd Prach and Christoph H Lampert. Almost-orthogonal layers for efficient general-purposs lipschitz networks. Computer Vision-ECCV 2022: 17th European Conference, 2022.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefintte relaxations for certifying robustness to adversarial examples. Advances in neural information processing systems, 31, 2018.
Max Revay, Ruigang Wang, and Ian R Manchester. Lipschitz bounded equilibrium networks. arXiv preprint xrXiv: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.
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference on Ma- chine Learning, 2021.
Sahil Singla and Soheil Feizi. Improved techniques for deterministic 12 robustness. In Advances in Neural Information Processing Systems, 2022a.
Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on CIFAR-10 and CIFAR-100. International Conference on Learning Representations, 2022b.
Asher Trockman and Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021.
Yusuke Tsuzuku, Issci Sato, and Masashi Sugiyama. musschizz-margin training: Scalable certifi- cation of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems, 2018.
Zi Wang, Gautam Prakriya, and Somesh Jha. A quantitative geometric approach to neural-network smoothness. In Advances Neural Information Processing Systems, 2022.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295. PMLR, 2018.
Xiaojun Xu, Linyi Li, and Bo Li. Lot: Layer-wise orthogonal training on improving certified robustness. In Advances in Neural Information Processing Systems, 2022.
Greg Yang. Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing all shapes and sizes. In International Conference on Machine Learning, 2020.
Tan Yu. Jun Li, Yunfeng Cai, and Ping Li. Constructing orthogonal convolutions in an explicit manner. In International Conference Learning Representations, 2022.

---

Published as a conference paper at ICLR 2023
A PROOFS
In this section, we present the proofs for the theorems presented in our paper.
A. PROOF OF THEOREM 1
To prove the first statement Theorem 1, notice that we have
lla(x) s(vill = ||W 1 (r - --)il = (x T W WT 20 y).
Based on our algebraic condition W W T, we immediately have
(1g(x) - - v (x (x-y) T -T) - v) || y1?
Therefore, Statement is true.
To prove Statement in Theorem 1, we need to use the property of the nonlinear activation func- tion a. Notice that the condition W < 'I' ensures that all the diagonal entries of the nonsingular matrix T are positive. Therefore, 7 also a diagonal matrix whose diagonal entries are all posi- tive. For all the three activation functions listed in the above theorem, is slope-restricted on [0, 1], and the following inequality holds for any fa', //} (Fazlyab et al., 2019, Lemma 1):
x' - v/ oox') (v')
]
-T #
of
a(x')-o(y)) S. [(x')
We can set = W + b and 3/ W y + b, and the above inequality becomes
WT y) G(W x + b) o ( y + b)]
[[ -T
WT
[(W x + b) o(W y b) 0.
2T
We can rewrite the above inequality as
x y oo x + oWT b [ -w WT 2T-1
-W--1
I y
50.
oo x b) o (W" y bb]
(9)
Now we can apply the following argument:
[l((x) - h22))12 =||o- - 2 (WT (W W
b) - WT-'o b))l
y (o(W (o + 2WT
o(WT b)) -1
I x- 2WT (o b) o(W 6))
I- o(WT x b) - o (WT y b)
1
-2
x- [ +bb o + b)
-2T
WT
- ( x + - o (
1
-2 47-1
y (W b) - o + b)
+ b)
2T
where the last step follows from the fact that our condition WTW W = T implies T W WT-1 T-1 Finally, we can combine the above incquality with (9) to show
x z- y [M(x)) k2)) < TT xb) OWT
I
6
0
F - y
(WT y + +b)
----wl1 - v112,
which is the desired conclusion. Our proof is complete.
12

---

Published as a conference paper at ICLR 2023
A.2 PROOF OF THEOREM 2
Since T' is nonsingular diagonal and T - WT E D", then we must have Tx 2 E, WWT, Given the following key relation:
tr( - - -) Σ Σ(
WT
becomes clear that we need to choose the smallest value of Tx for all to minimize tr(/ T WTTTTT WT Therefore the choice T for AOL minimizes tr(l - - 2 W WTW over T E T. The proof for the last equality in Theorem is similar. Let us denote X - -T-WTWTT--- For any (f,j), the quantity X?, is always monotone non-decreasing in Tą and Tj.- To minimize [| we just need to choose the smallest value for all T3 under the constraint Ta 2 Σ, [WTWly This completes the proof.
A.3 THE GERSHGORIN CIRCLE THEOREM AND PROOF OF THEOREM 3
Before stating the proof of Theorem 3, we will state the Gershgorin circle theorem, a useful result from matrix analysis which locates the eigenvalues of a real (or complex) matrix (Horn et al., 2012, Theorem 6.1.1).
Theorem (Gershgorin), Let A E Rax" and define the n Gershgorin discs of A by
2 =EC: Aul S Σ A
(
j
Then the eigenvalues of A are contained the union of Gershgorin discs
U zEC: A.l S Σ Aail
A useful consequence of this theorem is that whenever A is diagonally dominant (i.e. |Axl > Ejer (Ay)) with positive diagonal entries, then the eigenvalues of must be non-negative. With this fact, we now proceed the proof of Theorem 3.
Proof of Theorem 3 Given nonsingular matrix Q. clearly the eigenvalues of Q(T WTW)Q-' and (T WT) are the same. If QTT WT) diagonally dominant and only has positive diagonal entries, then we can apply Gershgorin circle theorem (Horn et al., 2012, Corollary 6.1.6) to show that all the eigenvalues of Q(T W w W (which is the same as T non-negative. Therefore, we know that all the eigenvalues of (T W WTW) are non-negative. Since (T - WT) symmetric, we have T > WTW Then we can apply Theorem to reach our desired conclusion.
A.4 PROOF OF THEOREM 4
detailed proof for Theorem 4 is presented here. Our proof is based on modifying the arguments used in (Fazlyab et al., 2019, Theorem 1), and mainly relies the quadratic constraint technique developed in the control field (Megretski et al., 1997).
First, notice that (7) is equivalent to the following condition:
HT HTG G CTG = AWT 2A
I
-WA
(10)
Suppose (10) holds. Next we will show that h(x)) = Hr + Go x + b) is 1-Lipschitz.
For all the three activation functions listed in the above theorem, o is slope-restricted on [0, 1]. and the following inequality holds for any {a', y'} (Fazlyab et al., 2019, Lemma 1):
क' v/ ) a(z') 0(s )
1 [[x
-A
x' v/ -/= 0(20) [ox0) -
50 0.
2A
13

---

Published as a conference paper at ICLR 2023
Table 6: Additional results for CIFARIO and CIFARI00 datasets with different offset values.
CIFARIO
CIFARI00
Offset
Models
Natural Accuracy
Provable Accuracy (c)
Natural Accurncy
Provable Accuracy (e)
108
108
265
256
265
256
265
266
SLL small
73.3
63.7
53.8
44.5
15.3
46.7
35.2
26.4
20.1
5.9
v2
SLL medium
74.0
64.7
54,9
45.3
16.0
47.2
36.1
27.1
20.7
6.5
SL.. larll
74.6
65.3
55.2
45.8
16.2
47.9
36.7
27.9
21.3
6.7
SLL xlarge
75.3
65.7
55.8
46.1
16.3
48.3
37.2
28.3
21.8
6.9
SL.. small
71.2
62.6
53.8
45.3
20.4
44.9
34.7
26.8
20.9
8.1
1/2
medium
72.2
48.3
23,9
46.0
35.5
27.9
22.2
9.1
SLL largo
72.7
65.0
57.3
49.7
25.4
46.4
36.2
28.4
22.7
9.6
SLL slarge
73.3
65.8
58.4
51.3
27.3
46.5
36.5
29.0
23.3
10.4
SLL small
70.0
61.5
53.4
45.7
22.7
44.6
34.5
26.5
21.0
8.6
2/2
medium
70.8
55.4
48.3
25.8
45.4
35.5
27.9
22.1
9.8
SLL large
71.4
63.9
56.7
49.8
27.8
45.9
36.0
28.2
22.7
10.3
SLL xlarge
71.6
64.6
57.7
50.8
29.6
46.1
36.3
29.0
23.6
11.0
We can set x' WT + b and y' WTy + b. and the above inequality becomes
WT (. - y) Lo x + (WT b)]
[[
-A
W (x - (OWT
+ o(W +bb] 50.
2A
We can rewrite the above inequality as
[( - x
I (W + b))
-AWT
-WA]
I- [oWTT +b) - o o y + b)
50. (11)
2A
Now apply the following argument:
[|((x) - h(2))l H - u) +
+ (G)
H(s - c x+ TW ()) 1 1
f ((((WT=+)) x o(W 6))
H(s y)
HTH [HT
HJG
x -OWT x + - o ( y + b)
y o( x + b) o ( y + b)
G GTG
x- y $ o(WT b) ( y + b)
1
-WA 2A
y oW x + b) (WT + +b)
LAWT
where the last step follows from the condition (10). Finally, we can combine the above inequality with (11) show
x- - [/6 o o(wT + - + bb]
[lh(z) - h2
y o(WT b) oWT +b]
=|x- v11.
which is the desired conclusion.
B ADDITIONAL RESULTS
In this section, we will present some additional results and discuss the effect of the offset value on training. The choice of the offset value will affect the performance of SLL significantly. Larger offset values will lead to decrease in natural accuracy and increase in certified robust accuracy. The details documented in Table 6.
14

---

Published as a conference paper at ICLR 2023
C FURTHER DISCUSSIONS
In this section, we provide some extra discussions on control-theoretic interpretations and possible extensions of main results.
C.I CONTROL-THEORETE INTERPRETATIONS FOR OUR MAIN RESULTS
Our work is inspired by the quadratic constraint approach (Megretski et al., 1997) and the Lur'e system theory (Lur'c e et al., 1944) developed in the control community. Specifically, the general network layer structure (5) can be viewed as Lur'c system, which is a feedback interconnection of a linear dynamical system and static nonlinearity. this section, we try to make this connection more transparent.
Specifically, we can denote = h(z) and rewrite (5) as follows
x' Hr + Gw
0 = T +
(())
which is exactly shifted version of the Lur's e system. Therefore, it is not surprising that one can tailor the Lur'e system theory to study the properties of (5). As a matter of fact, the previous developments in Fazlyab et al. (2019) and Revay et al. (2020) were based on similar ideas. The main difference is that our paper requires solving SDPs analytically. the controls literature, the formulated SDP conditions typically solved numerically.
C.2 A VARIANT THEOREM
When discussing AOL and SLL, our main paper makes the assumption that all the columns of W have least one non-zero entry such that (2) is well defined. To drop this assumption, we can use the following variant of Theorem 1.
Theorem 6. For any weight matrix W E mRRx,, if there exists a diagonal matrix I E S such that 3 1, then the two following statements hold true.
1. The mapping g(x) = W + b is 1-Lipschitz.
2. The mapping h(x) = I 2WTo(WT. x + b) is 1-Lipschitz if is ReLU,, tanh or sigmoid.
The proof omitted here, since we can use exactly the same argument before. T happens to be nonsingular, then we can set T = r-1, and the above theorem exactly reduces to Theorem 1. However, the above result allows I to be singular. This useful for designing AOL and SLL in the case where W has some zero columns. Suppose the (io, -)-ntry of W W is equal to 0 for all j. Then we can set the (ig. io)-th entry of as O and still use (2) or (4) for other entries. is straightforward to verify that the resultant I' is still feasible solution to IWTWT z Г. and then we can implement AOL or SLL accordingly.
C.3 A VARIANT OF THEOREM
We can also modify Theorem 3 for the non-residual network layer case. The following variant of Theorem 3 is useful.
Theorem 7. Let W be the weight matrix. Suppose is a nonsingular diagonal matrix. If there exists some diagonal matrix with all positive diagonal entries such that (T QWTQQ-)) is real diagonally dominant matrix with diagonal entries being all positive, then T > T and the function g(x) WT- r b is I-Lipschitz.
The proof is trivial and hence omitted. Based on the above result, it is possible that one can use (4) to construct non-residual layer that still improve upon AOL.
15


Reviews:
[{"review_id": "el8ieBmM8hq", "reviewer": "Reviewer_rDGJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces an SDP based formulation for the development of 1-Lipschitz architecture. They show that many of the existing techniques for generating 1-Lipschitz neural networks can cast as solution to this SGD condition (W^TW < T).\n\nFurthermore, based on the SDP formulation the authors derive new conditions for Lipschitz Layers (based on different values of T) and show through experimentations that the SDP based lipschitz layers get better performance than previous approaches on natural and certified accuracy. \n\nBased on their setup, the paper also provides motivation for why Almost-Orthogonal-Layers promote orthogonality of layers during training.", "summary_of_the_review": "I think the unifying framework introduced by the authors is interesting. However, the paper lacks enough empirical validation since the authors only show results for one type of layer from their SDP formulation.", "strength_and_weaknesses": "[Strengths]\n\n- The paper is well written and easy to follow, and provide a theoretical framework that can unify the existing methodologies to get 1-Lipschitz functions.\n- Theorem 1 provides shows that spectral normalization and convex potential layers can be looked at as the linear and residual block for the same value of T.\n- The authors apply theorem 3 to come up with a new formulation of T with a new diagonal matrix Q.\n\n[Weakness]\n\n- The empirical verification is lacking. The authors have provided with a general framework for designing Lipschitz Layers, however they only show empirical results with one result from this formulation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_qVN3W0irRM", "reviewer": "Reviewer_VQD9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a unified framework for a group of well-known Lipschitz regularization methods in deep learning. Theorem 1 presents the algebraic condition on normalizing matrix $T$ which requires $WW^\\top - T\\preceq \\mathbf{0}$. As a result, the framework includes spectral normalization, orthogonal regularization, Almost-Orthogonal-layer (AOL), Convex Potential Layers (CPL) schemes. Subsequently, Theorem 2 gives a new interpretation of AOL methods by observing that the chosen matrix $T$ results in the closest normalized matrix to the set of orthogonal matrices which is an important step toward achieving a $1$-Lipschitz network. Then, in Section 5 the authors generalize the CPL method by introducing new optimization variables in a diagonal matrix $Q$ which is simultaneously optimized with weight matrix $W$. The paper discusses several numerical results to show the merits of the proposed SLL method on robust learning problems over CIFAR-10 and CIFAR-100 datasets.\n\n**Review Update**\n\nThe authors' response satisfactorily addresses my comments and I therefore raise my score to 8. ", "summary_of_the_review": "This paper proposes an interesting unified framework for Lipschitz regularization methods, and the theorems help extend and generalize existing Lipschitz regularization schemes. The numerical contribution could be further improved by experimenting the proposed methods on more datasets and finding factors in which they outperform the baseline AOL.", "strength_and_weaknesses": "Strengths:\n\n1- The paper has an interesting theoretical contribution and proposes a nice unified framework for Lipschitz regularization methods in deep learning.\n\n2- The paper is well-written and easy to follow. The theorems are sufficiently explained and well supported by several examples.\n\nWeaknesses:\n\n1- The numerical results are somewhat preliminary and discussed for only CIFAR-10 and CIFAR-100 datasets. Discussing the results for one or two large-scale image dataset could provide a stronger support for the SLL approach. Also, the performance scores for the SLL method and AOL baseline are quite close and in several cases, AOL performs better than the proposed SLL apporach.\n\n2- While the theorem proofs are interesting, I think they could have been presented in the Appendix. The proofs' space could have been used to discuss additional numerical results.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TXrWw0_JKwK", "reviewer": "Reviewer_PHyU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a unified perspective on 1-Lipschitz layers. The 1-Lipschitz layers in previous literature can be recovered by the algebraic conditions in Theorem 1. The theoretical results also lead to new parameterizations of 1-Lipschitz neural network layers. Experiments on certified robustness shows the effectiveness of the new paramterizations.", "summary_of_the_review": "This paper proposes a unified perspective on the development of 1-Lipschitz neural network layer, and provides new parameterizations of 1-Lipschitz layer. The experiments show strong certified robustness results which demonstrate the flexibility of the new parameterization.", "strength_and_weaknesses": "Strength:\n1) The authors provide a unified perspective on the development of 1-Lipschitz layers, which provides better understanding of the connections between different methods, and allows for new parameterizations of 1-Lipschitz layer.\n2) Theorem 1 can recover a wide range of previous methods on parameterization 1-Lipschitz layers, and leads to varaitions of new parameterizations.\n3) The authors show some computational efficient parameterizations as an extension to CPL. The performance on certified robustness surpasses previous 1-Lipschitz neural networks and further reduces the gap between certified accuracy and AutoAttack accuracy, implying the new parameterization is more expressive. \n\nWeaknesses:\n1) The architectures that are used for SLL seem to be much larger than those used in OrthoConv (Trockman et al., 2021). For instance, Cayley-Large uses an architecture with 4 convolutional layers and 3 fully connected layers, while in Table 3, SLL-small has 20 convolutional layers and 7 fully connected layers. It may be good to also put number of parameters in the table performance comparison table, and comment on the effectiveness of different architectures of 1-Lipschitz neural network.\n2) What activation functions do the authors use for SLL? It seems that the authors follow the architecture choice in Meunier et al. (2022) but it'd be good to mention the activation function choice because it is important for training 1-Lipschitz neural networks. Some previous works (e.g. Trockman et al., 2021) finds that gradient-norm-preserving GroupSort is much more effective than ReLU in training 1-Lipschitz neural networks. I am curious on whether this is also the case for the residual architecture. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "EtDzWGFcJU", "reviewer": "Reviewer_BFUj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new formulation for designing 1-Lipschitz neural networks, which is more general than existing ones. To guarantee 1-Lipschitzness, existing works use a variety of parameterizations. This paper proposes a more general parameterization which covers existing ones (existing works can be seen as special cases of this parameterization), and the new parameterization allows more flexibility on designing the network. Additionally, experimental results on CIFAR-10 and CIFAR-100 show that the 1-Lipschitz network trained using the new parameterization performs better compared to baselines.", "summary_of_the_review": "Training 1-Lipschitz neural network is an important and challenging problem and I like the new formulation in this paper because it provides new insights to this problem. The empirical results also look positive. So I tend to accept this paper. I hope the authors can address the weaknesses questions above.\n", "strength_and_weaknesses": "Strengths:\n\n1. The new formulation for representing the 1-Lipschitz layer is novel. The theoretical analysis provide many insights on how to design neural network layers that are one Lipschitz.\n\n2. Empirical results look very promising - the proposed method achieves better provable robustness (one main application of 1-Lipschitz network) than prior works consistently, although in some cases the improvements are marginal.\n\n\nWeaknesses:\n\n1. One question is not clearly answered by this paper: Is it possible to show that the formulation proposed in this paper can universally approximate any 1-Lipschitz functions? If it is hard to prove theoretically, we hope to know if the new factorization for 1-Lipschitz neural network is more representative compared to previous ones. The paper provides some experimental comparisons, however some baselines use models of different sizes. Ideally, for a fair comparison the number of optimizable parameters should be same in each method.\n\n2. Table 1 should include other recent baselines for provable robustness for L2 norm, such as (Leino et al., 2021) and (Huan et al., 2021); it should be easy to add the results directly. In addition, I think it is important to report training time of each method.\n\nReferences:\n\n[1] Leino, Klas, Zifan Wang, and Matt Fredrikson. \"Globally-robust neural networks.\" International Conference on Machine Learning. PMLR, 2021.  \n[2] Huang, Yujia, et al. \"Training certifiably robust neural networks with efficient local lipschitz bounds.\" Advances in Neural Information Processing Systems 34 (2021): 22745-22757.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%