Robust Implicit Networks via Non-Euclidean Contractions
Year: 2022

Abstract:
Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicitdepth 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 `∞. 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 `∞ 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.

text: Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicitdepth 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 `∞. 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 `∞ 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.

heading: 1 Introduction
text: Implicit neural networks are infinite-depth learning models with layers defined implicitly through a 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]. Implicit networks can be considered as generalizations of feedforward neural networks with input-injected weight tying, i.e., training parameters are transferable between layers. Indeed, in implicit networks, function evaluation is executed by solving a fixed-point 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 to traditional neural networks. At the same time, implicit networks can suffer from instability in their training due to the nonlinear nature of their fixed-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 (NeurIPS 2021).
It is known that implicit neural networks require careful tuning and initialization to avoid 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 fixedpoint equations of implicit networks using frameworks such as monotone operator theory [Winston and Kolter, 2020], contraction theory [El Ghaoui et al., 2021], 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 a 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 `2-norm [Fazlyab et al., 2019, Combettes and Pesquet, 2020]. However, it turns out that in some applications, the inputoutput 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 widely-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 `2-Lipschitz constant can be very sensitive to widespread entrywisesmall perturbations of the input signal. On the other hand, the input-output `∞-Lipschitz 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 `∞-Lipschitz constant of the network provides more scalable bounds than its `2 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 a composition rule, which can be either a fixed-point iteration or a solution to a differential equation. Well-known frameworks for deep learning using implicit infinite-depth layers include deep equilibrium networks [Bai et al., 2019], implicit deep learning [El Ghaoui et al., 2021], and Neural ODEs [Chen et al., 2018]. 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 to 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 a recent interest in studying well-posedness and numerical stability of implicit-depth learning models. [El Ghaoui et al., 2021] proposes a sufficient spectral condition for well-posedness and for convergence 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, a suitable parametrization of the weight matrix is proposed which guarantees the stable convergence of suitable fixed-point iterations. A recent influential survey on 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]. A 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 a recent interest in designing classifiers that are provably robust with respect to adversarial perturbations [Madry et al., 2018, Wong and Kolter, 2018]. The input-output Lipschitz constant of a neural
network is a rigorous metric for its worst-case sensitivity with respect to input perturbations. Several recent works have focused on estimating the Lipschitz constant and enforcing its boundedness. For example, [Fazlyab et al., 2019, 2020] propose a 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], a 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., 2021, 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-Euclidean contraction theory with respect to the `∞-norm, we propose our novel framework, Non-Euclidean Monotone Operator Network (NEMON), to 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 a general fixed-point theorem with weaker requirements than classical results on Picard and Krasnosel’skii–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 `∞-norm, we show that this average iteration can be accelerated by choosing a larger step size. Additionally, we study perturbed fixed-point equations and establish a 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 our new fixed-point theorem to (i) establish `∞-norm conditions for their well-posedness, (ii) design accelerated numerical algorithms for computing their solutions, and (iii) provide upper bounds on their input-output `∞-Lipschitz constants. Third, we 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 on the MNIST and the CIFAR-10 datasets compared to the state-of-the-art models in [El Ghaoui et al., 2021, Winston and Kolter, 2020]. Additionally, by adding the input-output Lipschitz constant as regularizer in the training problem, we observe improved robustness to some classes of adversarial perturbations. We include all relevant proofs in Appendix C.

heading: 2 Review material
text: Matrix measures Let ‖ · ‖ be a norm on Rn and its induced norm on Rn×n. The matrix measure of A ∈ Rn×n with respect to ‖ · ‖ is defined by µ(A) := limh→0+ ‖In+hA‖−1h , that is, the one-sided directional derivative of the induced norm in direction of A, evaluated at In. Remarkably, the matrix measure is a tighter upper bound on the spectral abscissa of A than ‖A‖ and the set of matrices A ∈ Rn×n satisfying µ(A) ≤ 1 is an unbounded subset of Rn×n strictly containing the compact ball ‖A‖ ≤ 1. We refer to [Desoer and Haneda, 1972] for a list of properties enjoyed by matrix measures. We will be specifically interested in diagonally weighted `∞ norms defined by
‖x‖∞,[η]−1 = max i
1 ηi |xi|, (1)
where, given a positive vector η ∈ Rn>0, we use [η] to denote the diagonal matrix with diagonal entries η. The corresponding matrix norm and measure are
‖A‖∞,[η]−1 = max i∈{1,...,n} n∑ j=1 ηj ηi |aij |, µ∞,[η]−1(A) = max i∈{1,...,n} ( aii + n∑ j=1,j 6=i |aij | ηj ηi ) . (2)
Lipschitz maps Given a norm ‖ · ‖ with induced matrix measure µ(·), a differentiable map F : Rn → Rn is Lipschitz continuous with constant Lip(F) ∈ R≥0 if ‖DF(x)‖ ≤ Lip(F) for all x ∈ Rn. (3) For example, for an affine F(x) = Ax+ b, the (smallest) Lipschitz constant is Lip(F) = ‖A‖.
One-sided Lipschitz maps Given a norm ‖ · ‖, a differentiable map F : Rn → Rn is one-sided Lipschitz continuous with constant osL(F) ∈ R if
µ(DF(x)) ≤ osL(F) for all x ∈ Rn. (4) For example, for an affine F(x) = Ax+ 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) a Lipschitz continuous map is always one-sided Lipschitz continuous, and (iii) the one-sided Lipschitz constant may be negative. For a more in-depth review we refer to Appendix A. The notion of onesided Lipschitz continuity unifies several important concepts in dynamical systems and optimization theory. In operator theory, the map F is called a monotone operator if it is one-sided Lipschitz continuous with respect to the `2-norm with the constant − osL(−F) > 0 [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(F) < 0 [Desoer and Haneda, 1972, Lohmiller and Slotine, 1998, Pavlov et al., 2004]. In what follows, we let osL∞,[η]−1(F) ∈ R denote the one-sided Lipschitz constants with respect to the weighted `∞-norm.

heading: 3 Fixed-point equations and one-sided Lipschitz constants
text: In this section, we show that the notion of one-sided Lipschitz constant can be used to study solvability of fixed-point equation:
x = F(x), (5)
where F : Rn → Rn is a differentiable map. Let ‖ · ‖ be a norm on Rn, then in view of the Banach 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 α ∈ (0, 1] we define the average map Fα : Rn → Rn by Fα := (1− α)I + αF, where I is the identity map. Using this notion, an equivalent reformulation of the fixed-point equation (5) is:
x = (1− α)x+ αF(x) = Fα(x). (6) For α = 1, we have Fα(x) = F(x) and equation (6) coincides with equation (5). For every α ∈ (0, 1), the map Fα is different from F 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 a unique solution x∗ and the sequence {yk}∞k=1 defined by
yk+1 = (1− α)yk + αF(yk), for all k ∈ Z≥0 (7) converges geometrically to x∗ with rate Lip(Fα). As a result of the parametrization (6), the condition Lip(F) < 1 for existence and uniqueness of the fixed-point can be relaxed to sufficient conditions
Lip(Fα) < 1, (8)
parametrized by α ∈ (0, 1]. Additionally, if condition (8) is satisfied, then algorithm (7) computes the fixed point x∗. It can be shown that the condition (8) becomes less conservative as α decreases. The next theorem shows that in the limit as α→ 0+, condition (8) approaches the condition osL(F) < 1. Theorem 1 (Fixed points via one-sided Lipschitz conditions). Let F : Rn → Rn be differentiable and Lipschitz with constant ` > 0 with respect to a norm ‖·‖. Define the average map Fα = (1−α)I+αF and, for c > 0, the function γ`,c : ]0, c(c+`+1)(`+1) [→ R by:
γ`,c(α) := ( 1 + αc− α 2(`+ 1)2 1− α(`+ 1) )−1 .
Then the following statements are equivalent:
(i) osL(F) < 1− c, (ii) Lip(Fα) = γ`,c(α), for 0 < α < c(c+`+1)(`+1) .
Moreover, if the equivalent conditions (i) or (ii) hold, then, for condition number κ = 1+Lip(F)1−osL(F) ,
(iii) F has a unique fixed point x∗;
(iv) for 0 < α < 1κ(κ+1) , Fα is a contraction mapping with contraction factor γ`,c(α) < 1;
(v) the minimum contraction factor γ∗`,c = 1− 14κ2 + 18κ3 +O ( 1 κ4 ) and the minimizing averaging
parameter α∗ of Fα is
α∗ = κ
1− osL(F)
( 1− 1√
1 + 1/κ
) =
1 1− osL(F) ( 1 2κ2 − 3 8κ3 +O ( 1 κ4 )) .
The average iteration (6) is often referred to as the Krasnosel’skii–Mann iteration or the damped iteration [Bauschke and Combettes, 2017]. Compared to [Bauschke and Combettes, 2017, Theorem 5.15], Theorem 1(iv) studies convergence of the Krasnosel’skii–Mann iteration for arbitrary norms, proposes a weaker convergence condition of the form osL(F) < 1 (hence, F need not be nonexpansive). However, it ensures convergence for only sufficiently small α > 0 and assumes that F is differentiable (as will be shown, however, the latter assumption can be relaxed).

heading: 3.1 Accelerated convergence for weighted `∞ norms
text: For diagonally weighted `∞ norms, one can strengthen Theorem 1(iv) to prove the convergence of the average iteration (6) on a larger domain of the parameter α. Theorem 2 (Accelerated fixed point algorithm for `∞ norms). Let F : Rn → Rn be differentiable and Lipschitz with respect to the weighted non-Euclidean norm ‖ · ‖∞,[η]−1 . Define the average map Fα = (1− α)I + αF and pick diagL(F) ∈ [−Lip(F), osL(F)] to satisfy
diagL(F) ≤ min i∈{1,...,n} inf x∈Rn DFii(x). (9)
If osL(F) < 1, then F has a unique fixed-point x∗ and
(i) for 0 < α ≤ 1 1− diagL(F) , Fα is a contraction mapping with the contraction factor
1− α(1− osL(F)) < 1; (ii) the minimum contraction factor and minimizing averaging parameter of Fα are, respectively,
Lip(Fα∗) = 1− 1− osL(F) 1− diagL(F) = 1− 1 κ∞ , for κ∞ = 1− diagL(F) 1− osL(F) ≤ 1 + Lip(F) 1− osL(F) ,
α∗ = 1
1− diagL(F) .
Note that diagL(F) is well-defined because of the Lipschitz continuity assumption. Specifically, one can show that diagL(F) is the minus the minimum over i ∈ {1, . . . , n} of the one-sided Lipschitz constants of the maps xi 7→ −F(xi, x−i) at x−i = (x1, . . . , xi−1, xi+1, . . . , xn) fixed. It is instructive to compare the minimum contraction factor in the general Theorem 1 with the minimum contraction factor for `∞ norms in Theorem 2 and how they depend upon the corresponding condition numbers κ and κ∞. We note that (i) the relevant condition number diminishes κ ≥ κ∞, and (ii) the minimum contraction factor Lip(Fα∗) = 1− 14κ2 +O(1/κ4) improves to Lip(Fα∗) = 1− 1κ∞ . This acceleration justifies the title of this section.

heading: 3.2 Perturbed fixed-point problems
text: In this subsection, we focus on solvability of the perturbed fixed-point equation:
x = F(x, u), (10)
where F : Rn × Rr → Rn is differentiable in x. We define Fu(x) = F(x, u) and Fx(u) = F(x, u). Given a norm ‖ · ‖X in Rn and ‖ · ‖U in Rr, F is Lipschitz in its first argument with constant Lipx(F) ∈ R≥0 if
‖F(x1, u)− F(x2, u)‖X ≤ Lipx(F)‖x1 − x2‖X for all x1, x2 ∈ Rn and u ∈ Rr,
and it is Lipschitz in its second argument with constant Lipu(F) ∈ R≥0 if ‖F(x, u1)− F(x, u2)‖X ≤ Lipu(F)‖u1 − u2‖U for all x ∈ Rn and u1, u2 ∈ Rr,
and it is one-sided Lipschitz in its first argument with constant osLx(F) ∈ R if µ(DxF(x, u)) ≤ osLx(F) for all x1, x2 ∈ Rn and u ∈ Rr.
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 a norm ‖ · ‖X in Rn and a norm ‖ · ‖U in Rr, consider a map F : Rn × Rr → Rn differentiable in the first argument and Lipschitz in both arguments. If F is one-sided Lipschitz with constant osLx(F) < 1, then
(i) for every u ∈ Rm, the map Fu has a unique fixed point x∗u;
(ii) for every u, v ∈ Rm, ‖x∗u − x∗v‖X ≤ Lipu(F)
1− osLx(F) ‖u− v‖U .
Finally, Theorems 1, 2, and 3 are not directly applicable to activation function that are not differentiable. In Appendix C.3, we show that for specific form of the fixed-point equation (5), where F = Φ ◦ H and Φ : Rn → Rn is a weakly increasing, non-expansive, diagonal activation function and H : Rn × Rr → Rn is a differentiable function, all of the conclusions of Theorems 1, 2, and 3 hold by requiring equation (9) to be true almost everywhere.

heading: 4 Contraction analysis of implicit neural networks
text: In this section, we use contraction theory to lay the foundation for our Non-Euclidean Monotone Operator Network (NEMON) model of implicit neural networks. Given A ∈ Rn×n, B ∈ Rn×r, C ∈ Rq×n, and D ∈ Rq×r, we consider the implicit neural network
x = Φ(Ax+Bu) := N(x, u), y = Cx+Du, (11)
where x ∈ Rn, u ∈ Rr, y ∈ Rq, and Φ : Rn → Rn is defined by Φ(x) = (φ1(x1), . . . , φn(xn)). For every i ∈ {1, . . . , n}, we assume the activation function φi : R→ R is weakly increasing, i.e., φi(xi) ≥ φi(zi) for xi ≥ zi, and non-expansive, i.e., |φi(xi)− φi(zi)| ≤ |xi − zi| for all xi and zi; if φi is differentiable, these conditions are equivalent to 0 ≤ φ′i(xi) ≤ 1 for all xi ∈ R. We are able to provide the following estimates on all 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-expansive activation functions Φ. With respect to ‖ · ‖∞,[η]−1 , η ∈ Rn>0, on Rn and ‖ · ‖U on the input space Rr, the map N : Rn × Rr → Rn is one-sided Lipschitz continuous in the first variable and Lipschitz continuous in both variables with constants:
osLx(N) = µ∞,[η]−1(A)+ , Lipx(N) = ‖A‖∞,[η]−1 , (12) Lipu(N) = ‖B‖(∞,[η]−1),U , diagL(N) = mini∈{1,...,n}(Aii)− , (13)
where (z)+ = z if z ≥ 0 and (z)+ = 0 if z < 0; and (z)− = 0 if z ≥ 0 and (z)− = z if z < 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 non-expansive activation functions Φ. Define the average map Nα := (1−α)I+αN and consider the norms ‖·‖∞,[η]−1 , η ∈ Rn>0, on Rn, ‖ · ‖U on the input space Rr and ‖ · ‖Y on the output space Rq . Then
(i) if µ∞,[η]−1(A) < 1, then (11) is well posed, i.e., there exists a unique fixed point,
(ii) the map Nα is a contraction mapping for 0 < α ≤ α∗ := ( 1 − mini∈{1,...,n}(Aii)− )−1 with minimum contraction factor Lip(Nα∗) = 1− 1−µ∞,[η]−1 (A)+ 1−mini∈{1,...,n}(Aii)− .
(iii) the Lipschitz constants from input u to fixed point x∗u and to the output y = Cx ∗ u +Du are
Lipu→x∗ := Lipu(N) 1− osLx(N) = ‖B‖(∞,[η]−1),U 1− µ∞,[η]−1(A)+ , (14)
Lipu→y := ‖B‖(∞,[η]−1),U‖C‖Y,(∞,[η]−1)
1− µ∞,[η]−1(A)+ + ‖D‖Y,U . (15)

heading: 5 Training implicit neural networks
text: Problem setup Given an input data matrix U = [u1, . . . , um] ∈ Rr×m and a corresponding output data matrix Y = [y1, . . . , ym] ∈ Rq×m, we aim to learn matrices A,B,C,D so that the neural network (11) approximates the input-output relationship. We rewrite the model for matrix inputs as Ŷ = CX +DU , where X = Φ(AX +BU). From Corollary 5(i), if each φi is weakly increasing and non-expansive, the fixed point problem is well-posed when µ∞,[η]−1(A) < 1 for some η ∈ Rn>0. We consider a training problem of the form
min A,B,C,D,X
L(Y,CX +DU) + P(A,B,C,D) X = Φ(AX +BU), µ∞,[η]−1(A) ≤ γ, (16)
where L is a loss function, P is a penalty function, and γ < 1 is a hyperparameter ensuring the fixed point problem is well-posed. For η = 1n, we can remove the constraint µ∞(A) ≤ γ in the training optimization problem (16) using the following parametrization of weight matrix A:
A = T − diag(|T |1n) + γIn. (17) In Appendix B, we show that parametrization (17) characterizes the set of matrices in Rn×n satisfying µ∞(A) ≤ γ. 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 ∈ Rrs2 is a r-channel input of size s × s and x ∈ Rns2 is an n-channel hidden layer. To define our implicit CNN, we select the weight matrix A ∈ Rns2×ns2 as the matrix form of a 2D convolutional operator. If we consider a circular convolution operator, then A 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 ‖ · ‖U and ‖ · ‖Y as ‖ · ‖∞ in the input-output Lipschitz bound (15), we get
Lipu→y = ‖B‖(∞,[η]−1),(∞)‖C‖(∞),(∞,[η]−1)
1− µ∞,[η]−1(A)+ + ‖D‖∞,∞
≤ 1 2 ‖B‖2(∞,[η]−1),(∞) + ‖C‖2(∞),(∞,[η]−1) 1− µ∞,[η]−1(A)+ + ‖D‖∞,∞,
where the inequality provides a convex upper bound for the input-output Lipschitz constant. Therefore, using the hyperparameter λ > 0, the regularized optimization problem is written as
min A,B,C,D,X
L(Y,CX +DU) + λ (1
2 ‖B‖2(∞,[η]−1),(∞) + ‖C‖2(∞),(∞,[η]−1) 1− µ∞,[η]−1(A)+
+ ‖D‖∞,∞ )
X = Φ(AX +BU), µ∞,[η]−1(A) ≤ γ. (18)
Certified adversarial robustness via Lipschitz bounds Given a nominal input u ∈ Rr, we consider any perturbed input v within an `∞-ball of radius ε around u. In this case, we have
‖yu − yv‖∞ ≤ Lipu→y ‖u− v‖∞ ≤ Lipu→y ε. (19) Then we define margin(u) = (yu)i −maxj 6=i(yu)j , where (yu)i is the logit corresponding to the (correct) label i for the input u. Then provided Lε ≤ 12margin(u), NEMON is certifiably robust to any perturbed input v within an `∞-ball of radius ε centered at u.
Backpropagation of gradients via average iteration From [El Ghaoui et al., 2021] we now show how the average iteration can be used to perform backpropagation via the implicit function theorem. For simplicity, we assume that each activation function φi is differentiable and consider mini-batches of size 1, i.e., we have X = x ∈ Rn, U = u ∈ Rr and Ŷ = ŷ ∈ Rq. Let x∗ be the unique solution of the fixed-point equation (11). Then the chain rule implies
∂L ∂A = (∇x∗L)x>, ∂L ∂B
= (∇x∗L)u>, ∂L ∂C = (∇ŷL)x>, ∂L ∂D
= (∇ŷL)u>. Since L depends explicitly on ŷ, computing ∇ŷL is straightforward. Computing ∇x∗L is more complicated since X∗ is defined only implicitly. However, it be shown that ∇x∗L = (C(I −DΦA)−1DΦ)>∇ŷL. Since µ∞,[η]−1(A) < 1, by Lemma 8 we get that µ∞,[η]−1(DΦA) < 1. This implies that the matrix G := (In − DΦA)−1DΦ ∈ Rn×n exists and is the solution to the following fixed-point equation [El Ghaoui et al., 2021, Section 6.2]
G = DΦ(AG+ In). (20) Moreover, µ∞,[η]−1(DΦA) < 1 and Theorem 2 together imply that the fixed-point equation (20) has
a unique solution G∗ and, for every 0 < α ≤ α∗ := ( 1−mini(Aii)− )−1 , the average iterations Gk+1 = (1− α)Gk + αDΦ(AGk + In), for all k ∈ Z≥0 are contracting with the minimum contraction factor 1− α∗ ( 1− µ∞,[η]−1(A)+ ) at step size α∗.

heading: 6 Theoretical and numerical comparisons
text: In this section, we provide a comprehensive comparison of our framework with the state-of-the-art implicit neural networks2.

heading: 6.1 Implicit network models
text: We start by reviewing the existing models for implicit networks in the literature.
Implicit deep learning model. [El Ghaoui et al., 2021] proposes a class of implicit neural networks with input-output behavior described by (11). It is shown that a sufficient condition for existence and uniqueness of a solution and convergence of the Picard iterations for the fixed point equation x = Φ(Ax+Bu) is λpf(|A|) < 1, where |A| denotes the entrywise absolute value of the matrix A and λpf denotes the Perron-Frobenius eigenvalue. For training, the optimization problem (16) is used where the constraint µ∞,[η]−1(A) ≤ γ is replaced by ‖A‖∞ ≤ γ [El Ghaoui et al., 2021, Equation 6.3].3 It is easy to see that our well-posedness condition in Corollary 5(i) is less conservative than λpf(|A|) < 1 and its convex relaxation ‖A‖∞ < 1.
Monotone operator deep equilibrium network (MON). [Winston and Kolter, 2020] proposes to use monotone operator theory to guarantee well-posedness 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 µ∞,[η]−1(A) ≤ γ is replaced by In − 12 (A + A>) (1 − γ)In. In order to ensure that this constraint is always satisfied in the training procedure, the weight matrixA is parametrized asA = γIn−W>W −Z+Z>, for arbitrary W,Z ∈ Rn×n [Winston and Kolter, 2020, Appendix D].4 In the context of contraction theory, In − 12 (A+A>) (1− γ)In ⇐⇒ µ2(A) ≤ γ, which is shown in Appendix A. Thus, the parametrization A = γIn −W>W − Z + Z> can be considered as the `2-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 in this paper.
2All models were trained using Google Colab with a Tesla P100-PCIE-16GB GPU. 3The implicit deep learning implementation is available at https://github.com/beeperman/idl. 4The MON implementation is available at https://github.com/locuslab/monotone_op_net.

heading: 6.2 MNIST experiments
text: In the digit classification dataset MNIST, input data are 28× 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 a loss function, we use the cross-entropy. All models are of order n = 100, used the ReLU activation function φi(x) = (x)+, and are trained with a batch size of 300 over 10 epochs with a learning rate of 1.5× 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, 13 backward iterations, and 9.8 seconds to train per epoch. Using the Peaceman-Rachford 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, 5 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 to MON.
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 2, we consider a 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 `∞ 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.

heading: 6.3 CIFAR-10 experiments
text: In the image classification dataset CIFAR-10, input data are 32×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 to a 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 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 Peaceman-Rachford 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 `∞-norm bounded perturbations on CIFAR-10. To this end, we additionally trained two NEMON models with regularization parameters λ ∈ {10−4, 10−5}. In Figure 3, on the left is a plot of the certified robustness of each of the models via their `∞-Lipschitz constants. For MON, we got the `∞-Lipschitz bound using the method in [Pabbaraju et al., 2021] for the `2-Lipschitz bound and using the upper bound ‖u‖2 ≤ √ rs2‖u‖∞. 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 `∞-norm bounded perturbations than is MON.

heading: 7 Conclusion
text: Using non-Euclidean contraction theory, we propose a framework to study stability of fixed-point equations. We apply this framework to analyze well-posedness and convergence of implicit neural networks and to design an efficient training algorithm to 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.

heading: 8 Acknowledgments
text: 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 HDTRA1-19-1-0017, AFOSR under grant FA9550-22-1-0059, and NSF Graduate Research Fellowship under grant 2139319.

Review summaries:
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.

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.

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. ___________________________________________________ The author responses address most of my concerns. So I raised the score and tended to acceptance. 

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.