Robust Implicit Networks via Non-Euclidean Contractions
Authors: Saber Jafarpour
Alexander Davydov
Anton Proskurnikov
Francesco Bullo
Venue: NeurIPS 2021 Poster (2021)
Keywords: Implicit deep learning
Contraction theory
Robust neural networks.

Abstract: Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicit-depth learning models where function evaluation is performed by solving a fixed point equation. They generalize classic feedforward models and are equivalent to infinite-depth weight-tied feedforward networks. While implicit models show improved accuracy and significant reduction in memory consumption, they can suffer from ill-posedness and convergence instability.

This paper provides a new framework, which we call Non-Euclidean Monotone Operator Network (NEMON), to design well-posed and robust implicit neural networks based upon contraction theory for the non-Euclidean norm $\ell_\infty$. Our framework includes (i) a novel condition for well-posedness based on one-sided Lipschitz constants, (ii) an average iteration for computing fixed-points, and (iii) explicit estimates on input-output Lipschitz constants. Additionally, we design a training problem with the well-posedness condition and the average iteration as constraints and, to achieve robust models, with the input-output Lipschitz constant as a regularizer. Our $\ell_\infty$ well-posedness condition leads to a larger polytopic training search space than existing conditions and our average iteration enjoys accelerated convergence. Finally, we evaluate our framework in image classification through the MNIST and the CIFAR-10 datasets. Our numerical results demonstrate improved accuracy and robustness of the implicit models with smaller input-output Lipschitz bounds. Code is available at https://github.com/davydovalexander/Non-Euclidean_Mon_Op_Net.

Robust Implicit Networks via Non-Euclidean Contractions
Saber Jafarpour" Alexander Davydov' Anton V. Proskurnikov and Francesco Bullo'
Center for Control, Dynamical Systems and Computation, University of California, edu.
Santa Barbara, 131---007, USA, {saber, davydov,
2 Department of Electronics and Telecommunications, Politecnico di Torino, Turin, Italy; Institute for Problems Mechanical Engineering, Russian Academy of Sciences, St. Petersburg, Russia, anton. 19828iee.. org
Abstract
Implicit neural networks, a.k.a., deep equilibrium networks, are class of implicit- depth learning models where function evaluation performed by solving a fixed point equation. They generalize classic feedforward models and are equivalent to infinite-depth weight-tied feedforward networks. While implicit models show improved accuracy and significant reduction in memory consumption, they can suffer from ill-posedness and convergence instability.
This paper provides a new framework, which we call Non-Euclidean Monotone Operator Network (NEMON), design well-posed and robust implicit neural networks based upon contraction theory for the non-Euclidean norm foo. Our framework includes (i) novel condition for well-posedness based one-sided Lipschitz constants, (ii) an average iteration for computing fixed- fixed-points, and (iii) explicit estimates on input-ouiput Lipschitz constants. Additionally, we design a training problem with the well-posedness condition and the average iteration as constraints and, to achieve robust models, with the input-output Lipschitz constant a regularizer. Our lo well-posedness condition leads to larger polytopic training search space than existing conditions and our average iteration enjoys accelerated convergence. Finally, we evaluate our framework in image classification through the MNIST and the CIFAR-10 datasets. Our numerical results demonstrate improved accuracy and robustness of the implicit models with smaller input-output Lipschitz bounds. Code available https: /ttps://gi. //githbb. thub. com/ con/davydovalezeen exaader//ooooooooeee -ucliieaenn Mon_0p_____ Ne_Net.
Introduction
Implicit neural networks are infinite-depth learning models with layers defined implicitly through fixed-point equation. Examples of implicit neural networks include deep equilibrium models [Bai et al., 2019] and implicit deep learning models [El Ghaoui et al., 2021]. J. Implicit networks can be considered generalizations of feedforward neural networks with input-injected weight tying, i.c., training parameters are transferable between layers. Indeed, in implicit networks, function evaluation is executed by solving fixed-poins equation and backpropagation is implemented by computing gradients using implicit differentiation. Due to these unique features, implicit models enjoy more flexibility and improved memory efficiency compared traditional neural networks. At the same time, implicit networks can suffer from instability in their training due to the nonlinear nature of their fixed-pone point equations and can show brittle input-output behaviors due to their model flexibility.
These authors contributed equally.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

It is known that implicit neural networks require careful tuning and initialization to avoid ill- ill-posed training procedures. Indeed, without additional assumptions, their fixed-point equation may not have a unique solution and the numerical algorithms for finding their solutions might not converge. Several recent works in the literature have focused on studying well-posedness and convergence of the fixed- point equations of implicit networks using frameworks such as monotone operator theory [Winston and Kolter, 2020], contraction theory [El Ghaoui et al., 2021], I, and a mixture of both [Revay et al., 2020]. Despite several insightful results, important questions about conditions for well-posedness of implicit networks and efficient algorithms that converge to their solutions are still open.
One of the key features of implicit neural networks is their flexibility, which might come at the cost of low input-output robustness. As first noted in [Szegedy et al., 2014], the input-output behavior of deep neural networks can be vulnerable to perturbations; close enough input data can lead to completely different outputs. This lack of robustness can lead to unreliable performance of neural networks in safety-critical applications. Among several notions of robustness, the Lipschitz constant of neural network is a coarse but rigorous measure which can be used to estimate input-output sensitivity of the network [Szegedy et al., 2014]. For this reason, there has been a growing interest in estimating the input-output Lipschitz constant of deep neural networks with respect to the f--norm [Fazlyab et al., 2019, Combettes and Pesquet, 2020]. However, it turns out that in some applications, the input- output Lipschitz constants with respect to non Euclidean norms are more informative measures for studying robustness. One such application appears in the robustness analysis of neural networks with large-scale inputs under didtiy-distributed adversarial perturbations (examples of these adversarial perturbations can be found in [Szegedy et al., 2014]). For these examples, the input-output é2- Lipschitz constant does not provide complete information about robustness of the network; a neural network with small input-output fz-Lipschitz constant can be very sensitive widespread entrywise- small perturbations of the input signal. On the other hand, the input-output Lec-Lipse constant provides a different metric which appears to be well-suited for the analysis of widespread distributed perturbations. Another application is the estimation of input signal confidence intervals from output deviations, where the input-output Lippscitz constant of the network provides more scalable bounds than its lg counterpart.
Related works
Implicit learning models. Numerous works in learning theory have shown the power of deep learning models with implicit layers. In these learning models, the notion of layers are replaced by composition rule, which can be either fixed-point iteration or solution to a differential equation. Well-known frameworks for deep learning using implicit infinite-dppth layers include deep equilibrium networks [Bai al., 2019], implicit deep learning [E] Ghaoui et al., 2021], and Neural ODEs [Chen et al., 2018J. In [Kag et al., 2020]. a class of implicit recurrent neural networks is considered and it is demonstrated that, with this architecture, the models do not suffer from vanishing nor exploding gradients. Implicit layers have also been used to study convex optimization problems [Agrawal et al., 2019] and design control strategies [Amos et al., 2018]. Convergence to global minima of certain classes of implicit networks is studied in [Kawaguchi, 2021].
Well-posedness and numerical algorithms for fixed-point equations. There has been re- cent interest in studying well-posedness and numerical stability of implicit-depth learning models. [E] Ghaoui et al., 2021] proposes a sufficient spectral condition for well-posedness and for con- vergence of the Picard iterations associated with the fixed-point equation of implicit networks. In [Winston and Kolter, 2020, Revay et al., 2020], using monotone operator theory, suitable parametrization of the weight matrix is proposed which guarantees the stable convergence of suitable fixed-point iterations. A recent influential survey monotone operators is [Ryu and Boyd, 2016]. A recent survey on fixed point strategies in data science is given by [Combettes and Pesquet, 2021].
Robustness of learning models It is known that neural networks can be vulnerable to adversarial input perturbations [Szegedy et al., 2014]. large body of literature is devoted to improve robustness of neural networks using various defense strategies against adversarial examples [Goodfellow et al., 2015, Papernot et al., 2016]. While these strategies are effective in many scenarios, they do not provide formal guarantees for robustness [Carlini and Wagner, 2017]. However, there has been recent interest in designing classifiers that are provably robust with respect to adversarial perturba- tions [Madry et al., 2018, Wong and Kolter, 2018]. The input-output Lipschitz constant of neural

---

network is rigorous metric for its worst-case sensitivity with respect to input perturbations. Several recent works have focused on estimating the Lipschitz constant and enforeing its boundedness. For example, [Fazlyab et al., 2019, 2020] propose convex optimization framework using quadratic constraints and semidefinite programming to obtain upper bounds on Lipschitz constants of deep neural networks. In [Pauli et al., 2021], training algorithm is designed to ensure boundedness of the Lipschitz constant of the neural network via a semidefinite program. Other methods for estimating the Lipschitz constant of deep neural networks include [Krishnan et al., 2020, Revay et al., 202 I, Combettes and Pesquet, 2020]. For implicit neural networks, a sensitivity-based robustness analysis is proposed in [El Ghaoui et al., 2021]. Lipschitz constants of deep equilibrium networks have also been studied in [Pabbaraju et al., 2021, Revay et al., 2020] using monotone operator theory.
Contributions
In this paper, using non-Fuclidean contraction theory with respect to the &o -norm, we propose our novel framework, Eucl-dean Monotone Operator Network (NEMON), design implicit neural networks and study their well-posedness, stability, and robustness. First, we develop elements of a novel Non-Euclidean monotone operator theory akin to the frameworks in [Bauschke and Combettes, 2017, Ryu and Boyd, 2016]. Using the concept of matrix measure, we introduce the essential notion of one-sided Lipschitz constant of a map. Based upon this notion, we prove general fixed- fixed-point theorem with weaker requirements than classical results on Picard and Krasnosel Mann iterations. For maps with one-sided Lipschitz constant less than unity, we show that an average iteration converges for sufficiently small step sizes and optimize its rate of convergence. For the special case of the weighted (----orm, we show that this average iteration can be accelerated by choosing larger step size. Additionally, we study perturbed fixed-point equations and establish bound on the distance between perturbed and nominal equilibrium points as a function of one-sided Lipschitz condition. Second, for implicit neural networks, we use new fixed-point theorem to (i) establish fx -nor conditions for their well-posedness. (ii) design accelerated numerical algorithms for computing their solutions, and (iii) provide upper bounds their input-output & Lipsschtt constants. Third, propose a parametrization for matrices with appropriate bound on their one-sided Lipschitz constants and use this parametrization with the average iteration to design a training optimization problem. Finally, we perform several numerical experiments illustrating improved performance of NEMON in image classification the MNIST and the CIFAR-10 datasets compared the state-of-the-an models in [E] Ghaoui et al., 2021, Winston and Kolter, 2020]. Additionally, by adding the input-output Lipschitz constant regularizer in the training problem, we observe improved robustness some classes of adversarial perturbations. We include all relevant proof' in Appendix C.
Review material
Matrix measures Let || - || be a norm on R and its induced norm on RR The matrix measure of A R with respect to || || defined by (A) == lim,--ot [| - that is, the sided directional derivative of the induced norm in direction of A. evaluated at I,.. Remarkably, the matrix measure tighter upper bound on the spectral abscissa of A than ||-A]| and the set of matrices A E R satisfying {(AA) I 1 is an unbounded subset of Rax* strictly containing the compact ball ||-||| <
We refer to [Desoer and Haneda, 1972] for list of properties enjoyed by matrix measures.
We will be specifically interested in diagonally weighted for norms defined by
1
| max |zal.
(1)
where, given a positive vector 7) E Rg we use [n] to denote the diagonal matrix with diagonal entries 17. The corresponding matrix norm and measure are
||ll
max dE (I.......))
M laggl Moo.(o) (A)
max :E(I.....)
(at + j j=1.jght
Σ
|ais
(2)
Lipsehitz maps Given a norm | with induced matrix measure uu-), a differentiable map Rm + " is Lipschitz continuous with constant Lip(F) E Rzo if
[>F(x)]] S Lip(F) for all x E R".
(3)
For example, for an affine F(x) = Ar + b, the (smallest) Lipschitz constant is Lip(F) = ||A|||
3

---

One-sided Lipschitz maps Given norm || -1,, differentiable map F R" - R" is one-sided
Lipschitz continuous with constant (sL(()) R
p(DF(z)) osL(F)
for all 1"".
(4)
For example, for an affine F(z) = Ar + b, the (smallest) one-sided Lipschitz constant is osL(F) =
((A). Note that (i) the one-sided Lipschitz constant is upper bounded by the Lipschitz constant, (ii) Lipschitz continuous map is always one-sided Lipschitz continuous, and (ii) the one-sided Lipschitz constant may be negative. For more in-depth review refer Appendix A. The notion of one- sided Lipschitz continuity unifies several important concepts in dynamical systems and optimization theory. In operator theory, the map F is called monotone operator if it is one-sided Lipschitz continuous with respect to the ε2-norm with the constant - (-F) > [Ryu and Boyd, 2016, Bauschke and Combettes, 2017]. In control theory, the vector field F is called strongly infinitesimally contracting if it is one-sided Lipschitz continuous with the constant osL(() < 0 [Desoer and Haneda, 1972, Lohmiller and Slotine, 1998, Pavlov et al., 2004]. In what follows, we let [oi E I denote the one-sided Lipschitz constants with respect to the weighted foe norm.
3 Fixed-point equations and one-sided Lipschitz constants
In this section, we show that the notion of onesidee Lipschitz constant can be used to study solvability of fixed-point equation:
x = F(z),
(5)
where F: RR -> R is differentiable map. Let || be fixed-point theorem, a simple sufficient condition for existence of a unique solution for the fixed-point equation (5) is Lip(F)= < 1. We note that the sufficient condition Lip(F) 1 depends on the specific form of the fixed-point equation (5) and can be relaxed by a suitable rewriting of this fixed-point equation. Given an averaging parameter
RR, then in view of the Banach
(0, 1] define the average map F., R R by Fa = (1 aa)l + aF, where is the identity map. Using this notion, an equivalent reformulation of the fixed-point equation (5) is:
=1-1-a)r - aF oF(x) = (z).
(6)
For a = 1, we have (x) = F(xx) and equation (6) coincides with equation (5). For every a E (0, 1), the map F., is different from but equations (5) and (6) are equivalent. Hence, if Lip(F.) < 1, then by the Banach fixed-point theorem, the fixed point equation (6) (and therefore the fixed point equation (5)) has unique solution x= and the sequence (y))e= defined
Vk+1 = (1 - a)8k + aF())).
for all k E Zzo
converges geometrically to x² with rate Lip(F.). As result of the parametrization (6), the condition Lip(F) < for existence and uniqueness of the fixed-point can be relaxed to sufficient conditions
Lip(Fa) <1
parametrized by E (0, 1J. Additionally, if condition (8) is satisfied, then algorithm (7) computes the fixed point x=" It can shown that the condition (8) becomes less conservative as a decreases. The next theorem shows that in the limit as - 0+, condition (8) approaches the condition osL(() < 1.
Theorem 1 (Fixed points via one-sided Lipschitz conditions). Let F ; IR" + R" be differentiable and Lipschitz with constant l > with respect to norm and, for > 0, the function "e, J0, (c+e+1)(E+1)
||. Define the average map F.. (1 (1-aa) (1-a))++ar
+ R by:
(a) = (1 ac
a2 1)²
a(
Then the following statements are equivalent:
(i) osL(F) < -
(ii) Tip(Fa) = Te,e(a)), <a< (effFixe1))
Moreover, if the equivalent conditions (i) or (ii) hold, then, for condition number = 1+Lip(()
I-osL(F))

---

(iii) F has unique fixed point r";
(iv) for < a =(p-1j Fo: is contraction mapping with contraction facttt Te,e(a) < 1;
(v) the minimum contraction factor Tē.e = =1 -kx2 Sx parameter a' F is
+0 (x4)
and the minimizing averaging
a- - OsL(F) (1- /1+1/R/
1
3 8
O
osL(()
2k²
Ara
The average iteration (6) is often referred as the Krasnosel Maini-Mann iteration or the damped iteration [Bauschke and Combettes, 2017]. Compared to [Bauschke and Combettes, 2017, Theorem 5.15], Theorem I(iv) studies convergence of the Krasnosel srrssnsee'skiiMMii skii-Mann iteration for arbitrary norms, proposes weaker convergence condition of the form osL(F) 1 (hence, F need not be non- expansive). However, it ensures convergence for only sufficienlly small > and assumes that is differentiable (as will be shown, however, the latter assumption can be relaxed).
3.1 Accelerated convergence for weighted for norms
For diagonally weighted & norms, one can strengthen Theorem 1(iv) to prove the convergence of the average iteration (6) on larger domain of the parameter a.
Theorem (Accelerated fixed point algorithm for lox norms), Let F R² + R" be differentiable
and Lipschitz with respect the weighted non-Euclidean norm || [loo.in) 1. Define the average map
F. (1 a)) + oF and pick diagL(F) E [ (ip(FF),oL((FF)))
satisfy
diagL(F) S
min inf DF.(x)).
xE (E.....)) DER"
(FF) 1, then F has unique fixed-point x² and
(i) for 5 1
diagL(F) Fo contraction mapping with the contraction factor a(1 os)((F) <1;
(ii) the minimum contraction factor and minimizing averaging parameter Fa are, respectively, diagI.(F) + Lip(F)
(F)
1
Lip(Fa-)== = diagL(F)
for toc = 1 - oss((F)
< 1 - (FL
Koo
a' I dFagL(F))
Note that dFagL(F) is well-defined because of the Lipschitz continuity assumption. Specifically, one show that diagL(F) is the minus the minimum over i f1....,,1, n.) of the one-sided Lipschitz constants the maps 2; + -F(,, ( at x- = (I1, .., 21-1, ,.,,..... fixed.
Fn,)
It is instructive to compare the minimum contraction factor in the general Theorem with the minimum contraction factor for lo norms in Theorem 2 and how they depend upon the corresponding condition numbers and Kis- We note that (i) the relevant condition number diminishes 2 Kioo and (ii) the minimum contraction factor Lip(Fa.) This acceleration justifies the title of this section.
परन + (1/xx2) improves Lip(Fa.) Koc
3.2 Perturbed fixed-point problems
In this subsection, we focus on solvability of the perturbed fixed-point equation:
F(x,
(10)
where F: R x Rr > I is differentiable æ. define (z(x)) F(a,, u) and Fz(u) F(r, u). Given norm || a|x in R" and || Ilu in R", F is Lipschitz in its first argument with constant (ip, E R>0
(|F( F(x2, x)Ilx Lipx æ2 x2l1x for all 21, x2 E IR" and E R
5

---

and it is Lipschitz in its second argument with constant (F) E Rz0 if [[F(z, u1) - F(z, u2)llx & Lip. - u2llu for all x E IR" and u1, U2 E R,,
and it one-sided Lipschitz in its first argument with constant osL R if
|r Fxr, u)) I (F) for all ø1; 22 IR" and R².
The following result, which is in the spirit of Lim's Lemma [Lim, 1985], provides an upper bound on the distance between fixed-points of the perturbed equation (10).
Theorem 3 (Perturbed fixed-points). Given norm || -Ix in R" and norm || -lu in IR, consider map F IR" x I' + R differentiable in the first argument and Lipschitz in both arguments. If is one-sided Lipschitz with conslant (F) < 1, then
(i) for every u E R",, the map Fu has a unique fixed point x.:
LFp,(() (ii) for every u, U E RT", || - x 1- osT., 1|u vilke.
Finally, Theorems 2, and entiable. In Appendix C.3, we show that for specific form of the fixed-point equation (5), where == 4 and & R2 + IR" is a weakly increasing, non-expansive, diagonal activation function and H R" x R' + R² is differentiable function, all of the conclusions of Theorems 1, 2, and hold by requiring equation (9) to be true almost everywhere.
directly applicable to activation function that are not differ-
4 Contraction analysis of implicit neural networks
In this section, contraction theory to lay the foundation for our Non-Euclideaa Monotone Operator Network (NEMON) model of implicit neural networks. Given A E R= B R"xr, C' _axn, and D E Raxr, consider the implicit neural network
x (AAz + Bu) == N(x, u). y= - C
(1I)
where x E 12, u E R RR.YE E E R and 4 12 + R² is defined by 4(x) = (x) (21)..... (n()))) n). we assume the activation function o; -R + IR is weakly increasing, i... For every iE ( (x;) 2 (2) for x, 2 24, and non-expansive, i.e., (x;) (x(2;) I |2, 2, for all x; and 2;; if Φ, is differentiable, these conditions equivalent
(x;), I 1 for all E IR
We are able to provide the following estimates on relevant Lipschitz constants.
Theorem 4 (Lipschitz and one-sided Lipschitz constants for the implicit neural network). Consider the implicit neural network in equation (11) with weakly increasing and non ron-expansive activation functions O. With respect || [loe.[n)-t, 7) E R on R and ||. llu on the input space RT, the map N: : R" x R + R" is one-sided Lipschitz continuous in the first variable and Lipschitz continuous in both variables with constants:
2sL (N) = [o) (A)+
Lip (N) || |v] 1,
(12)
Lip, (N) = [Bll(o, 1),01
diagL(N) min.e (An)
(13)
where (=)+ if x and (z)+ + 0 if < 0; and (z) 0 if and (2) if 2 0.
We now use these estimates to establish multiple properties of the implicit neural network.
Corollary 5 (Well posedness, input-state Lipschitz constant, and computation). Consider the model (11), with parameters (A, B, C, D) and with weakly increasing and expaasxansvve acti- vation functions functions 4. Define the average map Na := =1-aa)l + aN and consider the norms || [|=11s0.17]
1 E 125, on IR"", || llu on the input space IT and || |ly on the output space Ra, Then
(i) if Poolll (A) < 1, then (11) is well posed, i.e., there exists unique fixed point,
(it) the map No contraction mapping for a S a* = (1 ml ......) (An)-) with minimum contraction factor (ip(NN.) = 1 I-min,e (1...... (A.))
1- (

---

(iii) the Lipschitz constants from input u to fixed point x,, and to the output Cæ + Du are
(N)
| (oc. 1,44
Lip
(14)
1 - oss (N) 1 1 Moo,[11 [000 (A)
B [oc. 1).2 (/lpa//Clll,,o,.,/t
Lipu-y
+ P|
(15)
Moo,[ol-1 (A)+
5 Training implicit neural networks
Problem setup Given an imput data matrix U [2g [ ..... um] E R= and a corresponding output data matrix Y = [y...... yml E R we aim to learn matrices A, B, C, D so that the neural network (1I) approximates the input-output relationship. We rewrite the model for matrix inputs as Y ==CX CX + DU, where X ((AX + BU). From Corollary 5(i), each Φ; is weakly increasing and non-expansive, the fixed point problem is well-posed when [o (A) < 1 for some R50- We consider a training problem of the form
min A.B.C.D.X
L(V,CX + DU) + P(A,
(16)
X= O BU), Moc.tv -1 (A) 5
where C is loss function, P is a penalty function, and y < 1 is a hyperparameter ensuring the fixed point problem is well-posed. For 1j 1, we can remove the constraint /o (A) S in the training optimization problem (16) using the following parametrization of weight matrix A:
A = T T diag([T[n.)) +IIn-
(17)
In Appendix B, we show that parametrization (17) characterizes the set of matrices in Rax sat- isfying (A) & y. Using the parametrization (17) in the training problem not only improves the computational efficiency of the optimization but also allows for the design of implicit neural networks with additional structure such as convolutions. Suppose u E RR* is a r-channel input of size 8 X and x E IR,ss is n-channel hidden layer. To define our implicit CNN, we select the weight matrix A Rns" xns" as the matrix form of 2D convolutional operator. If we consider a circular convolution operator, then is a circulant matrix. Using the parametrization (17), A is circulant if and only if T is circulant. Therefore, the training problem for implicit CNNs can be cast as an unconstrained optimization problem using the above parametrization with a circulant T.
Improving robustness via Lipschitz regularization We now focus on learning robust implicit neural networks with bounded Lipschitz constants via a regularization strategy. Setting both || l|x and || |yy as || ll in the input-output Lipschitz Lipschit bound (15), we get
Lip
+ ||D||
1 Mox (v) (A)+
[ [o..)))
|1C [000)) + |
(,) (A)+
where the inequality provides convex upper bound for the input-output Lipschitz constant. Therefore, using the hyperparameter X > 0, the regularized optimization problem is written as
|| 2
(x) + [|CT))())))0000)))))))))) +|DD|ooo,od
C(Y DU) + (
min A.B.C.D.X
1 -oo, - (A)+
X +(AX + BU),
- (A) 5-
(18)
Certified adversarial robustness via Lipschitz bounds Given nominal input E R". consider any perturbed input e within an loo-ball of radius e around u. this case, we have
I| Volloo < Tip ||u - 2/130 S Lipa
(19)
Then we define margin(w) u) = (y.); mi where (yw); the logit corresponding to the (correct) label i for the input u. Then provided L S 1 marginn(u). NEMON is certifiably robust to any perturbed input within an & -ball of radius centered at
7

---

Backpropagation of gradients via average iteration From [El Ghaoui et al., 2021] we now show how the average iteration can be used perform backpropagation via the implicit function theorem. For simplicity, we assume that each activation function &e is differentiable and consider mini-batches of size 1, i.e., have X of the fixed-point equation (11). Then the chain rule implies
R", U
I" and Y
R Let xx be the unique solution
ac
dc
0 (Vx.L)x',
0 (V C)u
0C
0C
(VoL)='
= (VgL)u
ac
0D
Since C depends explicitly on y. computing VgC is straightforward. Computing v. C more complicated since X is defined only implicitly. However, it be shown that
v=-L= (C(1 - -) DΦ) VgC.
Since (xx.(n)-1(A)) < 1, by Lemma 8 we get that Moo,[n)-1 (DDA) < 1. This implies that the matrix G == (In - A) (i))-DD D$ E I exists and is the solution to the following fixed-point equation [B] Ghaoui al., 2021, Section 6.2]
G (DG + I.).
(20)
Moreover, [ae (D < and Theorem together imply that the fixed-point equation (20) has unique solution G* and, for every 0 < S aa = (1 min)(4a)-) the average iterations
Gk+1 = (1 - a3 + (AG + In), for all & E Zzo
are contracting with the minimum contraction factor a* (1 Mo. (A)+) step size a².
6 Theoretical and numerical comparisons
In this section, we provide a comprehensive comparison of our framework with the state-of-the-ard implicit neural networks?.
6.1 Implicit network models
We start by reviewing the existing models for implicit networks in the literature.
Implicit deep learning model. [El Ghaoui al., 2021] proposes class of implicit neural networks with onput-output behavior described by (11). It is shown that sufficient condition for existence and uniqueness of a solution and convergence of the Picard iterations for the fixed point equation 4(Ax + Bu) is (IA) < 1, where |.|] denotes the entrywise absolute value of the matrix A and App denotes the Cerron-Frobeniig eigenvalue. For training. the optimization problem (16) is used where the constraint Moo.(n (A) S y is replaced by ||A|| S [EI Ghaoui et al., 2021, Equation that well possedessss condition in Corollary 5(i) is less conservative than
6.3]. It is easy (1A)) < and its convex relaxation ||A|| so < 1.
Monotone operator deep equilibrium network (MON). [Winston and Kolter, 2020] proposes to use monotone operator theory guarantee well-poss of the fixed-point equation as well as its convergence to the solutions. The input-output behavior of the network is described by (11). For training, the optimization problem (16) is used where the constraint [x))(x) (A) S ry is replaced by In - (A + A 2 (1 - 4n In order to ensure that this constraint always satisfied in the training procedure, the weight matrix A is parametrized as A = 7In W T W-
- Z + 2 for arbitrary W.Z Z _ax= [Winston and Kolter, 2020, Appendix DJ.² In the context of contraction theory,
I, - (A + A
IT + (2(A) S 7.
which is shown in Appendix A. Thus, the parametrization A= WTW - 2 + 2T can be considered as the norm version of the parametrization described by equation (17). In other words, the monotone operator network formulation is a Euclidean transcription of the framework we propose this paper.
All models were trained using Google Colab with Tesla P100-PCIE-16GB GPU.
"The implicit deep learning implementation is available at http://gghhha..cmm///pprrrraaaaa
'hhe MON implementation is available at https: : /// //////gtttt/bb/ http:///ww..uuussaa////oooooo...
8

---

6.2 MNIST experiments
MNIST handwritten digits
spachs MNIST
11100
01300
[ 0.35
11573
0.570
MON
0.000
0.000
0.175
0.130
0.545
4| S 2455
0.123
0.000
MDN
0.100
01089
Figure 1: Performance comparison between the NEMON model with Po (A) 0.95, the implicit deep learning model with >/ & 0.95, and MON with L, 1 (A + ) 2 0.052, on the MNIST dataset. The curves are generated by mean accuracy and mean loss over 5 different runs while light envelopes around the curves correspond the standard deviation over the runs. Average best accuracy for the NEMON model is 0.9772, while it is 0.9721 for implicit deep learning model and 0.9762 for the MON model.
In the digit classification dataset MNIST, input data are 28 x 28 pixel images of handwritten digits between 0-9. There are 60000 training images and 10000 test images. For training, images are reshaped into 784 dimensional column vectors and entries are scaled into the range [0, 1]. As loss function, we use the cross-entropy. All models are of order n 100, used the ReLU activation (x))+ and are trained with batch size of 300 over 10 epochs with a learning
function (x)) rate of 1.5 x 10-2 Curves for accuracy and loss versus epochs for the three models are shown in Figure 1. Regarding training times, using the average iteration, NEMON took, on average, 12 forward iterations, backward iterations, and 9.8 seconds to train per epoch. Using the Peaceman-Rachfort iteration, MON took, on average, 17 forward iterations, 16 backward iterations, and 9.5 seconds to train per epoch. Using the Picard iteration, the implicit deep learning model took, on average, 10 forward iterations, backward iterations, and 5.8 seconds to train per epoch. We observe that the NEMON model performs better than the implicit deep learning model and has a comparable performance MON.
Test error lipschitz constant MNIS handwritten digits
Accuracy vs perturbation MNIST T handovitten digits
= 10-2
10-96
80-5
Lillo 5 0.55
[[4] Al S EL55
0-
0.
0.
10F
10a
10t
1.0
0.1
63 Fe, awp.hhdeeeeeeeo pertrtotion
0.2
0.44
lipeditzz contont
Figure 2: On the left a plot test error versus Lipschitz constant for the implicit deep learning model with || < 0.95 and for NEMON with pas (A) & 0.95 and parametrized by the regularization hyperparameter A. We define the test error as 1 minus the accuracy. On the right is a plot of accuracy versus fa perturbation of deterministic adversarial image inversion attack where additionally include the MON model with I. (A + A 2 0.05
We also study the robustness of the NEMON model compared to the implicit deep learning model and the MON model on the MNIST dataset. We train various models regularized by the input-output Lipschitz constant as in (18). Additionally, to verify robustness of the different models, we consider several adversarial attacks and plot the accuracy versus perturbation of such an attack. In Figure we consider continuous image inversion attack [Hosseini et al., 2017], where each pixel is perturbed

---

in the direction of pixel value inversion with amplitude given by the foo perturbation. For more details on this and other types of adversarial perturbations, we refer to Appendix D. We observe that for À = -10-5 the regularized NEMON model achieves a two order of magnitude decrease in its input-output Lipschitz constant compared to the un-regularized NEMON models. In addition, we see that the implicit deep learning model and the MON model are more sensitive to the continuous image inversion attack than NEMON. Moreover, as the regularization parameter À increases, the NEMON model becomes increasingly robust to this attack.
6.3 C-FAR-10 experiments
In the image classification dataset CIFAR-10, 10, input data are 32 x 32 color images in 10 classes. There are 50000 training images and 10000 test images. We compare our proposed NEMON model with a convolutional structure
single convolutional layer MON model. Each model used 81 channels. We train both models with a batch size of 256 and a learning rate of 10-3 (0-3 for 40 epochs. For training, using the average iteration, NEMON took, on average, 10 forward iterations, 10 backward iterations, and 75.0 seconds per epoch to train. Using the Seaceman-Rachfore iteration, MON took, on average, 5 forward iterations, 5 backward iterations, and 101.8 seconds per epoch to train.
We focus primarily on the robustness of NEMON and MON with respect to -nrm bounded perturbations CIFAR-10. To this end, we additionally trained two NEMON models with regu- larization parameters À E {10- 10 100---0.--.. In Figure 3, on the left is a plot of the certified robustness of each of the models via their -Lipschhtt constants. For MON, we got the <>p-ssich bound using the method in [Pabbaraju et al., 2021] for the Ez-Lipschitz bound and using the upper bound ||u]|2 x Vrs²||u||oo- On the right is a plot of the accuracy of different models with respect to the projected gradient descent attack. We observe that the un-regularized and regularized NEMON models are more robust to &o norm bounded perturbations than is MON.
Certified robustness vs perturbation on CIFAR-10 images
Accuracy perturbation on CIFAR-10 images
Corefled robust rest sccurey
0.7
0.6
A- 10"1 Up-116611
0. Lip-6044.9
10"5 Lip-249.2
1 30-
0
32nd
Up:339882
0,5
0.4
0.5
0.3
0.4
0.2
0.1
0.0
0.1
0.000
0.002
0,004
0 0000
0.008
0.010
0.000
0.025
0.050
0.125 0.150 0.175 0.200 Cu amplitudde perturaation
0.075
0.100
4. amplitude of perturbation
Figure 3: On the left is a plot of certified rohustness via the Lipschitz constants of MON with the constraint In (A + A ) / In and NEMON with the constraint Mo (A) < 0. On the right is plot of accuracy versus loo perturbation of the projected gradient descent attack.
7 Conclusion
Using En-EEulideen contraction theory, we propose framework to study stability of fixed-poins equations. We apply this framework to analyze well-posedness and convergence of implicit neural networks and design an efficient training algorithm incorporate robustness guarantees. For future research, we envision that our framework is applicable to study stability and robustness of implicit learning models with additional structure such as graph neural networks.
8 Acknowledgments
The authors thank Ian Manchester for stimulating discussions about contraction theory and the anonymous reviewers for their insightful feedback. This work was supported in part by DTRA under grant 1-1DTRRA-11-1-000 AFOSR under grant 249550-22-1-0059, and NSF Graduate Research Fellowship under grant 1939319.
10

---

References
A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter. Differentiable convex optimization layers. In Advances Neural Information Processing Systems, 2019. URL https: //arxiv. org/ abs/ 19100 12430.
B. Amos, Jimenez, Sacks, B. Boots, and J. Z. Kolter. Differentiable MPC for end-to-end planning and control. In Advances in Neural Information Processing Systems, 2018. URL https: htopss//axxee //arxv//a.vv///aaa httgg/bs/18100 13400.
S. Bai, J. Z. Kolter, and V. Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, 2019. URL https::///// /tttpps://rxiv.../// http///aawvvv..raaaaaaeeaee
owgooog///aa. (trgg/bss/9900 01377.
H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2 edition, 2017. ISBN 978-3-319-48310-8.
N. Carlini and D. Wagner. Adversarial examples are not easily detected: Bypassing ten detec- tion methods. In ACM Workshop on Artificial Intelligence and Security, pages 3-14, 2017. doi:10. 10.11144 28572..3553
R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud. Neural ordinary differential equations. In Advances Neural Information Processing Systems, 2018. URL https://aaaae /twxxv.xivv///////////x/////aav/ org/ //bs// 1806. 07366.
L. Combettes and J.-C. Pesquet. Lipschitz certificates for layered network structures driven by averaged activation operators. SIAM Journal on Mathematics of Data Science, 2(2):529-557, 2020. doi: 10: N0.1137/9MM2227881
P. L. Combettes and J.-C. Pesquet. Fixed point strategies in data science. IEEE Transactions Signal Processing, 2021. 100.1110//SPPP22213306666
A. Davydov, S. Jafarpour, and F, Bullo. Non-Euclidean contraction theory for robust nonlinear stability. 2021. URL
www.orggg/bg....... 12263.
C. A. Desoer and H. Haneda. The measure of matrix tool to analyze computer al- gorithms for circuit analysis. 1oi: 1TT.T1997..18885.5
IEEE Transactions on Circuit Theory, 1965):480-486, 1972.
L. El Ghaoui, F. Gu, B. Travacca, A. Askari, and A. Tsai. Implicit deep learning. SIAM Journal on Mathematics of Data Science, 3(3):930- 958, 2021.
Y. Fang and T. G. Kincaid. Stability analysis of dynamical neural networks. IEEE Transactions on Neural Networks, 7(4):996-1006, 1996. doi: 10. 109977..08844
M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. J. Pappas. Efficient and accurate estimation of Lipschitz constants for deep neural networks. Advances Neural Information Processing Systems, 2019, URL
http://aaxxv..oo./.. htrgg/bss/99/... 04893
M. Fazlyab, M. Morari, and G. J. Pappas. Safety verification and robustness analysis of neural net- works via quadratic constraints and semidefinite programming. IEEE Transactions Automatic Control, 2020. 1o.: 109/TAC..000.30441199
I. Goodfellow, Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015. URL https://arxit: org/ abs/ org/abs/// 11111111.66561 6572.
W. He and J. Cao. Exponential synchronization of chaotic neural networks: a matrix measure approach. Nonlinear Dynamics, 55:55 65, 2009. doi: 1.1100...0s111111111 107 00001-00009-4---4
H. Hosseini, B. Xiao, M. Jaiswal, and R. Poovendran. On the limitation of convolutional neural networks in recognizing negative images. In IEEE International Conference on Machine Learning and Applications, pages 352-358, 2017. 100110..100//CML..11.0.000

---

A. Kag, Z. Zhang, and V. Saligrama. RNNs incrementally evolving on an equilibrium manifold: A panacea for vanishing and exploding gradients? In International Conference on Learning Representations, 2020. URI. httpts:/oppeereviiaiiee
net/forrumid--Hyypppee
K. Kawaguchi. On the theory of implicit deep learning: Global convergence with implicit layers. In International Conference on Learning Representations, 2021. URL https::/ net/ Berumfid-p-NZIurap
V. Krishnan, A. A. A. Makdah, and F. Pasqualetti. Lipschitz bounds and provably robust training by Laplacian smoothing. In Advances in Neural Information Processing Systems, 2020. URL
https://arxiv. wwtp://ggg/ab/o/o/eeeaeee abtp///.....0...///// 03712.
C. Lim. On fixed point stability for set-valued contractive mappings with applications to generalized differential equations. Journal of Mathematical Analysis and Applications, 110(2):436 1985. doi:10 0o::10.1016/0222 (00006/002222778888888888
W. Lohmiller and J.-J. E. Slotine. On contraction analysis for non-linear systems. Automatica, 34(6): 683-696, 1998. doi: 10. 1016/50000 10000016500000000000000000000000
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Machine Learning, 2018. URL
https://arxiv hww.aaiiiv.org/bra.eeaaeeeaeeaee org/abs/////eaooooooggoo.eee 1706. 06083..
C. Pabbaraju, E. Winston, and J. Z. Kolter. Estimating Lipschitz constants of monotone deep equilibrium models. In International Conference on Learning Representations, 2021. URL https: //opnreviee weteanrviee.net/forruuee wwwt/eeeuttniiiee 2it.frrrrmm7.d...o00000ty......
N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In IEEE Symposium on Security and Privacy, pages 582-597, 2016. doi: 109///.......
Pauli, A. Koch, Berberich, P. Kohler, and F. Allgower. Training robust neural networks using Lipschitz bounds. IEEE Control Systems Letters, 2021.
A. Paviov, A. Pogromsky, N. Van de Wouw, and H. Nijmeijer. Convergent dynamics, trib- ute to Boris Pavlovich Demidovich. Systems & Control Letters, 52(3-4):257-26) 2004. doi: 10::10.100 10i:10.10166/.sssee... s001//
H. Qiao, J. Peng, and Z.-B. Xu. Nonlinear measures: new approach to exponential stability analysis for Hopfield-type neural networks. IEEE Transactions on Neural Networks, 12(2):360-370, 2001. doi: 109/799997.2.000.
M. Revay, R. Wang, and R. Manchester. Lipschitz bounded equilibrium networks. 2020. URL nttps://arxiv...
abt//aas......//////////aa/a.aea 01732.
M. Revay, R. Wang, and I. R. Manchester. A convex parameterization of robust recurrent neural net- works. IEEE Control Systems Letters, 5(4): 2021. doi: 16000....1000.CSS2220000032222
E. K. Ryu and S. Boyd. Primer on monotone operator methods. Applied Computational Mathematics, 15(1):3-43, 2016.
C. Szegedy, W. Zaremba, I. Sutskever, Bruna, Erhan, I. Goodfellow, and Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL https: : /tte:://arxxx /arxxiivvv.. wwwpxivvoorr//eo wwwp//og/////...e..oee// 61999999....99
E. Winston and Z. Kolter. Monotone operator equilibrium networks. In Advances in Neural Information Processing Systems, 2020. URL https://arxiv org/ httg//bb/20066. 08591.
E. Wong and J. Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5286-5295, 2018. URL
mlr, press/v80/wons woog//0//w18.....m html.
12


Reviews:
[{"review_id": "emtFZks-ovU", "reviewer": "Reviewer_r3Ki", "summary": "The paper proposes a new well-posedness condition for DEQs that is less conservative than the l_\\infty norm proposed in [El Ghaoui et al., 2019]. A Lipschitz regularization is also developed to improve the robustness to some classes of adversarial perturbations. Several experiments show the effectiveness of the proposed method.\n___________________________________________________\nThe author responses address most of my concerns. So I raised the score and tended to acceptance. ", "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": "Studying the well-posedness and convergence of the fixed-point equations of DEQs is very important. Based on contraction theory for the l_\\infty norm, the paper develops a new well-posedness condition for DEQs. The paper is well-written and organized. However, the advantage over MON is not clear. Note that MON does not consider the robustness.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have two main concerns. \nFirst, how to choose \\gamma in (16) for a DEQ training problem? Also, it is better to study the effect of different settings of \\gamma. Why set \\gamma = 0.5 in subsection 6.1 and \\gamma=0.95 in subsection 6.2?\n\nSecond, it is better to plot the running time vs. test accuracy, e.g., in Figure 2. Does the proposed method outperform MON and l_\\infty norm in training efficiency?", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "aJmzUQO9CKb", "reviewer": "Reviewer_Q7s2", "summary": "This paper presents a thorough analysis of constructing provably convergent equilibrium networks in the non-Euclidean space. Instead of directly requiring Lipschitzness as in prior works (which mostly dealt with $L_2$), the authors show that we can further relax the constraint by considering one-sided Lipschitzness and exploit the contraction theory via semi inner products. The experimental results of the paper seem to demonstrate the validity of the theoretical results and the paper provides empirical evidence on the potential application of the theories in improving implicit networks' adversarial robustness.", "questions": "", "limitations": "", "rating": 6, "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": "Overall, I enjoy reading this paper, which provides a valuable discussion on how to extend (and exploit) implicit networks' stability analysis to non-Euclidean spaces. I believe this paper will be of interest to the relevant audience in the NeurIPS community and extends the current efforts (as pointed by the authors in the paper) to build provably stable implicit deep networks and scale them to more general settings. At the same time, while the final application of the theories (e.g., Thm 1 and 2) are for the equilibrium networks, the techniques used in this paper and part of the conclusions have been built on top of prior works that studies; e.g., [1,2,3]. Moreover, I find some critical empirical analysis missing. In summary, I find the following strengths and weaknesses:\n\nStrengths:\n- Clear explanation of the theory. I checked most of the proof (mainly appendix A & C) and they are well-written and correct. The theoretical motivation for using osL-ness and damped fixed point iteration is well explained and quite smart.\n- The paper extends prior works to non-Euclidean space and presents a new framework/condition through which we can build well-posed implicit networks (i.e., practical significance).\n\nWeaknesses:\n- Limited theoretical significance (to clarify, the application of such kind of contraction analysis to implicit neural networks is novel, and probably significant; but not the osL-based contraction theory itself).\n- Missing experimental details and comparisons (e.g., with Revay et al., which dealt with $L_2$; and on a wider range of experiments). The comparison with El Ghaoui is good but it's still only a weak baseline.\n- Still relatively weak empirical evidence on the benefit of applying the analysis in practice (i.e., having this larger parameter search space). Specifically, the advantage of using the proposed $L_\\infty$-based and relaxed-constraint formulation over MON or even the LBEN model in Revay et al. is not clear to me when in the presence of strong adversarial attacks, such as PGDM and FGSM (see Appendix D). \n\n-------------------------------------------------------------\n\nMore questions/comments:\n\n1. One particular theoretical benefit of the approach is the use of osL analysis and measure $\\mu_{\\infty [\\eta]^{-1}}(A)$ rather than the simplest matrix norm. This begs the question of how the pick of $\\eta$ affects the empirical performance (theoretically it's only a matter of existence issue, but I'm more interested in practical implications). The authors picked $\\mathbf{1} \\in \\mathbb{R}^n$ here. Could the authors expand more on this? Moreover, in the submitted code \"trainMNISTmodel.py\", I did not find any mechanism for actually ensuring $\\mu_{\\infty, [\\eta]^{-1}}(A) < \\gamma$ (you did compute the LHS, which is\n```python\nX = torch.abs(model.A) - torch.diag(torch.diag(torch.abs(model.A))) + torch.diag(torch.diag(model.A))\nmatmeas = torch.max(X.sum(1))\n```\nbut didn't quite use it; but it's likely that I missed something). How is the diagonally weighted measure preserved during training?\n\n2. One question that I found to be absent in the empirical discussion is the convergence rate. Although damped fixed point iteration helps us relax the Lipschitz condition a bit, it is also known to possibly bring the extra risk of slower fixed-point convergence than the non-average iterations. In the case where $\\alpha$ is small, I wonder how efficient this (albeit provable) convergence is?\n\n3. You may want to cite [4] as well, which is clearly related (but in Euclidean space). \n\n4. It seems to me that the results of Sec. 4 should be able to generalize even further to the case where $Ax$ is replaced by a non-linear transformation $\\Lambda(x)$, where $\\Lambda$ is everywhere differentiable. In that case, you only need to replace the $A$-based results in the conclusion with $D\\Lambda$. Is there any reason for not doing so in theory and in practice? E.g., the matrix measure of $D\\Lambda$ would be hard to compute?\n\n\n[1] https://arxiv.org/pdf/2103.12263.pdf\n[2] https://hal.archives-ouvertes.fr/hal-01313105/document\n[3] https://link.springer.com/content/pdf/10.1007/978-3-540-72234-2.pdf\n[4] https://openreview.net/pdf?id=VcB4QkSfyO\n\n-----------\n-----------\n\n#### Post-rebuttal\n\nI appreciate the authors' response. Overall, while I agree this paper has presented a solid work, I personally would love to see larger-scale, more practical, and more performant results of these provable implicit models and what we could achieve with them.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work and I think the limitations are well-addressed (mainly in the form of assumptions and sufficiency analysis in theorems).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6.5"}, "extra_text": {}}, {"review_id": "Wk6ANZonjDb", "reviewer": "Reviewer_xt3G", "summary": "This paper gives a novel characterization of well-posedness for implicit networks based on the one-sided Lipschitz constant (osL). This follows in a line of work of other such characterizations [1,2,3,4], but differs in that well-posedness is guaranteed by a constraint on the osL of the weights matrix, which can be wrt arbitrary norms. The authors focus on the $\\ell_\\infty$ norm, for which they show accelerated convergence of dampened fixed-point iterations.  They also drive a bound for the Lipschitz constant of the network wrt the $\\ell_\\infty$ norm on the input space, which is more natural for achieving robustness than the $\\ell_2$-based Lipschitz bounds of [3] and [4]. They train networks while enforcing well-posedness and using the Lipschitz bound as a regularizer, and demonstrate the empirical robustness of the models.", "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": "Overall, I think the connection between non-Euclidian contraction theory and implicit networks is quite interesting and will be beneficial for people working in this area. However, there are a number of comparisons to existing works that are lacking, both in the theory and experiments (see below). Additionally, some of the benefits described in the theory are not well demonstrated by the experiments.\n\nThis paper addresses an important topic, since implicit networks are growing in practicality and popularity, so understanding and improving their robustness properties is important. If the authors could address some of my concerns, I'd be inclined to increase my score.\n\n### Pros:\n\n*  The application of non-Euclidean contraction theory to implicit networks appears to be novel and provides a nice way to guarantee contraction wrt the $\\ell_\\infty$ norm and well-posedness. \n* The accelerated convergence in the $\\ell_\\infty$ norm seems important, since improving convergence times has been a practical consideration for implicit networks.\n* It's great to see that the Lipschitz bound can be computed for arbitrary norms via Lim's lemma, which is more general and elegant than the $\\ell_2$ bounds in [4].\n* Bounding the Lipschitz constant wrt the $\\ell_\\infty$ norm is valuable since it leads to robustness to $\\ell_\\infty$ attacks, which are arguably more natural than $\\ell_2$ attacks.\n\n###  Cons:\n* I think the paper would be much improved by better comparisons to exiting work. In particular, [4] also derives Lipschitz bounds for MON but is not cited.  It looks like Theorem 3 generalizes the bound in [4], while being a more elegant way of deriving it. \n* It would be good to understand how the set of networks characterized here compares to that of [2] and [3]. E.g. along the lines of Figure 2 in [3], which does a nice job of comparing the constraint in [2] and [3], showing how [3] is less restrictive. Do the osL-bounded networks correspond exactly to the set of MON networks in [2] if using $\\ell_2$ instead of $\\ell_\\infty$ norm? I believe this is stated in Appendix D but could be elaborated on in the main text.\n* I don't know how much of the theory is novel outside of the implicit networks literature. Could the authors comment on how Theorem 3 compares to the results in [5]?\n* It is unclear how the osL constraint is enforced during training. In Lemma 9, appendix B, the authors provide a parameterization of the well-posed network like those in [2] and [3], which allows for unconstrained training. But that doesn't seem to be used during training here?\n* Experimental comparison to LBEN [3] is missing, and it is unclear what value of monotonicity parameter is used for MON [2]. As is shown in [4], this parameter controls the robustness (at least to $\\ell_2$ attacks).\n* It would be nice to see certified robustness, since the authors provide a concrete bound on the $\\ell_\\infty$ norm.\n* It would be nice to see results on CIFAR-10, since robustness on MNIST is not as meaningful. \n* It's unclear what the take-away from the first experimental section is meant to be.\n* It would seem important to show if the accelerated convergence can be realized experimentally, and compare convergence to that of LBEN/MON. \n\n### References:\n* [1] [El Ghaoui et al. 2019. *Implicit deep learning*](https://arxiv.org/pdf/1908.06315.pdf)\n* [2] [Winston and Kolter 2020. *Monotone operator equilibrium networks*](https://arxiv.org/pdf/2006.08591.pdf)\n* [3] [Revay et al. 2020. *Lipschitz Bounded Equilibrium Networks*](https://arxiv.org/pdf/2010.01732.pdf)\n* [4] [Pabbaraju et al. 2020. *Estimating Lipschitz constants of monotone deep equilibrium models*](https://openreview.net/forum?id=VcB4QkSfyO)\n* [5] [Adly et al. 2014 *On one-sided Lipschitz stability of set-valued contractions*](https://06658af9-a-62cb3a1a-s-sites.googlegroups.com/site/adontchev/lim.pdf)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "* The authors state that the work is fundamental research so will not lead to negative societal impact. \n* In terms of limitations of the work, it would be great if the authors could report runtime and number of function evals for their models, which are typically quite high for such models.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0rCMIiig4Sp", "reviewer": "Reviewer_ivrZ", "summary": "This paper studies the implicit nn with non-Euclidean norms. In particular, the authors give the sufficient condition for the well-posedness of the fixed point problem under any norms, and provide the corresponding contraction factor. Consequently, the author derives the Lipschiz constant of their implicit model induced by the infinity norm and use the model for robustness tasks.", "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": "# Strength\nThis paper studies an important and interesting area. Implicit modelling starts to gain more attention as it's a good method to save memory while achieving comparable performance. The particular problem tackled by this paper is also important as previous results mostly focus on l2 norms and it is important to extend the existing results to other norms like l_infinity norm. The derivation is non-trivial. Although I didn't check the proof detail, the claims do seem sound and the paper is written clearly. \n\n# Weakness\n- In terms of writing, this paper has several big chunks of theorems but lack sufficient discussion of their significance. For example, the osLip is a weaker notion than the Lip constant, I think it's helpful that the author can provide some example where these two notions differ by a lot. \n- A comparison of the matrix measure and largest eigenvalue may also be helpful. For example, in corollary 5, the sufficient condition for the uniqueness of fixed point is that u(A)<1. I think this coincide with the largest eigenvalue of A if the underlying norm is l_2 (correct me if I'm wrong). It is valuable to include such comparisons in the discussion. I do realize that the authors have discussed about the PF eigenvalue used in El Ghaoui et al., I would also like to see a comparison to the condition used in Winston and Kolter.\n- The training problem is framed as a constrained optimization problem. To me this is not a desired property. I would guess that at every gradient step we have to project the updated parameters on the constrained set and it can be very time/resource consuming. It would be great if there's a way to re-parameterize the weights as done in Winston and Kolter.\n- More training details can be added. For example, the dimensions of A, B, C, D are missing in section 6. I would also want to see two more results: how many iterations does it take for forward and backward damped iterations, and what's the wall-clock time to train these models.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper originally got 2 "Marginally above the acceptance threshold"s and 2 "Marginally below the acceptance threshold", all with relatively high confidences. The major challenges include a number of comparisons to existing works being lacking both in the theory and experiments, relatively weak experiments, missing some important details, etc. The authors did heavy rebuttals, including presenting extra experiments, and they seemed to take effect. Reviewer xt3G raised his/her score from 5 to 7. Reviewer ivrZ also raised to 7. Considering that the extra experiments and clarifications can be easily incorporated in the revision, the AC deemed that the paper is acceptable, thus recommended acceptance. 
Decision: Accept (Poster)