Certified Robustness for Deep Equilibrium Models via Interval Bound Propagation
Authors: Colin Wei
J Zico Kolter
Venue: ICLR 2022 Poster (2022)
Keywords: deep equilibrium models
certified robustness
interval bound propagation

Abstract: Deep equilibrium layers (DEQs) have demonstrated promising performance and are competitive with standard explicit models on many benchmarks. However, little is known about certifying robustness for these models. Inspired by interval bound propagation (IBP), we propose the IBP-MonDEQ layer, a DEQ layer whose robustness can be verified by computing upper and lower interval bounds on the output. Our key insights are that these interval bounds can be obtained as the fixed-point solution to an IBP-inspired equilibrium equation, and furthermore, that this solution always exists and is unique when the layer obeys a certain parameterization. This fixed point can be interpreted as the result of applying IBP to an infinitely deep, weight-tied neural network, which may be of independent interest, as IBP bounds are typically unstable for deeper networks. Our empirical comparison reveals that models with IBP-MonDEQ layers can achieve comparable $\ell_{\infty}$ certified robustness to similarly-sized fully explicit networks.

Published as a conference paper at ICLR 2022
CERTIFIED ROBUSTNESS FOR DEEP EQUILIBRIUM MODELS VIA INTERVAL BOUND PROPAGATION
Colin Wei
J. Zico Kolter
Stanford University col inwn @nw.e@@ttaffordeede
CMU and Bosch Center for Al zko 1 terêcs cmu. edu
ABSTRACT
Deep equilibrium layers (DEQs) have demonstrated promising performance and are competitive with standard explicit models on many benchmarks. However, little is known about certifying robustness for these models. Inspired by inter- val bound propagation (IBP), we propose the IBP-MonDEQ layer, a DEQ layer whose robustness can be verified by computing upper and lower interval bounds on the output. Our key insights are that these interval bounds can be obtained as the fixed-point solution to iBP-inspired equilibrium equation, and furthermore, that this solution always exists and is unique when the layer obeys a certain param- eterization. This fixed point can be interpreted as the result of applying IBP an infinitely deep, weight-tied neural network, which may be of independent interest, as IBP bounds are typically unstable for deeper networks. Our empirical compar- ison reveals that models with IBP-MonDEQ layers can achieve comparable too certified robustness to similarly- sized fully explicit networks
INTRODUCTION
recent development in neural network design has been the introduction of implicit layers (Amos & [olter| [017]] Chen et al. [2018] AAgrawal et al.] 2019 Bai et al. 2019 2020 El Ghaoui et al. [022]] where the output is defined implicity as the solution to certain sets of conditions, rather than ex- plicitly, via closed-form functions. These layers are promising alternatives to standard explicit deep learning layers and have demonstrated improved expressivity and inductive biases in variety of set- tings. for example, processing time series (Rubanova et al. 2019), generative modeling (Grathwohl ct al. 2018), solving logical reasoning tasks (Wang et al. 2019), solving two player games (Ling al. 2018), and many others. One particularly promising class of implicit layers is deep equilib- rium layers (DEQs) (Bai et al.] 2019), which define the output as the solution to an input-dependent fixed point equation. DDFQ-based models have matched or outperformed traditional explicit models even in commonly benchmarked settings (Bai et al. 2019 2020).
Though recent empirical successes of DEQs have been promising, their implicit nature and inherent mathematical complexity also give rise to basic concerns. In order for DEQs to realize their promise, these concerns should ideally be mitigated or resolved. For example, one major issue with DEQs is well-posedness a solution to the fixed point equation defining the layer might not exist. On the other hand, explicit layers always have well-defined outputs. recent line of work has focused on addressing this important concern (Winston & Kolter 2020 Revay et al. 2020
Xie et al.) 2021).
This paper tackles a less- studied, but also important, question for DEQs: certified adversarial ro- bustness. Because robustness is basic concern for safe deployment of deep models (Szegedy al.) 2013 Goodfellow et al., 2014), for explicit models there a large literature dedicated to certifying robustness, guaranteeing correctness of the predictions even when the input is subject to imper- ceptible adversarial perturbations (see e.g. (Raghunathan et al. [2088]] Wong & Kolter 20188] Gowal ct al. 2018 Dvijotham al.) Xiao et al. 2018 Cohen et al. 2019)). Many certified robustness meth- ods require opening up the black box of the model and therefore only work for explicit models. is unclear how to certify robustness of DEQs, which only defined implicitly.
Coode available here: http://htttb...coocccc////o/oo//

---

In summary, contributions are as follows: 1) ing the BBDD,, a class of DEQs with a guaranteed unique fixed point with provable inter- val bounds on the fixed point value. 2) The proposed IBP-MonDEOS form expressive class of Published as a conference paper at ICLR 2022
Interval bounds on V
Interval bounds on z*
v(x)
oW2* +)
z xx))
(W) (W)_ (W) (W),
+x)
v(x)
Solve for equilibrium
2x {2 (x + 6) |1011 S e]
y(x)
True perturbed region: [v(x + 5) |1
Figure 1: Illustration of method. We propose an equilibrium equation which takes as input v(x) and interval bounds v(x),, g(æ), and solves jointly for 2", the standard output of the DEQ, well as 2", 2 interval upper and lower bounds on 2".
The certified robustness method motivating this work is interval bound propagation (IBP) (Mirman et al. 2018 Gowal et al., 2018), simple and cheap way to certify robustness to lx perturbations. IBP computes layerwise upper and lower bounds for each coordinate of the adversarially perturbed hidden layers. These bounds follow basic rules of interval arithmetic and simple to obtain in closed form as explicit functions of a layer's weights. However, it is unclear how to apply this idea when layers only defined implicitly.
In this paper, we propose the MonDEQ, deep equilibrium layer which is certifiably robust to lx perturbations. Motivated by principles from IBP, define the IBP-Monn Mo-MMoDEE output as the solution of an augmented fixed-point equation involving 3 quantities: the unperturhed output of the layer and upper and lower interval bounds this output. As with IBP for explicit models, interval bounds on the IBP-MonDEQ output are computed during the forward pass of the network and can be composed with other layers to certify robustness of the entire model.
More concretely, we build upon monotone operator deep equilibrium (MonDEQ) layers proposed by Winston Kolter (2020), which take the preceding layer v(x)) as imput and outputs the solution 2", which is guaranteed existence and uniqueness, to the following fixedpooint equation:
o(W>* v(x))
(1.1)
We propose an IBP-inspired fixed-point equation
([w)=
(W)
(W) (W)+
F(z) [(x))
(1.2)
which maps upper and lower interval bounds V. y on 2* and 2", which provide upper and lower interval bounds on =² Figure depicts this process. The augmented fixed-point equation is derived by unrolling the computation of into infinitely deep, explicit network and applying IBP the forward pass of this network.
One immediate challenge is that it is not clear that fixed point solution to should always exist, especially given its interpretation as the result of applying IBP to an infinitely deep network. Indeed, a major drawback of IBP that its performance degrades with deeper networks, observed by [Shi et al. (2021) and also shown in Figure ( (left). One potential explanation for this failure is that IBP bounds tend to be unstable with depth and can diverge for deeper models (Figure 2 right).
On the other hand, we show that a unique fixed-point solution to (1.2) is guaranteed to exist when W admits simple unconstrained parameterization which easy to enforce throughout training. Thus, our results pinpoint class of infinitely deep networks for which IBP bounds are provably stable, which may be of independent interest.
We experimentally compare the proposed IBP-MonDEQ layer against IBP for standard explicit models. We consider common certified robustness benchmark settings and evaluate architectures of various sizes. Our results show that models with IBP-MonDEO layers can achieve comparable fx certified robustness relative to fully explicit models with similar parameter counts.
We study the certified robustness of DEQs, propos-
2

---

Published as a conference paper at ICLR 2022
infinitely-deep models for which IBP is provably stable, which may be of independent interest. 3) Our experiments demonstrate that IBP-MonDEQ layers are competitive with standard explicit layers for to certified robustness.
2 BACKGROUND
bg certified robustness. Consider a K- K-way classification task with neural network classifier F Rd RRK For given input x with true label y, the classifier is adversarially robust to &ao. perturbations with radius c if
min de
F(x + 6)y F(x F(x+ O)y 0 VY #
(2.1)
Safety- critical applications require certifying the robustness of F, i.e. verifying whether 2.1 holds. Directly optimizing over ò to verify (2.1) is challenging because the objective is non-convex (Madry jet al., 2017). Thus, recent work on certified robustness has focused on verifying (2.I) via compu- lationally tractable relaxations (Raghunathan al.) 2018a Wong & Kolter 2018 Dvijotham et al.)
Raghunathan et al. 2018b Weng et al. 2018 Gowal et al. 2018 Salman et al. 2019b)..
Interval bound propagation. IBP is computationally efficient method for certifying ly robust- ness neural networks (Mirman et al. 2018 Gowal et al. 2018). proposes to verify (2.I) via (potentially loose) upper bound F I b)y F(x + J)y which is obtained by computing propagating upper and lower bounds on each layer through the forward pass the network.
More precisely, let z(x) compute some hidden layer of the network input We say that 2(x,e) 2(x, c) are interval bounds on z at x for perturbation if the following holds for all coordinates
(2(I, <
min (z(æ + 8)), < 6 Ee
max AER<:lol
(=(x + 6)); < ()(x,)));
(2.2)
We omit dependencies bounds Σs and Σι are obtained inductively via simple interval arithmetic. For an affine layer z W + b and pre-computed bounds 2k-1- 1 IBP computes Tye Eµ follows:
and when clear from context. Letting denote the layer index, the
Zk
(W)_ (W)+
(W) (W)
2k 26-1
6
(2.3)
Here (W)+ & max(W, 0} and (W)- min(W, 0} denote the matrix W with negative or positive values truncated to O. For simplicity we focus on ReLU networks, with denoting the ReLU activation. For layers 2 a(2x1) which apply coordinate-wiss wise, IBP computes 2 o (1 and Σn o ( Initial bounds are obtained via (Zo( c). (0 c)) (x cl, el), where denotes the all I's vector.
The interval bounds are propagated through all layers of the network by following the simple rules above. To certify 22.1 for the whole network, one straightforward method to confirm that the margins of the interval bounds on the logits are positive: (F(x,, <)), (F(zz e)) > Vy' of y- One important note about IBP is that the bounds should optimized during training order for the method to provide nontrivial robustness guarantees.
Monotone operator equilibrium networks. Proposed by Winston & Kolter (2020), MonDEQs are class of DEQs inspired by monotone operator theory (Ryu & Boyd 2016) which have guaranteed unique fixed point solutions to the following equilibrium equation:
= oW>= + v(x))
(2.4)
Let Ixxh denote the identity matrix on h dimensions, with the subscript omitted when clear. A unique fixed-pont point solution is guaranteed for 2.4 for the following class W:
Proposition 2.1 (Winsto & Kolter 2020 Suppose W R satisfies that I - W is positive definite (PD), i.e. W > O. Then Vu(x) RR,, a solution z" to (.4) exists and is unique.
Here 0 denotes the all 0's matrix and A 0 indicates that Au 0 for all nonzero (note that A does not need to be symmetric). Winston & Kolter 2020) guarantee that I- W is PD using the following unconstrained parameterization, which is enforced throughout training: W (1 - m - AAT + B BT, for positive hyperparameter m. Section 3.1 builds on these results to derive certified upper and lower bounds 2'.
3

---

Published as a conference paper at ICLR 2022
54
IBP-trained
10c
MonDEQ IBP.MonDFQ
Clean-triined
NVg. Upper Lowwer Bound
52
10a
50
10
10a
10c
80
# Linear Layers
Iteration
Figure 2: Difficulties of IRP with depth. Left: error v.s. depth for IBP and standard train- ing. We train deeper models with IBP on CIFARIO with 255 We find that final certified error increases with the depth of the model. On the other hand, depth does not hurt when mod- els are trained and evaluated on standard clean error. This suggests that IBP performs particularly poorly with depth. Right: convergence of interval bounds for standard MonDEQs and our IBP-MonDEQ. We plot the the average over coordinates of 2g 2g.- where εk. 2g denote bounds computed by the k-th iteration of the equilibrium solver for (3.3). This quantity blows up for the standard MonDEQ (Winston Kolter 2020) as the solver fails to find a fixed point. contrast,
solver converges with our IBP-MonDEQ parameterization. Implementation details are in Section
CERTIFYING ROBUSTNESS OF MONDEQS USING IBP
In this section, we describe our core methodology for developing certifiably robust MonDEQ layers. We will first demonstrate how obtain interval bounds for MonDEQ layers by computing the solution to a certain IBP-inspired fixed point equation (3.3). In Section 3.1 we characterize new
parameterization for W for which unique fixed point exists. In Section 3.3 provide theoretical justification that the resulting MP-MDoDD layers remain expressive.
Our aim is to derive upper and lower interval bounds 2 and 2 for the fixed point solution to 2..4 common interpretation of DEQs is that they compute an infinitely deep, unrolled explicit net- work (Bai al. 2019 Winston & Kolter 2020):
2 C W
(3.1)
with lime--o 24 This equivalence is informal and mainly serves to motivate our derivation of the FFn Given interval bounds and on e satisfying y & v & T, where the inequalities hold elementwise, also follow IBP and (2.3) to iteratively obtain interval bounds on 23:
([()==
(W)
2
U
(W)+
+
(3.2)
Just as we took limg Zk, we consider lim Zg. 2j.- motivating another fixed-point problem:
((w)
(W) (W) 2"
2-
T
(3.3)
U
As shown in Figure I this IBP- inspired fixed point equation essentially maps the region {u/ 0 $ of & J) to the region {2- x 2n & z" & ²*) where inequalities are coordinate-wist If they exist, the fixed points z and will indeed lead valid interval bounds (as defined in 2.2 on Proposition 3.2 states this observation formally.
3.1 FIXED POINTS OF THE IBP-INSPIRED EQUILIBRIUM EQUATION
Following the derivation above, the IBP fixed point equation 3.3 can be interpreted as the result of applying IBP to infinitely deep, weight-tied neural network. However, IBP is notoriously unstable for deeper networks, so unclear whether a fixed point solution to (3.3) always exists. This section characterizes class of W for which (3.3) does have fixed point (Theorem 3.
4

---

Published as a conference paper at ICLR 2022
Figure (left) demonstrates that the performance of IBP degrades for deep networks. We add linear layers to the architecture proposed by /ooal et al. (0018) for IBP. which is a wide but shallow network with 6 linear layers, and find that the final error certified by IBP increases with the depth of the model. This illustrates the challenge of getting IBP to work for deep models.
The challenges associated with depth also apply to the class of MonDEQs proposed by (Winston
& Kolter 2020). We will define W (W)++ + (W)-1
2h to be the linear transformation (W)- (W)+ E R 2h
for IBP. Recall that Proposition
demonstrates existence and uniqueness of a fixed point solution to 2.4) when I - W is PD, but this does not guarantee the positive-definitnnss of I2hx24 - W, which would be sufficient for fixed point solution to (3.3) Indeed, Figure 2 (right) shows that the fixed-point solver fails to solve (3.3) for the standard MonDEQ, as the interval bounds diverge.
Intuitively, this failure occurs because the spectral radius of W is always larger than that of W (see Lemma 3.4). so repeated application of (3.2) diverges. Thus, further restrictions on W are required.
The following theorem exactly characterizes the class of W for which X2 - W is PD. For these W, existence and uniqueness of fixed points (24) and (33) is guaranteed to hold.
Theorem 3.1. In the setting above, x2hx 2h W if and only W is parameterized as follows:
= D 1/2 MD-1/2 1/2
(3.4)
where D,M E Rixh and D is a diagonal matrix satisfying D > (IM 1)s where [M] Rixh takes the entry-wise absolute value of M. Thus, for W parameterized by (3.4) unique solutions =", ,"" to the standard (2.4) and IBP (36) equilibrium equations exist V c, u R
2
Theorem 3.1 iis our main theoretical result, and proposes a simple class of W for which the IBP equi- librium equation has a guaranteed unique fixed point. In this characterization, M is an unconstrained matrix (and is also treated as an unconstrained parameter in our implementation, as described in Sec- tion 4 In Section B.3] we theoretically analyze the expressivity of the induced class of DEQ layers. The proof of Theorem is discussed in Section 3.2
Next, it remains to check that 2* and 2 do provide valid interval bounds =", the derivation in Section 3 was only heuristic. The following proposition makes this derivation rigorous.
Proposition 3.2. In the setting above, suppose W satisfies Iahx24 W > O, so that unique fixed- point solutions 2²' 2n' to (3.3) always exist. Define the fixed-point solution 2" (v) as a function of as follows: 2" 2v) = a(W 2- (1) + v). Then for any v & E and all i, it must hold that
min (u)) EEPEB
max 2EUE0
(z"())) < (z*);
(3.5)
We present the proof in Section A Combining Theorem 3.1 and Proposition 3.2 we finally obtain the IBP-MonDEQ layer, which simultaneously solves two equilbrium equations to output both =* and valid upper and lower interval bounds 2*, 2* on 2":
(W> 30 + v(x))
= - (M =]
8(zz c) u(z,
(3.6)
+
To include an Mon-Mo layer in a deeper model, we set e(x) be the output of the preceding layer, and choose ,(2, e), v(2. e) to be upper and lower interval bounds on v(z). The interval bounds 2 and =" can propagated through the rest of the network following the standard IBP methods.
LBEN parameterization. We can relax the restrictions imposed by the parameterization (3.4) by leveraging the Lipschitz- equilibrium network (LBEN) parameterization proposed by Revay et al. 2020). Revay et al. (2020) show that a guaranteed unique fixed point of (2.4) still exists if the PD condition on I 7-10 W is relaxed to require A - -A > 0 for A E D the set of positive diagonal matrices. The following result exactly characterizes W such that 3F ho A > which is also sufficient for guaranteeing a unique fixed point solution to (.3).
Theorem 3.3. For weight matrix W, 3A E Du such that A A W 0 if and only W can be parameterized as follows:
W TD 1/2 MD 1/2
(3.7)
5

---

Published as a conference paper at ICLR 2022
for some T, D T with D satisfying D1.
(M1+ M
2
For W parameterized by (3.7) we have the following immediate consequences: 1) unique solutions 2", , to the equilbrium equations (3.6) exist for all 0,0,2 R.,, and 2) 2 ,, are upper and lower interval bounds on z" in the sense of Proposition
3.2
The proof provided in Section Al Note that Theorem 3.3 improves the expressivity of the IBP- MonDEQ layer because the class of W proposed in Theorem 3.3 contains that of Theorem 3.1 In Section 3.3 we show that, perhaps surprisingly, this more flexible parameterization allows IBP- MonDEQ layers to express all explicit networks. Section ddemonstrates that this parameterization can also lead to empirical improvements.
3.2 PROOF OF THEOREM 3.1
We sketch the proof of Theorem 3.1 To prove 12hx21 W require simple way to reason about the spectrum of W. The following lemma formalizes a connection between eigenvalues of W+WT and WW++WW
Lemma 3.4. All eigenvalues of W+FT are either eigenvalues of W W+WT 2
[W++WW1
As direct
2
consequence, the following equivalence holds:
T2hx2h
W
Taxh W
(3.8)
Note that the condition that Taxh W is is stricter requirement than requiring positive-
definiteness of Ta W. it always holds that Amax W
+II Amax (W where Amax
denotes the largest eigenvalue. Thus, in order for both (2.4) and (..) to have unique fixed points,
suffices have AA [W] O. The proof of Lemma 1.4] is completed in Section A and relies
the following basic fact about structured block matrices.
Claim 3.5. Let M 2h be any matrix of the form M
where A, B Bhxh, Then A
B B.
all eigenvalues of M are either eigenvalues of A + B or A
Following Lemma 3.4
we now complete the proof of Theorem 3.1 by analyzing Inxh - W/].
Proof of Theorem 3.1 By Lemma 3.4 is equivalent to characterize when Taxh [ 0. We We write
first show that 3.4 implies
W + IWIT
M + |M
--
D-12
D 1/2
D
DD D-1/22 1/2
(3.9)
By the lower bound on entries D, the matrix D dominant (SDD), and thus PD. Thus, we obtain |W++WW1 > 0, so W > 0.
|M 2
is symmetric and strictly diagonally
For the reverse direction, we appeal the theory of M-matrices (Plemmons) 1977). We note that nonsingular M-matrix, i.e., a matrix with negative off-diagonal entries whose eigenvalues have positive real parts. By an equivalent characterization of M-matrices, there exists diagonal matrix E E D+ such that E(I [W[+|W]" ) is SDD. Rearranging gives |W| I E E-'AE-1- S, where A is symmetric and SDD, and S is skew-symmetric (S =)..
2
Now we choose M satisfying |M] = E² A ESE and D = E so that W has the pa- rameterization W D 1-2 DD - 1/2, To check that Dí,5 (IMI))++M we note that
2
(IM ((F2 A)1); Et,- A Σett Ai, EZ,,, where we use the fact that A > Ejerl | because A is SDD. Plugging Di, = ET,, gives the desired inequality. O
3.3 EXPRESSIVITY OF THE IBP-MONDEQ
Guaranteeing that 3.3) has a fixed point requires placing further restrictions on W on top those already proposed for MonDEQs (Winston & Kolter 2020). This section examines the expressivity

---

Published as a conference paper at ICLR 2022
of the resulting IBP-MonDEQ parameterization. To sanity check that parameterization is not too restrictive, we first contrast against normalization techniques for controlling Lipschitz constants in neural networks. Next, we demonstrate that with the relaxed parameterization of Theorem 3.3 the IBP-MonDEQ is able to express traditional explicit feedforward networks.
Operator norm of W. We first investigate the operator norm of W. A number of papers constrain the weight matrices so that their operator norms are bounded by 1, which prevents blowup of the naive upper bound [[allopp
the Lipschitz constant of the whole network (Cisse et al. 2017 Miyato et al. 2018 Farnia et al. 2018: Trockman & Kolter 202T). This approach has applica- tions in robustness, but there are also concerns that constraining the operator norms to 1 severely harms expressivity (Huster et al., 20188 Anil et al. 2019). We verify that the parameterization of Theorem 3.1 does not imply the stringent constraint [ op & 1.
Example 3.6.
The following choice of W satisfies the parameterization (.4 with [
1.9:
0
1.9
W-
We set M W and D 12x2, W D-1 1/2 as in 3.4
0.05
0
1..mplee3.6mma be surprising given superficial similarities between (3.4) and the following param- eterization, which does imply |Wllop < 1: W D-1M, where D satisfies Di,: > (IM[ The parameterization in Theorem 3.1 avoids this constraint because the requirement is instead
D2,: [[M]]+|M]] 1), so mass in M can be asymmetrically distributed between the upper and
2 lower triangular halves, as in Example 3.6
Expressing explicit feedforward networks. The following result states that using the parameteri- zation in Theorem 3.3 single IBP-MonDEQ layer can express all explicit feedforward networks. Proposition 3.7. Consider explicit neural net embedding functions of the following form:
2ι(x) o(ALo(AL-11--O(A))) 0(A1))....)
(3.10)
where Rd Rh and A E Ri v1 Ei L. There is a DEQ layer 2" : R.th oututting 2" xx) = o oW22 (x) + Br), where W, B E I.h.I such that W obeys the parameterization of Theorem and the last ls coordinates of =" satisfy
(z (=(x))) =1(x) Vx E Rd
Proposition 3.7 states that the IBP-MonDEQ parameterized in Theorem 3.3 is at least as powerful as standard explicit networks, and is somewhat surprising given that the parameterizations (3.4) and (3.7) may appear restrictive. The proof, provided in Section leverages the fact that provides flexibility in scaling the weights, essentially allowing us to cancel out the normalization matrix D.
4 EXPERIMENTS
In this section, we empirically compare models with IBP-MonDEQ layers against fully explicit mod- els. Our results show that MBD-MonDEQ models can achieve comparable performance on common certified robustness benchmarks relative to IBP with standard explicit models.
Explicit models. Table [ illustrates the explicit architectures: smaller 3LAYER model with convolutional layers and T28 output channels, and a larger 7LAYER model. The 7LAYER model is a wide and shallow network with million parameters proposed by Gowal et al. (2018) for IBP.
IBP-MonDEQ models. As shown in Table we consider replacing convolutional layer in fully- explicit model with an IBP-MonDEQ layer where W' computes an equivalently-sized convolutional transformation. This leads to DEQ-3 and DEQ-7 models with equivalent parameter counts as their fully-explicit counterparts. We use + +LBEN to indicate that the IBP-MonDEQ layer uses the LBEN parameterization in Theorem 3.3 To solve for the fixed points, use the bewwardbbckwward
algorithm with Anderson acceleration Walker & Ni.
imp 2020p.
To guarantee that 3.6 has unique fixed point, enforce either whether we use the LBEN parameterization) for the IBP-MonDEQ weight W. To enforce (3.4). we
3.7 (depending
set W DD where M is the only trainable parameter and D diag [[
2(1 ((1mm)
fixed function of M, where diag(-) maps vector diagonal matrix. Here m (0, 1) is
7

---

Published as a conference paper at ICLR 2022
Illustration of architectures. CoNv-h-kxk-s denotes a convolution with h output chan- nels, kok kernel size, and stride. We consider DEQ models where a CONV layer is replaced by ---kos layer with an equivalently-sizz convolutional operation.
Table 1:
3LAYER
DEQ-3
7LAYER
DEQ-7
CoNV-64-3x3-1
CoNv-64-3x3-
CONV-64-3x3-1
IBPMoN-64-3x3-1
CONV-1 12NV-11--33-1 CONV-128-3x34
CONV-128-3x3:3
CONV-128-3x.0
1BPM0N-128-3<3-1
CoNV-128-3x33 128-3x3-1
128-3338-
FC-10
FC-10
CONv- 1283-12--333-1
CONV- 128-3331
FC-512
FC-512
FC-10
Fc-10
Table 2: Certified robustness results. We display the average certified error and standard (clean) enror for explicit and BBP-MonDEQ architectures (lower is better). We compute the mean errors over 3 independent training runs, with standard deviations in parentheses. Our results show that the IBP- MonDEQ models can achieve smaller certifiably robust error than their fully explicit counterparts.
MNIST
CIFARIO
6 0.1 c 0.2
6 0.3
6 0.4
255
6 255
3LAYER
4.19 (0.27) 9.16 (0.17) 19.14 (0.39) 28.98 (0.41)
53.01 (0.45) 72.38 (0.35)
Certified eтror
DEQ-3
3.18 (0.09) 6.56 (0.11) 12.72 (0.49) 19.80 (0.66)
53.9 (0.37) 71.97 (0.31)
(+LBEN)
3.15 (0.07) 6.64 (0.13) 11.96 (0.38)
19.11 (0.32)
54.18 (0.12) 72.33 (0.59)
Standard
3[AAERR
2.10 (0.06) 3.33 (0.21) 6.54 (0.09) 6.49 (0.12)
39.22 (0.16) 58.66 (0.15)
(Clean) error
DEQ-3
1.62 (0.03) 2.62 (0.11) 4.71 (0.27)
4.44 (0.20)
40.25 (0.39) 59.35 (0.99)
(+LBEN)
1.60 (0.04) 2.49 (0.12) 4.54 (0.12)
4.58 (0.31)
40.77 (0.29) 59.41 (0.29)
7LAYER
2.61 (0.11) 4.21 (0.26) 7.39 (0.09) 12.41 (0.27)
48.46 (0.31) 66.95 (0.35)
Certified eтror
DEQ-7
2.58 (0.06) 4.24 (0.07) 6.80 (0.04) 12.32 (0.37)
48.29 (0.28) 66.87 (0.34)
(+LBEN)
2.51 (0.03) 4.15 (0.04) 6.92 (0.14) 12.25 (0.03)
48.23 (0.34) 67.2 (0.37)
Standard
7LAYER
0.89 (0.02) 1.27 (0.04) 2.25 (0.19) 2.29 (0.15)
32.82 (0.33) 52.84 (1.30)
(clean) DEQ-7
0.79 (0.06) 1.16 (0.03) 2.13 (0.05) 2.13 (0.07)
33.04 (0.49) 53.12 (0.88)
eтror
(+LBEN)
0.80 (0.04) 1.13 (0.02) 2.04 (0.05) 2.10 (0.07)
33.08 (0.48) 53.42 (0.58)
tunable hyperparameter governing tradeoff between expressivity and convergence rate: smaller m leads to more expressivity but also slower convergence of the equilbrium solvers. For the LBEN parameterization
(3.7). we parameterize the additional diagonal scaling matrix T E D4*A by
diag 2-1 sigmoid (3) + +) where > 1 is scalar hyperparameter, and / E R is a trainable
parameter / E R. This parameterization enforces that the condition number of T is bounded by
4.1 CERTIFIED ROBUSTNESS RESULTS
Tables 2 shows certified and standard classification errors of 3 and 7 layer models trained with IBP on the MNIST and CIFARIO datasets for various values of 6. For most settings, IBP-MonDEQ models able to achieve lower mean certified errors than their fully explicit counterparts.
The improvement is particularly striking in the case of layer models on MNIST, where IBP- MonDEQ models perform much better, e.g. 9.87% better on MNIST for e 0.4. We also find that using the more relaxed LBEN parameterization (Theorem 3.3) generally leads to better performance on MNIST, but the reverse trend may hold for CIFAR10. We hypothesize that the LBEN parameter- ization may lead to optimization difficulties in the IBP-MonDEQ layer. Investigating and improving the optimization of IBP-MonDEO layers is an interesting direction for future work.
8

---

Published as a conference paper at ICLR 2022
Implementation details. We train using IBP with the Adam optimizer (Kingma & Ba 2014) with a learning rate of 5e-4, and report errors at the last epoch of training averaged over 3 runs. We use a smooth warmup schedule for (Xu et al. 2020; [Shi et al. 202I). interpolating between 0 and
< Crmin, a target training e lower bounded by Grest-
Following Shi et al. 22021) we use batch normalization (BN) after every linear layer besides the last Fc- 10 layer. There is no BN within an IBP-MonDEQ layer, but BN is applied to outputs of the IBP-MonDEQ layers. For 3 layer models, we insert a 4x4 pooling layer before the FC-10 layer. Additional details are in Section
5 ADDITIONAL RELATED WORKS
Implicit layers. Various fundamental properties of DEQs have been investigated in the literature, most notably convergence and existence of fixed point (Winston & Kolter 2020; Revay et al.
2020 Bai et al. ).21). Bai et al. (2021) propose empirical Jacobian regularization techniques for speeding up equilibrium solving in DEQs. Another studied property of DEQs is their Lipschitz- ness: Revay et al. (2020) and Pabbaraju et al. (2020) derive bounds on the Lipschitz constants of MonDEQs which are applicable in certified robustness settings. However, because the Lipschitz constants are tailored to the & norm, these works only consider & bounded adversaries. Chen jet al. (2021) propose polynomial optimization programs for certifying robustness of MonDEQs, but their methods only succeed for & perturbations and do not work empirically against Eo adver- saries. Kawaguchi (2021) theoretically analyze optimization of equilibrium models.
Other prominent classes of implicit models include neural ODEs (Chen al. 2018 Dupont al., 2019 Li al. 2019: Finlay et al. 2020), and convex optimization layers (Amos et al. [217]] Amos & Kolter 2017: Agrawal al.) 2019). Neural ODE outputs are implicitly defined as the solution to some differential equation. Adversarial robustness is also an interesting topic of study for neural ODEs, which may be more robust than explicit models Yan et al. 2019), though the cause of this might be gradient obfuscation (Huang et al. 2020).
Certified robustness. A common technique in certified robustness is express a convex pro- gram which lower bounds the worst-case perturbed output of the network, either via semidefinite relaxations (Raghunathan et al., 2018a bb; or linear relaxations (Wong & Kolter 2018 Wong al.] 2018 Dvijotham et al.) /Zhan et al. 2018, Wang et al.] (018). One advantage of TBP compared to these approaches is its simplicity and efficiency, making it viable for training larger models (Gowal ct al. 2018). Zhang et al. (2019) propose CROWN-IBP, which combines IBP with linear relaxation methods during warmup training. Xu et al. (2020) extend this approach to general computation graphs. Shiphss.Shieee et al. (2021) propose methods for speeding up optimization of IBP-trained networks.
Another well-studied certified robustness approach is randomized smoothing (Li et al., 2018 Cohen al. 2019 Lecuyer et al.) 2019; Salman al., 2019a Yang al., 2020), which in theory pro- duce probabilistic certificates of robustness for generic models (including, in theory, DEQs). How- ever, these certificates are random,
deterministic, and have some error probability. In addition, randomized smoothing has theoretical limitations for certifying Lo robustness for high-dimensional
data (Blum et al. 2020 Kumar al. 2020 Yang et al. 2020).
6 CONCLUSION
This work aims to certify robustness of DEQ models. We propose the IBP-MonDEQ layer, a DEQ layer which solves two equilibrium equations: one for the unperturbed fixed-point output, and one for upper and lower interval bounds on adversarially perturbed values the fixed point. Our math- ematical analysis reveals how to parameterize the IBP-MonDEQ so that existence and uniqueness of a fixed point is guaranteed. One interesting interpretation of these results is that they characterize class of infinitely deep, weight-tied neural nets for which IBP is stable. An interesting direction for future work is to explore whether other methods besides IBP for certifying robustness of explicit networks can also be adapted to work for DEQs.
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank Huan Zhang for helpful discussions and Alex Wang for helpful comments on a draft of this work. CW was supported by NSF Graduate Research Fellowship. Portions of this work were supported by funds from Toyota Research Institute and the Bosch Center for AI.
ETHICS AND REPRODUCIBILITY STATEMENTS
We do not expect ethical concerns to arise from this research because DEQ methods are still ex- ploratory in nature, and the main impacts of this work are still mainly theoretical and algorithmic.
All proofs omitted from the main body of the paper are in Section A Additional implementation details are provided in Section B and code is available at the following link: https:: /tttps///itthb.
code code
REFERENCES
Deep implicit layers neural odes, deep equilibirum models, and beyond, 2020. URL http:
//implicit- tuut----raaattttta........
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. arXiv preprint arXiv:1910.12430. 2019.
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks.
In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Confer- ence on Machine Learning, pp. 146-155. PMLR, 2017.
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In Inter- national Conference Machine Learning, pp. 291-301 PMLR, 2019.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. arXiv:1909.013777 2019.
Deep equilibrium models. arXiv preprint
Shaojie Bai, Vladlen Koltun, and J Zico Kolter. Multiscale deep equilibrium models. arXiv preprint arXiv:2006.0866 08656, 2020.
Shaojie Bai, Vladlen Koltun, and J Zico Kolter. Stabilizing equilibrium models by jacobian regular- ization. arXiv preprint arXiv:2106. 14342, 2021.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might unable to certify Lo robustness for high nigh-dimensional images. J. Mach. Learn. Res., 21:211-1, 2020.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differ- ential equations. arXiv preprint arXiv: 2018
Tong Chen, Jean- Bernard Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic repre- sentation of monotone deep equilibrium models and applications to certification. arXiv preprint arXiv:2/066014553 2021.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854-863. PMIR, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019. arXiv preprint
Emilien Dupont, Amaud Doucet, and Yee Whye Teh. Augmented neural odes.
1904000804 2019.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks.
10

---

Published as a conference paper at ICLR 2022
Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai. Implicit deep learning. SIAM Journal on Mathematics of Data Science, 3(3):930-9553 2021.
Farzan Farnia, Jesse M Zhang, and David Tse. Generalizable adversarial training via spectral nor- malization. arXiv preprint urXiv:1811.0744 2018.
Chris Finlay, törn-Henrik Jacobsen, Levon Nurbekyan, and Adam Oberman. How to train your neural ode: the world of jacobian and kinetic regularization. In International Conference on Machine Learning, pp. 3154-3164. PMLR, 2020.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic. Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:/8/00 12715, 2018.
Will Grathwohl, Ricky TQ Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint arXiv: 2018.
Yifei Huang, Yaodong Yu, Hongyang Zhang, Yi Ma, and Yuan Yao. Adversarial robustness of sta- bilized neuralodes might be from obfuscated gradients. arXiv preprint arXiv:2009. 13145,, 2020.
Todd Huster, Cho-Yo Yu Jason Chiang, and Ritu Chadha. Limitations of the lipschitz constant as a defense against adversarial examples. In Joint European Conference on Machine Learning and Knowledge Discovery in Databuses, pp. 16-29. Springer, 2018
Kenji Kawaguchi. On the theory of implicit deep learning: Global convergence with implicit layers. arXiv preprint arXiv:2102.07346 2021.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 14Xiv:1412.690 2014.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality randomized smoothing for certifiable robustness. In International Conference on Machine Learn- ing. pp.
PMLR, 2020.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. arXiv preprint arXiv: 03113, 2018.
Chun Kai Ling, Fei Fang, and J Zico Kolter. What game playing? end-to-end learning in normal and extensive form games. arXiv preprint arXiv: 000///050007777 2018.
Xuanqing Liu, Si Si, Qin Cao, Sanjiv Kumar, and Cho-Jui Hsieh. Neural sde: Stabilizing neural ode networks with stochastic noise. arXiv preprint arXiv:1906.02355 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.
Towards deep learning models resistant to adversarial attacks. arXiv preprint urXiv:1706.06000 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3578-3586. PMLR, 2018.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv: 2018.
Chirag Pabbaraju, Ezra Winston, and J Zico Kolter. Estimating lipschitz constants of monotone deep equilibrium models. In International Conference on Learning Representations, 2020.

---

Published as a conference paper at ICLR 2022
Robert J Plemmons. M-matrix characterizations. nonsingular m-matrices. Linear Algebra and its Applications, 18(2):175-188, 1977.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. arXiv preprint
2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying bustness to adversarial examples. arXiv preprint arXiv:/811.0005 2018b.
Max Revay, Ruigang Wang, and lan R Manchester. Lipschitz bounded equilibrium networks. arXiv preprint 2rX1v:2010.01732 2020.
Yulia Rubanova, Ricky TQ Chen, and David Duvenaud. Latent odes for ireeularly-samplle time series. arXiv preprint arXiv: 1:XXv:990700300) 2019.
Ernest K Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. Comput. Math, 15 (1):3-43, 2016.
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv: 04584, 2019a.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. convex relax- ation barrier to tight robustness verification of neural networks. arXiv preprint arXiv: 1xXiv:9902.08722, 2019b.
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Fast certified robust training with short warmup. arXiv preprint arXiv:2103.1721 2021.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Asher Trockman and Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. arXiv preprint arXiv 104.0716.. 2021.
Homer F Walker and Peng Ni. Anderson acceleration for fixed-poin iterations. SIAM Journal Numerical Analysis, 49(4): 2011.
Po-W Po-Wei Wang. Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and log- ical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, pp. 6545-6554. PMLR, 2019.
Shiqi Wang, Kexin Pei, Justin Whitehouse. Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. arXiv preprint 1809::8800000 2018
Lily Weng. Huan Zhang, Hongge Chen. Zhao Song. Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5276-5285. PMLR, 2018.
Ezra Winston and Zico Kolter. Monotone operator equilibrium networks. Advances in Neural Information Processing Systems, 33:10718-10722 2020.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295 PMLR, 2018.
Eric Wong, Frank R Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. arXiv preprint arXiv: 12514, 2018.
Kai Y Xiao, Vincent Tjeng. Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint 2018.
Xingyu Xic, Qiuhao Wang, Zenan Ling, Xia Li, Yisen Wang, Guangcan Liu, and Zhouchen Lin. Optimization induced equilibrium networks. arXiy preprint arXiv:2105. 13228, 2021.
12

---

Published as a conference paper at ICLR 2022
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang. Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 33, 2020.
Hanshu Yan, Jiawei Du, Vincent YF Tan, and Jiashi Feng. On robustness of neural ordinary differ- 2019.
ential equations. arXiv preprini
Greg Yang. Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. International Conference on Machine Learning, pp. 10693- 10705, PMLR, 2020.
Huan Zhang, T'ui-Wei Weng. Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. arXiv preprint arXiv: 18/ 1.00866, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li. Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint arXiv: /tt:::99960631/11 2019.
13

---

Published as a conference paper at ICLR 2022
A
MISSING PROOFS IN SECTION 3
We first fill in the proofs of Claim 3.5 and Lemma 3.4
Proof of Claim 3.5
Let u
be any eigenvector of M, with eigenvalue X. There are two cases:
Case 1: of As A
8
Mu
As + Bt
it follows that As As + Bt. and
Bs + At.
t
Bs + At
Thus, follows that (A + (s + As + Bt Bs At A(s t). As the condition of this case assumed (s + 1) * 0, is an eigenvalue of A + B.
(A B)s (A B)s
Case 2: s -t. Then
= Mu
It follows that As = (A B)s, so is an
eigenvalue of A B.
Using Claim 3,5 we can complete the proof of Lemma 3.4
Define A [W)++(m)) and (W)+ so
A
B
Proof of Lemma 3.4
We note
2
B
A
that A +
W+WT and likewise A 2
B
|W++W||
We
2
now directly apply Claim 3.5 to conelude that eigenvalues W are either eigenvalues of A B or
A - B, as desired.
To see the left-to-right implication of (388. we use the faet that the set of eigenvalues of W + W contains those of [W] [W]T subset. For the right-to-left implication, we note that I- WW| > O implies that [ma] //1 < 1. Next, we can observe that Xmax ([W) + (W]T)
Amax W WT) because eigenvalues of W + WT either eigenvalues of W + WT eigenvalues of [WI+ +IWIT. Now we can use the fact that Amax(WW + WT) & Amax ([WI+ [W]T). which would give us Amax B[W + 1/2) < or W > 0.
Finally, to see that Amaax (W W & Amax [ma] [W]T). let e be the eigenvector corresponding to the maximum eigenvalue of W + WTT The key observation is that T + +W & [W] because terms in the expansion of the first quantity will be replaced by positive versions with the same magnitude in the r.h.s.
[c]
Next, we complete the proof of Proposition 3.2
Proof of Proposition 3.2 the damped iteration
By results of Winston Kolter (2020).
there exists 0 << a < 1 such that
(1
a)
+ a
21
2k-1
E
(A.1)
guaranteed converge for any initial 20, 2n: lim Zk. 24
2, For any e satisfying
& v & U, we consider iterating (A.I) with 2o = 2n = 2" (v).
We claim that the following invariant holds: 2ạ > (v) > E5 Vk the damped iteration for 2" (v)), noting that the following equality holds by (Winston & Kolter 2020
To see this, we also consider
u" (1-a)z
a(W (w))(()) (v) + v)
(A.2)
=-vv== = o(u")
Now we apply induction k. The base case given by our choice of 5o, Zn- We compare corresponding terms in (A. and (A.2) for computing ū. u, and u*. We note that žt-1
> x =*(r) by
the inductive hypothesis.
W
2 x= (v) by the inductive hypothesis and properties of
Σk-1
0ch
14

---

Published as a conference paper at ICLR 2022
the IBP iteration, and 8 > by assumption. Thus, it follows that üy > u², and likewise, Wi & u². Since a nondecreasing, we obtain ž > 2²(v) > Eg. completing the induction. Taking limits as k s0, obtain 2* 2 2" (v) e 2 as desired.
Next, we complete the proof of Theorem
3.3
The following lemma will be useful.
Lemma A.1. In the setting of Theorem
3.3 suppose that W satisfies A AW > for some A Dixh, Then there exists < a & 1 such that the following iteration converges:
2k
af[1 aA) aA( W (AA(WWkk11 u))
(A.3)
with limg- 2h z", where x" is the solution to the fixed point equation x" = ooW2" v).
Proof of Lemma A.7 We first observe that the linear operator a( AW) is contractive for sufficiently small as A - AW > O. Thus, since ReLU is 1-Lipschitz, the iteration in (A.3)
contracts and therefore converges to a fixed point. To check that this gives the same fixed point as 3.3 we will check that the following holds:
= = - aa))= + +a(W=" + t))
(A.4)
Note that for coordinates where +))+ v)4 O, the definition of x implies 27 (W2* v) so (A.4) is verified for such coordinates. Otherwise, for coordinates i where (W>* x" + v)s < 0, since is the ReLU activation, 2 0, so we can again verify (A.4) for these coordinates.
We now complete the proof of Theorem 3.3
Taking A = r-2 we have DD1 Now by invoking Theorem 3.1 we conclude that the middle term in this product PD, A AW 0.
Proof of Theorem 3.3 First, we consider any W of the form (37
AW = r-1
To prove the reverse implication, note that A - AJWI A A A A|W| 0 I- 1/2 A//////11 > O. By invoking Theorem 3.1 it follows that have the parameterization A 1/2 1/2 MD'/ so setting I' 112 and rearranging gives the desired result.
A 1/2 1 / so
Next, check that 2.4 and 3.3 have guaranteed unique fixed points whenever W is parameter- ized as in (3.7). Using the observation derived above, we can check that
A
AW 0
(A.5)
A
1/2
W A 1/2 > 0
(A.6)
I
W A 1/2 0
(A.7)
AW 0
(A.8)
Thus, apply Theorem of (Revay et al.
2020 to conclude the existence of unique fixed
point for (24 For 3.3 we apply Lemma 3.4 to conclude that Ä Â-AW > 0, where A
A
0
A
22hx2h Thus, Theorem 1 of (Revay et al. 2020) can also be used to conclude that (3.3) has unique fixed point.
Finally, it remains to check that 2 and =" are indeed valid interval bounds on =². The proof of Proposition 3.2 no longer directly applies because the damped iteration (A.T) might not converge,
as we no longer have the guarantee /2 W > 0. Instead, we invoke Lemma A. which states the existence of ( <
such that the following iteration converges:
2 2B
o ( - aλ)
-
+ aλ
w
3
+
(A.9)
2
with limg-o -as Σω same, we can follow Proposition 3.2 to complete the proof.
limg--co 2g = 2". Using this modified iteration but keeping other steps the
Next, we provide the proof of Proposition 3.7
15

---

Published as a conference paper at ICLR 2022
A1
0 0
0
0
Proof of Proposition 3.7
We set B
According to (37 the weight matrix
W should take the following form: W
LD 1/2
D 1/2
T
We choose I' to take the following
form:
71 Tllx
0 0
0
Y2Inxh
r
(A.10)
M will take the following lower triangular block form:
0
0
A2
0
M
0
A3
0
0
(A.11)
0
A
0
where if we split M into a grid of x blocks, the block the i-th row and 1-th column has value A,, and all other blocks are O. Finally, D will take the form:
Bi Iaxk
0
0
B2lxxh
D
(A.12)
0
BLLaxh_
[AA 1)g
In order to satisfy the constraints of 3.7
require maxje[[]
Br. We now observe
max (1 and 3, > maxxe[M]
(( |A 1) for 2 &
i
<
2
that W is of the form
7208
1/2
A
1/2 71"
0
0
W-
0
33
1/2
1/2
72
0
0
0 Nr.37 A1.8 71-1
(A.13)
We observe now that we have L degrees of freedom in choosing so we can choose such that 7, 1/2 8-11/ = v & L, this only imposes L - constraints. For example, set 71 1, and set . in sequence so that the desired equalities hold. This gives W = M. Finally, it is straightforward to see that the equilibrium for this constructed W and B concatenates all of the hidden layers of the network, so the desired equivalence between the DEQ and explicit network holds.
B ADDITIONAL IMPLEMENTATION DETAILS
Implementation details for Section 4 For all models, we use a batch size of 128 and anneal the learning rate, which is initially 5e-4, by factor of 0.2 at certain steps. For models trained on MNIST and CIFARIO with = 2/255, annealing occurs at the 120th and 280th epochs, and for CIFARIO with 8/255, annealing occurs at the 240th and 280th epochs. We use gradient clipping with a max & norm of 10. To preprocess the data, all inputs are normalized to the range [o. 1] before subtract the mean and divide by the standard deviation of the training images across each input channel. Note that the e adversarial perturbations are applied to the [0, 1] normmazzee image before subtracting the mean and dividing by the standard deviation. For MNIST, do not use data
16

---

Published as a conference paper at ICLR 2022
Table 3: Etriin v.s. Gtest for MNIST.
Grest
0.1
0.2
0.3
0.4
Errain
0.2
0.3
0.4
0.4
augmentation, and for CIFARIO we use random crops and horizontal flips. We note that during both training and testing, when computing IBP bounds we elide the last FC-10 transformation with the output margins of the model (which can be expressed as a linear function of the logits), as Gowal ct al. 2018) show that this leads to performance benefits.
For CIFARIO, we choose Egain = Frests whereas for MNIST we use a larger value of Erains follow- ing Gowal et al. (2118) and Shi al. (202I). The values are displayed in Table To schedule c, set = 0 for the first epoch of trainigg and afterwards we smoothly increase following Xu et al. 22200) The e schedule interpolates between 0 and
Grain in a smooth manner: for the first of the ramp-up iterations, increases according to a degree 4 monomial. After this, e increases linearly until it reaches a final value of Eqain- The linear slope and coefficient of the monomial are chosen so that the derivative of é is continuous. For CIFARIO with e 8/255, we use 159 ramp-up epochs; otherwise, we use 79 ramp-up epochs. For models trained on MNIST, we also use the IBP initialization proposed by (Shi et al. (02I)) for all explicit layer weights, which helps prevent IBP bounds from exploding initialization.
All models besides the DEQ-3 3 can be trained within a day single NVIDIA TitanXp GPU, The DEQ-3 can take up to two days because the hidden layer size larger (128 output channels), so each iteration of the equilibrium solver is more costly. In all, the training times of the IBP-MonDEQ models vary based on the current model weights but generally are 3-10 times longer than the fully- explicit models. As it is already known that DEQ models tend to compare unfavorably to fully
explicit models terms of runtime (Bai et al. 2019 2021). improving the runtime discrepancy is deferred to future work.
Finally, we provide additional ABP-MonDEQ-speciffe implementation details. For IBP-MonDEQ layers, we set outperforms m = 0.1 for DEQ-7 models despite the reduced expressivity, likely due to optimization difficulties. We set y 3 when training models with the more relaxed LBEN parameterization. For DEQ-7 models, we also find it helpful for optimization to use warmup schedule on the value of m matching the schedule on E, and set Meaurent m (0.99 m1 Fiumau))
0.1 in DEQ-3 models and m 0.5 in DEQ-7 models. We find that m 0.5
Cuii so that the value of Mearrent interpolates between 0.99 and < 0.99 throughout training. The stopping criterion for the 10241-8xl2 & f, where t le-5 is the tolerance threshold, and 2 denotes the 1
fixed-point solver is
k-th iterate of the fixed-pone point solving method. For models with the LBEN parameterization, we tie the trainable scaling parameter B across channels, so that has the same shape as the convolutional bias parameter.
Details for Figure The models trained in Figute are obtained by taking the 7LAYER model and adding additional CONV-128-3x3-1 layers to reach the desired depth. For Figure 2 (right), the bounds are computed for randomly initialized models. We obtain the bounds by attempting to solve (3.3) for DEQ models where W corresponds to a fully-connected layer with output dimension 128. We obtain these bounds on MNIST with e = 0.1 and average the mean of 2ة 2g for each the entire MNIST test set. We the damped forward-backwart algorithm the equilibrium solver with damping factor a = 0.1 (see (A. We note that the standard equilibrium iteration (2.4) converges for both MonDEQ and IBP-MonDEQ models, whereas (3.3) fails to converge for Mon- DEQ models only.
17


Reviews:
[{"review_id": "tuzQ2tFZMmA", "reviewer": "Reviewer_KViU", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n* This paper derives parameterizations for DEQ such that the fixed-point solution of the DEQ augmented with IBP bounds exists and is unique.\n* The paper theoretically show that a single IBP-MonDEQ layer can express all explicit feedforward networks. \n* The paper empirically demonstrates the certified defense of IBP-MonDEQ.\n\nWeaknesses:\n* The empirical results are limited which do not show significant improvement over traditional CNN (As shown in the paper, on CIFAR-10, the improvement is no more than 0.5 percentage points compared to traditional CNN used in this paper).\n* Baselines results are too weak -- the performance of the baselines is much worse than state-of-the-art results (e.g.,  Shi et al., 2021). For example, on CIFAR-10 eps=8/255, Shi et al., 2021 shows certified error 65.58 ± 0.32 (or 67.01 ± 0.29 partly without their improvements), but the baseline in this paper has higher errors 69.51 ± 0.46.", "summary_of_the_paper": "This paper considers the certified adversarial robustness of Deep Equilibrium Models (DEQ) and derives the Interval Bound Propagation (IBP) on DEQ for training certifiably robust models, namely IBP-MonDEQ.  ", "summary_of_the_review": "This paper is interesting and can be meaningful for further research as it derives the IBP computation on DEQ for certified defense. But the empirical results are limited so far.\n\n=========Post-rebuttal updates=========\n\nThanks for the response from the authors. The authors have improved their experimental results where the baselines match better with [Shi et al.’21] (currently this update is not visible to the public). \n\nThis paper does present interesting findings in terms of verifying DEQ and can be potential interesting for the area of DEQ, and this is the first work for verifying DEQ which is different from explicit networks.\n\nBut the contribution is kind of insufficient. The paper fails to demonstrate the benefit of using DEQ itself. If it is unclear why we need DEQ, it will be minor to study IBP bounds for DEQ, especially  IBP-MonDEQ fails to really outperform baselines with explicit models (very marginal gap). I think it may help if the authors can introduce some scenaraios in the experiments that are particularly suitable for applying DEQ, to demonstrate that DEQ is really needed. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "sSa7o2B8zSM", "reviewer": "Reviewer_7ZJs", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Pros:\n1. Standard training schemes and architectures cannot guarantee accuracy and certified robustness at the same time. The work focuses on addressing this issue and therefore the problem considered here is an important and challenging one.\n\n2. The construction of IBP-MonDEQ is novel and is among the first attempts to create certified implicit networks. While the interval analysis is relatively simple, the authors provide non-trivial theoretical analysis and guarantees.\n\nCons:\n1. Some of the details about theoretical formalism and empirical evaluation was not clear to me (see my comments below).\n\n2. The practical relevance of the certified robustness obtained on the more challenging CIFAR10 dataset presented here is not clear as the results do not advance the state-of-the-art. For example, the best-certified robustness for CIFAR10 for epsilon=2/255 achieved here is 51% with the corresponding standard accuracy as 64%. This is significantly worse than that obtained by the state-of-the-art which is 60.4% robustness and 78.4% accuracy as reported by COLT (https://openreview.net/pdf?id=SJxSDxrKDr). Similarly for epsilon=8/255, the best-certified robustness and accuracy achieved here are 30% and 44% respectively. These are again worse than the state-of-the-art bounds of 35% robustness and 50% accuracy from L_oo nets (https://arxiv.org/pdf/2102.05363.pdf).\n\nI have a few other questions:\n\n1. Since the interval abstraction is a complete lattice. Therefore, fixed points exist for any monotone (wrt interval inclusion) neural network. Is the class of networks that you identify in Theorem 3.1 and 3.3 a subset of those provided by the classical Knaster-Tarski theorem (https://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem)?\n\n2. Is it possible to define a class of DEQs that have multiple fixed points? \n\n3. Can one equivalently identify a class of fixed-point obtaining implicit networks for other analysis types? e.g., CROWN, DeepPoly, or Zonotopes?\n\n4. The authors should consider providing an intuitive meaning of symbols (e.g., M, D) used in equations (3.4) and (3.7). The text in the evaluation says that M is a learnable parameter which makes things clearer but it comes too late. An example showing instances of W that satisfy these equations and those that do not would also help in improving the readability of the paper.\n\n5. Is it possible to train IBP-MonDEQs for perturbations that cannot be exactly captured by intervals?\n\n6. Is the certified robustness in Table 2 for explicit networks computed using IBP analysis? If yes, will the numbers improve with a complete verifier or with a more precise analysis like Crown or DeepPoly? This is important as it seems that the IBP-MonDEQ cannot be analyzed with anything else besides the IBP analysis while the explicit networks support other analyses.\n\n7. What are the implications of computing a post fixed-point by replacing the equality constraint in eq. (3.6) with interval inclusion, i.e., compute a fixed-point such that the interval of RHS is included inside that for LHS? ", "summary_of_the_paper": "The paper presents a new class of neural networks called IBP-MonDEQs that are an extension of the recently introduced implicit networks MonDEQs. The authors identify a class of weight matrices of the network that ensures that fixed point of the implicit layers exist with respect to the interval analysis and is unique. The construction of IBP_MonDEQ is motivated by the goal of obtaining networks that can be certified to be robust. The authors then train such networks comparing against explicit networks of the same architecture constructed using the certified IBP training. The results show that IBP-MonDEQs can obtain better certified robustness than explicit networks on the MNIST and CIFAR10 dataset.", "summary_of_the_review": "The paper makes solid theoretical and empirical contributions for obtaining new implicit architectures with certified guarantees on their robustness. However, I am not sure whether the  proposed method advances the state-of-the-art in certified robustness unlike the L_oo nets. Further, many key details were not clear to me including comparison with the classical Knaster-Tarski theorem and whether the explicit networks are certified with complete verifiers or IBP.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Oee901fJ2r", "reviewer": "Reviewer_wCmR", "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": "The authors present a non-trivial extension of IBP to DEQ models. A fixed-point version the standard IBP technique is presented, which involves imposing additional constraints on the DEQ weights in order to guarantee that a unique fixed-point solution exists. Two different settings are considered: MonDEQ, and the less restrictive LBEN parametrization. It is shown that the IBP-friendly version of the LBEN parametrization maintains enough expressive power to represent explicit feedforward networks.\n\nThe theoretical analysis seems solid and quite comprehensive, and I believe that the experimental results are interesting on their own, as they present the first results for robustly trained DEQ models. However, I think the quality of the paper would benefit from addressing the following points:\n- Figure 2 shows that (UB - LB) grows with the iterations of the fixed-point solver (until convergence). I believe this implies that the output of the fixed-point solver is a valid bound on the DEQ layer activations only if it is run until convergence. Is this indeed the case? If so, do the authors take this into account (that is, is it always run to convergence in the experiments)?\n- On top of the training experiments, it would be interesting to assess the tightness of the IBP-MonDEQ bounds (to equation (2.1)) of a pre-trained network (both trained via vanilla SGD, and via IBP-MonDEQ robust training). For instance, they could be plotted against the bounds obtained via a PGD attack.\n- The experimental results show that IBP-MonDEQ networks are competitive with IBP-trained explicit networks. However, other robust training methods for explicit networks exist. Would IBP-MonDEQ training be still competitive against CROWN-IBP, for instance?\n- Appendix B reports that the runtime overhead is quite large: a factor 3-10 compared to explicit networks. This seems to be quite a large overhead, given that the empirical gains seem to be limited. Do the authors believe that these results call for the use of DEQ models for adversarial robustness? Or rather that explicit models are still more advantageous?\n\nMinor comments:\n- Isn't (2.2) generally defining lower/upper bounds rather than IBP specifically?", "summary_of_the_paper": "The paper presents IBP-MonDEQ, a modification of monotone deep equilibrium layers (MonDEQ) that allows for the computation of lower and upper bounds on its output via (a fixed-point version of) interval bound propagation. As a result, the authors can train a certifiably robust DEQ model, whose performance is shown to be competitive with an explicit model trained via IBP.", "summary_of_the_review": "IBP-MonDEQ is an interesting and non-trivial extension of IBP to deep equilibrium layers that allows for relatively effective robust training of DEQ networks. The theoretical analysis seems comprehensive, and the experiments show that the proposed algorithm works in practice. I believe the paper would further improve by extending the experimental section and addressing its limitations (large runtime overhead).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1NBynTdG7iP", "reviewer": "Reviewer_jEVJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Implicit layers such as DEQs are a promising tool in machine learning. Creating DEQ models that admit unique fixed points is an important research question, as is developing deep learning models that are certifiably robust. This work addresses both questions simultaneously, and its theoretical contributions serve as useful tools. On the dow side, only fully connected/convolutional layers are considered in the theoretical framework. There is no obvious theoretical extension of these results to skip connections, transformer architectures, or other complicated deep learning models. As a result, the empirical evaluation is far from what one might be interested in implementing in practice. Still, I think that addressing these problems for fully connected and convolutional layers is an important contribution and a good first step, and the empirical evaluation serves its primary purpose of instantiating the theory presented in this paper. \n\nPlease address these questions/comments in your rebuttal. I am willing to upgrade my confidence score if you can address all of these questions.\n1. In the statement of theorem 3.1, what does |M| mean? It is mentioned in section 3.2 but I think it would help the reader to move this definition to before it is used for the first time. Is \\mathbf{1} a vector of all ones? \n2. I am confused by example 3.6. I thought W was required to be symmetric (since I - W should be PD in Proposition 2.1). But this matrix is not symmetric.\n3. In the experiments, you mention that you use batch normalisation. Is it true that your theory (utilising 3.6) does not analyse the use of batch normalisation?\n4. In the proof of Lemma 3.4, you make reference to \\widetilde{W}, which I cannot find a definition for. I think it should be \\hat{W}.\n5. Can you explain further the last sentence of the proof of Lemma 3.4? I don't understand how (3.8) follows.\n6. I can't see where the matrix S comes from in the proof of theorem 3.1. We have E(I - |W|)E = B for B SSD. Writing B = A - ESE we obtain |W| = I-E^{-1} A E^{-1} +S. But how do you know the restrictions on A and S?\n7. I do not understand why contribution 1) is separated from 2). Perhaps I missed something subtle in the words. Does \"stable\" have the same meaning as \"guaranteed unique fixed point\"? If so, I suggest merging contribution 1) and 2).\n\nMinor points:\n- Missing space after period. \"...via closed-form functions.These layers are promising ...\"\n- Winston & Kolter (2020). The arxiv version in your references is now published in NeurIPs.", "summary_of_the_paper": "The authors propose a deep equilibrium (DEQ) layer that provides certifiable robustness via the interval bound propagation technique. This involves augmenting the original fixed point condition considered in DEQs with two additional fixed point conditions, one for each bound. The main contribution is a theoretical result that says that when parameterised in a certain way, this IBP-DEQ admits a unique fixed point (Theorem 3.1, 3.3), and also that the model provides valid IPB (Proposition 3.2). Motivated by a theoretical result (Proposition 3,7), the authors show empirically that such restrictions imposed by the specific DEQ and parameterisation achieve comparable or improved performance compared with explicit models on MNIST and CIFAR10.", "summary_of_the_review": "A theoretical paper that develops a new class of certifiably robust deep equilibrium models with guaranteed unique fixed points, a worthy open problem. The model is largely theoretical (i.e. basic networks such as fully connected or convolutional layers), and as such will not achieve state of the art predictive performance. Nevertheless, the empirical evaluation serves its purpose at demonstrating the utility of the model.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Note: This meta review is written by the SAC, but it's synced with the AC.

Summary (adopted from Reviewer wCmR): This paper presents a modification of monotone deep equilibrium layers that allows to compute the bounds on the output via the IBP algorithm. This also allows to train a certifiably robust DEQ model with a competitive performance.

Initial reviews were mixed, but post rebuttal the opinions generally improved. Reviewer wCmR intend to increase their score slightly (6 to 7) and Reviewer KViU also mentioned that their opinion improved. Reviewer 7ZJs maintained their score and, during discussion phase, made many arguments against acceptance. One of those was about Tarski's theorem which was deemed not so important by the AC and also KViU. Another concern was about experimental results to which KViU agreed, and this remains the main concern for now.

Most reviewers agree that the work is interesting and is a good step, but then utility of the new modification and significance of the results remains a question. It is likely that the work may be useful in the future, and as there is an overall increase in the opinion, I believe that it is okay to accept the paper.

I encourage the authors to take the comments of the reviewers into account, and clearly mention the issues raised in the paper.

SAC
Decision: Accept (Poster)