Estimating Lipschitz constants of monotone deep equilibrium models
Authors: Chirag Pabbaraju
Ezra Winston
J Zico Kolter
Venue: ICLR 2021 Poster (2021)
Keywords: deep equilibrium models
Lipschitz constants

Abstract: Several methods have been proposed in recent years to provide bounds on the Lipschitz constants of deep networks, which can be used to provide robustness guarantees, generalization bounds, and characterize the smoothness of decision boundaries. However, existing bounds get substantially weaker with increasing depth of the network, which makes it unclear how to apply such bounds to recently proposed models such as the deep equilibrium (DEQ) model, which can be viewed as representing an infinitely-deep network. In this paper, we show that monotone DEQs, a recently-proposed subclass of DEQs, have Lipschitz constants that can be bounded as a simple function of the strong monotonicity parameter of the network. We derive simple-yet-tight bounds on both the input-output mapping and the weight-output mapping defined by these networks, and demonstrate that they are small relative to those for comparable standard DNNs. We show that one can use these bounds to design monotone DEQ models, even with e.g. multi-scale convolutional structure, that still have constraints on the Lipschitz constant. We also highlight how to use these bounds to develop PAC-Bayes generalization bounds that do not depend on any depth of the network, and which avoid the exponential depth-dependence of comparable DNN bounds.

Published as a conference paper at ICLR 2021
ESTIMATING LIPSCHITZ CONSTANTS OF MONOTONE DEEP EQUILIBRIUM MODELS
Chirag Pabbaraju" & Ezra Winston"
J. Zico Kolter
Carnegie Mellon University
Carnegie Mellon University
{cpabbara, ewinston] cmu, edu
Bosch Center for Artificial Intelligence zkolter@cs. cmu. edu
ABSTRACT
Several methods have been proposed in recent years to provide bounds on the Lipschitz constants of deep networks, which can be used to provide robustness guarantees, generalization bounds, and characterize the smoothness of decision boundaries. However, existing bounds get substantially weaker with increasing depth of the network, which makes it unclear how apply such bounds to re- cently proposed models such as the deep equilibrium (DEQ) model, which can be viewed as representing an infinitely-deep network. In this paper, we show that monotone DEQs, a recently- -roppooed subclass of DEQs, have Lipschitz constants that can be bounded as simple function of the strong monotonicity parameter of the network. We derive simple-yet-tigee bounds on both the input-output mapping and the weight-output mapping defined by these networks, and demonstrate that they are small relative to those for comparable standard DNNs. We show that one use these bounds to design monotone DEQ models, even with e.g. multi- scale convolutional structure, that still have constraints on the Lipschitz constant. We also highlight how to use these bounds to develop MMC-Bayes generalization bounds that do not depend on any depth of the network, and which avoid the ex- ponential depth-dependence of comparable DNN bounds.
INTRODUCTION
Measuring the sensitivity of deep neural networks (DNNs) to changes in their inputs or weights is
important in wide range of applications. A standard way of measuring the sensitivity of a function
f is the Lipschitz constant of f. the smallest constant L E R4 such that [l - f(y)ll2 S L Li[x-y]] yyl2 for all inputs and y. While exact computation of the Lipschitz constant of DNNs is NP-hard (Virmaux & Scaman 2018). bounds or estimates can be used to certify a network's robustness to adversarial input perturbations (Weng et al.) 2018). encourage robustness during training (Tsuzuku jet al. 20188).... or as a complexity measure the DNN (Bartlett et al. (017), among other applications. An analogous Lipschitz constant that bounds the sensitivity of f to changes in its weights can be al. 2018 growing number of
used to derive generalization bounds for DNNs (Neyshabur methods for computing bounds on the Lipschitz constant of DNNs have been proposed in recent works, primarily based on semidefinite programs (Fazlyab et al. 2019 Raghunathan et al., 2018) or polynomial programs (Latorre et al., [019). However, as the depth of the network increases, these bounds become either very loose or prohibitively expensive to compute. Additionally, they are typically not applicable to structured DNNs such as convolutional networks which are common in everyday
The deep equilibrium model (DEQ) Bai et al. 2019) is an implicit-depth model which directly weight-tied network. DEQs have been shown to perform as well as DNNs in domains such as computer vision (Bai et al. 2020) and sequence modelling (Bai et al., 2019), while avoiding the large memory footprint required by DNN training in order to backpropagate through a long computation chain. Given that DEQs represent infinite-depth networks, however, their Lipschitz constants clearly cannot be bounded by existing methods, which are very loose even on networks of depth 10 less.
solves for the fixed point of "infinitely-deg"
"Equal contribution.

---

Published as a conference paper at ICLR 2021
In this paper we take up the question of how to bound the Lipschitz constant of DEQs. In particular, we focus on monotone DEQs (monDEQ) (Winston & Kolter, 2020), a recenty--roposse class of DEQs which parameterizes the DEQ model in a way that guarantees existence of unique fixed- point, which can computed efficiently as the solution to a monotone operator splitting problem. We show that monDEQs, despite representing infinite-depth networks, have Lipschitz constants which can be bounded by simple function of the which therefore directly influences the bound. We also derive bound on the Lipschtiz constant w.r.t. the weights of the monDEQ, with which we derive a deterministic PAC-Bayes generalization bound for the monDEQ by adapting the technique of (Neyshabur et al. 2018). While such generalization bounds for DNNs are plagued by exponential dependence on network depth, the corresponding monDEQ bound does not involve any depth-like term.
parameter, the choice of
Empirically, demonstrate that our Lipschitz bounds on fully-connected monDEQs trained on MNIST are small relative to comparable DNNs, even for DNNs of depth only 4. We show a similar trend single- and multi contiiioovoll monDEQs compared to the bounds on traditional CNNs computed by AutoLip and SeqLip (Virmaux & Scaman 2018). the only existing methods for (even approximately) bounding CNN Lipshitz constants. Further, monDEQ generalization bounds are comparable with bounds on DNÑs of around depth 5, and avoid the exponential dependence on depth of those bounds. Finally, we also validate the significance of the small I. Lipschitz bounds for monDEQs by empirically demonstrating strong adversarial robustness on MNIST and CIFAR-10.
2 BACKGROUND AND RELATED WORK
Lipschitz constants of DNNs were proposed as early as Szegedy al.] (2014) as a potential means of controlling adversarial robustness. The bound proposed in that work was the product of the spectral norms of the layers, which in practice is extremely loose. Virmaux & Scaman (018)) derive tighter bound via convex maximization problem; however the bound is typically intractable and can only be approximated. Combettes & Pesquet (2019) bound the Lipschitz constant of DNNs by noting that the common nonlinearities employed as activation func- tions are averaged, nonexpansive operators; however, their method scales exponentially with depth of the network. (Zou al. 2019) propose linear- program- based bounds specific to convolutional networks, which in practice are several orders of magnitude larger than empirical lower bounds. Upper bounds based on semidefinite programs which relax the quadratic constraints imposed by the nonlinearities are studied by Fazlyab et al. 2019 Raghunathan et al. (2018); Jin & Lavaei (2018). The bounds can be tight in practice but expensive compute for deep networks; as such, Fazlyab] jet al. (2019) propose a sequence of SDPs which trade off computational complexity and accuracy. This allows us to compare our monDEQ bounds to their SDP bounds for networks of increasing depth (see Section (5). Latorre et al. (219)) show that the complexity of the optimization problems can be reduced by taking advantage of the typical sparsity of connections common to DNNs, but the resulting methods are still prohibitively expensive for deep networks.
Lipschitz constants of DNNs
DEQS and monotone DEQS An emerging focus of deep learning research is on implicit-depth models, typified by Neural ODES (Chen et al.] 2018) and deep equilibrium models (DEQs) (Bai ett al., 2019 2020). Unlike traditional deep networks which compute their output by sequential, layer-wise computation, implicit-depth models simulate "infinite-depth" networks by specifying, and directly solving for, some analytical conditions satisfied by their output. The DEQ model di- rectly solves for the fixed-point of an infinitely-deep. weight-tied and input-injected network. which 9(2, xI) where, 9 represents nonlinear layer computation
would consist of the iteration 21+1 which is applied repeatedly, 2 is the activation at "layer" i, and x is the network input, which is injected at each layer. Instead of iteratively applying the function g (which indeed may not con- verge), the infinite-depth fixed-point x = g(2", x²) can be solved using a root-finding method. A key advantage of DEQs is that backpropagation through the fixed-point can be performed analyti- cally using the implicit function theorem, and DEQ training therefore requires much less memory than DNNs, which need to store the intermediate layer activations for backpropagation.
In standard DEQs, existence of unique fixed point not guaranteed, nor stable convergence to a fixed-point easy to obtain in practice. Monotone DEQS (monDEQs) (Winston & Kolter (020) improve upon this aspect by parameterizing the DEQ in a manner that guarantees the existence of stable fixed point. Monotone operator theory provides a class of operator splitting methods which guaranteed to converge linearly the fixed point (see Ryu & Boyd (2016) for primer). The
2

---

Published as a conference paper at ICLR 2021
monDEQ considers weight-tied, input-injected network with iterations of the form
(k+11) (W + Ux
(1)
where E Rn is the imput. U Rxxa the input-injection weights, 200 R2th the hidden unit activations at "layer" i, and W E Raxh the hidden-unit weights, and E R a bias term, and RRAh + Rhh elementwise nonlinearity. The output of the monDEQ is defined the fixed point
of the iteration, a =" such that
oW2" + Ux b).
Just as for DEQs, forward iteration of this system need not converge to :; instead, the fixed point is found as the solution to a particular operator splitting problem. Various operator splitting methods can be employed here, for example forwand-buckward iteration, which results damped version of the forward iteration
2(++1) = =
a((T a W) (Ux+ + b))) = W))
a(Ux + b))- (3)
The operator aa -W) appearing in this iteration is contractive for any 0 < a S 2m/ L2 and this iteration is guaranteed to converge so long as the operator I- W Lipschitz and strongly monotone with parameters L (which is in fact the spectral norm || Will) and m (Ryu & Boyd 2016). In Section 3
we will see how unrolling this iteration leads directly bound on the Lipschitz constant of the monDEQ. To ensure the strong monotonicity condition, that / W 2 ml, the monDEQ parameterizes W
W (1 m)) A
The strong-monotonicity parameter m will in fact figure in directly to the Lipschitz constant of the monDEQ.
Lipschitz constants for implicit-eepth models A few prior works have proposed methods for bounding the Lipschitz constants of other classes of implicit depth network. Ghaoui al. (2020) define restrictive conditions for well well-posedness of the monDEQ. In particular, they require the weight matrix W to be such that forward iteration stable (as opposed to the stability of the operator splitting methods required by monDEQ). They derive Lipschitz constants and robustness guarantees under these conditions; for example when || < then a Lipschitz bound can be derived by simply manipulating the fixed-point equation as they demonstrate in equation 4.3. Herrera et al. (2020) propose a framework for implicit depth models which incorporate the Neural ODE (Chen et al. 2018) (which the solution of an ODE at a given time T) but not the monDEQ (which can be cast as finding the equilibrium point of ODE). They derive bounds on the Lipschitz constant w.r.t. network weights, but their framework cannot be applied to bound the Lipschitz constant of the monDEQ.
an implicit network which are different from those
3 LIPSCHITZ CONSTANTS FOR MONOTONE DEQS
We now present our main methodological contributions, casily-computee bounds on the Lipschitz constants of monDEQs. We first derive the Lipschitz bound on the input-output mapping defined by the monDEQ. followed by that for the woight-output mapping. As we describe below, both bounds turn out to depend inversely the strong-monotonicity parameter of the monDEQ. Since m is chosen for the monDEQ at design time, this implies an analytical handle on its Lipschitz constant.
3.1 LIPSCHITZ CONSTANTS WITH RESPECT TO INPUT
The naive way of computing L for feedforward deep networks is by multiplying the spectral norms of the weight matrices. As stated above, just employing forward iterations does not lead to con- vergence of the monDEQ. Analogously, if we were to adopt the naive method and simply unroll the forward iterations the monDEQ as described equation [] we would end up with an infinite product of spectral norms, which would not converge unless W itself is contractive. Here again, we consider unrolling the averaged operator T == I a(I W) employed in the forward-bace backward iterations, which ensures that the monDEQ converges, and will also lead to a finite bound on the Lipschitz constant. Notice that T' appears in the forward iterations in equation R In the sequel, let [[A) denote the Lipschitz constant of a function or operator A. The following proposition, which prove in Appendix A bounds the Lipschitz constant T. [T].
3

---

Published as a conference paper at ICLR 2021
Proposition 1. L[T] v1 2am + a² W]²
L[T] 1. In our subsequent analysis, we only consider values of in this range. We are ready to state bound for the Lipschitz constant of the monDEQ:
This implies that for a (0, L [[--(?
Theorem (Lipschitz constant of monDEQ). Let f(x) =
2" denote the output of the monDEQ on input a, in equation! 2 Consider any 2. E IR", Then, have that
||U|| m | 8112.
llf(z) f(y)l12 -
In other words, L[f]= <
||0||
Proof. Let (x) = (a) denote the kdh iterate of the forward-backward backward iterations as described in
equation (we begin with [u(x) 0). We will try and unroll these iterations the following:
(x) - f (1( a aUx - (TT(--i + aUyy + ab)
< 17 -uyy -Uyy-billl (a RR-UU is 1-Lipschitz))
- (f(x fx-1(v)) a [x((x v)lla
s 1
=
k-1
s - fo(u)la a v1l2 > (L[TT)
(unrolling times)
2=0
=a|lUl|a 81l Ear (since fo(x) = fo(y) 0)
Since the above inequality holds for all k we can take the limit on both sides as k -> oo, keeping or fixed. But notice that since the forward-backward iterations converge the / (which does depend on a),, we have that limg-sso fu = f. That is, the dependence on a disappears on the LHS once we take the limit on k. Thus, by using the continuity of the l2 norm, have
lIf())) f(v)l22
lim fa(x)) 1-000
lim fe(y) 4000
Sa vll2 E(ITT)
al|U/11 L
||
vll
(since [[]] 1)
|
2am + az L W æ vll2 (from Proposition 1
Now, since the above result holds for any in the range considered, taking - O, we have that
a |l1l
Lifl
lim a 1- /1 2am + a a2L I W
|
(applying L'Hopital's rule)
We observe here that the Lipschitz constant of the monDEQ with respect its inputs indeed depends on only two quantities, namely || 2| and m, and doesn't I depend at all on the weight matrix W. Furthermore, because the notable property that one can essentially control the Lipschitz parameter of the network (insofar the influence of W is concerned) by appropriately choosing m, and not require any additional structure or regularization on W. This is in stark contrast to most existing DNN architectures, where enforcing Lipschitz bounds requires substantial additional effort.
hyperparameter chosen by the user, this illustrates that monDEQs have

---

Published as a conference paper at ICLR 2021
3.2 LIPSCHITZ CONSTANTS WITH RESPECT TO WEIGHTS
We now turn to the question of bounding the change in the output of the monDEQ when the weights perturbed but the input remains fixed. This calculation has several important cases, of which is in the derivation generalization bounds for the monDEQ. Given a bound on the change in the output on perturbing the weights of the monDEQ, we can derive bounds on the generalization error a trraight-forwaan manner, as detailed Dection[Tbeloo The following theorem establishes a perturbation bound for the monDEQ.
Theorem (Perturbation bound for monDEQ). Let I- W Z ml and I I- W Z ml. The change in the oulput of the monDEQ on perturbing the weights and biases from W, U, b to W, U, is bounded
as follows:
II(WW S(W, S IW - Wllallux + blla I1 - U-x 12 + 1 bll2
mim
The proof steps for Theorem 2 parallel closely those involved in the derivation of the Lipschitz constant with respect the inputs, and are outlined in Appendix [ We highlight here again that the bound depends inversely on m, a design parameter in our control. Further, when compared to similar perturbation bound derived in Neyshabur et al. (2018), we note that perturbation bound for the monDEQ does not involve depth-dependent product of spectral norms of weights. In addition, although we state the theorem in terms of perturbation of W (which thus lead to different strong monotonicity parameter m the bound can also be adapted to perturbations on A and B in the typical monDEQ parameterization, which leads to a perturbed network that will necessarily still have the same monotonicity parameter m as the original (indeed, we take this approach in the next section, when deriving the generalization bound).
4 GENERALIZATION BOUND FOR MONDEQ
In this section, we demonstrate how the perturbation bound derived in Section 3.2 to deterministic PAC-Bayes, -aagin-based bound on the monDEQ generalization error, following the analysis for DNNs of Neyshabur et al. (2018). A key difference from our work, however, is that the perturbation bound they derive involves the product of spectral norms of all the weight matrices in the DNN. Thus, the network gets deeper, their bound grows exponentially looser. As in Neyshabur et al. (2018), our generalization bound is based on two key ingredients. The first is their deterministic PAC-Bayes margin bound (Lemma i the Appendix C) which adapts traditional PAC-Bayes bounds to bound the the expected risk of a parameterized, deterministic classifier in terms of its empirical margin loss. The second is the perturbation bound monDEQ with respect to weights as derived Section abooe. Crucially, since our perturbation bound does not explicitly involve product of spectral norms of weights (which in the case of the monDEQ, would be an infinite product), our final generalization bound does not either.
leads directly
The monDEQ model we consider here consists of a fully connected layer at the end that maps f to the output, so that (z) Wof((x) + by where W. and b, are the weights and bias in the output layer; these parameters are important to include here since they contribute directly to the perturbation bound. We also restrict the input z to the monDEQ to lie in an l2 norm ball of radius B. Let h denote the hidden dimension of the monDEQ, and M the size of the training set, and define = max [|7,,,, the monDEQ on the data distribution D, where
||, |[b]|2, |lW, ll2) Let (fo) denote the expected margin loss at margin y of
Ly (fo) (=.W)~> fo(x), ST max fo()); JFy
and (.o) denote the corresponding empirical margin loss on the training dataset. We are now ready state our generalization bound for the monDEQ: Theorem (Generalization bound for monDEQ). Let
Σ | = | + | + | + 1 + IW + 11b.11
For any 8, v > O. with probability at least 8 over the training set of size M, we have that
Lo(f) < (.()) + (AAMCANSs B(y + 3) + m3B + m2?
In MyM
W 12
22m-M
M
5

---

Published as a conference paper at ICLR 2021
10²
10"
LipSDP-neurol
width-60, our ub
Lipschitz constant
naive upper bound
Lipschitzz constant
width=60, empirical lb
empirical lower bound
width-40 our ub
width=40, empirical lb
10a
10
10"
4
6
10
12
14
5
10
15
20
depth
strong-monotonicity param m
(a) DNN Lipschitz bounds Depth
(b) monDEQ Lipschitz bounds vs m
10
400
CNN greedy SeqLip
single-con munDEQ
Lipschitz constant
10
CNN annealing
Lipschitz constant
multi-covy monDEQ
singlo-conv monDEQ, m=
300
10
multi-conv monDEQ, m=1
200
10a
10
100
8
15
20
depth
mtnotoitott param
(c) CNN bounds Depth
(d) Convolutional monDEQ bounds
Figure I: MNIST results: Lipschitz bounds as a function of depth and strong monotonicity parame- ter. lb: lower bound; ub: upper bound.
Note that our bound above does not involve any depth-like term that scales exponentially. like the term that involves the product of spectral norms the weight matrices /Neyshabur al. (2018) (while still having the same dependence on h, which is vh In h). To the best of our knowledge, this is the first generalization bound for an implicit-layer model having effectively infinite depth. The proof of Theorem 3 given Appendix
EXPERIMENTAL RESULTS
5.1 LIPSCHITZ CONSTANTS
In this section, we empirically verify the tightness of the Lipschitz constant of the monDEQ with re- spect to inputs. We conduct all experiments MNIST and CIFAR-10, for which several bench- marks exist for computing the Lipschitz constant. We conduct experiments for different monDEQ ar- chitectures (fully commected/convllutionall with varying parameters wwroon-mmootoniccig parameter m and width h), which we compare to DNNs with different depths and widths. We compute empir- ical lower bounds by maximizing the norm of the gradient 10k randomly sampled points. A naive upper bound can be computed as [ WWll2 We include these bounds wherever applicable.
MNIST Here, we train DNNs for various depths from d = 3. 14 for a fixed hidden layer width h 40, and plot (Figure Ta] the bound the Lipschitz constant given by the SDP-based method of Fazlyab et al. (2019) on these DNNs. We can observe that all estimates the Lipschitz constant increase exponentially with depth. For comparison, in Figure Db we plot our Lipschitz constant bounds for monDEQs with fixed h = 40, 60. for a range of ttrong-monotoiictt parameters m. We note that the DNNs all have test error of around 3%, while the monDEQ test enror ranges from
Experimental code available httpa//iiiilaae////ooooooooooaaa it__mndeee

---

Published as a conference paper at ICLR 2021
10
menDE(Q
34
Lipschitz constant
menDEOs
CNN med
CNN sm
CNN lg
CNN lg
CNN sm
% test crror
32
10"
30
10
26
10
15
mrooon-monooonicity param
0
5
10
15
20
durong-monotonicii param m
(a) Lipschitz bounds for monDEQs vs m and for three CNN models. Solid lines: upper bounds; dashed lines: empirical lower bounds.
(b) Test for CNNs and monDEQQ m.
Figure 2: CIFAR-10 results: Lipschitz bounds and test accuracy for monDEQs as a function of strong monotonicity parameter and for CNNs. See text for description of models.
2.4%-4.3% increasing with m (see Figure in Appendix P for details). We see that the Lipschitz constant of the monDEQ is much smaller, and that on increasing m, the Lipschitz constant of the monDEQ decreases, outlining how can exercise control on the Lipschitz constant.
We also compare the Lipschitz constants mEnS and DNNs having the same width, for a fixed depth d = 5. The results shown in Figure 6 in Appendix FF The DNN numbers are derived from Figure 2(a) in (Fazlyab et al. 2019). We observe that the Lipschitz constant of the monDEQ for the same width (and essentially infinite depth) is much lower than the bounds for regular DNNs
we compute the Lipschitz constant of convolutional monDEQ architectures, namely single convolutional and multi-tier convolutional monDEQs. We compare the numbers in Figure in Virmaux & Scaman 20188. which reports the Lipschitz con- stants computed by various methods for different CNNs with increasing depth. For our estimate on the single convolutional monDEQ, we use single convolutional layer with 128 channels, whereas for the multi-tier convolutional monDEQ, we use 3 convolutional layers with 32, 64 and 128 chan- nels. In Figure Tcl can observe that as for DNNs, the CNN Lipschitz constants estimated by existing methods also suffer with depth. However, we can observe in Figure that that the Lipschitz bounds for convolutional monDEQs Lipschitz constant both single as well as multi-tier convolutional monDEQs. The test error for the convolutional monDEQs is 0.65%- increasing with m (see Figure 5 in Appendix (). but is not reported for the CNNs in Virmaux Scaman (2018).
Next, using the bound derived in Section 3.1
much smaller. Also, increasing m,
control the
CIFAR-10 To demonstrate that the Lipschitz bounds scale to larger datasets, we run similar ex- periments on CIFAR-10. Figure 2a shows our bound (solid blue lines) for single-convoluttinnal monDEQs (128 channels) with a range of m values, together with empirical lower bounds (dashed blue lines). Also shown are upper bounds (solid lines) and empirical lower bounds (dashed lines) for three standard CNN models (CNN sm, med, and Ig. having 2, 4, and 6 convolutions respectively, detailed in Appendix Fb. The upper bounds are computed using the Greedy SeqLip method of Vir- mmaxx& & Scaman 2018). We see that a) the monDEQ Lipschitz bounds decrease with m, and b) the upper bounds (and gap between upper and lower bounds) for the medium and large CNNs are large by comparison. In Figure 2b we see that test error of the monDEQ increases with from 26% to 33%, and that, despite their much higher Lipschitz bounds, the three CNNs have similar test error.
Finally, CIFAR-10 with data augmentation, also trained a larger multi-tier convolutional mon- DEQ with three convolutional layers with 64, 128, and 128 channels. This model obtains 10.25% test error and has Lipschitz upper bound of 1996.86, which is on par with the upper bound of the medium CNN (plotted in brown; with I. 1554.001 test error =30.6%).
Unrolling monDEQQ In this experiment, we study if unrolling the monDEQ with m = 1, = 40 up to finite depth and constructing equivalent DNN with this depth leads to tight estimate of
7

---

Published as a conference paper at ICLR 2021
DNN monDEQ. m=
10
gen. bound
10a
gen. error
10"
10²
10"
4
8
10
12
5
10
15
20
depth
strong-monotonicity param m
(a) DNN generalization bound Depth
(b) monDEQ generalization bounds vs m
Figure 3: Generalization bounds for DNNs and monDEQs as function of depth and m.
the Lipschitz constant of the monDEQ. Concretely, we do this for two operator splitting methods in the monDEQ: Forward-backward (FB) iterations and Peaceman-Rachfone (PR) iterations. For each value a in a range, we calculate the number of iterations (FB or PR) required to converge within tolerance 1e-3, and construct the equivalent DNN with this depth. Note that these unrolled DNNS compute the same function as the monDEQ (up to tolerance), and therefore, must have the same Lipschitz constant (which is around 10). We compute naive upper bounds on the Lipschitz constants of these DNNs (we cannot use the SDP-based bound of Fazlyab et al. (2019) due to technicalitics in the construction of the unrolled DNN; refer to Appendix D). We can observe (Figure 7 in Appendix F) that the upper bounds corresponding to both PR and FB iterations are the range 10 10S3. suggesting that unrolling the monDEQ and employing standard techniques on the unrolled monDEQ not viable way to bound the Lipschitz constant. More details about the construction of these equivalent DNNs for both FB and PR iterations are provided in Appendix D
5.2 GENERALIZATION BOUNDS
key advantage of the monDEQ generalization bounds derived in Section iis the lack of any depth analog that can cause the bounds to grow exponentially. To assess this aspect experimentally,
first compute the DNN generalization bound following the protocol of Nagarajan & Kolter (2018). We train DNNs (width 40) of varying depth of 3 to 14 layers, and compare to similar monDEQs with various m values. Each model is trained on a sample margin error at margin across choice of batch size and learning rate. As widely reported, we see that DNN bounds increase exponentially with depth, ranging numerically from 10º for depth 3 networks to 10 (see Figure For monDEQQs of width 40, range 10* to 10 seen in Figure 3b (note the difference in scale). In contrast, the true test error of the DNNs increases only slightly with depth, and that of the monDEQs increases only slightly with m. Note that the DNNs and monDEQ have comparable test error (see Figure 8 in Appendix G).
4096 MNIST examples until the 10 reaches below 10% which serves to standardize the experiments
bound decreases monotonically with m, and confined to the
Finally, as done for Lipschitz bounds above, we compare our generalization bound what we obtain by unrolling the monDEQ into a DNN, and then computing the Neyshabur et al. (2018) bound more- or-less directly (see Appendix E We do this only for FB iterations, as the inverted operators of PR iterations complicate the analysis. As seen in Figure &c the resulting bounds are quite high, though the difference with our bound is not great We attribute this to the fact that our generalization bound technique is minimal modification to that of Neyshabur et al. (2018); expect that it can be tightened with more refined analysis.
seen for the unrolled Lipschitz bounds above.
5.3 ADVERSARIAL ROBUSTNESS OF MONDEQS
In this section, we empirically demonstrate an important use case for the tight Lipschitz constants of the monDEQ: robustness to adversarial examples. We experiment with both certified adversarial & robustness as well as empirical robustness to adversarial PGD Ez-bounded attacks. Here we describe results MNIST, and report similar experiments CIFAR-10 in Appendix H
8

---

Published as a conference paper at ICLR 2021
Certified Robust Test Accuracy
PGD Attack Test Accuracy
0.8
0.6
0.4
0.2
0.100
1.0
12
14
DNN d=3 1=14.15
DNN d= L=199.19
DNN d=3
DNN d=14
DNN d=4 L=23.46
DNN d=8 L=557.46
monDEQ
DNN d=5 L=51.59
monDEQ m=0.1, L=47.38
monDEQ
DNN d-6 L-82.41
monDEQ m-20, L-3.83
(a) Certified Adversarial Robustness
(b) Adversarial robustness to PGD attacks
Figure 4: Superior adversarial robustness monDEQs as compared to DNNs
Certified adversarial robustness Then, we have that
Consider any point x' within an l2 ball of radius around x.
[1((x) - f(')l< 11((z)-((z')))
L||or x/112 Le
Define margin(x) f(x) maxi / (x)); where [(x) is the logit corresponding to the label of the input z. Then if Lc S margin(z)) we are certified robust to any perturbed input z' within an 12-ball of radius around z. Thus, we can empirically compare DNNs and monDEQs with regards to this certificate on MNIST. For range of values, we compute the (certified) robust test accuracy (fraction of points test for which the aforementioned condition holds) for trained DNNs as well as monDEQs. We note here that our choice of values corresponds to inputs normalized in the range [0, 1]. For DNNs, just in Figure Ta we vary the depth for fixed h = 40, and the L values computed by using the method in Fazlyab et al. (019).. For monDEQs, we set width upper bound for T. Note that since the L values for
0.1, 20 and substitute monDEQs observed in Section 5. were significantly smaller than those for the DNNs, one would expect the condition for the certificate to hold more easily for monDEQs. Indeed, we verify this in our experiments. In Figure 4al we can observe that the robust test accuracy for the monDEQ with 20 at 0.2 is 51%, while that for the best DNN (d 3), is just 4%. This illustrates that monDEQs allow for better certificates to adversarial robustness, owing to their small Lipschitz constants, and the ability control it by setting
40,
Empirical robustness We also assess the empirical robustness of monDEQs to lg-bounded Pro- jected Gradient Descent attacks (implemented part of the Foolbox toolbox (Rauber et al.) 2017; 20200) on both, trained monDEQs and DNNs on MNIST, and compute the accuracy on these adver- sarially perturbed test examples. Figure 4b shows the results: in general, over range of values, the robust test accuracy of the monDEQ with m 20 larger than that of the DNNs.
CONCLUSION
In this paper, we derived Lipschitz bounds for monotone DEQs, a recently proposed class of impicit- layer networks, and showed that they depend in straighforward manner on the strong monotonicity parameter of these networks. Having derived Lipschitz bound with respect to perturbation in the weights, we were able to derive a PAC- -Cy-Bay generalization bound for the monotone DEQ, which does not depend exponentially can be controlled by choosing m suitably, and do not suffer with increasing depth of the network. As future work, aim to analyze the vacuousness of the derived generalization bound. As such, since our bound does not suffer exponentially with depth, we hope to be able to make the analysis tighter and derive non vacuous generalization bound.
depth. We showed empirically that our bounds sensible,

---

Published as a conference paper at ICLR 2021
REFERENCES
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, pp. 690-701, 2019.
Shaojie Bai, Vladlen Koltun, and Zico Kolter. Multiscale deep equilibrium models, arXiv preprint arXiv:2006. 2000:20006.86666, 2020.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalizze margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In Advances in neural information processing systems, pp. 6571-6583, 2018.
Patrick Combettes and Jean-Christophe Pesquet. Lipschitz certificates for neural network struc- tures driven by averaged activation operators. arXiv preprint urXiv:1903.011 2019.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems, pp. 11427-11438, 2019.
Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Annin Askari, and Alicia Y. Tsai. Implicit deep learning, 2020.
Calypso Herrera, Florian Krach, and Josef Teichmann. Estimating full lipschitz constants of deep neural networks, 2020.
Ming Jin and Javad Lavaei. Seatiiit reinforcement learning: A chhtrol- perspec- tive. arXiv preprint arXiv: 1505, 2018.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference Learning Representations, 2019.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing resileeesi. In International Conference on Learning Representa- tions, 2018
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. pac-bayesian approach to seoctaally-nommaliee margin bounds for neural networks. In International Conference on Learn- ing Representations, 2018.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Representations, 2018.
Jonas Rauber, Wicland Brendel, and Matthias Bethge. Foolbox: A python toolbox to benchmark the robustness of machine learning models. In Reliable Machine Learning in the Wild Workshop, 34th International Conference on Machine Learning. 2017. URL http: org/ abs/
1707. 04131
Jonas Rauber, Roland Zimmermann, Matthias Bethge, and Wieland Brendel. Foolbox native: Fast adversarial attacks to benchmark the robustness of machine learning models in pytorch, tensor- flow, and jax. Journal of Open Source Software, 5(53):2607, 2020. doi: 10.21 12500 URL httpt:::p//........... htt.pps:/ddoooo/ .oroi.org//. 10. 21105 joss. 02607
Emest K Ryu and Stephen Boyd. Primer monotone operator methods. Appl. Comput. Math, 15 (1):3-43, 2016.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna Estrach, Dumitru Erhan, Ian Goodfellow, and Robert Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certifi- cation of perturbation invariance for deep neural networks. In Advances in neural information processing systems, pp. 6541-6550, 2018
10

---

Published as a conference paper at ICLR 2021
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, pp. 3835-3844, 2018.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference Machine Learning, pp. 5276-5285, 2018.
Ezra Winston and J Zico Kolter. Monotone operator equilibrium networks. arXiv preprint arXiv:2006.08591, 2020.
Dongmian Zou, Radu Balan, and Maneesh Singh. On lipschitz bounds of general convolutional neural networks. IEEE Transactions on Information Theory, 66(3):1738-1755) 2019.

---

Published as a conference paper at ICLR 2021
A
PROOF OF PROPOSITION 1
Proof.
11TT - = - -(W+- a) + aW)yl
= || - al ( y)1l
= | vll - -2a(r - y1 - W) [ y) + a [[][I--)== 3)1
I I v 2a(x y)
(1- -
v) a22LII --]- - -11
Now, note that by the strong monotonicity of the monDEQ.
1 - W ž ml, (z which implies that - (x) (1-)( - y) 2 m x - U| Substituting this bound above, we have that
[Tx - Tyll3 & || - y1 2am r + - v11
(11 20m + a² a²T.(T W| v
Thus, we have that T.T]] < v 20m + 2 W
B PROOF OF THEOREM 2
In order to derive the perturbation bound in Theorem 2 we first state the following proposition, which bounds the norm of the output after & forward-backwant iterations.
Proposition 2. Let f&( U. b) denote the hth iterate of the monDEQ parameterized by W, U, on a fixed arbitrary input x. Further, let T(W) = (1 aa +
backward iterations of the
aW. Then, we have that
a aUx bl12 U,,
1 1-L(WWW)
Proof of Proposition
f (WU,,b)le (W..)
S ( (ReLU is 1-Lipschitz)
1/71:)16-1((/,2000])=+1111- bl12
417,0|1 +611
<417"166(0.C000)]==00111 + bll2
8=0
=allUx +612
LIT (since fo(, 0)
SallUxx + b12
Σ L[7
1=0
a/IUxx + 6|l2
(since L[T] < 1)
1 L[T]
We are now ready to prove Theorem 2
Proof of Theorem
2 Denote fx fw( U,b) and ft = fu(W,U,b) Further, denote A
[/ Sxl12.
For E min - LU-
2m
2m
we have from Proposition that both
12

---

Published as a conference paper at ICLR 2021
[T(W]l2. < 1. Thus,
A = - - (T(W) - a(U - U) a(b b)]l
bb]ll2 bb]l2
U)x a(b- b)ll2
(7(W)((--1-1--)) -0 U) + a(b b)
(T(W)]l2A W -)]lal/fe-11aa-00000 -U)))))) + a:| b|l2
[T(WW)122 a² \ W)]la||U+++bl +a U)>12 al1B b|l2
(Proposition
- |T(W))l2
a WW)laauu bll2
R-1
+ all(U - U)>12 + allb b|[2
Σ
|T(WI)
1- 1-]]())
Notice here again that the above incquality holds for all k. Taking the limit as - oo similar to the step in the proof of Theorem 1 we have
|l 0) - f(W, U, U,W,U,))122 12 = lim A
k--000
a² I - 12 x + bll2 + aall - U)x|12 2 + +alb bbll
T(W
1- --[T(W)
==0
a² W W)llalUx bll2
11(0 U))=ll2 + 11b- b1l2
[T(W))la) (
(W))2
Finally, taking 0, we have that
a 22 6 11
- ([, < lim
a (1 - U)2112
1|b 6112
1 [-I)
= I W) + b112 lim
lim
a a 1- 1T
a=+0 1 [T l22
(I(@ U))112 + ([b-bll)) lim
a
[T(W)l 22
| W/ + bll2
|1(0 - U)al| + || b112
+
(applying L' L'Hopital's 's rule)
mm
m
C PROOF OF THEOREM 3
Proof. We first state Lemma from Neyshabur et al. (2018).
Lemma 1 (Lemma from Neyshabur al. (2018)). Let Jw be any predictor with parameters w, and let P denote any distribution on the parameters that is independent of the training data. Then, 5 over the training data of size M. for any w, and any random perturbation u such that P P(maxz [lfwta(x) - fw))l) < 2 2 we have
for any 8, > O with probability
KL(w + ul P)) + In
6M 8
Lo(fw) < (.((F) + +41
M-1
Now, we derive perturbation bound for the monDEQ when we incorporate the fully connected layer at the end, as mentioned in Section That is, we consider fo(x) = Wof(x) + bo where ff is the output of the fixed-point iterations of the monDEQ. Next, we consider perturbations A.. Ag, Ay, As, Aw., Ae, for A, B, U.b, W.. b, respectively. The entries in the perturbation ma- trices are each drawn independently from Gaussian (0, Let fo denote the function the
13

---

Published as a conference paper at ICLR 2021
perturbed values of the weights. Then, we have that
Ilfo (x) - fo(2)]l2 = [Waf(()) + bo Wof(x) - boll2
I [[o(f(x) - f(x)) + (W, - Wo)f(x)llz + 1,b boll2
I W Wol221Ux + b112
& |Wol224 +
+ lib - boll2
where is the bound from Theorem 2
Now, let 3 max([|U] 12. ||A || [[]]l]). Just in (Neyshabur et al. 2018). since cannot use 3 in determining the parameters of the prior distribution P Lemma we will consider pre- determined values 3 on grid, and then do a union bound. For now, we fix B, and consider all the values 3 such that |
8 for some constant 01 < 1.
Since the entries in the perturbations are drawn from (0, o²), we have the following bound on the norms of these perturbations:
P 1|
S 2he -2 /2ho"
where A. a placeholder for each of the perturbation matrices. Thus, we have that with probability 2 1/2, all of the ||A.||a l|2 are bounded above by a o In(24h) := w.
Now, we bound the perturbation in ||W 2l2 when A and B are perturbed. We have that
A 1|2
|| A A A A + AB 1/222
||| All2 + || S (3 w) (with probability 1/2)
Substituting this above, have that for all x. with probability at least 1/2,
llfo(z) fo(x)ll2 v w + WB + +1 2w3(B + 1) m²
m
Here, let 02 0 be some constant such that w 02 Thus, have that 211 + (B) + 1)
2 + 1)
[lfo(z) fo(x)]le <
m²
m
21 + c2) + 1)
2 + 1) m(1 c1)
< w
m²(
(2
2m, + 1)(1 c1) + m² - -1)
2h (24hh)
m² C1
Setting 4
7m (1-201
makes this 3. Since
need S 0g we can take the smallest 02 such that
(1 + 11
OV 2h 1n
w
B
B
B
Taking 02 = (1+a1) suffices. We will later plug in the value
48
= + c1)7
2 02
4(1 - c3
bound C2.
Then,
Σ I.
KL(W. + Aw.P) S
20²
16hln(44)) C + 1) + 2m. 1)(1 c1 m -3)333
Σ W|
22 (1
16h (G0 2m
1)(1 - m (1 Σ w.
32m 6
14

---

Published as a conference paper at ICLR 2021
Then, by Lemma 1
have that with probability 1 5,
(Jo) s (fo)+
16h +1 -
7 01) (M ()-11)))111 c1)² m m 03)3
In 6M
M
Now we need to take a union bound over 3 so that the above result holds for all 3. Observe that only need to consider |8 in the range
YMV M 2 + SBS
7
2(B + +1)
If 3 <
2,4+Ij then 1s(z) < 8(B-1) I 3 so ()) > 1. If 2
mm
TMV then the second term in 20++]
the first term in the numerator is greater than so the theorem holds trivially.
So | - 31 <
2(+1) guarantees | - - < 8 in this range. So we can use cover of size
7m
/ /2:: This amounts to replacing In 6.// with In AM/3///c22.
(1+ti) Finally, substituting C3 4(1-c1)8+ get the theorem statement. We can also effectively optimize over 0j to remove it from the final bound.
D UNROLLING FORWARD-BACKWAN AND PEACEMAN-RACHFORT ITERATIONS
In this section, derive the form of the equivalent feedforward DNN that computes the same quan- tity as running iterations of either operator-spliting methods for computing the fixed point of equation I (refer Winston & Kolttr 2220
or
iterations, which are
D.1 UNROLLING
ITERATIONS
One step in the forward-Backwart iterations computes
2(+1)
a(1 a) + aW)z + a(Ux+b))
To simulate k steps of these computations depth k-feedforward network, let construct the following weight matrices:
aU I
Wi
(1
a) T + &W
aU I
W
0
W I
0]
Then, we can observe that
abb
200= Wix +
(2) æ
[bb]
(f+1)
W
+
Here, applies only to the top h coordinates corresponding to (0) Finally, we multiply the output of the monDEQ after iterations with the output weights, to obtain fo(x) as
(R)
fo(x) W
b.
Thus, the equivalent depth-k DNN which we construct would have weight matrices W1, W,. In this DNN, the ReLUs in the intermediate layers would only apply to the top coordinates corresponding given by (Fazlyab et al.] 2019) for computing the Lipschitz constants of these unrolled networks, since they require the same nonlinearity to apply pointwise all coordinates).
(this is the technical reason why we can't the SDP bound
15

---

Published as a conference paper at ICLR 2021
D.2 UNROLLING PEACEMAN-RACHFOR ITERATIONS
Define V = (I (ala w)) One step in the Rachforr iterations computes
(1++)) u 22 + +V=2 2V + VaV 2a
(6+1) = o
To simulate & steps of these computations depth k-feedforward network, let construct the following weight matrices:
Va 2aVU
W
I
[[ - 2V
4V
21
Va
W
2V
4V
Va
0
I
Wf
0
W.
0
Then, we can observe that
20
W +
2aVb
[+))
2uV
((+1)
W
2(t)
+
2
Here, a applies only to the top coordinates corresponding to 20) Finally, we multiply the output of the monDEQ after iterations with the output weights, to obtain fo(x)
(k) (k)
fo(x) W'
+ bo
Thus, the equivalent depth-k DNN which we construct would have weight matrices W1. [Walt W, and the ReLUs in the intermediate layers would only apply to the top coordi- nates corresponding
GENERALIZATIION BOUND FOR UNROLLED MONDEQ
In this section, we derive generalization bound for an unrolled monDEQ after unrolling the forward-backward iterations d times and constructing the equivalent depth-d network. The anal- ysis follows the derivation of the generalization bound for DNNs by (Neyshabur et al. 2018), but we have to be careful since the weight matrices across the hidden layers are all the same and are of certain parameterized form. Since the analysis in (Neyshabur al., 2018) does not include biases in the DNNs, here, we consider unrolling monDEQs which do not have the bias term
Take each layer weights to be
a: W) aU
W
0
where the network is now a function of
(i)
Σ
and the ReLU applies only to the (0) component. And
W
W
=
0
16

---

Published as a conference paper at ICLR 2021
Our prior distribution will now be over Aw., AA. Ap. Au N2), Similar to the corre- sponding step in C above, we have that with probability 2 2. the perturbations are each bounded by : a / 22 In 16h). Also
A 1 = ||A" A A A+ B - B- B + 17
$ ||A + 2 12 Alla + 2114B12
And so
| w.. 1l2 = || adw a&v
a (IAA 11 + 2/ A 12 A|I2 + 2/| 2 B l2 + +| l12)
We take 3 == =max | 21 ||, |W [.ll2)- We assume that /3 - 31 s 2 and d 2 2, 80 we
have B eB. Then applying Lemma 2 in (Neyshabur al. 2018). we have
Ifw.+Aw.
f Se -)lldd-))]-l0 A) l/A.. l12) I < 1)a (1 + 2 A |22l + 211 + 11uul12) + 11A.. l12)
S SeBgt 1))x(1> + 2w/3 3w)) w)
S SBB3d- l(d 1)a( 2 3 + 23 + 1)w
I e² B3d ((d - 1)a( ()d-)aa( e 20 + 8) + 1) 1n66)) S ?
4
we choose
7
0 4e2 1) + 2e,3 3) 1) / 2h (n616))
Let
Σ = || + B
+ | + W.
Then
KL(A + A B An, U+Au, W. + Aw.)llP) Σ |A, B,U, W.13
20²
16e B B² 32d- ((d () + 2eB
+ 3) + 1)22h 1))1)2hh1((16 (n616))
WW.11
72
16e B2 gad 2 ((d 1)a( 3 + 23 3) 1) (n(16))
IW..11
72
Now, instantiating Lemma above, we have that with probability least 1 5,
16ca 32 ()a( 3 8 2, + 3) + 1) In(16h) > |[ 12
In
Lo(f) L((f)+ + av
+
7²(M 1)
M
Following Neyshabur et al. 2018), we need to take union bound over 3 so that the above result holds for all B. Observe that we only need to consider 3 in the range
1/d
1/d
7
M
< 335
<
2B
2B
If 3dd
2B then [f(x)] < gdB < so ł. (f) 1. If gd >
2B T/M then the second term in the
first term in the numerator is greater than the result holds trivially. So 13 31 <
1/d
guarantees 3 - | < 8 in this range. So we can use a cover of size 1// just as in Neyshabur et al. 2018
17

---

Published as a conference paper at ICLR 2021
F
ADDITIONAL MONDEQ LIPSCHITZ BOUND RESULTS
single-conv monDEQ
4.0
multi-conv monDEQ
% test error
% tost emor
3.5
2
3.0
5
10
15
20
0
5
10
15
20
strong-momolonicity param. m
strong-momolonicity param. m
Width 40 monDEQs shown in Figure
(b) Convolutional monDEQs shown Figure
Figure 5: Test error for the monDEQs from Section
5.1
500
LipSDP-neuron
our ub
Lipschitz constant
naive upper bound
Lipschitz constant
12.5
empirical lb
10.0
300
7.5
100
5.0
20
40
60
80
100
20
40
60
80
100
width
width
(a) DNN bounds Width
(b) monDEQ bounds vs Width
Figure 6: Evaluating Lipschitz bounds as function of width. lb: lower bound; ub: upper bound.
Lipacinz COUNIII
Lipschitz constant
10a
2 10
10
10a
10²
10º
0.1
0.2
0.3
0.4
0.2
0.4
0.6
0.8
1.0
Forward-Backwant unrolled Lipschitz bounds
(b) Rachhoo unrolled Lipschitz bounds
Figure 7: Lipschitz bounds for monDEQ by unrolling forward-backward or Geaceman-Rachhoore for range of a.
18

---

Published as a conference paper at ICLR 2021
MNIST test error In Figure plot the test error of the width 40 monDEQs for which the Lipschitz bounds are given Figure Tb We see that increases from 2.4% for m = 0.5 4.2% for m = 20. For comparison, the DNNs shown in Figure Ta have test error between 2.8% and 3.2%, with no trend w.r.t. depth.
MNIST width experiments F shows the lower and upper bounds for DNNs and monDEQs of varying widths, as described Section 5.1 Figure 6a is transcribed from Fazlyab et al. (2019) figure 2(a).
CIFAR-10 CNN models
The details of the CNN sm, CNN med, and CNN ig models used in
Section 5. are as follows:
CNN sm:
Layer
Layer
channels out
stride
1
Conv2D
32
1
2
Conv2D
32
2
3
Linear
100
4
Linear
10
CNN med:
Layer
Layer
# channels
stride
Conv2D
32
2
Conv2D
32
2
3
Conv2D
64
1
4
Conv2D
64
2
5
Linear
100
6
Linear
10
CNN Ig:
Layer
Layer
# channels out
stride
Conv2D
32
2
Conv2D
32
2
3
Conv2D
64
1
4
Conv2D
64
2
5
Conv2D
128
1
6
Conv2D
128
2
7
Linear
100
8
Linear
10
All models use ReLU activations and kernels of size 3.
Unrolling monDEQs The approximate upper bounds on monDEQ Lipschitz constants obtained by unrolling the operator splitting methods are shown in Figure 7
19

---

Published as a conference paper at ICLR 2021
G ADDITIONAL MONDEQ GENERALIZATION BOUND RESULTS
We validate that both the monDEQ and DNN models considered Section 5.2 for generalization bound comparisons indeed achieve comparable accuracy well. Figures Sa illustrate this: can observe that the various models considered all achieve test error in the same range.
Next, compute generalization bounds for unrolled monDEQs (Section B for variety of values, to get a sense of the quality of our generalization bound for the monDEQ. Figure 8c we can observe that the generalization bounds for these unrolled networks are larger (on the order of 10%) as compared the generalization bound for the monDEQ (on the order 10"). This shows that our bound is tighter.
DNNs monDEQ, m-20
7.0
6.5
Test
test
6.0
6.5
8
10
12
5
10
15
20
depth
strong- momioonittt param
DNN Test error vs Depth
monDEQ Test error m
gen. bound
10
0.2
(c) Forward-Backwar unrolled generalization bound
Figure 8: Test error for DNNs and monDEQs, and monDEQ generalization bounds by unrolling iterations.
20

---

Published as a conference paper at ICLR 2021
H
ADDITIONAL ADVERSARIAL ROBUSTNESS RESULTS
Certified Robust Test Accuracy
0.6
0.2
0.000
0.002
0.004
0.006
0.088
0.010
CNN d=2, L=42.41, 36.46%
monDEQ m=1, L=159.96, 26.44%
CNN d-4, L-1554.01, 6%
monDEQ m-2, L-109.23, 27.29%
CNN d-6, L-5.79 10', 26.94%
m=10, L=78.90,
monDEQ m=0.1, L=806.56, 26.65%
monDEQ m=20, L=S1.19, 33.34%
monDEQ
L=250.64,
(a) Certified Adversarial Robustness the legend,
we state the Lipschitz constant of each model, and its
(clean) test error
PGD Attack Accuracy
0.6
0.3
0.1
0.3
0.4
CNN d-2
monDEQ m-1
CNN d=4
monDEQ m-2
CNN d=6
monDEQ m=10
monDEO m=0.1
monDEQ m-20
(b) Adversarial robustness to attacks
Figure 9: Adversarial robustness of monDEQs compared to CNNs
We run the same experiments that we ran Section 5.3 on the CIFAR-10 10 dataset. We train single convolution monDEQs (128 channels) with range of m values, as well as CNN models: CNN sm, CNN med and CNN Ig whose architectures described Appendix abbove.
As in the case of the MNIST experiments. we see that varying m gives a range of trade offs between clean accuracy and adversarial robustness. In terms of certified robustness,
in Figure th all of the monDEQ besides m 20 have both better clean and better robust accuracy than all the CNNs (with the exception of the CNN with d 9b terms of empirical robustness, we see that m parameterizes a similar trade-off between robust and clean accuracy. In fact, it possible choose m (e.g. m 1 here), such that the monDEQ outperforms all CNNs in terms of clean accuracy and at all attack sizes.
which has much lower clean accuracy). In Figure
21


Reviews:
[{"review_id": "zZlbjt8yNoP", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the Lipschitz constant of a recently proposed implicit-depth model, the monotone deep equilibrium model (monDEQ). Simple-form bounds on the Lipschitz constant w.r.t both the inputs and the weights are derived. The derived bounds are used to show an attracting property of the monDEQ model that its Lipschitz bound and PAC-Bayes generalization bound does not have exponential dependence on network depth as normal DNNs. \n\nPros:\n1.\tThe paper is well-written and easy to read. \n2.\tThe proofs for Lipschitz bounds that I have checked are correct.\n\nCons:\n1.\tMy major concern is the rather limited contributions of this paper. The methods for estimating the Lipschitz bound and the PAC-Bayes generalization bound are not novel. And the result that the Lipschitz constant of the monDEQ model is depth-independent is interesting but not surprising, since in some sense the DEQ model could be viewed as only having one layer.\n2.\tWhen deriving the Lipschitz bound, I don’t understand why to take the limit as $\\alpha → 0$ since $\\alpha$ is also a hyperparameter. In the experiment part, which $\\alpha$ is using for each model? And if the bound involving $\\alpha$ is used, will it be much tighter?\n3.\tThe experiment regarding the Lipschitz constants of the unrolled monDEQs is confusing to me. I don’t see why the Lipschitz constant computed in this way is much larger than the derived bound. Instead, I suppose it should be close to the bound because in the end it would also be computed as a convergent series similar to the derivation in the paper. Could you explain this in more detail? Besides, the notations and derivations in Appendix E are not very clear.\n4.\tIn the experiment of the generalization bound, why does the computed bound increase as $m$ increases (Fig. 3(b)), but the test error increases (Fig. 4(b))?\n\nAdditional Comments/Questions: \n1.\tIn the experiments, how is the empirical lower bound of the monDEQ Lipschitz constant computed?\n2.\tTypos in the related work part: “… several orders of magnitude larger *than than* empirical lower bounds …” and “The DEQ model directly solves *for for* the fixed-point …”\n3.\tTypo in Theorem 3: “training set of size $m$”-> “training set of size $M$”\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "z2BPQS1ddR6", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary\nThe authors of this paper derive analytic expressions for the Lipschitz constants (LCs) of monotone deep equilibrium networks (mDEQs) with respect to their inputs and learnable parameters.  Further, they leverage these estimates to provide a PAC-Bayes style generalization bound.  Finally, they empirically calculate their bound and compare to relevant approaches for computing the LCs of feed-forward networks.\n\n#### Strengths\n- The simplicity of the results is both a strength and (as I will discuss later) something of a weakness.  On the positive side, the authors show that their bounds do not have an exponential dependence on the depth of the network (which is especially important given that these networks are in some sense \"infinite-depth\" neural networks).  I checked each of the proofs, and they all appear to be correct.\n- The ability to control (an upper bound on) the LC with the strong monotonicity parameter $m$ is quite useful here.  Indeed, there is no such term in any of the methods that can be used to derive an upper bound on the LC of a feed-forward NN.  \n- The PAC-Bayes style bound is interesting, and should be further examined in future work.\n\n#### Weaknesses\n- It's not immediately clear to me why this problem is of particular use to the broader community.  Much of the literature that seeks to derive LCs for feed-forward/convolutional NNs is motivated by the connections between adversarial robustness and the LC (see, for example, Prop. 1 in (Fazlyab et al., 2020)) or by the prevalence of LCs in generalization bounds.  However, as far as I am aware, it is not known whether mDEQs are fragile to adversarial examples.  Furthermore, as the mDEQ network is such a new architecture (the paper came out earlier this year in 2020), it remains to be seen whether this architecture will be broadly and/or practically useful for the deep learning community, whereas it has been shown repeatedly that feed-forward networks and CNNs are broadly applicable in a variety of domains (see e.g. LeCun et al., 2015).  So while this problem may be interesting from a technical point of view, I am not sure whether it is a useful result that will have noteworthy down-the-line implications.\n- The technical results of Props 1-2 and Theorms 1-2 are quite straightforward, and as far as I can tell, the argument used to show Theorem 3 is quite similar to that of Neyshabur et al (2018).  Compared to works such as Fazylab et al (2019) and Raghunathan et al (2018), both of which build novel semidefinite programming frameworks, and Latorre et al (2019), which exploits underlying structure to derivate a polynomial optimization scheme, there is significantly less technical innovation here, and no new tools are developed that might be more broadly useful to the community.\n- The presentation of the experiments is sloppy.  Empirical bounds are computed for mDEQs, but not for other architectures.  Further, abbreviations (e.g. lb == lower bound?) are used which are not defined in the text.  Furthermore, given the apparent scalability of this approach, I would argue that performing experiments only on MNIST is not enough.  Why not try to compute bounds for more challenging/higher-dimensional datasets?\n\n#### Literature review\n- The literature review concerning the work that has been done toward deriving upper bounds on the LC of DNNs is relatively thorough.  The bounds in this paper are the first that I am aware of that calculate LCs for mDEQs, so there are no competing methods here.\n\n#### Points of clarification and questions\n- Is there any way to extend you analysis to other norms?  Given that Theorems 1 and 2 essentially follow from applications of Cauchy-Schwarz and the triangle inequality, it seems likely that more general results hold for other p-norms.  \n- As written, the proofs of Theorem 1 and Prop 2 rely on $\\sigma$ being the ReLU activation function.  However, the argument holds more generally for 1-Lipschitz activations.  The authors should clarify this, as it is confusing to appeal to properties of ReLU when an easy and more general result holds.\n- In the proof of Theorem 1, the authors gloss over some details that I feel should be more clearly explained.  For example, one must rely on _continuity_ of the $2$-norm $||\\cdot||_2$ to exchange the limit with the norm.  This is used but not stated, and may confuse some readers.\n- In the proof of Prop 2, an implicit assumption that $||T||_2 \\leq L[T]$, where $L[T]$ denotes the Lipschitz constant of the operator $T$ (with respect to the 2-norm, although the norm of choice is actually not explicitly specified when defining this notation).  However, I'm not sure whether this is actually true.  Given that $T$ is applied linearly in this case, it certainly seems to hold that $L[T] \\leq ||T||_2$, as $||Tx - T_y||_2 = ||T(x-y)||_2 \\leq ||T||_2 ||x-y||_2$.  However, if the other direction holds (i.e. $||T||_2 \\leq L[T]$), then given the previous sentence, it would follow that $||T||_2 = L[T]$, meaning that we could have an equality in that step of the proof rather than an inequality.  If I have misunderstood something here, clarifications by the author would be helpful.\n- In the proof of the generalization bound, it is assumed that all perturbations are generated by a normal distribution with mean 0.  I wonder if the authors can say anything about perhaps the more interesting case in which perturbations are _adversarially chosen_ rather than generated via a known distribution.  \n- How were the empirical estimates of the LCs computed for the mDEQ bounds in the experiments (e.g. Figs 1b and 2b).  It seems that to offer a fair comparison, empirical estimates should also be computed for feed-forward DNNs.\n- The authors mention that both mDEQs and feed-forward NNs are trained to obtain \"similar test accuracies.\"  These accuracies should be reported for further clarity.\n- It looks to me that Figure 2(a) is incorrectly transcribed from Fazlyab et al. (2019).  The authors should double check this.\n- What are the \"expected margin loss\" and \"empirical margin loss\"?  These are used in the PAC bound, but I don't see the definition of these losses.\n\n#### Final thoughts\nThe problem studied here is certainly interesting and has not been studied before in the literature.   The proofs rely on straightforward mechanisms, making them easy to follow, and the bounds do not suffer from exponential dependence on network depth, which has been an issue for previous bounds.  Further, the literature review is solid and empirically the bounds seem to be low relative corresponding DNNs.  However, I am not sure whether this problem will be of interest to many others in the community, given that it is not yet clear how broadly applicable mDEQs are.  Further, I am not sure there are enough results here to merit a full paper.  There are a number of ways that the authors could further their analysis within the scope of this topic, including extending the analysis to include other norms.  Indeed, one could imagine leveraging the analysis via alpha-averaged operators of Combettes et al. (2019) to potentially refine these bounds.  Such connections could be explored and exploited, and room could be made in the main text by pushing the proofs to the appendix.  Finally, some of the writing and proofs are a little bit imprecise (as I discuss above).  For these reasons, I am leaning toward suggesting rejection for this paper, as I believe that with further refinement the authors could submit a more complete version to a future conference.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "u4KTaCw8Da", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**after rebuttal**: The authors have addressed some of my major concerns in an updated version. for this reason I raise my score to a point where I can recommend acceptance. I now add after-rebuttal comments at the end of each item of my original review.\n\n## Summary\nThis work obtains upper bounds on the Lipschitz constant of a Monotone Deep Equilibrium Model (monotone DEQs) depending only on their strong monotonicity parameter $m$. This is in contrast to the naive bound for deep neural networks, which degrade with the depth. This also implies that controlling the smoothness of a monotone DEQ is possible just via the single parameter $m$, rather than controlling operator norms of each layer of a DNN. Additionaly, the authors derive generalization bounds  for such type of models, based on the deterministic PAC-bayes approach. This generalization bound reveal a dependency on the strong monotonicity parameter $m$, as well as the size of the hidden layer and appears to be the first result of such kind.\n\n## Pros:\n**1. Clarity: The main claims of the paper and their exposition are clearly stated**: The main contributions i.e., the upper bound on Lipschitz constant (Thm1) Upper bound on change after perturbation of the weights (Thm2) and Generalization bound (Thm3) draw from well developed techniques from monotone operator theory and statistical learning theory, using well known concepts which are accessible to researchers with basic knowledge in such areas.\n\n**2. Significance: It appears that DEQs have many advantages like reduce memory usage as well as good performance, hence it is of major importance to understand their smoothness properties and generalization guarantees, which this work contributes to**. Controlling the smoothness of traditional neural networks seems to suffer from a computation-quality tradeoff where simple bounds on the Lipschitz constant are easy to enforce, but are of dubious quality, while tight estimates are computationally inefficient. This work provides evidence that exerting such control on monotone DEQs is conceptually easier.\n\n**3. Originality: although the results mostly come from standard techniques, they are useful and novel, to my knowledge**. Previous work has mostly focused on computational aspects and variations, illustrating the feasibility of the approach.\n\n## Cons:\n**1. Originality/Significance: there is a major relevant work that is not cited nor compared to.** There is some work studying bounds on the Lipschitz constant  of implicit models, although more of the flavor of Neural ODEs https://arxiv.org/pdf/2004.13135.pdf \nthis work also appears to focus on the Lipschitz constant w.r.t. the parameters of the networks. I have to accept that the results there are somewhat convolved but I think this work should be cited and the differences between this work should be clarified\n\nThere is also the following work https://arxiv.org/abs/1908.06315v4 (note that the v4 is recent so it might not classify as prior work given that the deadline was beginning of october, but there is an initial version v1 dating from 2019). THis work also studies many aspects of implicit models. In particular it looks like section 4 in v4 deals with Lipschitz constants with respect to the L-infinity norm, which is related to the current work but it is not cited. Again I think this work should be cited and the differences with the submitted work should be clarified. **after rebuttal**: The authors have included such references and a discussion of the main differences (end of section 2), making clear how their approach differs.\n\n**2. Clarity: Some claims are misleading, regarding the Lipschitz constant**: It is claimed that theorem 1 shows that the Lipschitz constant does not depend on the matrix W. However the distinction should be made that the value obtained is an upper bound, so in fact it is possible that the minimal Lipschitz constant depends on W, but this particular upper bound obtained does not. This should make the claim more clear. **after rebuttal**: authors acknowledge this issue, for some reason I don't see that this is fixed in the new version, but could be fixed with minor rewriting in the final version. They should only write the conclusions for their **derived upper bound on the Lipschitz constant** rather than **THE Lipschitz constant** which is traditionally understood as being an infimum over the set of possible constants with the Lipschitz property.\n\n**3. Clarity: It looks like the proposition 2 is not used anywhere and does not correspond to any substantial claim and thus should be removed**. Unless I am missing something, I don't understand why is preposition 2 relevant or how it is used to support the important theorems. After checking, it is not used in the proofs of the theorems. Am I missing something? **after rebuttal** the authors do not seem to address this. I have now realized that Proposition 2 is used in the proof of theorem 2 but because such proof is found in the appendix, it seems that including an intermediate result in the main text is a poor stylistic choice. However this is not a major issue.\n\n**4. Significance: I think that the pros of the generalization bound (no explicit dependence of depth) is great, but its weaknessess are downplayed. In particular the generalization bound depends linearly in the width $h$**. Weaknessess should also be acknowledged. In contrast, as far as I know the DNN gen bounds like that of Bartlett et al. or Neyshabur et al. depend only logarithmically on the width.\n\n## Other comments:\n1. THeorem 3: typo, change m to M(set of size M)\n2. In the experiments in 5 it is weird to use the \"lower bound\" from Combettes et al. as it is not really a lower bound. I don't remember what is the motivation to use this but seems really confusing to use something which is not a lower bound and call it lower bound. A better lower bound could be sampling points and taking the maximum norm of the gradients as is done in other papers. Could this be changed/added easily? **after-rebuttal**: the authors have changed the lower bound to a true lower bound.\n\nAll in all, I think the missing references/discussion are a major point that has to be addressed. Hopefully this can be done in moderate space/time during rebuttal. In that case I would be willing to increase my score because my overall impression is positive.", "extra_scores": {}, "extra_text": {}}, {"review_id": "pEgEk7Sst3_", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work analyses the Lipschitz constant of monotone Deep Equlibrium models by exploiting the fixed point formulation of the input/output relation. They derive analytical upper bounds to the Lipschitz constants both with respect to input perturbations (L_in) as well as with respect to the network's weights perturbations (L_w). These bounds depend on the networks parameters and do not involve exponential constant, as opposed to Deep Neural Networks that suffer from their Lipschitz constant being exponential in the depth.\n\nIn particular, the derived upper bound for L_in oinly depends on the strong monotonicity parameter m and the input injection weight matrix U (and not on the hidden unit weight matrix W). These easily computable upper bounds allow for controlling the Lipschitz constants by carefully selecting the weight parametrization, and especially the strong monotonicity parameter m. This is useful for ensuring robustness of the model with respect to adversarial perturbations.\n\nIt is well known that bounds on L_w can be used to derive generalisation bound. By using their bound on L_w, the authors show a new generalisation bound for trained monDEQ models, with polynomial dependence on the network parameters.\n\n1. I am not so familiar with DEQ's but I imagine that the input injection weight matrix U is also learned during training? In this case, setting a value of m is not sufficient for controlling the L_in, since the upper bound also depends on \\|U\\|_2.\n\n2. In a similar way that the finite depth of a DNN limits its capacity, I believe that the strong monotonicity parameter of a DEQ also limits its capacity. For a fair comparison between the dependence of each model on depth/m, it would be nice to compare the dependence on depth/m on the capacity of respective models.\n\nFigure 4a: The value of the test error for the dashed red line (about 6.7) does not correspond to the value of the test error for monDEQ with m=20 as shown in Figure 4b (about 7.1)", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZJHYsn5d49s", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider the problem of estimating the Lipschitz constant of a specific type of network known as a Monotone Deep Equilibrium Model (monDEQ). These models are a recursive model designed such that the recurrence equations converge to a fixed point. Previous approaches to bounding the Lipschitz condition work on fixed depth DNNs and would not work in this case, as monDEQs are essentially infinite length. The authors develop an approach to bound the Lipschitz constant on monDEQs, both when we consider the model a function of the input and a function of the variables.  They then use their bounds to establish generalization results for monDEQs. Finally they use their bounds to experimentally compare monDEQs to DNNs in terms of their Lipschitz constants.\n\nWhile I think the results in this paper are interesting, I think that they are somewhat incremental. The approaches used are fairly standard techniques. Additionally, the ML field is not yet broadly interested in monDEQs. The authors argue that monDEQs are powerful due to their lower Lipschitz constants compared to DNNs which still achieving good statistical results. They can strengthen the paper by explicitly demonstrating that this is indeed true, say by training networks with good statistical performance compared to DNNs that are more resistant to adversarial attacks.\n\nThe theory sections are well written. I think adding more details to the captions can improve the clarity of the experimental section.\n\nThe authors write \"We note that the models obtain similar test accuracy to the DNNs.\" Can we get a more quantitative comparision of the statistical performance of monDEQs to DNNs?\n\n\"we aim to analyze the vacuousness of the derived generalization bound\" -> Can you clarify this statement? What is the vacuousness of the derived generalization bound?\n\nOverall, while I feel the paper is interesting, I feel it needs more impact before it is ready for acceptance. Further justifying the user of monDEQs based on their Lipschitz properties can increase the impact of the paper.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is interested in the Lipschitz constant estimation of deep equilibrium models. The estimation of this constant provides us the ability to certify classification decisions and understand robustness as well as has important bearings on the generalization ability of a neural network.  Overall a solid theoretical contribution with rigorous theory in a well-written paper.  
Decision: Accept (Poster)