Semialgebraic Representation of Monotone Deep Equilibrium Models and Applications to Certification
Authors: Tong Chen
Jean B. Lasserre
Victor Magron
Edouard Pauwels
Venue: NeurIPS 2021 Poster (2021)
Keywords: Semialgebraic optimization
deep equilibrium model
robustness certification
Lipschitz constant

Abstract: Deep equilibrium models are based on implicitly defined functional relations and have shown competitive performance compared with the traditional deep networks. Monotone operator equilibrium networks (monDEQ) retain interesting performance with additional theoretical guaranties. Existing certification tools for classical deep networks cannot directly be applied to monDEQs for which much fewer tools exist. We introduce a semialgebraic representation for ReLU based monDEQs which allow to approximate the corresponding input output relation by semidefinite programs (SDP). We present several applications to network certification and obtain SDP models for the following problems : robustness certification, Lipschitz constant estimation, ellipsoidal uncertainty propagation. We use these models to certify robustness of monDEQs with respect to a general $L_p$ norm. Experimental results show that the proposed models outperform existing approaches for monDEQ certification. Furthermore, our investigations suggest that monDEQs are much more robust to $L_2$ perturbations than $L_{\infty}$ perturbations.

Semialgebraic Representation of Monotone Deep Equilibrium Models and Applications to Certification
Tong Chen LAAS-CNRS Université de Toulouse 3 1100 Toulouse, France tchen&laas.fr
Jean-Bernard Lasserre LAAS-CNER & IMT Université de Toulouse 31400 Toulouse, France lasserre@laas. fr
Victor Magron LAAS-CNRS Université de Toulouse 3 440 Toulouse, France vmagron@laas... fr
Edouard Pauwels IRIT & IMT
Université de Toulouse 31400 Toulouse, France edouard, www.aaad.paeeeeiiri.... pwwwels@irit...
Abstract
Deep equilibrium models are based on implicitly defined functional relations and have shown competitive performance compared with the traditional deep networks. Monotone operator equilibrium networks (monDEQ) retain interesting performance with additional theoretical guaranties. Existing certification tools for classical deep networks cannot directly be applied to monDEQs for which much fewer tools exist. We introduce semialgebraic representation for ReLU based monDEQs which allows to approximate the corresponding input output relation by semidefinite programming (SDP). We present several applications network certification and obtain SDP models for the following problems: robustness certification, Lipschitz constant estimation, ellipsoidal uncertainty propagation. We use these models certify robustness of monDEQs w.r.t. general Lg norm. Experimental results show that the proposed models outperform existing approaches for monDEQ certification. Furthermore, our investigations suggest that monDEQs are much more robust to L2 perturbations than Los perturbations.
Introduction
With the increasing success of Deep Neural Networks (DNN) (e.g. computer vision, natural language processing), one witnesses a significant increase in size and complexity (topology and activation functions). This generates difficulties for theoretical analysis and a posteriori performance evaluation. This is problematic for applications where robustness issues are crucial, for example inverse problems (IP) in scientific computing. Indeed such IPs are notoriously ill-posed and stressed in the March 2021 issue of SIAM News M.. "Yet DL has an Achilles' heel. Current implementations can be highly unstable, meaning that certain small perturbation to the input of trained neural network can cause substantial change in its output. This phenomenon is both nuisance and major concern for the safety and robustness of DL.bbssed systems in critical applications- like healthcare-where reliable computations are essential". Indeed, the Instability Theorem (1] predicts unavoidable lower bound on Lipschitz contants, which may explain the lack of stability some DNNs, over-performing on training sets. This underlines the need to evaluate precisely a posteriori critical indicators, such as Lipschitz constants of DNNs. However, obtaining an accurate upper bounds on the Lipschitz constant of DNN is a hard problem, it reduces to prove global inequality "V/ (x) > 0 for all x in domain".
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

i.e,, to provide a proof of positivity for a function V, which has no simple explicit expression. Even for modest size DNNs this task practically challenging, previous successful attempts 8 were restricted in practice to no more than two hidden layers with less than hundred nodes. More broadly existing attempts to DNN certification rely either on zonotope calculus, linear programming (LP) or hierarchies of SDP based on positivity certificates from algebraic geometry [3], which may suffer from the curse of dimensionality.
Recently, implicit deep learning 12 arises as a generalization of the recursive rules of traditional feedforward neural networks. Specifically, Deep Equilibrium Models (DEQ) 2 have emerged as a potential alternative to classical DNNs. With their much simpler layer structure, they provide competitive results on machine learning benchmarks 32. Training DEQs involves solving fix fix-toint equations, which requires further conditions to make the iteration converge. Fortunately, Monotone operator equilibrium network (monDEQ) introduced [45] satisfies such conditions. Moreover, the authors in [3] provide explicit bounds on global Lipschitz constant of monDEQs (w.r.t. the (--norm) which can be used for robustness certification.
From a certification point of view, DEQs have the definite advantage of having only one implicit layer compared to DNNs and therefore is potentially more amenable to sophisticated techniques (e.g. algebraic certificates of positivity) which rapidly face their limit even for classical DNNs with modest size (but long depth). Therefore monDEQs constitute class of DNNs for which robustness certification, uncertainty propagation or Lipschicity could potentially be investigated in a more satisfactory way than classical networks. Contrary DNNs, for which variety of tools have been developped, certification of DEQ modeld is relatively open, the only available tool is the Lipschitz bound 3
Contribution
We present three general semialgebraic models of ReLU monDEQ for certification (p E [+000)
Robustness Model for network L, robustness certification.
Lipschitz Model for network Lipschitz constant estimation with respect to any Lp norm.
Ellipsoid Model for ellipsoidal outer-approximation of the image by the network of a polyhedra or an ellipsoid.
All these models can be used for robustness certification, a common task which we consider experi- mentally. And the main originality of this work is to successfully apply the proposed techniques to monDEQ networks (especially for the Ellipsoid model which is a novel form of reachability analysis), which was not proposed before. Both Lipschitz and Ellipsoid models can in addition be used for further a posteriori analyses. Interestingly, all three models are given by solutions of semidefinite programs (SDP), obtained by Shor relaxation of a common semialgebraie representation of ReLU MonDEQs. Our models are all evaluated to simple ReLUU monDEQs on MNIST dataset similar as B3 on the task of robustness certification. We demonstrate that all three models ourperform the approach of (33) and the Robustness Model being the most efficient. Our experiments also suggest that DEQs are much less robust to L perturbations than L perturbations, in contrast with classical DNNs 366 which have been shown to be robust on MNIST dataset to the level we are considering (6 0.1).
Related works
Neural network certification is challenging topic in machine learning, contributions include:
Even with high test accuracy, DNNs are very sensitive to tiny Robustness to input perturbation has been investigated in many different works with various techniques, including SDP relaxation in SDP-cert (36). first-order dual SDP method [10], abstract interpretation with ERAN [5] 41), multi-neuron convex relaxations with PRIMA [1I, GPU-based based method GPUPoly 30 which can scale to large networks with one million neurons and 34 layers, scalable quantitative verification framework with PROVERO (4) LP relaxation in Reluplex (25). analytical certification with Fast-lin [4] and CROWN 47), and their extension to convolutional neural networks with CNN-Cert (7]. All these methods are restricted to DNNs or CNNs and do not directly apply to DEQs
Robustness certification of DNNs
input perturbations, see e.g.
42 16

---

Lipschitz constant estimation of DNNs Lipschitz constant of DNNs can be used for robustness certification 42 [8] Existing contributions include naive layer-wise product bound 22 49 con-
trolled ordinary differential equations (ODE) method (20). nonotope-based method 224 which can be
further extended to generative models, Mixed-Integer Programming (MIP) (33] for exactly computing
the local Lipschitz constant of ReLU networks, the LP relaxations for CNNs
48 and DNNs [28] as
well as SDP relaxations [35 14 8)
Lipschitz constant estimation of DEQs The authors in [33 provide an optimization-fre upper bound of the Lipschitz constant of monDEQs depending on network weights. This bound is valid for 1,2 norm and we present general model for arbitrary IP norm. Based on the works of [33], the authors in 38 introduced new parameterizations of DEQs that admit Lipschitz bound during training via unconstrained optimization.
2 Preliminary Background and Notations
We consider the monotone operator equilibrium network (monDEQ) 45]. with single implicit hidden layer. The main difference between monDEQ and deep equilibrium network (DEQ) [ is that strong monotonicity is enforced on weight matrix and activation functions to guarantee the convergence of fixed point iterations. The authors in [45] proposed various structures of implicit layer, we only consider fully-connected layers, investigation of more advanced convolutional layers is in our list of future works.
Network description: Denote by F: IR R a fully-connected monDEQ for classification, where Po is the input dimension and K is the number of labels. Let Xg E R be the input variable and z R' be the variable in the implicit layer. We consider the ReLU activation function, which is simply defined as (eLU(x)= = max (0, x}, and the output of the monDEQs can be written as
F(xo) Cz + c ReLU(Wz + Uxo + uu)
(monDEQ)
where W E IRPX,, U E RPXP0 u E R2, C CKXP, E RR are parameters of the network. The vector-valued function Fxx,) provides score for each label E (l...., K} associated to the input Xo. the prediction corresponds to the highest score, i.e., Vx, = arg max;=l.... F(xo); k. As in 45) the matrix I,- W strongly monotone: there a known m constraint can be enforced by specific parametrization of the matrix W. With the monotonicity assumption, the solution to equation z = ReI.U(Wz + Uxg + u) is unique and can be evaluated using convergent algorithms, see (55 for more details.
such that Ip W ž mIp. this
Robustness of monDEQs:
Given an input Xg R a norm || ||, and a network F: R - RKK let y0 be the label of input Xo. i.e., 9/ = arg max;= K F(xo); For & > O, denote by E = B(xo, é; ||. II) the ball centered at Xo with radius for norm || Il. If for all inputs of x equals yo. i.e., y = arg maxi I.....K K F(x); = yo. then we say that the network F is e-robust at input Xo for norm || ||. An equivalent way verify whether the network F is s-robust to check that for all labels # yo. F(x); - F(x)y. < 0.
E, the label
The key reason why neural networks with ReLU activation function can be tackled using polynomial optimization techniques is semialgebraicity of the ReLU function, i.e., it can be expressed with system of polynomial (in)equalities. For x. y E R, we have (0,
Semialgebraicity of ReLU function:
y = (cLU(x)) = max (0, xx) if and only if yv x)) = 0, 2 x, 2 0. For x, E IR"", we denote by (eLU(x) the coordinate- of x and y. A subset of IR" defined by a finite conjunction of polynomial (in)equalities is called a basic closed semialgebraic set. The graph of the ReLU function is basic closed semialgebraic set.
evaluation of ReLU function, and by xy the coordinate-wise product
Going back to equation (monDEQ). we have the following equivalence:
z = ReI.U(W2 + Uxp + u) e 2(2 Wz- Uxo - u) = 0, z 2 Wz + Ux9 + u, z 2 0, (1)
where the right hand side is a system of polynomial (in)equalities. For the rest of the paper, mention of the ReL. function will refer to the equivalent polynomial system O..
POP and Putinar's positivity certificate: In general, a polynomial optimization problem (POP) has the form
p max (f(x)) g (x) 2 0, = I.....P..
(POPn)
XER*
3

---

where f and 9: are polynomials whose degree is denoted by deg. The robustness certification model 3.I Lipischitz constant model (3.2) and ellipsoid model (3.3) are all POPs.
In most cases, the POPs are non-linear and non-convex problems, which makes them NP-hard. A typical approach reduce the complexity of these problems is replacing the positivity constraints by Putinar's positivity certificate (34). The problem (POPn) is equivalent to
min ( : À - f(x)= 2 O, 9 2 0, = 1,....................... P. VX E R" XER
(POP)
In order to reduce the size of the feasible set of problem (POP), replace the positivity constraint À f(x) 2 0 by a weighted sum sum-of-square (SOS) polynomial decomposition, involving the polynomials 9t- Let be a non-negative integer. Denote by (x)x, ox) some SOS polynomials of degree at most 2d, for each = 1, ......P. Note that if d = O, such polynomials are non-negative real numbers. Then the positivity of X - f(x) is implied by the following decomposition
P
X- f(x)
= xx)
Σ (x)):(x) wi = [degg:/2) Vx E RR"
for any d 2 max; wi. Equation is called the order-d Putinar's certificate.
By replacing the we have for
positivity constraint f(x) - x N in problem (POP) by Putinar's certificate
2 max; Wis
Pa = min (A: X X = xx) + AER
(x)9:(x). wi = [: vx E R"). (POP-d)
It is obvious that Pa 2 for all d max; wip. Under certain conditions (slightly stronger than compactness of the set of constraints). it is shown that limg- Pa p [27]. The main advantage of relaxing problem (POP) to (POP-d) is that problem (POP-d) can be efficiently solved by semidefinite programming (SDP). Indeed a polynomial ff of degree at most 2d is SOS and only if there exists a positive semidefinte (PSD) matrix M (called Gram matrix) such that fxx v(x) v(x))MM(i (x))), for all X E IP, where v(x) is the vector monomials of degree at most d.
Problem (PPP-) is also called the order-d Lasserre's 's relaxation. When the input polynomials are quadratic, the order-1 Lasserre's 's relaxation is also known as Shor's relaxation [40] All our models are obtained using variations of Shor's 's relaxation applied to different POPs, see Section 3.3 for more
details.
3 Semialgebraie Models for Certifying Robustness of Neural Networks
In this section, we introduce several models for certification of monDEQs. All the models are based on semialgebraicity of ReLU and ØReLU (the subgradient of ReLU, see Section 3.2) to translate our targeted problems to POPs. Then use Putinar's certificates, defined in Section 2 to relax the
non-convex problems to convex SDPs which can be solved efficiently using modern solvers.
Notation:
consider monDEQ for classification, denoted by F, with fixed. given parameters, W E RP ,, U E P2 u E RP, C E IR xxx,, c E RK where Po is the number of input neurons, p is the number of hidden neurons, and K is the number of labels. For g E+ U {+oo}. ||- ll, is the L, norm defined by ||x|| Throughout this section é > 0 and Xo E IPPo are fixed, we denote by 3 == B(xo, e lllo) (x E R |xx g #} the ball centered at xy with radius for Lg norm, perturbation region. If q < toc i.e., is a positive integer. ||x - Xullg I E is equivalent to the polynomial inequality oo, || - l S E is equivalent to |x xpl² S e² (where |x| denotes the vector of absolute values of coordinates of x) which is system of Po polynomial inequalities. Hence the input set is a semialgebraic set for all considered Lg norms. For a matrix A E m its operator norm induced by the norm is given by ||||||| := inf{A: ||Ax|| < X||x||, Vx RR).
Throughout this section,
(> t x 12)//)// for all x IRPo,
x - xo < c9;
3.1 Robustness Model
Let yo be the label of xn and let z E Rp be the variables in the monDEQ implicit layer. The proposed model directly estimates upper bounds on the gap between the score of label yo and the score of labels

---

different from yo. Precisely, for i E fl...., } such that i * yo, denote by &, = i yo..:"" For x E E, the gap between its score of label and label is F(x), - y0 = E z. The Robustness Model for monDEQ reads:
.
83
max [0 z z ReLU(Wz Ux u) x x
(CertMON-i)
XER
Using the semialgebraicity of both ReLU in (T. and set &, problem (CertMON-i a POP for all i. As discussed in Section 2 one is able to derive a sequence of SDPs (Lasserre's s relaxation) to obtain converging serie of upper bounds of the optimal solution of [CertMON-... For Robustness Model, we consider only the order-1 Lasserre's relaxation (Shor's relaxation), and denote by ó; the upper bound of 6, by Shor's relaxation, i.e., 6; S & Recall that for all label different from yo, we have F(x); F(x) then the label of still you This justifies the following claim:
Certification criterion: If 8, 0 for all yo, then the network F is e-robust X0-
Robustness Model for DNNs has already been investigated in [36]. where the authors also use Shor's relaxation do. Different from DNNs, only have one implicit layer in monDEQ. Therefore, the number of variables in problem (CertMON-] only depends on the number of input neurons Po and hidden neurons p.
3.2 Lipschitz Model
We bound the Lipschitz constant of monDEQ with respect to input perturbation. Recall that the Lipschitz constant of the vector-valued function F (resp. 2) w.r.t. the I., norm and input ball S 3 E, denoted by Lis (resp. L2 is the smallest value of such that [[F(x) F(y)llo S L||x y yll
(resp. |z(x) - z(y)llg I L||x yllg) for all x, E S. For x, Xy E E, with ||x xolle S c, we can
estimate the perturbation of the output follows:
[F(x F(xo)1lg S p4.s ||x 1xxlxll4--0 S eL..
| F - ||CII|, L2 ||x xollo S : C Lg
(4)
The authors in 33
use inequality 4 with g = 2, as they provide an upper bound of L2,s- In contrast, model provides upper bounds on Lipschitz constants of F or for arbitrary Lg norms. We directly focus on estimating the value of L instead of L.
Since the ReLU function non-smooth, we define its subgradient, denoted by ŌReLU, as the set-valued map RRe.U(x)) = 0 for < O, ReI.U((x) = for x > O, and (ee. = 00, 1] for J 0. Similar ReLU function, RRLLU is also semialgebraic.
Semialgebraicity of RRLLU: af E TR, we have y E @ReLU(x)). if and only if y I 0, ay 2 0,-(y 1) 2 x E R", then ÖReLU(x) denotes the coordinate-wise evaluation of dReLU, Going back to monDEQ, let s be any subgradient of the implicit variable: s E RReLU(Wz+ Ux+u). We write equivalently system of polynomial inequalities:
s(s 1) < 0, s (z + Ux + u) 0, (s 1)(Wz + Ux + u) 0.
For the following discussion, ØReLU will refer to the equivalent polynomial systems
With the semialgebraicity of ReLU in | and ØReLU in (5). one is able to compute upper bounds of the Lipschitz constant of via POPs. The proof of the next Lemma is postponed to Appendix A.I
Lemma Define
1g.s = max ( (TUTY : 1, Ro, s, RD, V, w W K XES,
(nax(tTuu
C.v. diag(s).r. -r: s E ORCLU + Ux + u). z == ReLU(Wz + Ux+ (LipMON)
||t|l < 1, w $1, ||| -- w
Then ig s is upper bound of the Lipschitz constant of F w.r.t. the Lg norm, i.e., L i
Since problem [ipMON a POP. we also consider Shor's relaxation and denote by L%. the upper bound of Li.s by Shor's relaxation, i.c., Li. S L Define å := ==Lh.s- By equations 3) . if
5

---

E C S. using Lemma I and the fact that || /l S || 11-10 llg. we have |F((x) - - F(xo)llo S 8, yielding the following criterion:
Certification criterion: Let yo be the label of Xp- Define T == F(xo)ys - max F(xo)&= If
26 < T, then the network F is e-robust Xp-
Remark: In order to avoid some possible numerical issues, we add some bound constraints and redundant constraints to problem (LipMON), see Appendix [A.2] for details. Shor's relaxation of Lipschítz Model for DNNs has already been extensively investigated in [4 84 If one want to certify robustness for several input test examples, then one may choose S to be big ball containing all such examples with an additional margin of c. Choosing a big ball for all input points requires to solve only one optimization problem, while choosing one ball for each input point (say among N) requires to solve N optimization problems, which is much more costly. In this case it is more favorable to use the Certification Model directly.
3.3 Ellipsoid Model
As above, the input region & a neighborhood of input X E I with radius E for the Lg norm, i.e., E = (x E RP: -oll, S æ). More generally, & could be other general semialgebraic sets, such as polytopes or zonotopes. Denote by F(E) the image of by F. In this section, we aim at finding a semialgebraic set C such that F(E) C C. We choose C to be ellipsoid which can in turn be used for robustness certification. Our goal is to find such outer-approxe aprrxxippooiittiinnn ellipsoid with minimum volume. Let C = [ E gx ||Q + bll2 S 1} be an ellipsoid in the output space It parametrized by Q E S and b E RK, where S is the set of PSD matrices of size K K. The problem of finding the minimum-volume ellipsoid containing the image F(E) can be formulated as
max QESK BERK
(dct(Q) E. ||QCZz + c) + bll2 S RcLU(W2 Ux+ u))-
(EIlipMON-POP)
By semialgebraicity of both ReLU in and C, problem EllippMON-POP can be cast POP (the determinant being a polynomial). We no longer apply Shor's 's relaxation, we rather replace the c) + bll2 2 0 by stronger Putinar's certificate related to both ReLU and input constraints. We can then relax the non-convex problem (EIP to a problem with SOS constraints, which can be reformulated by (convex) SDP constraints. This is due to the fact that a polynomial f of degree at most 2d is SOS if and only if there exists a PSD matrix M (called Gram matrix) such that f(x) v containing all monomials of degree at most d. In summary, we relax problem EllipMON. to an SOS constrained problem keeping the determinant unchanged:
non-negativity output constraint 1 IQ(Zz Cz +
Mv Mx) (x)). for all R2, with v(x) being the vector
QES" .ERR {eet Q): 1- QC + c) + bll2 = ,o(x, z) + oo -01((x2) 2) 9y(x - -x))
max
=T(xxz)((z(z Wz Ux u)) + (x 2) (z- Wz -Ux Ux-ui u) 03(x, z)²zz)
(EllipON--SOS-d)
where 9g (x) = -|x] for 9 +o0 and 9q (x) =
for q +00, og is vector of SOS
polynomials of degree at most 2d, 0 is vector of SOS polynomials of degree most 2(d - [q/2]) for q < +oo and 2d 2 for q = +00, a2 03 are vectors of SOS polynomials of degrees at most 2d - 2, is a vector of polynomials of degree at most 2d 2. Problem (ElippON-SOS-d provides an ellipsoid feasible for (EII that is an ellipsoid which contains F(E). In practice, the determinant is replaced by a log-det objective because there exist efficient solver dedicated to optimize such objectives on SDP constraints. By increasing the relaxation order d in problem (EllipMON-SOS-)),, one is able to obtain hierarchy of log-det objected SDP problems for which the outer-approximation ellipsoids have decreasing volumes.
In this paper, we only consider the case p 2, oo, and order- I relaxation (d 1). Therefore, o, and T are all (vectors of) real (non-vegative) numbers for = 1, 2, except that og is an SOS polynomial of degree at most 2. In this case, problem CCllipOO--OS--A is equivalent to problem with log-det objective and SDP constraints, as the following lemma states (proof postponed to Appendix A.3):
Lemma 2 For p = or p- = cc, problem (llippON--OS--) with d = 1 is equivalent to (BllipMON-SDP)
max
flog det Q) -M = 0)
QESK beR* 01 00.02.00.0000..

---

where M E Slnotot1)x(o-p-i) is symmetric matrix parametrized by the decision variables (Q, b), the coefficients (0), 02, 3. T), and the parameters of the network (W, U, u, C.
Since the outer-approximation ellipsoid C {E E F(E), i.., all possible outputs of the input region &, one is able to certify robustness by solving the following optimization problems.
R ||Q
+ bll2 < 1} contains the image
Let yo be the label of X For i * yo- define 6; := max (E: Eyo [[ + bll2 I 1}. If ó; < O for all i # yo, then the network F is e-robust at Xo-
Certification criterion:
The certification criterion for Ellipsoid Model has geometric explanation: for i * you denote by P. the projection map from output space RK to its 2-dimensional subspace Ry x R2 i.e., PP((E) = 15n. sil" for all Ç E IK. Let L, be the line in subspace Ryo x RR defined by {lSpo &il" E R,0 R, Eyo {.}. Then the network F is e-robust if the projection P:(C) lies strictly below the
line L; for all i + yoo We give an explicit example in Section 4.3 to visually illustrate this.
3.4 Summary of the Models
We have already presented three models which can all be dedicated certify robustness of neural networks. However, the size and complexity of each model are different. We summarize the number of variables in each model and the maximum size of PSD matrices in the resulting Shor's relaxation, see [ The complexity of our models only depends on the number of neurons in the input layer and implicit layer. The size of PSD matrices is limiting factor for SDP solvers, our models are practically restricted to network for which such size can be handled by SDP solvers. For the popular dataset MNIST [46]. whose imput dimension is 28 x 28 784, we are able to apply our model on monDEQs with moderate size implicit layers (87) and report the corresponding computation time.
Table 1: Summary of the number of variables the three models
Robustness Model
Lipschitz Model
Ellipsoid Model
Num. of variables Max. size of PSD matrices
Pu +
2pu + 4p + 2K
Po + 3p + K + K 1 po +
1 1 Po +
1 1+ 2pu + 4p + 2K
4 Experiments
In this section, we present the experimental results of Robustness Model, Lipschitz Model and Ellipsoid Model described in Section 3 for pretrained monDEQ on MNIST dataset. The network we use consists of a fully-connected implicit layer with 87 neurons and we set its monotonicity parameter m to be 20. The training hyperparameters are set to be the same as in Table D1 of [45). where the training code (in Python) is available at //ttps://githui
com/locus// 1 aaa/maaotooonneeee op_net net Training is based on the normalized MNIST database [45), we use the same normalization setting on each test example with mean μ = 0.1307 and standard deviation
0.3081, which means that each input an image size 28 x 28 with entries varying from -0.42 to 2.82. And for every perturbation e, we also take the normalization into account, i.e., we use the normalized perturbation e/o for each input.
Since all our three models can be applied to certify robustness of neural networks, we first compare the performance of each model in certification of the first 100 test MNIST examples. Then we compare the upper bounds of Lipschitz Model with the upper bounds proposed in (33). Finally we
show that Ellipsoid Model can also be applied for reachability analysis. For Certification model and
Lipschitz model, we implement them in Julia []] with JuMP [II] package; for Ellipsoid model, we implement it in Matlab (3 with CVX [17 package. For all the three models, we use Mosek [29] as a backend to solve the targeted POPs. All experiments are performed on a personal laptop with an Intel 8-Core i7-8665U CPU @ 1 1.90GHz Ubuntu 18 04.5 LTS, 32GB RAM. The code of all our models is available at https:://// / thub. www/Neor Ips

---

4.1 Robustness certification
We consider E = 0.1 for the L2 norm and E = 0.1, 0.05, 0.01 for the Los norm. For each model, we compute the ratio of certified test examples among the first 100 test inputs. Following [3]. also compute the projected gradient descent (PGD) attack accuracy using Foolbox library (7], which indicates the ratio of non-successful attacks among our 100 inputs. Note that the ratio of certified examples should always be less or equal than the ratio of non-successful attacks. The gaps between them shows how many test examples there are for which we are neither able to certify robustness nor find adversarial attacks.
For Lipschitz Model, we use inequality (3) to test robustness, i.e., compute directly the upper bound of the Lipschitz constant of rather than z (seen as a function of x) where S is a big ball containing all test examples.
Remark:
From Table 2 we see that the monDEQ robust to all the 100 test examples for the T22 norm and 8 =00 0.1 (the only example that we can not certify is because the label itself is wrong). However, it is not robust for the Lex norm at the same level of perturbation (all our three models cannot certify any examples), and the PGD algorithm finds ad adversarial examples for 85% of the inputs. The network becomes robust again for the Loe norm when we reduce the perturbation to 0.01. Overall, we see that Robustness Model is the best model as it provides the highest ratio, Ellipsoid Model is the second best model compared to Robustness Model, and Lipschitz Model provides the lowest ratio. As trade-off, for each test example, Robustness Model requires to consider at most optimization problems, each one being solved around 150 seconds, while Ellipsoid Model requires to consider only one problem, which is solved in around 500 seconds. We only need to calculate one (global) Lipschitz constant, which takes around 1 1500 seconds, so that we are able to certify any number of inputs. Each model we propose provide better equal certification accuracy compared to 33 and significant improvements for L perturbations.
Table 2: Ratio of certified test examples and running time per example by different methods. We consider L2 norm with e = 0.1 and Lx norm with 0.1, 0.05, 0.01. The ratio is based the first 100 MNIST test examples, and we count the average computation time (with unit second) for one example of each method. The ratio in parentheses of the column "Lipschitz Model" are computed by the Lipschitz constant given in 33 (see Section intervals are given in bracket.
2 for details). Exact binomial 95% confidence
Robustness Model (1350s/ example)
Lipschitz Model (1500s in total)
Ellipsoid Model (500s / example)
Norm
PGD Attack
L2
0.1
99%
[>94]
91% (91%) [>83]
99%[>>9]
99%[>94]
0.1
0%
[<4]
0% (0%) [<4]
0%[[<]]
15% [8, 24]
Logo
0.05
24%
16, 34]
0% (0%) [<4]
0%
[<4]
82% [73, 89]
0.01
99%
[>94]
24% [16, 34] (0%)
[<4]
92%
[>84]
99% [>94]
Figure 2 in Appendix shows the original image of the first test example (2a) and an adversarial
attack 26
for the Lo norm with & 0.1 found by the PGD algorithm in
4.2 Comparison with Lipschitz constants
In this section, we compare the upper bounds of Lipschitz constants computed by Lipschitz Model with the upper bounds proposed in 33.. Notice that the upper bounds in [3] only involve the function 2xx), hence we are only able to use inequality (4) to test robustness. In fact the quantity ||| ||C||,, T.2.
can be regarded as an upper bound of L the Lipschitz constant of F. We denote by UB² the upper bound of the Lipschitz constant of z w.r.t. the L2 norm, given by UB² = [/U'Il//m according to [33]. where U is the parameter of the network and m is the monotonicity factor. We can then compute the upper bound w.r.t. the Loo norm by UB yPo UB? where Po is the input dimension. The upper bound of Lipschitz constant of F is computed via the upper bound of z: UB% = ||[]]I, UB2. Denote similarly by SemiUB?. the upper bounds of Lipschitz constants of F provided by Lipschitz Model, w.r.t. the Lg norm.
8

---

Table Comparison of upper bounds of Lipschitz constant for L2 and Lo norm, and the correspond-
ing computation time (with unit second).
00
bound
time (s)
bound
time (s)
UB
4.80
824.14 14
SemiUBB
4.67
1756.58
108.84
1898.65
From Table 3 we see that Lipschitz Model provides consistently tighter upper bounds than the ones in [3]. Especially for Loo norm, the upper bound computed by | UB is rather crude compared the bound obtained directly by Lipschitz Model. Therefore, we are able certify more examples using S than UB see Table
4.3 Outer ellipsoid approximation
In this section, we provide visible illustration of how Ellipsoid Model can be applied to certify robustness of neural networks.
Take the first MNIST test example (which is classified as 7) for illustration. For e = 0.1, this example certified be robust for the L2 norm but not for the Loo norm. We show the landscape of the projections onto R x RR, i.e., the z-axis indicates label 7 and the y-axis indicates label 3. In Figure 1. the red points are projections of points in the image F(E), for an L2 or Loo norm perturbation zone, the black circles are projections of some (successful and unsuccessful) adversarial examples found by the PGD algorithm. Notice that the adversarial examples also lie in the image F(E). The blue curve is the boundary of the projection of the approxiapoiiinioonn ellipsoid (which is ellipse), and the blue dashed line plays the role of a certification threshold. Figure Ta shows the landscape for the L2 norm, we see that the ellipse lies strictly below the threshold line, which means that for all points E C, we have {3 < &.. Hence for all & E F(E), we also have & < εT. On the other hand, for the Lo norm, we see from Figure [bb that the threshold line crosses the ellipse, which means that we are not able to certify robustness of this example by Ellipsoid Model. Indeed, we can find adversarial examples with the PGD algorithm, as shown in Figure 1b by the black circles that lie above the threshold line. The visualization of one of the attack examples is shown Figure in Appendix A.4
Outputs, ellipsoid and threshold line
Outputs, outer allipsoid and threshold line
25
Ellipsied
Outputs Attacks
20
Outputs
Attacks
Threshold
Threshold
10
9
2.5
label 3
label
1.5
-30
0.5
-15
-10
10
label 7
label 7
(a) Certified example for the L2 norm
(b) Non-certified example for the Loo norm
Figure 1: Visualization of the outer-approun approximation ellipsoids and outputs with E = 0.1 for Le norm (left) and L. norm (right). The red points are image of the input region, the blue curve is the ellipsoid we compute, the blue dashed line is the threshold line used for certifying robustness of inputs, and the black circles are attack examples found by PGD algorithm.

---

5 Conclusion and Future Works
In this paper, we introduce semialgebraic representations of monDEQ and propose several POP models that are useful for certifying robustness, estimating Lipschitz constants and computing outer- approximation ellipsoids. For each model, there are several hierarchies of relaxations that allow to improve the results by increasing the relaxation order. Even though we simply consider the order-1 relaxation, we obtain tighter upper bounds of Lipschitz constants compared the results in [33 Consequently, we are able to certify robustness of more examples.
Our models are based on SDP relaxation, hence requires efficient SDP solver. However, the stat- of-the-art SDP solver Mosek (by interior-point method) can only handle PSD matrices of moderate size (smaller than 5000). This is the main limitation of our method if the dimension of the input gets larger. Moreover, we only consider the fully-connected monDEQ based on MNIST datasets for illustration. One important and interesting future work is to generalize our model to single and multi convolutional monDEQ, and to other datasets such as CIFAR [26] and SVHN (22. Directly using off-the-shelves interior point SDP solvers to solve the problems for convolutional networks is not possible because of their current size limitation. Fortunately, convolutional layer can be regarded as
fully-connected layer with larger (but sparse) weight matrix. Hence one able to build similar models via sparse polynomial optimization tools.
The authors in 10] provide an interesting and promising first-order method alternative to the costly interior point methods for solving semidefinite relaxations associated with robustmess certification of DNNs. What is crucial in [10] is to exploit the network layer structure for efficient mack-propagation in gradient computation. In particular, the algorithm requires memory only linear in the total number of network activations and only requires a fixed number of forward/backwan passes through the network per iteration. This enables the algorithm to certify robustness of large- scaled networks more efficiently and accurately. However, the auto-differenniation technique for computing subgradients in DNNs does not apply directly to monDEQs, since computing subgradients in monDEQs involves solving fixed-point equations. Therefore, adapting the approach of [0 for solving more efficiently our semidefinite relaxations associated with monDEQs is certainly worth considering but not straightforward.
a topic of further investigation.
The authors in 33 showed that we can train DEQs with small Lipschitz constants for the L2 norm, by controlling the monotonicity of the weight matrix. This guarantees the robustness of monDEQ w.r.t. the L2 norm but not for the To norm. A natural investigation track is to adapt this training technique to the Io norm with better control of the associated Lipschitz constant.
Acknowledgments and Disclosure of Funding
The authors acknowledge the support of AI Interdisciplinaty Institute ANITI funding, through the French "Investing for the Future - PIA3" program under the Grant agreement AN---19-P3AA-00 Edouard Pauwels acknowledges the support of Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbersFA9550011911 0017-01. This work was supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. Victor Magron was supported by the FMJH Program PGMO (EPICS project) and EDF, Thales, Orange et Criteo, as well as from the Tremplin ERC Stg Grant ANR- 1-R-1-8-2C20000-000 (T-COPS project). This work has benefited from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions.
6and ANR MaSDOL 19-CE23-
References
[1] Vegard Antun, Nina M. Gottschling, Anders C. Hansen, and Ben Adcock. Deep learning in scientific computing: Understanding the instability mystery. SIAM NEWS MARCH 2021, 2021.
[2] Shaojie Bai, J. Zico Kolter, and Vladien Koltun. Deep equilibrium models. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
10

---

[3] Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Multiscale deep equilibrium models. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5238-5250 Curran Associates, Inc., 2020.
[4] T. Baluta, Z. Chua, K. S. Meel, and P. Saxena. Scalable quantitative verification for deep neural networks. In 2021 IEEF/ACM 43rd International Conference on Software Engineering: Companion Proceedings (ICSE- Companion),, pages 248 Los Alamitos, CA, USA, may 2021. IEEE Computer Society.
[5] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral Shah. Julia: A fresh approach to numerical computing. SIAM review, 59(1):65-99,, 2017.
[6] Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, pages 1-33, 2020.
[7] Akhilan Boopathy, Tsui-Wor Weng, Pin- Yu Chen, Sijia Liu, and Luca Daniel. Con-cert: An efficient framework for certifying robustness of convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3240-3247, 2019.
[8] Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimization for lipschitz constants of relu networks. H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19189-19200. Curran Associates, Inc., 2020.
[9] F. H. Clarke. Optimization and Nonsmooth Analysis. Wiley New York, 1983.
[10] Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy R Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy S Liang, and Pushmeet Kohli. Enabling certification of prificaationaannssii networks via memory- semidefinite programming. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5318-5331. Curran Associates, Inc., 2020.
[11] lain Dunning, Joey Huchette, and Miles Lubin. Jump: A modeling language for mathematical optimization. SIAM review, 59(2):295-320, 2017.
[12] Laurent EI Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai. Implicit deep learning. SIAM Journal on Mathematics of Data Science, 3(3):930-958, 2021.
[13] Mahyar Fazlyab, Manfred Morari, and George J. Pappas. Probabilistic verification and reacha- bility analysis of neural networks via semidefinite programming. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 2726-2731, 2019.
[14] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
(15) Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEF Symposium on Security and Privucy (SP), pages 3-18. IEFE, 2018.
[16] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
[17] Michael Grant and Stephen Boyd. Cvx: Matlab software for disciplined convex programming. version 2.1, 2014.
[18] Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.

---

[19] Didier Henrion, mization and semidefinite programming, Optimization Methods Software, 24(4-5):711-77, 2009.
Lasserre, and Johan Löfberg. Gloptipoly 3: moments, opti-
[20] Calypso Herrera, Florian Krach, and Josef Teichmann. Estimating full lipschitz constants of deep neural networks. arXiv preprini urXiv:2004.131. 2020.
[21] Haimin Hu, Mahyar Fazlyab, Manfred Morari, and George J. Pappas. Reach-sdp: Reachability analysis of closed-loop systems with neural network controllers via semidefinite programming. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 5929-5934 IEEE, 2020.
[22] Todd Huster, Cho- 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 Databases, pages 16-29. Springer, 2018.
[23] Matt Jordan and Alexandros G. Dimakis. Exactly computing the local lipschitz constant of relu networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7344-7353. Curran Associates, Inc., 2020.
[24] Matt Jordan and Alexandros G. Dimakis. Provable lipschitz certification for generative models. In International Conference on Machine Learning, pages 5118-5126 PMLR, 2021.
[25] Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference Computer Aided Verification, pages 97-117. Springer, 2017.
[26] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[27] Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):76--17,, 2001.
[28] Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference Learning Repre- sentations, 2020.
[29] ApS Mosek. The mosek optimization toolbox for matlab manual, 2015.
[30] Christoph Müller, François Serre, Gagandeep Singh, Markus Püschel, and Martin Vechev, Scaling polyhedral neural network verification on gpus. In A. Smola, A. Dimakis, and I. Stoica, editors, Proceedings of 4th MLSys Conference, volume 3, pages 733-746, 2021.
[31] Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. Prima: Precise and general neural network certification via multi-neuron convex relaxations. arXiv preprint
2021.
[32] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
[33] Chirag Pabbaraju, Ezra Winston, and J. Zico Kolter. Estimating lipschitz constants of monotone deep equilibrium models. In International Conference on Learning Representations, 2021.
[34] Mihai Putinar. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal, 42(3)969--84, 1993.
[35] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference Learning Representations, 2018
[36] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
12

---

[37] Jonas Rauber, Roland Zimmermann, Matthias Bethge, and Wieland Brendel. Foolbox native: Fast adversarial attacks to benchmark the robustness of machine learning models in pytorch. tensorflow, and jax. Journal of Open Source Software, 5(53):2607, 2020.
[38] Max Revay, Ruigang Wang, and Ian R Manchester. Lipschitz bounded equilibrium networks. arXiv preprint arXiv:2010.01732, 2020.
[39] Gaurav Sharma and Jos Martin. MatlabO: a language for parallel computing. International Journal of Parallel Programming. 37(1):3-36, 2009.
[40] Naum Z. Shor. Quadratic optimization problems, Soviet Journal of Computer and Systems Sciences, 25:1-11, 1987.
[41] Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In S. Bengio, H. Wallach, Larochelle, K. Grauman, N. Cesa- Beanchinnci and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[42] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
[43] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[44] 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 on Machine Learning, pages 5276-5285. PMLR, 2018.
[45] Ezra Winston and J. Zico Kolter. Monotone operator equilibrium networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 107 10-18-0 Curran Associates, Inc., 2020.
[46] LeCun Yann, Cortes Corinna, and Burges Christopher J. C. Mnist handwritten digit database. 2010. [ATT Labs Online].
[47] Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, Cesa-Biances and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[48] Dongmian Zou, Radu Balan, and Maneesh Singh. On lipschitz bounds of general convolutional neural networks. IEEE Transactions on Information Theory, 66(3) 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] All the claims made in the abstract are justified in methodological sections 2 and 3 or experimental section[]
(b) Did you describe the limitations of your work? [Yes] We restrict ourselves to fully- connected ReLU monDEQs presented in Sections 2 and [ We also discuss the limitation due to the size of PSD matrices which can be handled by SDP solvers in Section 3.4
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work methodological and we do not foresee any direct negative societal impact of this
work.
(d) Have you read the ethies review guidelines and ensured that your paper conforms them? [Yes] The paper conforms to the guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] As presented in Section we consider monDEQ models, which is our main assumption, no further assumption is required for all our models.
(b) Did you include complete proofs of all theoretical results? [Yes] The methodological sections and and describe all proof arguments for the soundness of our models. Proofs of some technical lemmas are postponed to the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] The code is available https: htt///gtttbbbtt com http://c///eeee////////rrr////// S0eio// which is included in the main text.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We discuss training details in Section we report the code used for training at httpp::///// /:g:::///tttbt com/locusll http////aaammmoooonn.......
http/moootoneeeoee _eponne_pp_______ op__nt
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We report exact 95% binomial confidence intervals for proportions reported in Table
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We report in Section 4 the number of experiments, the average computation time and the type of personal computer used to perform all these experiments.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cited references for all the software used in our experiments.
(b) Did you mention the license of the assets? [Yes] We report licenses for all assets used in the paper in Appendix AA.5
(c) Did you include any new assets either the supplemental material or as URL? [Yes] experiments separate URL.
We include code to reproduce
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [No] We did not obtain any kind of new data.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] We did not obtain any kind of new data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] We did not use crowdsourcing.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We did not use crowdsourcing.
14


Reviews:
[{"review_id": "jUVk0QKyxfS", "reviewer": "Reviewer_kdsN", "summary": "Authors consider the certification of properties of deep equilibrium models. Some of these properties are novel and the mathematical apparatus employed is very elegant, if not completely novel.\n\n", "questions": "", "limitations": "", "rating": 7, "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": "Originality:\n\nThe authors consider the problem of verification of properties of monotone deep equilibrium models [1], while using techniques of polynomial optimization [2,3], or rather the first level of several hierarchies (wherein their coincide and which is known as Shor's relaxation). While both the problem and the use of polynomial optimization therein is relatively recent, the extent to which the present paper is \"original\" is much less than [1,2,3]. Specifically, the semialgebraic form or ReLU (line 109) and Putinar's positivity certificate (line 112 and following) are well known and the inequalities for testing Lipschitz constants (line 176) have been used previously, as suggested by the authors themseleves. So the contribution lies in \n-- generalizing the results related to Lipschitz constants to arbitrary L_q norms in Lemma 1\n-- utilizing a well-known \"minimum-volume enclosing ellipsoid\" technique in Lemma 2, for the first time in verification of neural networks.\nThis contribution is not particularly well articulated.\n\nQuality:\n\nStill, the problem of verification of properties of deep-learning approaches is of considerable interest, and the authors make several contributions. Crucially, these may enable further work, such as the use of the Frank-Wolfe methods in the ellipsoid model [5]\n\nComputationally, the authors find instances where the generalized SemiUB_f^q provides substantially better (cca. 8x) bounds than previous works. In Figure 1, they provide a very impressive example of the use of the ellipsoid model. Throughout, as can be expected, the computational results are limited to small-scale, hand-picked illustrations. \n\nIt may be worth pointing out that the contribution of the paper is essentially conceptual, rather than presenting a complete system or even a scalable approach. Other systems and approaches (not cited by the present authors), e.g.:\nhttps://arxiv.org/abs/2002.06864\nhttps://arxiv.org/abs/2007.10868\nhttps://arxiv.org/abs/2103.03638\nroutinely scale to millions of neurons, which may be impossible even with Shor's relaxation.\n\nClarity:\n\nThe text is not particularly well structured. For instance, Section 4.3 explains again the ellipsoid model, which has been introduced twice previously?\n\nThe discussion of the empirical results of Section 4.1 is hard to relate to the results of Table 2.\n\nThe authors do not cite important recent drafts, such as [4].\n\nSome of the sentences read a bit like Google Translate from some language other than English:\n\"The training of DEQs involves solving fix-point equations for which algorithmic success requires conditions.\"\n\n--\n[1] Chirag Pabbaraju, Ezra Winston, and J. Zico Kolter. Estimating lipschitz constants of monotone deep equilibrium models. In International Conference on Learning Representations, 2021.\n\n[2] Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimization for lipschitz constants of relu networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages\n375 19189–19200. Curran Associates, Inc., 2020.\n\n[3] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In H. Wallach, 384 H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.\n\n[4] Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy Liang, Pushmeet Kohli: Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming. https://arxiv.org/abs/2010.11645\n\n[5] S Damla Ahipasaoglu, P Sun, MJ Todd: Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optimisation Methods and Software 23 (1), 5-19 (2008).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This could help improve the applicability of neural networks to mission-critical applications, eventually.", "review_text": "", "extra_scores": {"ethical_concerns": "This could also give false hope of being able to certify properties of real-world applications of neural networks to mission-critical applications, which we are very far from.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "eCnjGzr5o_E", "reviewer": "Reviewer_ENDm", "summary": "The authors propose a framework for the robustness verification of monDEQs (monotone operator deep equilibrium networks). In this framework the paper introduces three different methods: one for direct robustness verification, one for Lipschitz constant estimation and one to compute the ellipsoid over-approximating all possible outputs for a set of inputs (in a norm ball).\nThe authors also show how the Lipschitz constant and ellipsoid in turn can be used for robustness verification.\n\nMathematically this is enabled encoding the monDEQ as the constraints of a (polynomial) optimization problem.\nIn particular, the fix-point $z = ReLU(Wz + Ux_{0} + u)$ is encoded using the semialgebracity of ReLU, similar to [27]*. This encoding as well as encoding $\\ell_{2}$ and $\\ell_{\\infty}$ inputs yields quadratic constraints. (Other $\\ell_{p}$-norms $p>2$ yield higher-order constraints.)\nThe resulting constraints are relaxed via Puntinar's positivity certificate and Lasserre's/Shor's relaxations into a SDP (semidefinite program), e.g. approximated lower-degree polynomials.\n\nFor the robustness verification approach the authors follow [27] and maximize the difference between any logit and the target logit. If all of these differences are $< 0$ a robustness certificate is obtained. To make the resulting problem tractable Shor's relaxation is applied.\nThe Lipschitz approach bounds the Lipschitz constant by bounding the supremum of the operator norm of the generalized Jacobian. This in turn, via Shor's relaxation gives an SDP.\nThe Ellipsoid model minimizes the volume of an ellipsoid that covers the output. Via a custom relaxation this also yields an SDP.\n\nAll methods are evaluated on an MNIST classifier with a single feed-forward fix-point layer where $z \\in \\mathbb{R}^{87}$.\nAll three approaches allow for robustness certification (although the robustness formulation performs the best).\nThe computed Lipschitz bound are close to those obtained by [24] for the $\\ell_{2}$-norm but much tighter for the $\\ell_{\\infty}$-norm. Lastly, in an example the authors showcase how the output-ellipsoid method allows insights into the model robustness.\n", "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": "Overall the paper is well written and appears to be technically sound.\nWhile well presented, the overall tone is very technical tone and readers might benefit from deferring technical details to the appendix in favor of more intuitive explanations (e.g. L112-L136).\n\nThe mathematical arguments in the main text seem correct. However, I did not check the proof of Lemmas 3 in detail. Based on it the construction of Lemma 1 it seems correct and so od the constructions in Section 3.3 and Lemma 2.\n\nThe main drawback of the approach appears to the scalablity of the SDP solver as well as the fact that the approach currently is tied to single-layer ReLU feed-forward models.\nIn comparison, [24] is much more scalable and less limited in architecture. Yet, their approach is limited to $\\ell_{2}$ Lipschitz constants.\n\nWhile the paper might benefit from a wider discussion of related certification approaches, the most closely related works (with one notable exception -- see below) seem to be cited.\n\nQuestions:\n- It seems the related work is missing a discussion of [Dathathri et al.]. In particular, can you comment on wether their solver would allow you to certify larger monDEQs as you name the underlying SDP solver as a key limitation in L252-254,L347.\n- In 3.2 you introduce the Lipschitz constant w.r.t the set $\\mathcal{S}$ and in L296 you say that you compute global Lipschitz constants. So you take $\\mathcal{S}$ as the set of all legal inputs?\n- The choice of specifically 87 neurons was made due to the capability of the SDP solver?\n- I am unsure why convolutional layers can not be handled, as they (as you point out in L351-352) can be encoded as linear layers. Is this again an issue of size?\n- While definitely intresting on a technical level, can you speak to possible uses of the output ellipsoid? It seems to be well suited to (multi-dimensional) regression tasks. How would it compare to a (local) Lipschitz constant in such cases.\n\nReferences:\n\nDathathri et al., Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming, NeurIPS'20\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss technical limitations and note that due to the theoretical nature of the work no direct negative social impacts can be foreseen.\nThis seems sufficient for this kind of work.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "eBQztGfW0We", "reviewer": "Reviewer_SqFE", "summary": "This paper introduces a semialgebraic representation of the monotone deep equilibrium model (monDEQ), a type of implicit-depth equilibrium network which guarantees the convergence of fixed-point iterations. This representation is used to derive SDP models for 1) certifying robustness, 2) estimating the Lipschitz constant, and 3) ellipsoid uncertainty propagation. These techniques show improved performance over existing methods for certifying robustness and bounding the Lipschitz constant of monDEQs. In addition, they apply to general $\\ell_p$ norms, unlike existing work.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Pros\n* This paper deals with an interesting topic which is gaining in importance as there is increasing attention on implicit-depth models. To date, there is very little work dealing with the robustness of implicit-depth models, and techniques that apply to standard DNNs cannot be applied. \n* The paper is quite well written and thoroughly presented. \n\n### Cons\n* The LBEN implicit network of [Revey et al.](https://arxiv.org/pdf/2010.01732.pdf) is not cited or compared to. It generalizes the monDEQ as well as admitting a Lipschitz bound during training.  \n* The experimental results are very small-scale. It would be nice to see larger-scale experiments, for example on CIFAR-10. Does the computational complexity of the SDPs rule this out?\n\n\nAdditional comments/questions:\n * I think that the characterization of monDEQ as \"less robust\" to $\\ell_\\infty$ attacks than to $\\ell_2$ attacks is a bit misleading. Isn't it common to to use attack radii of different scales when comparing attacks of different norms?  See for instance Appendix H  in [Wong et al. 2018](https://arxiv.org/pdf/1805.12514.pdf), where they scale $\\ell_2$ attacks up a lot so as to have comparable volume of the attack regions across norms.\n * In two places you state that the network is robust _if and only if_ the projection $\\mathcal{P}_i(\\mathcal{C})$ lies below the classification boundary (lines 245 and 322). I'm confused where the \"only if\" comes from?\n * For the Lipschitz model, why was $\\mathcal{S}$ chosen to be a single ball around all the test points, rather than an individual ball for each test point to be certified. Was this just for computational reasons? \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "SfrS6WJtAzV", "reviewer": "Reviewer_kbiJ", "summary": "Based on semialgebraic of $\\text{ReLU}$ and $\\partial\\text{ReLU}$, this paper proposes three models that are useful for certifying robustness, estimating Lipschitz constants and computing outer approximation ellipsoids.  The authors also use Putinar’s certificates to relax the non-convex problems to convex SDPs which can be solved efficiently. Experiments on MNIST demonstrate the effectiveness of all three models.", "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": "[Strength]:\n\n1 This paper is well-written and easy to read. The proofs are generally easy to follow (and pretty standard, to be honest).\n\n2 The theoretical and empirical results demonstrate the improvement over the previous approach [24].\n\n3 The empirical observation is interesting. ``DEQs are much less robust to $L^\\infty$ perturbations than $L^2$ perturbations, in contrast with classical DNNs.”\n\n[Weakness]:\n\n1 While the results in this paper are interesting, I think that they are somewhat incremental. The idea of utilizing semialgebraic of $\\text{ReLU}$ and $\\partial\\text{ReLU}$ is not new, even for monDEQs, see Proposition 5 in [c1], please. The approaches used are standard techniques. Moreover, as the authors point out, the size of the corresponding PSD matrix seems an unavoidable limiting factor. Thus, the proposed method appears troublesome to be extended to large models.\n\n2 The relationship between the three models is unclear. In line 142, the authors say that “each model can be eventually used to certify robustness but they also have their own independent interest”. However, I do not find more description of “their own independent interest”. Did I miss something? There is a lack of discussion on the motivation of the three models.\n\n3 The experiment is relatively weak. The empirical results are still on very small scales and not quite convincing. The authors conduct detailed comparison with [24], but the method are only evaluated on MNIST. \n\n4 In line 43-45, “... DEQs have the definite advantage of being relatively small in size compared to DNNs and therefore...”. I do not agree with this argument. DEQs can be very large in size. As illustrated in previous empirical results, DEQs requires comparable parameters to achieve performance comparable to DNNs.\n\n5 In Conclusion and Future work, the authors admit the limitation of the method. I really appreciate it. However, after reading your future work, I cannot feel the potential of this paper. I just feel that this paper is not well ready.\n\n[Additional questions]\n\nThe authors observe that ``DEQs are much less robust to $L^\\infty$ perturbations than $L^2$ perturbations, in contrast with classical DNNs.” To be honest, I think this experimental result is quite interesting. But is this only an empirical observation? Moreover, as I mentioned in Weakness 4, the experiments are on very small scales (MNIST), it seems that this observation is not quite convincing. I will appreciate it if you provide more explanations that are theoretical. \n\nOverall, there is still a lot of room for improvement in this paper. I suggest weak acceptance for this paper, but I believe that with further refinement the authors could submit a better version to a future conference. \n\n[c1] https://openreview.net/forum?id=bodgPrarPUJ.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48 hours"}, "extra_text": {}}, {"review_id": "753iRcfR8eh", "reviewer": "Reviewer_UG93", "summary": "Summary: \nThe authors present three semialgebraic models that are applicable to fully connected monDEQs that are used to provide certificates of robustness of three different flavors. These are then applied to a monDEQ trained on MNIST and the resulting certificates are tighter than those generated by previous Lipschitz bounds.", "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": "Originality: \nWhile the formulation of robustness or lipschitz certificates in a semialgebraic model has been applied to deep neural networks in the past, such standard approaches have not yet been tried on monDEQs, which may be more amenable to these techniques given their smaller parameterizations. The ellipsoidal model is a novel form of reachability analysis to the best of my knowledge, and is possibly the most interesting novelty presented in this work. Several important works are not cited with respect to Lipschitz estimation: Jordan & Dimakis have several papers exactly computing or estimating Lipschitz constants (https://arxiv.org/abs/2003.01219, https://arxiv.org/abs/2107.02732), and these works (https://arxiv.org/pdf/2004.13135.pdf, https://arxiv.org/pdf/1908.06315v4.pdf ) discuss Lipschitz constants of implicit models. \n\nClarity: \nThe main contributions are clearly stated and the paper is fairly easy to read. The parallelism in the exposition of each of the three semialgebraic models is useful for cleanliness and clarity. \n\nQuality: \nThe work is theoretically sound and the proofs I checked seem to be devoid of typos. Accepting that this work is primarily theoretical, the experiments are still quite limited. With no extra technical innovations, more experimental evaluations could be performed to examine: how performance/runtime are affected on monDEQs of varying #neurons or training regularizers/hyperparameters; the size of the safe-radii guaranteed by the Lipschitz bound; monDeqs trained on different datasets. Further, more traditional Lipschitz estimation techniques could be applied and compared against: e.g. CLEVER. Additionally, other POP-certification papers exploit sparsity to improve performance, but no mention of such approaches were discussed here: any attempts to improve runtimes would greatly strengthen this paper. \n\nSignificance: \nThe broader community has not yet latched on to monDEQs as a viable alternative for DNNs, so certification of these networks does not seem very useful for the community-at-large. On the other hand, the relatively small size of these nets can accelerate SDP-based certification schemes, and breakthroughs in this line of work could be a clear strength of DEQs over more traditional DNNs. \n\nOverall: \nThis is a cute paper that uses reasonably standard techniques and only minor technical innovations to provide certifications on an interesting, but not-very-popular, class of models. The theory is sound and interesting, but the experiments are slightly limited.  \n\nSome typos/bugs:\n- Some of the references in the appendix don't line up to the main bibliography. For example, ref 5 (line 526-527) in the appendix should not point to CNN-cert. \n- There is a bug in the formulation of dual norms. Specifically, the second-to-third line in equation 8 is incorrect. Indeed, in the third line, w can be chosen to be zero and v can have unbounded norm, driving the objective value to infinity. Why not just keep the semialgebraic constraint that ||v||q*<= 1? (or alternatively flip the inequality constraining the q-norm of w)? This bug carries over to the main statement of Lemma 1. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations were discussed in the conclusion, but no attention was paid to the societal impacts of this work. Certification papers are quite benign, so it is unclear if such ethical discussion is required. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper got 4 "Marginally above the acceptance threshold"s and 1 "Good paper, accept", all with relatively high confidences. The author rebuttals mostly addressed the concerns from the reviewers. Reviewers UG93, kdsN, SqFE, and ENDm were all in favor of accepting the paper in their post-rebuttal opinions. Thus the AC recommended acceptance. Nonetheless, some issues remain, e.g., scalability of the experiments, a bit overselling, etc. The AC also found that the "certification" problem, the core topic of the paper, was not clearly defined (lines 29-30 may allude to, but still in a vague manner). Hope these issues could be addressed in the revision. 
Decision: Accept (Poster)