Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: Pros:
1. 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.

2. 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.

Cons:
1. Some of the details about theoretical formalism and empirical evaluation was not clear to me (see my comments below).

2. 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).

I have a few other questions:

1. 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)?

2. Is it possible to define a class of DEQs that have multiple fixed points? 

3. Can one equivalently identify a class of fixed-point obtaining implicit networks for other analysis types? e.g., CROWN, DeepPoly, or Zonotopes?

4. 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.

5. Is it possible to train IBP-MonDEQs for perturbations that cannot be exactly captured by intervals?

6. 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.

7. 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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.  
main_review: Strengths:
* This paper derives parameterizations for DEQ such that the fixed-point solution of the DEQ augmented with IBP bounds exists and is unique.
* The paper theoretically show that a single IBP-MonDEQ layer can express all explicit feedforward networks. 
* The paper empirically demonstrates the certified defense of IBP-MonDEQ.

Weaknesses:
* 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).
* 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_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.

=========Post-rebuttal updates=========

Thanks 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). 

This 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.

But 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

The 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:
- 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)?
- 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.
- 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?
- 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?

Minor comments:
- Isn't (2.2) generally defining lower/upper bounds rather than IBP specifically?
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).
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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. 

Please address these questions/comments in your rebuttal. I am willing to upgrade my confidence score if you can address all of these questions.
1. 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? 
2. 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.
3. 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?
4. 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}.
5. Can you explain further the last sentence of the proof of Lemma 3.4? I don't understand how (3.8) follows.
6. 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?
7. 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).

Minor points:
- Missing space after period. "...via closed-form functions.These layers are promising ..."
- Winston & Kolter (2020). The arxiv version in your references is now published in NeurIPs.
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.
review_title: null

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)