Lipschitz-Bounded Equilibrium Networks
Authors: Max Revay
Ruigang Wang
Ian Manchester
Venue:  (2021)
Keywords: Adversarial Robustness
Equilibrium Networks
Neural ODE

Abstract: This paper introduces new parameterizations of equilibrium neural networks, i.e.
networks defined by implicit equations. This model class includes standard multilayer
and residual networks as special cases. The new parameterization admits
a Lipschitz bound during training via unconstrained optimization, i.e. no projections
or barrier functions are required. Lipschitz bounds are a common proxy for
robustness and appear in many generalization bounds. Furthermore, compared to
previous works we show well-posedness (existence of solutions) under less restrictive
conditions on the network weights and more natural assumptions on the
activation functions: that they are monotone and slope restricted. These results
are proved by establishing novel connections with convex optimization, operator
splitting on non-Euclidean spaces, and contracting neural ODEs. In image classification
experiments we show that the Lipschitz bounds are very accurate and
improve robustness to adversarial attacks.

Under review as a conference paper at ICLR 2021
LIPSCHITZ-BOUNDER EQUILIBRIUM NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
This paper introduces parameterizations of equilibrium neural networks, i.e. networks defined by implicit equations. This model class includes standard mul- tilayer and residual networks as special cases. The new parameterization admits a Lipschitz bound during training vía unconstrained optimization: no projections barrier functions bustness and appear in many generalization bounds. Furthermore, compared to previous works we show well-posedness (existence solutions) under less re- strictive conditions on the network weights and more natural assumptions on the activation functions: that they are monotone and slope restricted. These results are proved by establishing novel connections with convex optimization, operator splitting on non-Euclidean spaces, and contracting neural ODEs. image clas- sification experiments show that the Lipschitz bounds very accurate and improve robustness to adversarial attacks.
required. Lipschitz bounds are common proxy for ro-
INTRODUCTION
Deep neural network models have revolutionized the field of machine learning: their accuracy on practical tasks such as image classification and their scalability have led an enormous volume of research on different model structures and their properties (LeCun et al., 2015). In particular, deep residual networks with skip connections He al. (2016) have had major impact, and neural ODEs have been proposed as an analog with "implicit depth" (Chen et al. [018 8). Recently, a new structure has gained interest: equilibrium networks (Bai et al. [ Winston & Kolter 2020). a.k.a. implicir deep learning modely (El Ghaoui et al., 2019), in which model outputs are defined by implicit equations incorporating neural networks. This model class is very flexible: easy to show that includes many previous structures special cases, including standard multi-layer networks, residual networks, and (in a certain sense) neural ODEs.
He
However model flexibility in machine learning is always in tension with model regularity robust- ness. While deep learning models have exhibited impressive generalisation performance in many contexts it has also been observed that they can be very brittle, especially when targeted with ad- versarial attacks (Szegedy et al. 2014). In response to this, there has been major research effort understand and certify robustness properties of deep neural networks, e.g. RRahunnthaan et al.) (2018)); Tjeng et al. (2018); Liu et al. (2019); Cohen et al. (2019) and many others. Global Lip- schitz bounds (a.k.a. incremental gain bounds) provide somewhat crude but nevertheless highly useful proxy for robustness (Tsuzuku et al. 20188] Fazlyab et al. (2019), and appear in several anal- yses of generalization (e.g. (Bartlett et 2017) Zhou Schoellig 2019)).
Inspired by both of these lines of research, in this paper we propose new parameterizations of equi- librium networks with guaranteed Lipschitz bounds. We build directly on the monotone operator framework of Winston & Kolter (2020) and the work Fazlyab et al. (2019) on Lipschitz bounds.
The main contribution of our paper the ability to enforce tight bounds on the Lipschitz constant of an equilibrium network during training with essentially no extra computational effort. In addi- tion, we prove existence of solutions with less restrictive conditions on the weight matrix and more natural assumptions on the activation functions via novel connections to convex optimization and contracting dynamical systems. Finally, we show via small-scale image classification experiments that the proposed parameterizations ial attacks with little degradation in nominal accuracy. Furthermore, we observe small gaps between certified Lipschitz upper bounds and observed lower bounds computed via adversarial attack.
provide significant improvement in robustness adversar-

---

Under review as a conference paper at ICLR 2021
2 RELATED WORK
Equilibrium networks, Implicit Deep Models, and Well-Posedness. As mentioned above, has been recently shown that many existing network architectures can be incorporated into flexible model set called an equilibrium network (Bai al., 2019, Winston & Kolter 2020) or implicit deep model (El Ghaoui et al., 2019). In this unified model set, the network predictions are made not by forward computation of sequential hidden layers, but by finding a solution to an implicit equation involving single layer of all hidden units. One major question for this type of networks is its well- posedness. i.c. the existence and uniqueness of a solution to the implicit equation for all possible inputs. El Ghaoui et al. (2019) proposed computationally verifiable but conservative condition the spectral norm of hidden unit weight. In Winston & Kolter (2020), a less conservative condition was developed based monotone operator theory. Similar monotonicity constraints were previ- ously used to ensure well-posedness of a different class of implicit models in the context of nonlin- car system identification (Tobenkin al. 2017, Theorem 1). On the question of well pell-posedness, our contribution is a more flexible model set and more natural assumptions on the activation functions: that they are monotone and slope-restricted.
Neural Network Robustness and Lipschitz Bounds. The Lipschitz constant of a function mea- sures the worst-case sensitivity of the function, i.e. the maximum "amplification" of difference in inputs to differences in outputs. The key features of good Lipschitz bounded learning approach in- clude a tight estimation for Lipschitz constant and a computationally tractable training method with bounds enforced. For deep networks, [Tsuzuuu al. (2018) proposed a computationally efficient but conservative approach since its Lipschitz constant estimation method is based on composition of estimates for different layers, while (Anil et al.) (2019) proposed a combination of novel activation function and weight constraints. For equilibrium networks, El Ghaoui et al. (2019) proposed an esti- mation of Lipschitz bounds via input-to-state (ISS) stability analysis. Fazlyab al. (2019) estimates for deep networks based on incremental quadratic constraints and semidefinite programming (SDP) were shown to give state-of-the-a results, however this was limited to analysis of an already-trained network. The SDP test was incorporated into training via the alternating direction method of multi- pliers (ADMM) in Pauli et al. (2020), however due to the complexity of the SDP the training times recorded were almost 50 times longer than for unconstrained networks. Our approach uses a similar condition to Fazlyab et al. (2019) applied to equilibrium networks, however we introduce a novel direct parameterization method that enables learning robust models via unconstrained optimization, removing the need for cumputationalll--xpenssie projections or barrier terms.
3 PROBLEM FORMULATION AND PRELIMINARIES
3.1 PROBLEM STATEMENT
We consider the weight-tied network in which x E Rd denotes the input, and E R denotes the hidden units, E IRP denotes the output, given by the following implicit equation
z z=o + Ur+ + b2), = W + by
(1)
where W& E Ruxn, U E Baxd, and W. E RPxx= are the hidden unit, input, and output weights, respectively, by E RD and by E RR are bias terms. The implicit framework includes most current neural network architectures (e.g. deep and residual networks) special cases. To streamline the presentation we assume that a R + IR is a single nonlinearity applied elementwise, although our results also apply in the case that each channel has different activation function, nonlinear linear.
Equation (T) is called an equilibrium network since its solutions are equilibrium points of the differ- ence equation =+1 o(W>* + Ux + bb)) or the ODE &(t) =2(t) + oW + Ur + b.). Our goal is to learn equilibrium networks ① possessing the following two properties:
Well-posedness: For every input and bias b., equation admits unique solution 2. -iipschitz: It has a finite Lipschitz bound of y, i.c., for any input-output pairs (#1, v1), (I2, U2) we have lyy yalla S >1|00 x22 12
2

---

Under review as a conference paper at ICLR 2021
3.2 PRELIMINARIES
Monotone operator theory. The theory of monotone operators on Euclidean space (see the survey Ryu & Boyd (2016)) has been extensively applied in the development of equilibrium networks (Winston & Kolter 2020). In this paper, we will use the monotone operator theory on non-Euclidean spaces (Bauschke et al. (211), particular, we are interested H. which we identity with In equipped with a weighted inner product (z, v)Qq == y Qz where Q > 0. The main benefit that we can construct more expressive equilibrium network set. A brief summary or relevant theory can be found in Appendix [.I] here we give some definitions that are frequently used throughout the paper. An operator is set-valued or single-valued function defined by subset of the space A S H. x H. A function H + R U {oo} is proper if f(x) < oo for at least one æ. The subdifferential and proximal operators of a proper function f are defined as
finiteddimensional Hilbert space
0f(c) = [g - H f(v) 2 f() (y - z. q.Q. Vy E H}.
1 I11 alls + af(uu) 2
(x) (= E H arg min
respectively, where | == (2, the induced norm. For 1, we only consider the case
of Q 1. An operator A is monotone if (u 10--,, v, uiQ 2 0 and strongly monotone with parameter m if (u v, - Q 2 m|| | vIl for all (zz, u), (v, v) E A. The operator splitting problem is that of finding zero of sum of two operators A and B, i.c. find an such that 0 E (A [A+ (z).
Dynamical systems theory. In this paper, we will also treat the solutions of IT] as equilibrium points of certain dynamical systems =() = [(x(()). Then, the well-posedness and robustness properties of (T can be guaranteed by corresponding properties of the dynamical system's solution set. A central focus in robust and nonlinear control theory for more than 50 years and largely unified by the modern theory of integral quadratic constraints (Megretski & Rantzer 1997) has been systems which interconnections of linear mappings and "simple" nonlinearities, i.e. those easily bounded in some sense by quadratic functions. Fortuitously, this characteristic is shared with deep, recurrent, and equilibrium neural networks, connection that we use heavily in this paper and has previously been exploited by Fazlyab et al. (2019); El Ghaoui et al. (2019); Revay al. (2020) and others. A particular property we interested in called contraction (Lohmiller & Slotine 1998). i.e., any pair of solutions 21 (t) and 22()) exponentially converge to each other:
(t) (+)ll - a (0) (2)l]]e
for all / >> 0 and some a. 3 > 0. Contraction can be established by finding a Riemannian metric with respect to which nearby trajectories converge, which a differential analog of Lyapunov function. A nice property of a contracting dynamical system is that if it is time-invariant, unique cquilibrium exists and it possesses a certain level robustness. Moreover, contraction can also be linked to monotone operators, i.e. system is contracting w.r.t. to a constant (state-independen)) metric Q if and only if the operator -f is strongly monotone w.r.t. Q-weighted inner product. We collect some directly relevant results from systems theory in Appendix C.2
MAIN RESULTS
This section contains the main theoretical results of the paper: conditions implying well well-posedness and Lipschitz-houndedness of equilibrium networks, and direct (unconstrained) parameterizations such that these conditions automatically satisfied.
Assumption 1. The activation f is monotone and slope-restricted in [0. 1], i.e.,
(xx a(y) < 1, Vx, y E IR, x
Remark 1. We will show below (Proposition in Section 4.2 that Assumption is equivalent to the assumption in Winston & Kolter (2020), i.e. that (-) prox) (.) for some proper convex function f. However, the above assumption is arguably more natural, since it is easily verified for standard activation functions. functiono Note also that if different channels have different activation functions, then simply require that they all satisfy
3

---

Under review as a conference paper at ICLR 2021
The following conditions central to results well-posedness and Lipschitz bounds: Condition 1. There exists A E D*t, with D+ denoting diagonal positive-deffnit matrices, such that W satisfies
2A AW - WT > O.
(3)
Condition 2. Given prescribed Lipschitz bound 7 > O, there exists A E D+ such that W, Wo U satisfy
2A - AW - WTh W W. -.no---UUR 1 _UU O.
(4)
Remark 2. Note that Condition 2 implies Condition since 1//(WT + AUU A) = O. As
partial converse, if Condition 7 holds, then for any W there exist sufficiently large 7 such that Condition 2 is satisfied.
The main theoretical results of this paper are the following:
Theorem 1. If Assumption I and Condition 7 hold, then the equilibrium network 7 is well-posed. i.e. for all and by, equation 7 admits unique solution 2. Moreover, it has finte Lipschitz bound from x to y.
Theorem 2. If Assumption and Condition hold, then the equilibrium network well-posed and has a Lipschitz bound of 7.
As consequence, we call ① Lipschitz bounded equilibrium network (LBEN) if its weights satisfy either (3) or 4 The full proofs appear in Appendices E. and E.2, but here we sketch some of the main ideas. We can represent ( as an algebraic interconnection between linear and nonlinear parts:
= Wa + Ur + bz. 2 = (v), y = -,, + by.
(5)
can be shown that for any pair of solutions to the nonlinear part =a a (v,)) =6 = (1b), if we define A Eo- 2b and A Za 26 then Assumption ! implies the following:
A A. A=)A 2 0.
(6)
for any E ID+ This and Condition can be used to prove global stability of a unique equilibrium of the differential equation é v W (v) + Ux b., which proves there is unique solution to (T) for any inputs. Next, straightforward manipulations of Snndition[sshov that any pairs of inputs
Ta Ty and outputs yas yb satisfy the following, where A
Ia Ib and A, ya yb:
1 11 2 2(A A. AMA20.
A1
where the inequality comes 6 This implies the Lipschitz bound |Ayl S S711A1112
Remark 3. In Fazlyab et al. (2019) was claimed that (6) holds with richer (more powerful) class of multipliers A which were previously introduced for robust stability analysis of systems with repeated nonlinearities (Chu & Glover 1999. D D'Amato et al.) [200]] Kulkarni & Safonov 22002) However this is not true: counterexample was given in Pauli et al. (2020), and here we provide brief explanation: even if the nonlinearities a (v4) are repeated when considered as functions of Us their increments Agi = (v + Av)) - a (v:) are not repeated when considered as functions of Avi. since they depend on the particular v, which generally differs between units.
Example 1.
We illustrate the extra flexibility of Condition D compared the condition of Winston
& Kolter (020)) by toy example. Consider W E RR222 and take a slice near W = 0 of the form
W =
[0 W12 W22
for which we have: 27 2T-W8 W - WT WW12 2
2
-W12
22
By Sylvester's criterion, this matrix is positive-defiitte if and only if W22 < 1 and det(2T W.
WT) = 4(1 222) W 0, which defines a parabolic region in the W12, Wza plane.
Applying our condition without loss of generality take A = diag(1, a) with a > and we have
2A AW WTA =
2
-W12
W12
2x
2a 22
4

---

Under review as a conference paper at ICLR 2021
Figure I: Valid coefficient ranges for Example |
Gray region: the condition from Winston & Kolter 2020 is fea- sible: 27 W W > 0.
20
White region (including gray region); our well-posedness con- dition is feasible: 3λ D :2 AW - W A 0.
W1:
Black region: neither condition feasible.
-0
40
-50 -60
-40
-20
We
The positivity test is now W22 < and 4a(1 - Wi2 >0. For each W12 there is sufficiently large or such that the second condition is satisfied, since the first implies 1 W2 > 0. Hence the only constraint on W is that W22 < 1, which yields a much larger region in the W12, W22 plane (see Zy. Interestingly, in this simple example with ReLU activation, the condition W22 < 1 is also a necessary condition for well- sell-posedness (El Ghaoui et al. 2019 Theorem 2.8).
4.1 DIRECT PARAMETERIZATION FOR UNCONSTRAINED OPTIMIZATION
Training network that satisfies Condition I or Can be formulated optimization problem with convex constraints. In fact, Condition | is linear matrix inequality (LMI) in the variables and AW, from which W can be determined uniquely. Similarly, via Schur complement, Condition Z is an LMI in the variables A, AW, AU, W., and 7, from which all network weights can be determined. In certain theoretical sense LMI constraints are tractable Nesterov Nemirovskil (1994) proved they are polynomial-tne -time solvable however for even for moderate-scale networks (c.g. < 100 activations) the associated barrier terms projections become major computational bottleneck.
In this paper, propose direct parameterization that allows learning via unconstrained optimization problem, i.e. all network parameters are transformations of free (unconstrained) matrix variables, in such way that LMI constraints (3) or (4) are automatically satisfied.
For well poseedpsss,ssss i.e. Condition 1 we parameterize via the following free variables: E ROxx d E TR.,, and skew-symmetrid matrix S = -5 E RRx from which the hidden unit weight is
= VVVVV +S+
where V = diag (ed) and >> 0 is some small constant to ensure strict positive-definiteness Then it follows from straightforward manipulations that Condition holds with A = -- if and only if W can be written (8). When v 1, this reduces the parameterization of Winston & Kolter 2020).
Similarly, for specific Lipschitz bound, i.e. Condition we add to the parameterization the free input and output weights U and W., and arbitrary 0. We can construct
W = -
W 27
W. WTW.
27 -
(9)
for which (4) is automatically satisfied. Again, it can easily be verified that this construction is necessary and sufficient, i.c. any W satisfying 44h can be constructed via
4.2 MONOTONE OPERATOR PERSPECTIVE
In this section, will show that finding the solution to LBEN I is equivalent to solving a well- posed operator splitting problem, and hence unique solution exists. First, we need the following observation on the activation function a.
Proposition 1. Assumption 7 holds if and only if there exists a corvex proper function f IR (00) such that a+)) prox) (-).
Note that S can be parameterized via its upper lower triangular components, via $ = N N with N free, which be straightforward if W defined implicitly via linear operators, e.g. convolutions.
5

---

Under review as a conference paper at ICLR 2021
The proof of Proposition 1 with a construction of f appears in Appendix E.3 along with a list of f for popular a. is well-known in monotone operator theory (Ryu & Boyd 2016) that for any convex closed proper function f. the proximal operator prox (2) monotone and non-expansive (i.e. slope-restricted in [0, 1)). Proposition is converse result for scalar functions.
Remark 4. To our knowledge Proposition 7 is novel, however for several popular activation func- tions the corresponding functions f were computed Li et al. (2019) (see also Table 3 in Ap- pendix E.4 Compared with Li al. (2019). our work gives necessary and sufficient conditions.
Now we connect LBEN to an operator splitting problem.
Proposition Finding a salution of LBEN 1 is equivalent to solving the well-posed operator splitting problem O E A + B)(z) with the operators
A(z)
(z) (Ux+bb), B Of
(10)
where f(2) == Ei= (z(( with X; as the ith diagonal element of A.
The proof appears Appendix E.4 and Theorem follows directly since the above operator splitting problem has a unique solution for any I, by.
Computing an equilibrium. There exist various of operator splitting algorithms to compute the solution of LBEN (I), e.g., ADMM (Boyd et al.) 2011) and Peaceman Rachfood splitting (Kellogg) 1969). Winston & Kolter (2020) found that Peaceman-Rase Rachford splitting converges very rapidly when properly tuned, and our experience agrees with this.
Gradient backpropagation. As shown in (Winston Kolter 2020 Section 3,5), the gradients of the loss function E(-) can be represented by
dt a(-)
0E (T J-) 0(Wz, 2. Ux + bz) O2.-
(11)
a())
where 2. denotes the solution of TT. (-) denotes some learnable parameters in the parameterization
8) or ( and J E Do + Ux + b.) with Do as the Clarke generalized Jacobian of a. Since piecewise differentiable, then the Do 2, + Ux + b.) is singleton almost everywhere. The following proposition reveals that (11 is well-defined, see proof in Appendix E.5
Proposition 3. The matrix
JW is invertible for all n., x and b..
4.3 CONNECTIONS TO CONVEX OPTIMIZATION
Since LBEN equivalent to an operator splitting problem, interesting question is whether can further be connected to a convex optimization problem. Here we construct an equivalent convex problem for the LBEN whose parameterization satisfies S
Proposition 4. If the direct parameterization (either ( (9) of an LBEN satisfies S = 0, then for all and by, the solution of I is the minimizer of the following strongly convex optimization problem:
min
W) Un bey
+ +()).
(12)
The proof is Appendix E.6 Furthermore, for an important subclass of LBEN where is ReLU, it has equivalent convex quadratic programming (QP) formulation.
Proposition 5. Consider an LBEN ( with ReLU activation. For all x and b., the solution of is
the minimizer of the following strongly convex QP problem:
min
11 TT s.t. =2 (1-WW W)= Un b
(13)
where 2A - AW WTA and - A(Ux bz).
Note that the QP [3) also works for the where S is non-zero. The proof (see Appendix E.7 is built on the "key insights" of ReLU activation from Raghunathan et al. (2018b). This allows one to compute the solution of LBEN (T) using the many free or commercial QP solvers.

---

Under review as a conference paper at ICLR 2021
4.4 CONTRACTING NEURAL ODES
In this section, we will prove the existence of a solution to ① from a different perspective: by showing it is the equilibrium of contracting dynamical system "neural ODE"). We first add smooth state v(() E I to avoid the algebraic loop in (5) This idea has long been recognized as helpful for well-posedness questions (ames 1964).
We define the dynamics of v(t) by the
following ODE:
b(t) = --()) + Wz(() +Ux+b. bz, =())=)(v(t))
(14)
The well-posedness of ①T) equivalent the existence and uniqueness of an equilibrium of (14) for all x and bg. which is established by the following proposition.
Proposition 6. If Assumption some constant metric P >
and and Condition hold, then the neural ODE 14) is contracting w.r.t.
The proof is in Appendix E.8 Moreover, the metric P can be found via semidefinite programming.
The above proposition also proves that the nonlinear operator f with f() --+ Wo(v) +U++ ba. zeros of which define solutions of LBEN ([) is actually monotone w.r.t. the P-weighted inner product, which gives a first-order
tutting--lanee oracle for the zero location v, such that f(v.) ) = 0.
Le. given a test point e # v", it proves that v. is in the half-space defined by (v. we. f())
0.
This may offer alternative ways to solve LBEN c.g. vemiiooio (2004); Nesterov (2007).
4.5 FEEDFORWARD NETWORKS AS A SPECIAL CASE
Consider multi-layer feedforward network of the form
21 Une + bu: *++1 (Wezz + be), (= 1 L-1,
y WLE + bL,
(15)
which can be rewritten as an equilibrium network (I] as shown in Appendix A The above equilibrium
network is obviously well-posed as a unique solution exists. The following proposition shows that is also an LBEN.
Proposition 7. The LBEN parameterizattion 8 contains all feedforward networks.
In Winston & Kolter 2020). set well cell-posed equilibrium network, called monotone operator equilibrium network (MON), is introduced via the following parameterization
W (1- A A -B
(16)
where >> 0 is parameerr,,,er... A, B are Icarnable matrices. The MON parameterizatton can be understood as a special case of L.EN with a fixing I.
Proposition The MON parameterization (T6] does not contain all feedforward networks, and if it does not contain any feedforward networks.
The set of feedforward networks in MON shrinks as the hyper- parameter increases. Most experiments in Winston & Kolter 2020 use m which excludes all feedforward networks.
From the proof (see Appendix E.11
In the feedforward case, our Lipschitz bound condition is equivalent to the state-of-art bound estimation method in Fazlyab et al.) (2019). The major benefit of our direct parameterization (9) is that it allows such bounds to imposed during training without any additional computational cost. The details are given in Appendix
5 EXPERIMENTS
In this section we test our approach on the MNIST and CIFAR-10 image classification problems. Our numerical experiments focus on model robustness, the trade-off between model performance and the Lipschitz constant, and the tightness of the Lipschitz bound. We compare the proposed LBEN to unconstrained equilibrium networks, monotone operator equilibrium network (MON) of
Winston & Kolter (020), and fully connected networks trained using Lipschitz margin training (LMT) (Tsuzuku et al. 2018). When studying model robustness to adversarial attacks, we use the
1.2 Fast Gradient Method, implemented as part of the Foolbox toolbox (Rauber et al. 2020 All
7

---

Under review as a conference paper at ICLR 2021
LUEN
LBEN
LBEN 08
LBEEN
X LBEN 5.0
80
LDEN
X LBEN
LDEN
LATT' -
Tost Erzor (%)
--MON
Teat Ervor
[MT 250
LAT 100
LMT a 1.0
Unconstaiiad
LOCT' 1030
10
15
Lipechitz
f perturbation
Nominal test error Lipschitz constant esti-
(b) Test error with adversarial perturbation versus size of adversarial perturbation. Lower better.
mates: markers indicate observed lower bounds all methods, vertical lines indicate certified upper
bounds for LBEN
Figure 2: Image classification results on MNIST character recognition data set.
models are trained on either standard desktop computer with an NVIDIA GeForce RTX 2080 graphics card using a google cloud instance with a Nvidia Tesla V100 graphics card. Details of the models and training procedure can be found in Appendix [F] all code will be made available online but links are omitted due to the double-blind review process.
5.1 MNIST EXPERIMENTS WITH COLLY-CONEECTED NETWORKS
In Figure 2a the test error versus the observed Lipschitz constant, computed via adversarial attack for each of the models trained. We can see clearly that the parameter y in LBEN offers trade-off be- tween test error and Lipschitz constant. Comparing the LBEN,=5 with both MON and LBEN we also note a slight regularizing effect in the lower test error.
By comparison, LMT (Tsuzuku et al. 2018) with qualitatively similar trade-off, but underperforms LBEN terms of both test error and robustness. If we examine the unconstrained equilibrium model, we observe Lipschitz constant more than an order of magnitude higher, i.e. this model has regions of extremely high sensitivity, without gaining any accuracy in terms of test error.
tunable regularization parameter displays
For the LBEN models, the lower and upper bounds on the Lipschitz constant are very close: the markers are very close to their corresponding lines in Figure 2a see also the table of numerical results in Appendix A in which the approximation accuracy is in many cases around 90%.
Next tested robustness of classification accuracy adversarial attacks of various sizes, the results are shown in Figure an summarized in Table [ We can clearly see that decreasing (i.c. stronger regularization) the LBEN models results in far more gradual degradation of performance as perturbation size increases, with only a mild impact on nominal (zero perturbation) test error.
computational complexity compared to other equilibrium models. The test and training errors versus number of epochs are plotted in Figure []] and we can see that all models converge similarly, and also take roughly the same amount of time epoch. This is clear contrast to the results of Pauli et al. (2020) in which imposing Lipschitz constraints resulted fifty-fold increase in training time. Interestingly, we can also see Figure 5 the effect of regularisation for LBEN with y 5: higher training error but lower test error. We have observed several cases where the unconstrained equilibrium model became unstable during training, LBEN never exhibits this problem.
Next, examined the impact of our parameterization
Finally, we examined the quality of the Lipschitz bounds as a function of network size, comparing the upper and lower bounds fully connected networks with width 20 1000. The results shown in Figure g It can observed that network size only has a mild effect on the quality of the I Lipschitz bounds, which decrease slightly width is increased by factor of 50.
8

---

Under review as a conference paper at ICLR 2021
100
36
LBBEN
155
LBEN
90
LBEN
MON
FeedForward
1est Error (76)
Test Exror
33
32
31
50
LBEN
8
LBEN 5.0
40
LBEN
LBEN
29
Feetforward
10a
10
0.5
1.5
2
2.5
Lipschitz (lower bound)
perturbation
(a) Nominal test error vs observed lower bound on (b) Test error with adversarial perturbation versus Lipschitz constant.
size of adversarial perturbation. Lower is better.
Figure 3: Image classification results on CIFAR-10 data set.
5.2 CIFAR-10 EXPERIMENTS WITH CONVOLUTIONAL NETWORKS
The previous example looked at simple fully connected networks, however, our approach can also be applied to structured layers such as convolutions. Here, we perform several experiments exploring the use of convolutional layers on the CIFAR-10 dataset. To study the improved expressibility we will compare the LBEN to the LBEN with its metric set to the identity, denoted LBEN A=I. Note that the model set LBEN A= corresponds to the MON, Additional model details can be found in Appendix
In Figure 3a we have plotted the test performance versus the observed Lipschitz constant for the LBEN and LBEN A=I for varying Lipschitz bound 7 1, 3, 5, 50, along with the LBEN,<<0>> MON, and feed-forward convolutional networks with 40, 81, 160, and 200 channels. Again, we that the Lipschitz bound has regularizing effect, trading off between nominal fit and robust- ness. Additionally, we see that the LBEN provides both better performance and robustness than the traditional feed-forward convolutional networks of similar sizes, highlighting the benefit of the equilibrium network structure.
Comparing LBEN and LBENA= can see that the metric gives higher quality models for LBEN with specified 7 but it is slightly worse for LBEN < oc compared to MON, This is likely due the extra expressiveness of the model leading to some overfitting. This can also be seen in the training curves in Figure
Figure 3b shows the test error versus the size of adversarial perturbation for the IBEN and 162 channel feed-forward convolutional network. We observe that the LBEN provides much more gradual loss in performance than the feed-forward network, with y = 5 offering an excellent mix of nominal performance and robustness. The feed-forward networks of different sizes exhibited similar results, however only one is plotted in Figure 3b for clarity.
CONCLUSIONS
In this paper, we have shown that the flexible framework of equilibrium networks can be made robust via simple and direct parameterization which results in guaranteed Lipschitz bounds. These results can also be directly applied (as special case) to standard multilayer and residual deep neural networks, and also provide direct parameterization of nonlinear ODEs satisfying strong stability and robustness properties.
Extension equilibrium network structures more general than is interesting area for future research. Our results can be extended to more general multivanable "activations" if they can be described accurately via monotonicity properties integral quadratic constraints. One particular example where this is possible where the "activation" " computes the arg min quadratic pro- gram of the sort that appears in constrained model predictive control (Heath & Wills 2007).

---

Under review as a conference paper at ICLR 2021
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In Inter- national Conference on Machine Learning, pp. 291-301. PMLR, 2019.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, pp. 690-701, 2019.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalizer margin bounds for neural networks. Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Heinz H Bauschke, Patrick L. Combettes, al. Convex analysis and monotone operator theory in
Hilbert spaces, volume 408. Springer, 2011.
Stephen Boyd, Neal Parikh, and Eric Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In Advances in neural information processing systems, pp. 6571-6583, 2018.
Yun-Chung Chu and Keith Glover. Bounds of the induced norm and model reduction errors for systems with repeated scalar nonlinearities. IEEE Transactions on Automatic Control, 44(3): 471-483, 1999.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320, 2019.
Fernando J D' Amato, Mario A Rotea, AV Megretski, and UT Jönsson. New results for analysis of systems with repeated nonlinearities. Automatica, 37(5)7739-747, 2001.
2001.
Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Y. Tsai. Implicit deep
learning. urXiv:1908.0633 2019.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural 11427-1 1438, 2019.
Information Processing Systems,
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
WP Heath and AG Wills. Zames-falb multipliers for quadratic programming. IEEE Transactions on Automatic Control, (912)))994-199111 2007.
Joao P Hespanha. Linear Systems Theory. Princeton university press, 2018
Bruce Kellogg. A nonlinear alternating direction method. Mathematics of Computation, 23(105): 23-27, 1969.
Hassan K Khalil. Nonlinear systems. Prentice-Hall 2002.
Diederík Kingma and Jimmy Lei Ba. Adam: A method for stochastic gradient descent. In ICLR: International Conference Learning Representations, 2015.
Vishwesh V Kulkarni and Michael G Safonov. All multipliers for repeated monotone nonlinearities. IEEE Transactions on Automatic Control, 47(7):1209-1212, 2002.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):4364444 2015.
Jia Li, Cong Fang, and Zhouchen Lin. Lifted proximal operator machines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4181-4188, 2019.
Changliu Liu, Tomer Amon, Christopher Lazarus, Clark Barrett, and Mykel J Kochenderfer.. Algo- rithms for verifying deep neural networks. arXiv preprint arXiv: /903006700007555 2019.
10

---

Under review as a conference paper at ICLR 2021
Winfried Lohmiller and Jean-Jacques E Slotine. On contraction analysis for non-linear systems. Automatica, 34(6):683-6) -6883,666,,66 1998.
Alexandre Megretski and Anders Rantzer. System analysis via integral quadratic constraints. IEEE Transactions Automatic Control, (2(6):819-830 1997.
Arkadi Nemirovski. Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems. SIAM Journal on Optimization, 15()):229-251, 2004.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319-44,, 2007. 2007.
Yurii Nesterov and Arkadii Nemirovskii. Interior-poinl polynomial algorithms in convex program- ming. SIAM, 1994.
Patricia Pauli, Anne Koch, Julian Berberich, and Frank Allgöwer. Training robust neural networks using Lipschitz bounds. arXiv preprint arXiv:2005.022 02929, 2020.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Representations, 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pp- 10877-10887, 2018b.
Anders Rantzer. On the Kalman- Yakubovich-Popov lemma. Systems Control Letters, 28(1):7-10, 1996.
Jonas Rauber, Roland Zimmermann, Matthias Bethge, and Wieland Brendel. Foolbox native: Fast adversarial attacks to benchmark the robustness of machine learning models pytorch, tensor- flow, and jax. Journal of Open Source Software, 5(53):2607, 2020.
Max Revay, Ruigang Wang, and Ian R Manchester. A convex parameterization of robust recurrent neural networks. IEEE Control Systems Letters, 2020. doi: (D0.0//.SSSS..0.........
Ernest K Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. Comput. Math, 15 (1):3-43, 2016.
John W Simpson-Pores and Francesco Bullo. Contraction theory on riemannian manifolds. Systems & Control Letters, 65:74-80, 2014.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR: International Conference on Learning Representations, 2014.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2018.
Mark M Tobenkin, Ian R Manchester, and Alexandre Megretski. Convex parameterizations and fidelity bounds for nonlinear identification and reduced-order modelling. IEEE Transactions on Automatic Control, 62(7):3679-33)
2017.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certifi- cation of perturbation invariance for deep neural networks. In Advances in neural information processing systems, pp. 6541-65500 2018.
Ezra Winston and J. Zico Kolter. Monotone operator equilibrium networks. arXiv:2006.0859) 2020.
G. Zames. Realizability Condition for Nonlinear Feedback Systems. IEEE Transactions on Circuit Theory, 11(2):186-194, 1964.
SiQi Zhou and Angela P Schoellig. An analysis of the expressiveness of deep neural network architectures based their lipschitz constants. arXiv preprint arXiv: 1912. 2019.
11

---

Under review as a conference paper at ICLR 2021
A
EXPERIMENTAL RESULTS ON MNIST CHARACTER RECOGNITION
This appendix contains tables of results on MNIST and CIFAR-10 data sets.
Legend:
Err: Test error (%),
|a]|2: norm of adversarial attack.
Tupi certified upper bound on Lipschitz constant (for models that provide onc),
Now: observed lower bound on Lipschitz constant via adversarial attack.
approx: approximation ratio of Lipschitz constant as percentage 100
Now
Tup
Models:
LBEN: the proposed Lipschitz bounded equilibrium network..
MON: the monotone operator equilibrium network of Winston & Kolter (002))
UNC: an unconstrained equilibrium network, i.e. W directly parameterized.
LMT: Lipschitz Margin Training model as in Tsuzuku et al. (2018).
Lip-NN: The Lipschitz Neural Network model of Pauli et al (2020). Note these figures are as reported in (Pauli et al. 2020), all other figures are calcu lated by the authors of the present paper.
Model
Err: |all2 = 0
Err:
||a/|
S 5
Err:
||]||
S
10
Yup
Now
approx
LBEN 600
2.03
56.0
82
9.8
LBEN 45
1.81
46.4
95.4
5
2.912
58.2%
LBEN
2.36
19.4
85.5
0.865
86.5%
LBEN =088
2.59
17.4
80.1
0.8
0.715
89.4%
LBEN 0.4
4.44
16.1
65.0
0.4
0.372
93%
LBEN
7.41
14.4
42.6
0.2
0.184
92%
MON
2.04
55.8
88.6
7.75
UNC
2.08
48.75
77.9
239.0
LMT c=
2.3
59.4
88.1
17.5
LMT LMT0=10 100 100
3.4
65.4
92.0
7.66
LMT -50
6.92
61.8
98.4
6.92
LMT 1000
12.23
78.4
98.9
3.10
Lip-NN
3.55
8.74
Table 1: Results from MNIST experiments.
12

---

Under review as a conference paper at ICLR 2021
Top to bottom is increasing perturbation size. Left to right are different examples.
4
4
4
4
22
2
2
2
2
2
22
2
2
2
2
2
Z
2
3
3
3
3
3
3
7
7
7
7
9
7
9
7
7
7
7
7
7
7
8
8
8
8
8
7
7
7
7
4
4
9
9
4
4
4
4
4
#
6
6
4
Figure Random selection of MNIST adversarial examples from Figure 2b
4
4
4
4
7
7
7
7
0
O
O
O
A
3
3
3
3
3
3
7
7
7
7
7
9
9
7
7
7
7
7
2
2
2
2
2
2
2
2
3
3
3
3
3
8
8
8
13

---

Under review as a conference paper at ICLR 2021
10
MON
MON
5,0
Unconstrained
Unconstrained
LBEN 7 < 00
-BEE y 00
4.5
LBEN 5
LBEN 5
Test Error (56)
1rrin Eivor
3.5
10-1
2.5
10
25
10
15
25
30
Epochs
Epochs
Figure 5: Left: Training set error versus epochs. Right: Test set versus epochs. Note that the left and right plots are on different scales. The time per epoch for the MON, unconstrained, LBEN, and LBEN networks are 14.4, 16.1, 14.9 and 14.8 seconds per epoch respectively.
0.8
Noo Tuu
0.6
0.4
0.2
LBEN,
LBEN, 1.0
LBEN, = 20
200
400
600
800
1000
Width
Figure 6: Approximation accuracy of the Lipschitz bound versus the network width of LBEN from the MNIST example. The certified upper bound is Top and the observed lower bound is Now-
14

---

Under review as a conference paper at ICLR 2021
B EXPERIMENTAL RESULTS ON CIFAR-10 DATASET
Model
Err:
a
Emr:
a
2
S
0.5
Emr:
2
1.0
Tup
Now
Y approx
LBEN 2.00
31.1
96.1
100
31.1
LBEN 50
28.4
75.5
95.4
50
2.89
5.7%
LBEN
=5
29.9
65.8
85.5
5
1.39
27.8%
LBEN
31.3
64.2
83.5
3
1.14
38.0%
LBEN
37.9
62.5
80.5
0.92
46.0%
LBEN y=1
36.2
61.8
78.8
0.60
60.0 %
FF
33.07
91.5
99.8
6.06
%
Flw-81
32.6
93.3
100
8.42
%
F16=
32.5
95.0
100
11.3
%
=200
32.6
94.5
100
12.4
%
Table 2: Results from CIFAR experiments. FF refers to the feed-forward convolutional network.
60
LBEN 1=1.0.
LBEN 7.5..l And
50
LBEN 3-2000 A=
LBEN 9-1.0
LBEN
Training Error
LBEN
40
LBEN
MON
Fredforward
30
20
10
10
15
20
25
Epochs
Figure 7: LBEN and MON training error versus epochs on CIFAR-10 dataset. The red curves have the metric set so that A whereas the blue curves optimize over the metric. The line styles correspond to different gain bounds. Note that both MON and LBEN,<oc achieve zero training error.
C PRELIMINARIES
C.I MONOTONE OPERATORS WITH NON-EUCLIDEAN INNER PRODUCTS
We present basic properties of monotone operators finit-diimensional Hilbert space H. which we identify with R."" equipped with a weighted inner product (z. viQ = y Qx with Q > 0. For n 1, we only consider the case of Q = 1. The induced norm ||و|| is defined as (xzz))0- A relation or operator a set-valued or single-valued map defined by a subset of the space A C HxH: we use the notation A(z) = {y (x, y) E A}. If A(x) is singleton, we called A a function. Some commonly used operators include: the linear operator A(x) = Ax) x E H); the z) (I,y) E A, (x E B): the inverse operator A-1 ((y.z) (z, v) E A}; and the subdifferential operator Of = {(x, 0x)))) with x = dom ff and (f(x) (g H. f()) 2 f(x) + (y x. I.9)q, Vy E H.. An operator A has Lipschitz constant L for any (z, u), (g. v)
operator sum A + B {(x,
||u u1l2 & T|I vlle-
(17)
15

---

Under review as a conference paper at ICLR 2021
An operator A is non-expansive if L and contractive if L 1. An operator A is monotone if (u U, x y) 0, V(z,u), (y, E
(18)
is strongly monotone with parameter m if
(u - v, - u)q 2 m|| vl2. v(a, u), (v.
(19)
A monotone operator A is maximal monotone if no other monotone operator strictly contains it, which property required for the convergence of most fixed point iterations. Specifically, an affine operator A(x) Wa - b is (maximal) monotone if and only if QW + W Q > 0 and strongly monotone if QW + Q = ml. A subdifferential 0 is maximal monotone and only if f is convex closed proper function.
The resolvent and Cayley operators for an operator A are denoted RA and CA and respectively defined as
RA = (I+aA)=+ CA=
(20)
for any > 0. When A(x) Wr + b, then
RA(x) = (1 + aW) -abb
(21)
and when A = 0f for some CCP function f, then the resolvent is given by proximal operator
1 (a = prox) (x) == arg min マ -11====12
=12 az))).
(22)
The resolvent and Cayley operators are non-expansive for any maximal monotone A, and are con- tractive for strongly monotone A. Operator splitting methods consider finding a zero sum of operators (assumed here to be maximal monotone), i.e., find & such that 0 E (A+ (2). For ex- ample, the convex optimization problem in (12) can be formulated as an operator splitting problem with A(=) (T W)= b and B 0f. Proposition 2 shows that A is strongly monotone and Lipschitz with some parameters m and L. Here we give some popular operator splitting methods for this problem follows.
Forward-backward splitting:
k+1 RB(= aA(z*)) i.e.
" ((1 a)l + aW) ab
(23)
k+1 -prox
Rachhoo splitting: ++1 = CACB(u*), 2 = RR(ut))ice.
u k+122 2= u/,
1+2 (I a(1 -W xbb,
(24)
++1 k+1/2 n k+1/2
k+1 proxf (noxx((1**) (1).
Douglas-Rachfoon splitting (or ADMM): k+1
1/2(I+ CCCn)((u) Rp(lu)).
i.e.,
" k+1/2 2 =,,
2 1+1/2 = (I a(I - W)) -u ab),
(25)
d k+1 1 1+12 v k+1/2
k+1 proxf" (u (1).
A sufficient condition for forward-ber backward splitting converge is < 2. The Peacemance- Rachford and Douglas-Race Rachford methods converge for any a > 0, although the convergence speed will often vary substantially based upon a.
16

---

Under review as a conference paper at ICLR 2021
C.2 DYNAMICAL SYSTEM THEORY
In this section, we present some concepts and results of dynamical system theory that are used in this paper. We consider a nonlinear system of the form
(t) f(z(t)
(26)
where z(t) RR is the state, and the function f is assumed to Lipschitz continuous. By Picard's existence theorem we have unique solution for any initial condition. The above system is time- invariant since
not explicitly depends on L. System 26) is called linear time-invariant (LTI)
system if f(2) Az b for some matrix A I=" and b IR.. The point E R" is call an cquilibrium of 26 if fz.) =
The central concern in dynamical system theory is stability. While there many different stability notions (Khalill 2002), here we mainly focus on two of them: exponential stability and contraction w.r.t constant metric Q 0. System (26) is said to be locally exponentially stable the equilib-
rium 2, w.r.t. to the metric Q if there exist some positive constants a, 3, such that for any initial condition x0) E Bx(z)) = {= || 2. l1e 5). the following condition holds:
(+= - 2+11 S a0)=(0) z ==loge 8t Vt 0.0.
(27)
And it is said to be globally exponentially stable if the above condition also holds for any 8 > 0. The exponentially stability can be verified via Lyapunov's 's second method. i.c., finding a Lyapunov function V = ||> with > 0 such that (t) S 223V(tt along the solutions, i.c.,
(= - 2.) 2 P(())+ P(= - z.) + 23(= - 2.) P(= - z+) S.O O.
(28)
System (26 is said be contracting w.r.t. the metric Q if there exist some positive constants a, B such that for any pair of solutions z1 (1) and =2),), we have
(t) - (2)ll S al| (0) 22 (0) St
Vt > 0.
(29)
Note that contraction is much stronger notion than global exponential stability as Condition (27 can be implied by Condition (29) by setting 21 and
z., However, unlike the Lyapunov analysis, contraction analysis can done via simple local analysis which does not require any prior-knowledee about the equilibrium 2,, Specifically, contraction can be established by the local exponential stability of the associated differential system defined by
A = Df(z)
where (!) is the infinitesimal variation between =(t) and its neighborhood solutions, and D is Clarke generalized Jacobian. The condition for (26) to be contracting can be represented as state-dependent Linear Matrix Inequality (LMI) as follows
PDJ(=) + +D(()) 23P 0
(30)
for some P > 0 and all E RR. For an LTT system, exponential stability and contraction are equivalent and the stability condition can be s A is Hurwitz stable (i.e. all eigenvalues of have strictly negative real part).
For most applications, the dynamic system usually involves an external input x=(1) R and an output v() E IRP, whose state-space representation takes the form of
a(t) = f(z(t),<(t)), y(t) = h(=(t), x()).
(31)
Here measure the robustness of the above system under input perturbation by incremental Ly- gain. That is, system (31) has an incremental L2-gain bound of y if for any pair of inputs x (-),
for all T > 0, and any initial conditions 21 (0) and 20), the solutions of 31 exists and satisfy
with 1o" || (t) (B
J' [lon(t) - (2) S 72 /-' [[2 +2(1) di (0),
(32)
for some function n(21, 22) > 0 with n(2, 2) = 0. Note that y can be viewed as a Lipschitz bound of all the mappings defined by (31 with some initial condition from the input signal sx.)) to
17

---

Under review as a conference paper at ICLR 2021
y(-). For any two constant imputs 21, 22. let 21, 22 and 1/1 U2 be the corresponding equilibrium and steady-state output, respectively. From (32) we have
|1 U/ l - 1 - xall #2)1;
which implies a Lipschitz bound of y as 7 co.
A particular class of nonlinear systems that have strong connections to various neural networks is the so-called Luré system, which takes the form of
(tt) = Az(t) + Bo(C2(t))
(33)
where A, B, C are constant matrices with proper size, and Φ is static nonlinearity with sector bounded of [a, 3]: for all solution (v, w) with w o(v)
ww - av) T (Bu w) 2 0
(34)
equivalently
II
2 0 with
W
W
203I (a + 55I 5)I
(a + 8)
II
(35)
-21
This implies that the origin is an equilibrium since (60) = 0. The above system can be viewed as feedback interconnection of linear system
G: ((t) Az(t) + Bw(t) v(() Cz(t)
(36)
and nonlinear memoryless component w((() o(u(t).. The above linear system also be described by a transfer function G(s) with 8 E C. We refer to Hespanha (2018) for details about rrequencyddomain concepts and results of linear systems. The frequency-domain representation for
the sector bounded condition 34) can be written as
{(jw] w(jw)
((jw) ((w))
E R
(37)
where j(jw) and ((jjw) are Fourier transforms of and w. respectively, (.) denotes the com- plex conjugate. Then, the closed-loop stability of the feedback interconnection can be verified by the Integral Quadratic Constraint (IQC) theorem (Megretski & Rantzer 1997). Although the IQC framework allows for more general dynamic multipliers, here we only focus on the simple constant multiplier defined in (35).
of Theorem 3. Let G be stable and di be static nonlinearity with sector bound of [o, B). The feedback
interconnection of G and & stable if here exists >> O such that
[(jw)]
G(jw)
1 -el,
Vi R.
(38)
The Kalman- Yakubovich-Pope Popov (KYP) lemma (Rantzer, 1996) can be applied to demonstrate the equivalence of Condition in Theorem 3 to an LMI condition. The result is stated follows.
Theorem 4. There exists a E > such that (38) holds if and only if there exists matrix P = PT such that
A PA B
PB 0
CT
C 0
0
1
D LBEN PARAMETERIZATION FOR FEEDFORWARD NETWORKS
Given an equilibrium network I with weights U, W,W. and W., we can estimate its Lipschitz bound y by solving the following SDP with (n 1) decision variables:
2A AW WTA
W. AU I
min 7 s.t. AED+
UTA
0
> 0.
(39)
W
71
18

---

Under review as a conference paper at ICLR 2021
Note that the above LMI constraint is equivalent to via Schur complement. A tight upper bound then obtained by minimizing y. When a deep neural network (a special case of equilibrium network) is considered, the above SDP yields the same bound estimation LipSDP-Neuron in Fazlyab et al. 2019) since both formulations involve minimizing the gain bound subject to an equivalent constraint (41).
Training a feedforward network with a prescribed Lipschitz. bound is a challenge problem due to the LMI constraint (39) well as the sparse structure of W. Following the similar idea of direct parameterization, we will construct a parameterization built on to represent the following weight
W1
W
(40)
WL-1 0
We first look simple case where W is dense strictly lower triangular matrix. Given square matrix H. its LDU partition defined as = D + [H] + +H] where [H] diagonal matrix, [H)]r) a strictly lower(upper) triangular matrix. Given any hyper-parameter the parameterization contains the following free variables: E Raxx, W. Rexx, and 0 E Raxd Let = [ [ v = D' and = VŪ where H = VTV + el + (W, W. + (ÚÚT)/22
0,
Then, the LBEN parameterization 9 yields
W = 1 v
W W. +
VV + = 2 H
1 w LUTTUTTT- +VV 27
2
which is dense lower triangular matrix. To impose the sparse pattern like 440
we need
A1
H
H1
A2
H
H2
A3
H3
H
HL-2
AL-1
H AL
H
where A; belongs to D with 1 < i < L, and H2 has the same dimension as W, for S $ L - 1. To make VTV have the same band structure as H, we further parameterize V as follows
r $ Vi
T2
V
L- PzJ
where T,, d E D and V, I. The unitary matrix V, can be parameterized by Vj= = cc where ST = Sy. The diagonal blocks of VTV are I + o with 4 0 while the lower off-diagonal blocks are I 11++1h 2 V, with s j L-1. Similar techniques can be applied to the parameterization of W, and 0.
E PROOFS
E. PROOF OF THEOREM
We presents two proofs for the well-posedness of equilibrium network (1. All these proofs based on the following lemma.
Lemma (Simpson-
Porppson-Pooco-- Porco & Bullo (0144). For a time-invariant contracting dynamical system, all its solutions converge to unique equilibrium.
(Monotone operator perspective): This proof is mainly based on Proposition 2 which states that the
solution of (1) is also zero of the operator splitting problem 0 (A (2), where the operators
19

---

Under review as a conference paper at ICLR 2021
A and B given in (10). Condition 1 implies that the operator A is strongly monotone while maximal monotone. Furthermore, the Clay operator CA is contractive and On is non-expansive. Thus, applying Peaceman Rachford algorithm to 0 e (A + (2) yields a contracting discrete-time system (24) since CaCB is a contractive operator.
Assumption [ implies that the operator
Since 24 time-invariant, it yields a unique solution for any and b_-
(Neural ODE perspective): This proof is built on Proposition 6 which states that the neural ODE
[4 is contracting continuous-time dynamical system under the Assumption and Condition | For any fixed input and bz. system (14) is also time-invarian and hence its solution converges to
unique equilibrium, which is also the solution of (T.
We now prove the Lipschitz boundedness of well-posed equilibrium network. Condition implies that there exists a constant such that
2A - AW - W
For any 5 e0 and weights W., U, we can find a sufficiently large but finite 7 such that
W.W.. + AUUTA) A) ( (c- 5)T.
Then, Condition
2 holds for A and since
2A AW WTA (WTW. W. + AUUT A) = 87 >
From Theorem is Lipschitz bound for the well-posed equilibrium network
E.2
PROOF OF THEOREM 2
Rearranging Eq. yields
2A - AW - A (W.W. w. + AUUTA) =
The well-posedness of the equilibrium network bound, we first apply Schur complement to 4
follows by Theorem
To obtain the I Lipschitz
2A AW
W T A W.
-AU Wo
71 > 0.
TA
Left-multipliing [
A and right-multiplying [
A!] T
gives
2 AA, 2 AWA, 1 W.WWW W.A, 24 AUA, + + 2 0.
Since 5 implies A. WA, + +UA, and A, = W.A., the above incquality is equivalent to
>| 1 1 | 12 2 AA 2A,AA, 2(A, A.)
(41)
Then, the Lipschitz bound of 7 for the equilibrium network T follows by (6)
E.3 PROOF OF PROPOSITION
(i/): well-known that f is convex closed proper function, then prox is monotone and non- expansive, i.e., it is slope-restricted in [o, 1]. Here not necessary to be closed as dom f (i.e. the range of a)) could be open interval (zi, žr) half-open interval (R,, zr] or [z,, zr). This can be resolved by defining f as the restriction of on the closed interval [ 2,]. and then make & 21 and 2, Zy.
(only if): Assumption I implies that is non-decreasing and piece-wise differentiable function on R. Then, the range of a is an interval, denoted by Z. We will construct the derivative function f' on Z first and then integrate it to obtain f. Let {2₁ E Z Zlyez be the sequence containing all points such that either o' (x-
a (x+) for all x (zz). Note that --((2) is singleton for
20

---

Under review as a conference paper at ICLR 2021
Activation
(xx)
Convex f(z)
dom f
ReLu
max(x, 0)
0
[0, (0)
LeakyReLu
max(x, 0.01z)
9 min(z, 0)2
I
Tanh
tanh(ar)
[n(1 - 2²) + 21
1+2 22
(-1,1)
Sigmoid
1/(1 -/(++6
ln (1 - 2) [n(]nn11 -2)
(0.1)
Arctan
arctan(x)
-In(] In[[cos=2]]
(-1,1)
Softplus
In(1 + 6*)
-ii((e*) - -izz - =2/12 (0, xc)
Table 3: A list of common activation functions oxx) and associated convex proper f(2) whose proximal operator is (x). For & dom f, we have f(z) cc. In the case of Softplus activation, [i,(2) is the polylogarithm function.
all E (zj, 1)+)), whereas - 1 (zz) is a closed interval of the forms (-o0, 2r), [2), xir] or (mt, oo). Then, we define f' as follows
if == 2j and min (z) -OC, max (2)] 2, if = 2j and min o (2) -CC, otherwise.
min(o (iin(oo((()) [z)]
(z)
(2) -2,
Without loss of generality, assume that 0 E Z and o -0) is well-defined. We define the function as follows
f()) - [
(())C ('() if E
otherwise,
where an arbitrary constant. Note that f convex function as f' a piecewise differentiable
function on Z and for those points where r = o 0=) is well-defined, f is differentiable with (z(2) 1/0'(z) - 2 0 as d'(x) (0, 1]. Finally, the definition of f implies that E 2 (=) + 0f(z). which implies that (Ix) is the unique minimizer of 1/2(= z)² + f(z). Furthermore, since is well-defined, we can conclude that / is bounded from below. We also provide list of for common activation functions in Table 3 A similar list can also be found in Li ct al. (019)).
E.4 PROOF OF PROPOSITION
Similar to Winston & Kolter 2020), first show that the solution of ① if it exists, is fixed point of the forward-backwart iteration (23) with a =
_+I
R2(=* AA=²) prox| (z* - a(I - W)2* + a(Ux + b.)) = oWW** * + +Ux + bz).
The last equality follows by
arg min,, 1 (21 x2 + f(21)
arg min 1 - 2
((x)
:
Aef())) prox (x).
min.,.,.. [zn xI,²²a= ) + f f(x))
Note that the necessary condition for o(.) to be diagonal is that the weight A is positive diagonal.
Now we prove the well- posedness of LBEN by showing that the operator splitting problem 0 E (A+ (2) has unique solution for any and bg. Both Condition [ [[anndimmlies implies that the operator is strongly monotone and its Cayley operator C^ is contractive. Then, the Peaceman -acchman-Raccford iteration 24 is contracting and hence it converges unique fixed point.
21

---

Under review as a conference paper at ICLR 2021
E.5 PROOF OF PROPOSITION
The matrix J is diagonal with elements in [0. 1]. Decompose A = II(] + uZ) for some small >> 0.
Lee II A(J + ul)-1 which is diagonal and positive-definite By denoting H II( W) (T w IT we obtain the following inequality from 3):
[L - W) + (1 - w) /11 μH = el,
which can be rearranged as
II JW) + (I- Jw) el + 211(1 - μH.
Since 2T J) = 0, we can choose sufficiently small μ such that
II - JW) + II > 0,
which further implies that I JW is strongly monotone w.r.. II-weightd inner product, and is therefore invertible.
E.6 PROOF OF PROPOSITION
First, we show that 12 strongly convex. Since f(=) conic combination of convex functions fz;). we only need to show that the quadratic term is strongly convex, i.e.,
V A(T - W) + A
where
1 2 w) Uz - b2s
[(z)
A
which follows by either Condition or Moreover, since 5 = 0 for the direction parameterization and hence ØJ A. Then, finding the global minimizer
of W, we have A(I W) = (I
of the strongly convex optimization problem 12 is equivalent to finding zero for the operator splitting problem E a(J + f))
B (z).
E.7 PROOF PROPOSITION
The proof is based the "key insights" of ReLU activation from Raghunathan al. 20188))
That is, a ReLU constraint 2 = max( 0) equivalent to the following three linear and quadratic constraints between and æ: (i) 2(2 x) = 0, (ii) 2 and (iii) 0. From this observation an equilibrium network (1 can be equivalently expressed as the following constraints (I) (=-g) g) = 0,
(II) 2 4. and (III)= 2 0, where q Wz + Ux + b. Note that (II) and (III) can be rewritten the
linear constraints in the QP problem
13 while (I) is equivalent to J (() = with
J(z) = A(a 4) = 5² H T
for any A E D It is obvious that J(z) 2 0 for all satisfying (II) and (III), and hence the solution of (T) global minimizer of the QP problem 13}. If A satisfies either Condition [ or [ then H
is positive-definite T3) is strongly convex QP problem. Thus, its global minimizer is unique,
which is also the solution of LBEN
E.8 PROOF OF PROPOSITION
From (14 the dynamics of A. and A, can be formulated feedback interconnection of linear system A. -,, + W A, and static nonlinearity A o(v)) (vx). The linear system can be represented by a transfer function is G(s) = 1/(s + 1)W. The nonlinear component can be rewritten A, Tb ( 12) A, where & as diagonal matrix with each a [0. 1]. For the nonlinear component +, its input and output signals satisfies the quadratic constraint (6) For the
linear system G, have the following lemma.
Lemma 2. If Condition holds, then for all w
{IR [R)
G()w)
0
A
[G(ww)
<0.
(42)
A
-2A
22

---

Under review as a conference paper at ICLR 2021
The KYP Lemma (Theorem states that (42 is equivalent to the existence of a P PP such that
-2P
PW
A
W
0
A
22
0.
It is clear from the upper-left block that P > O. The above incquality also implies
2(-A. + WA A (A, Au, Az)A <(IlA
12 + || (12) - (1..112
for some > The contraction property of the neural ODE 14 follows since
d | 2 WA,, P v < 1 | (2) 2,3 2
dt
for some sufficiently small / > 0. As byproduct of the above inequality, we will show that the operator -f with with f(v) = v + Wo(v) Ur + bg strictly monotone w.r.t. the P-weighted inner product since
(-f(va) f(bb), va ut) = (A. V.A.A.)) 11
E.9 PROOF OF LEMMA 2
Note that 42 is equivalent to
2A Gu(jw)AW Gu(-ju)W" μI
(43)
where Go(jw) T+ For some w E (R 00) let g = RGG(jw) = RGo( (-j]) where denotes
real part. It is easy verify that g 1/222 1) [0, 1]. From
we have
2gA gAW -gW = gel
for some
0. Rearranging the above inequality yields
2 gW ž gel + (1 g)2A
Now, since E [0, 1] the right-hand-sid is convex combination of two positive definite matrices: el and 2A, therefore (43) holds for some μ > and all E (IR U oc).
E. PROOF OF PROPOSITION
It is straightforward to verify that an equilibrium network with the following weights is identical to the feedforward network [5):
T1
0
Un
22
W
2
W-
U
W. =1
0 Wz]. (44)
:
0
W 0_
To construct LBEN parameterization in the form for W, we first need the following lemma. i holds for any strictly lower triangular W.
Lemma 3. Condition
Proof. We prove it by showing that for any 5 > 0, there exists a A E D such that (An, W..) = A,,
W..) + (I- TT > 22-"81. where An: Wi, are the upper left n x n elements of A, W. respectively. For = 1, A1 sufficient since W1 Assuming that 45) holds for A, and Wn. then have
(45)
> 8 is
H(An, W..) 21-18T
-A n+1 2(An+1 - 2 20)
H(An+1, 1i4t1,Wa4 Wn+1) - 21-"8T
(46)
Wn
[ 0]
where An+1 = diag(Ans An+1) and Wa+1
By applying Schur complement to
Wn+1
0
Inequality holds for the case of + 1 Ant1 2- 2n-2 W
Based the above lemma,
construct V such that V 1/2[A(TT (AEA(T-W)--RE AI-
where < = 2 21-"8. By choosing = A and S (AW - W A)/2, the LBEN parameterization
g recovers the exact W. Thus, LBEN contains all feedforward networks 44h.
We note that "skip connections" as residual network can easily be added to the above structure via additional non-zero blacks in the lower-left part of the weight W.
23

---

Under review as a conference paper at ICLR 2021
E.11 PROOF OF PROPOSITION
g
From the MON parameterization
16 we have
(m,, W) 2(1 m) W W 2. TATA22 A
Let Wm. be the set of non-zero and strictly lower triangular W such that Hm, W) = O. Note that Wm, C Wmg if > mg. Because (m,, W) 0 implies H (m2, W) H [m1, W) + 2(m, - m2) > 0 for all m2 < m. Proposition X follows if lim Wm. does not contain all strictly lower triangular W. Since W is strictly lower triangular, HO,, W) is semidefinite matrix whose diagnoal elements are 2. As the norm of W increases, H(,, W) becomes indefinite. example, the set of Wo is characterized by
Taking the feedforward network 44 with I
W, Wi
< 4/ since
27 W1
-W. 21
H(O, W)
= 0.
Now we show that W,, = 0 for all m 2 Since the diagnoal elements of H (m, W) are non- positive when 2 the matrix H (m, W) not semi-definite for any strictly lower triangular W.
F TRAINING DETAILS
F.I MNIST EXAMPLE
This section contains the model structures and the details of the training procedure used for the MNIST examples. All models are trained using the ADAM optimizer Kingma & Ba (2015) with an initial learning rate of x 103. All models trained for 40 Epochs, and the learning rate reduced by a factor 10 every 10 epochs.
The models in the MNIST example are all fully connected models with 80 hidden neurons and ReLU activations. For the equilibrium models, the forward and backward passes models are performed using the Peaceman-Rachford iteration scheme with evaluating the models, we decrease the tolerance of the spitting method to x 10-1 We use the same a tuning procedure as Winston & Kolter (2020). All models were trained using the same initial point. Note that for LBEN, this requires initializing the metric A 1.
1 and tolerance of 1 x 10-2. When
The feed-forward models trained using Lipschitz margin training were trained using the original author's 's code which can be found at https:://// /t//t/ttttu//t com/ coom/ytsma st weaiiiinggiiai 1mt
F.2 CIFAR-10 EXAMPLE
This section contains the model structures and the details of the training procedure used for the CIFAR-10 10 examples. All models are trained using the ADAM optimizer Kingma & Ba (2015) with an initial learning rate of 103. The models was reduced by a factor of 10 after 15 epochs. Each model contains a single convolutional layer, an average pooling layer with kernel size and linear output layer.
trained for 25 epochs and the learning rate
The convolutional LBEN has 81 channels and is parametrized as discussed below. The MON sim- ilarly has 81 channels. Unless otherwise stated, the feed-forward convolutional network has 162 channels which gives approximately the same number of parameters as the LBEN.
The MON was evaluated using the Peaceman-Rachfort Iteration scheme.
CONVOLUTIONAL LBEN
Following the approach of Winston Kolter 2020), we parametrize U and in equation 9 via convolutions. The skew symmetric matrix constructed by taking the skew symmetric part of convolution 5, so that S = (S (5-
T.). (T)
Similar, to Winston & Kolter (2020), we also find that using the following
weight normalized parametrization improves performance. Specifically,
parametrization: V
Va V. 5 1st
V
i and W. = vt We W.
24

---

Under review as a conference paper at ICLR 2021
Reaceman-Rachford is used and the operator W can be quickly inverted using the fast Fourier transform. This situation is more complicated in our case as the term W out W out cannot be represented strict convolution and this is not diagonalized by the Fourier matrix,. Instead, we apply require matrix inversion.
In Winston & Kolter (2020)
Splitting algorithm shown in equation 23 which does
We have observed that the rate of convergence of the -arkawrddd splitting algorithm is highly dependent on the monotonicity parameter m. In particular, for the convolutional models, we found there was a strong trade-off between the ease of solve for the equilibrium versus the model express- ibility and the accuracy of the Lipschitz bound.
25


Reviews:
[{"review_id": "_iFN_Jm2wwM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides a novel approach to guarantee Lipschitz for a special type of equilibrium network. Since I am not an expert in equilibrium networks, I can only comment on high-level problems.\n\n(a) The use of equilibrium networks is not well motivated. Different from a feed-forward network, the computation of an equilibrium network is not always well-posed. It raises the question of why the equilibrium is adopted at the very beginning. While equilibrium networks generalize traditional networks, it is not well explained why people need to deal with the complicated constraints instead of using a traditional network. The toy problems in the experiments are relatively easier to solve using traditional networks. \n\n(b) The choice of equilibrium equation (1) is not very well explained. The fact that it covers a deep or residual network as a special case is not a good reason for generalization --- we hope the generalization has additional properties that a special case does not have. It seems the paper only addresses the direct parameterization of the particular choice of equation (1) and can not be adopted if the equilibrium equation is changed. \n\nI was concerned about the method because the proposed method seems to overkill the original version's simple experiments. The newly added experiments and clarifications make sense to me. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "EMf2eSshzv", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Objective: Find a way to parametrize equilibrium neural networks to allow setting a Lipschitz bound on the input-output mapping. \n\nCentral claims: \n1.\tThere exists an extension to the parametrization proposed in Monotone Operator Equilibrium Networks (MON) that allows for explicitly setting a Lipschitz bound. \n2.\tThe resulting networks (dubbed LBEN here) can be practically trained via. unconstrained optimization, which involves computing the equilibrium using tools from convex optimization. \n3.\tEmpirically, LBEN models can achieve comparable performance with Monotone Operator Equilibrium Networks, their pre-set Lipschitz constants are tight and therefore achieve favorable accuracy-robustness tradeoff. \n\nStrong points: \n1.\tInteresting idea with very strong theoretical backing: I found the theoretical development and analysis of LBEN models very rich and interesting. There are a bunch of novel results scattered throughout, and the analysis draws from a wide variety of disciplines, including convex optimization, dynamical systems theory and control theory. I found the paper delightful to read. The properties that LBEN models are proven to possess (well-posedness under less restrictive conditions than MON and more natural assumptions on the activation functions) are quite compelling. LBEN models also don’t have any extra computational overhad over MON models. \n2.\tClaims are well supported. Claims 1 and 2 are very well supported in theory. Claim 3 can only be confirmed for very small scale experiments. \n\n\nWeak points: I believe the only relative weakness of the paper is its experiments section. \n1.\tLack of large scale experiments: The models trained in the experiments section are quite small (80 hidden neurons for the MNIST experiments and a single convolutional layer with 40 channels for the SVHN experiments). It would be nice if there were at least some experiments that varied the size of the network and showed a trend indicating that the results from the small-scale experiments will (or will not) extend to larger scale experiments. \n2.\tNeed for more robustness benchmarks: It is impressive that the Lipschitz constraints achieved by LBEN appear to be tight. Given this, it would be interesting to see how LBEN’s accuracy-robustness tradeoff compare with other architectures designed to have tight Lipschitz constraints, such as [1]. \n3.\tPossibly limited applicability to more structured layers like convolutions: Although it can be counted as a strength that LBEN can be applied to convnets without much modification, the fact that its performance considerably trails that of MON raises questions about whether the methods presented here are ready to be extended to non-fully connected architectures. \n4.\tLack of description of how the Lipschitz bounds of the networks are computed: This critique is self-explanatory. \n\n\n\nDecision: I think this paper is well worthy of acceptance just based on the quality and richness of its theoretical development and analysis of LBEN. I’d encourage the authors to, if possible, strengthen the experimental results in directions including (but certainly not limited to) the ones listed above.  \n\n\nOther questions to authors: \n1.\tI was wondering why you didn’t include experiments involving larger neural networks. What are the limitations (if any) that kept you from trying out larger networks? \n2.\tCould you describe how you computed the Lipschitz constant? Given how notoriously difficult it is to compute bounds on the Lipschitz constants of neural networks, I think this section requires more elaboration.  \n\nPossible typos and minor glitches in writing: \n1.\tSection 3.2, fist paragraph, first sentence: Should the phrase “equilibrium network” be plural? \n2.\tD^{+} used in Condition 1 is used before it’s defined in Condition 2. \n3.\tJust below equation (7): I think there’s a typo in “On the other size, […]”. \n4.\tIn Section 4.1, \\epsilon is not used in equation (10), but in equation (11). It might be more clear to introduce \\epsilon when (11) is discussed. \n5.\tSection 4.2, in paragraph “Computing an equilibrium”, first sentence: Do you think there’s a grammar error in this sentence? I might also have mis-parsed the sentence. \n6.\tSection 5, second sentence: There are two “the”s in a row. \n\n\n\n\n[1] Anil, Cem, James Lucas, and Roger Grosse. \"Sorting out lipschitz function approximation.\" International Conference on Machine Learning. 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "C1MrdKsPHbK", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "> Summary: This paper studies a new and more general way of parameterizing the simplest equilibrium network of the form $\\sigma(Wz+Ux+b)$, a form that has been tackled by works like (Winston & Kolter 2020)and (El Ghaoui et al. 2019). The authors provide a computationally (relatively) efficient way of computing Lipschitz-bounded equilibrium networks and a detailed analysis of how the network should be constructed, along with the proof of the existence and uniqueness of the fixed point (and with less restrictive conditions when compared to MON). The empirical results on adversarial robustness shows that the proposed approach is a bit more robust than prior layer-based networks and other implicit networks, and validates most of the theoretical claims made by the authors.\n\nMy general opinion is that this paper extends the discussion made in (Winston & Kolter 2020) with its Condition 1 and 2 (e.g., they show that MON is simply a special case of condition 1 with $\\Lambda=I$), and thus provides a reasonable method for constructing Lipschitz bounded equilibrium networks. The paper is overall well-written, and the insights are explained in a clear fashion (I especially like the Example 1, where the authors showed that Condition 1 is a less restrictive formulation). The experimental results validates the theoretical claims of the authors by demonstrating the effectiveness of the approach, but they could also be made stronger. But in general, I think this paper offers an insightful extension on the prior work(s) in this direction, and is an important addition to the implicit-depth neural network literature.\n\nPros:\n\n1. Well-written paper with clearly defined notations and dimensionalities. The proofs are generally easy to follow (and pretty standard, to be honest).\n2. The theoretical and empirical results demonstrate the improvement over the previous MON approach.\n3. The authors additionally study the relationship between LBEN and neural ODEs, which to my knowledge is new (in terms of formally connecting these two implicit models).\n\nCons:\n\n1. The empirical results are still on very small scales and not quite convincing.\n2. While the relaxation of the constraints is novel, many other theoretical contents were already discussed in the MON paper. For example, the non-singularity of $I-JW$, the monotonicity and non-expansiveness of the proximal operators (a well-known result), Appendix B, etc. Granted, the two papers also have slightly different focuses (e.g., MON talked more about the PR algorithm).\n3. The scope of the paper is still on the simplest $\\sigma(Wz+Ux+b)$ form, which has been studied before. There is a lack of discussion on the challenge involved in building Lipschitz equilibrium models more generalized than this, and it's unclear how well some of the claims of the authors hold in a general setting (see my questions below).\n\n---------------------------------\n\nSome more questions/comments:\n\n1. I didn't find the proof to Theorem 1's claim on \"finite Lipschitz bound from $x$ to $y$\" in the paper. I didn't find a formal \"proof\" to Theorem 1, and the proof of uniqueness is simply on page 4. But what does Assumption 1 and Condition 1 imply about the Lipschitz constant?\n\n2. In the Neural ODE discussion, the paper claims that \"for any well-posed equilibrium network, there corresponds a contracting (strongly stable) neural ODE\", which intuitively makes sense to me (as one can think of a deep equilibrium model as a backward Euler...?). But more strictly speaking, is this supposed to be a general statement for deep equilibrium neural networks, or just for networks of the form (1) in the paper (i.e., $\\sigma (Wz+Uz+b)$)? If the latter, I think the authors may want to clarify this; if the former, I think a proof would be hard (e.g., the (Bai et al. 2019) DEQ-Transformers), but I'd appreciate if the authors can give more theoretical insights on this.\n\n3. One concerning part is the empirical study of the approach. To be clear, I think the authors did a good job validating the approach by comparing with MON and unconstrained DEQs (where their finding seem to agree with prior works that these unconstrained DEQs eventually have pretty bad Lipschitz constant). But I think two important pieces are missing. First, since Condition 1 (and thus Eq. (10) in the paper) provide a less restrictive formulation than MON, one would naturally think that the LBEN built in this way could have stronger representational power. But the results do *not* seem to suggest so. The $\\text{LBEN}_{\\gamma < \\infty}$ seems overall very close to the $\\text{MON}$ results in Table 1 and Figure 3(a). Second, (and together with the first point), I think it would be more useful to study a larger dataset, like CIFAR-10/100 (which MON did provide), with a convolutional LBEN. I'm curious to see how it compares with MON and other implicit models there. \n\n4. Since LBEN also uses similar method(s) as MON to compute the equilibrium point (e.g., Peaceman-Rachford), I'm assuming this method is not \"more scalable\" than the previous methods as you are solving the same high-dimensional equilibrium system? Can the authors confirm this? What about the memory efficiency during training?\n\n---------------------------------\n\nSome minor things:\n\n- i) I didn't realize that the text following Theorem 2 on page 4 is the proof to Theorem 1 & 2 (as there is a \"but first we make some straightforward remarks\" sentence). It'd also be helpful, I think, to say something like you are assuming for (the sake of) contradiction that there are two solutions $z_a \\neq z_b$. It was a bit surprising to me to see $z_a$ and $z_b$ as the theorem claimed \"uniqueness\".\n\n- ii) Page 4 \"on the other size\" ---> \"on the other side\"?", "extra_scores": {}, "extra_text": {}}, {"review_id": "1hAgXDNxQLz", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary: The paper introduces a new condition for showing the existence of the solution of a deep equilibrium model (which defines an implicit mapping via the fixed point). The new formulation also comes with a convenient and accurate Lipschitz bound. The proposed condition can be satisfied via reparameterizing an unconstrained set of trainable parameters. \n\n\nContributions: introduces a new parameterization of DEM. The parameterization satisfies a condition which is shown to imply the existence of the unique solution of the fixed point. The paper introduces two proofs: the solution of the DEM can be shown to be equivalent to 1) the minimizer of a strongly convex potential and 2) the equilibrium of a contractive neural ODE. The results seem nontrivial (although I did not check the correctness). \n\n\nWeakness: the paper is more theoretical, and weaker on the empirical side. The new condition on the weights are less restrictive than the condition of Winston & Kolter, which means the model has better expressivity. However, the benefit of this extra expressivity is not discussed much and demonstrated empirically, which is why I lean towards weak rejection. The model used in the experiment section is also very small (80 hidden units for MNIST), which does not seem very realistic for testing adversarial attack. \n\nAlso, I think the paper is quite borderline given its scope, and it depends on the wider adoptability of DEM. It will help me better understand its potential impact if the authors could try to motivate it better, explaining the need to further study the theoretical properties of DEM. \n\nAdditional details\n- What is the L2 fast gradient sign method? FGSM restricts the L infinity norm of the perturbation. \n- Please provide some visualization of the perturbed and unperturbed data points. \n\n\nMinor points:\n- The discussion of computational complexity can be moved to the main text (right now it’s not really in Fig 4, it’s in its caption). Also are all four variants run on the same machine? Why is unconstrained slower? \n- Typo: between (7) and (8), “on the other size*”\n\n\n=== AFTER REBUTTAL ===\n\nThe authors have raised a few fair points in the rebuttal (especially point 1), so I've adjusted my rating accordingly. \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is an extension of Monotone Operator Equilibrium Networks (MON). It first tries to address a key issue in MON: whether the activation function $\sigma$ can be represented by a proximal operator of some function $f$. Then it derives the constraints on the weight $W$. Connections to neural ODEs and convex optimization are also built. 

Pros:
1. Very nice theory, reads exciting, and provides great insights.
2. Experiments seem to validate part of the theoretical analysis.

Cons: Besides the issue of weak experiments raised by the reviewers (and the authors admitted "quite rudimentary empirical results"), the AC regretted that the proofs have some key flaws. 
1. The proof of Proposition 1, which is the cornerstone of the paper, is wrong. Although the AC believed that Proposition 1 is likely to be true, the current proof of "only if" is unfortunately incorrect. Please notice the claim at the first line of the "only if" proof, which writes "$\sigma$ is a non-decreasing and piece-wise differentiable function". Although it is known in real analysis that monotone functions are almost everywhere differentiable, this does not necessarily mean that monotone functions can be piece-wise differentiable functions as the non-differentiable points can be dense, though of zero measure. 
2. Proposition 7, which claims that LBEN parameterization (8) contains all feedforward networks, is wrong. From the proof on page 19, the AC doubted whether the lower diagonal blocks of $-2H_D^{-1}  H_L$ can be $\{W_i\}$. This is because by the definition of $H$ given at 5 lines below (40), $H$ must be positive definite. If the lower diagonal blocks of $-2H_D^{-1} H_L$ can be $\{W_i\}$, then $H_i=\Lambda_i W_i$.  It is not apparent whether for any choice of $\{W_i\}$ there exist $\{\Lambda_i\} \in D^+$, such that $H$ is positive definite. Moreover, the lower diagonal block of $V^TV$, i.e., $\Gamma_{j+1}V_j\Phi_j$ (corrected from the typo in the minor issue 2 below), must equal to $\Lambda_j W_j$. However, it is obvious that for some $W_j$ (e.g., it has more columns than rows), there cannot exist $\Gamma_{j+1}$, $V_j$, $\Phi_j$ and $\Lambda_j$, such that $\Gamma_{j+1}V_j\Phi_j=\Lambda_j W_j$, due to the structures of these matrices. Moreover, due to the existence of $(...)/(2\gamma)$ in the definition of $H$, the diagonal blocks of $H$ cannot be diagonal by the choice of $V$.
3. Proposition 7 again. The choice of parameters in (44) does not match the feedforward network in (15). Please observe that by (44) $z_1=\sigma(U_0 x + b_0)$, rather than $z_1=U_0 x + b_0$ in (15).

Minor issues:
1. The proof on page 19 is for claiming that (9), rather than (8), contains all feedforward networks.
2. In the choice of $V$, $\Psi_i V_i$ should be $V_i\Phi_i$.

Although the reviewers and the AC liked the paper, due to the above flaws and limited acceptance rate, the AC deemed that the flaws should be fixed prior to acceptance.
Decision: Reject