Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper gives a novel characterization of well-posedness for implicit networks based on the one-sided Lipschitz constant (osL). This follows in a line of work of other such characterizations [1,2,3,4], but differs in that well-posedness is guaranteed by a constraint on the osL of the weights matrix, which can be wrt arbitrary norms. The authors focus on the $\ell_\infty$ norm, for which they show accelerated convergence of dampened fixed-point iterations.  They also drive a bound for the Lipschitz constant of the network wrt the $\ell_\infty$ norm on the input space, which is more natural for achieving robustness than the $\ell_2$-based Lipschitz bounds of [3] and [4]. They train networks while enforcing well-posedness and using the Lipschitz bound as a regularizer, and demonstrate the empirical robustness of the models.
main_review: Overall, I think the connection between non-Euclidian contraction theory and implicit networks is quite interesting and will be beneficial for people working in this area. However, there are a number of comparisons to existing works that are lacking, both in the theory and experiments (see below). Additionally, some of the benefits described in the theory are not well demonstrated by the experiments.

This paper addresses an important topic, since implicit networks are growing in practicality and popularity, so understanding and improving their robustness properties is important. If the authors could address some of my concerns, I'd be inclined to increase my score.

### Pros:

*  The application of non-Euclidean contraction theory to implicit networks appears to be novel and provides a nice way to guarantee contraction wrt the $\ell_\infty$ norm and well-posedness. 
* The accelerated convergence in the $\ell_\infty$ norm seems important, since improving convergence times has been a practical consideration for implicit networks.
* It's great to see that the Lipschitz bound can be computed for arbitrary norms via Lim's lemma, which is more general and elegant than the $\ell_2$ bounds in [4].
* Bounding the Lipschitz constant wrt the $\ell_\infty$ norm is valuable since it leads to robustness to $\ell_\infty$ attacks, which are arguably more natural than $\ell_2$ attacks.

###  Cons:
* I think the paper would be much improved by better comparisons to exiting work. In particular, [4] also derives Lipschitz bounds for MON but is not cited.  It looks like Theorem 3 generalizes the bound in [4], while being a more elegant way of deriving it. 
* It would be good to understand how the set of networks characterized here compares to that of [2] and [3]. E.g. along the lines of Figure 2 in [3], which does a nice job of comparing the constraint in [2] and [3], showing how [3] is less restrictive. Do the osL-bounded networks correspond exactly to the set of MON networks in [2] if using $\ell_2$ instead of $\ell_\infty$ norm? I believe this is stated in Appendix D but could be elaborated on in the main text.
* I don't know how much of the theory is novel outside of the implicit networks literature. Could the authors comment on how Theorem 3 compares to the results in [5]?
* It is unclear how the osL constraint is enforced during training. In Lemma 9, appendix B, the authors provide a parameterization of the well-posed network like those in [2] and [3], which allows for unconstrained training. But that doesn't seem to be used during training here?
* Experimental comparison to LBEN [3] is missing, and it is unclear what value of monotonicity parameter is used for MON [2]. As is shown in [4], this parameter controls the robustness (at least to $\ell_2$ attacks).
* It would be nice to see certified robustness, since the authors provide a concrete bound on the $\ell_\infty$ norm.
* It would be nice to see results on CIFAR-10, since robustness on MNIST is not as meaningful. 
* It's unclear what the take-away from the first experimental section is meant to be.
* It would seem important to show if the accelerated convergence can be realized experimentally, and compare convergence to that of LBEN/MON. 

### References:
* [1] [El Ghaoui et al. 2019. *Implicit deep learning*](https://arxiv.org/pdf/1908.06315.pdf)
* [2] [Winston and Kolter 2020. *Monotone operator equilibrium networks*](https://arxiv.org/pdf/2006.08591.pdf)
* [3] [Revay et al. 2020. *Lipschitz Bounded Equilibrium Networks*](https://arxiv.org/pdf/2010.01732.pdf)
* [4] [Pabbaraju et al. 2020. *Estimating Lipschitz constants of monotone deep equilibrium models*](https://openreview.net/forum?id=VcB4QkSfyO)
* [5] [Adly et al. 2014 *On one-sided Lipschitz stability of set-valued contractions*](https://06658af9-a-62cb3a1a-s-sites.googlegroups.com/site/adontchev/lim.pdf)
limitations_and_societal_impact: * The authors state that the work is fundamental research so will not lead to negative societal impact. 
* In terms of limitations of the work, it would be great if the authors could report runtime and number of function evals for their models, which are typically quite high for such models.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a thorough analysis of constructing provably convergent equilibrium networks in the non-Euclidean space. Instead of directly requiring Lipschitzness as in prior works (which mostly dealt with $L_2$), the authors show that we can further relax the constraint by considering one-sided Lipschitzness and exploit the contraction theory via semi inner products. The experimental results of the paper seem to demonstrate the validity of the theoretical results and the paper provides empirical evidence on the potential application of the theories in improving implicit networks' adversarial robustness.
main_review: Overall, I enjoy reading this paper, which provides a valuable discussion on how to extend (and exploit) implicit networks' stability analysis to non-Euclidean spaces. I believe this paper will be of interest to the relevant audience in the NeurIPS community and extends the current efforts (as pointed by the authors in the paper) to build provably stable implicit deep networks and scale them to more general settings. At the same time, while the final application of the theories (e.g., Thm 1 and 2) are for the equilibrium networks, the techniques used in this paper and part of the conclusions have been built on top of prior works that studies; e.g., [1,2,3]. Moreover, I find some critical empirical analysis missing. In summary, I find the following strengths and weaknesses:

Strengths:
- Clear explanation of the theory. I checked most of the proof (mainly appendix A & C) and they are well-written and correct. The theoretical motivation for using osL-ness and damped fixed point iteration is well explained and quite smart.
- The paper extends prior works to non-Euclidean space and presents a new framework/condition through which we can build well-posed implicit networks (i.e., practical significance).

Weaknesses:
- Limited theoretical significance (to clarify, the application of such kind of contraction analysis to implicit neural networks is novel, and probably significant; but not the osL-based contraction theory itself).
- Missing experimental details and comparisons (e.g., with Revay et al., which dealt with $L_2$; and on a wider range of experiments). The comparison with El Ghaoui is good but it's still only a weak baseline.
- Still relatively weak empirical evidence on the benefit of applying the analysis in practice (i.e., having this larger parameter search space). Specifically, the advantage of using the proposed $L_\infty$-based and relaxed-constraint formulation over MON or even the LBEN model in Revay et al. is not clear to me when in the presence of strong adversarial attacks, such as PGDM and FGSM (see Appendix D). 

-------------------------------------------------------------

More questions/comments:

1. One particular theoretical benefit of the approach is the use of osL analysis and measure $\mu_{\infty [\eta]^{-1}}(A)$ rather than the simplest matrix norm. This begs the question of how the pick of $\eta$ affects the empirical performance (theoretically it's only a matter of existence issue, but I'm more interested in practical implications). The authors picked $\mathbf{1} \in \mathbb{R}^n$ here. Could the authors expand more on this? Moreover, in the submitted code "trainMNISTmodel.py", I did not find any mechanism for actually ensuring $\mu_{\infty, [\eta]^{-1}}(A) < \gamma$ (you did compute the LHS, which is
```python
X = torch.abs(model.A) - torch.diag(torch.diag(torch.abs(model.A))) + torch.diag(torch.diag(model.A))
matmeas = torch.max(X.sum(1))
```
but didn't quite use it; but it's likely that I missed something). How is the diagonally weighted measure preserved during training?

2. One question that I found to be absent in the empirical discussion is the convergence rate. Although damped fixed point iteration helps us relax the Lipschitz condition a bit, it is also known to possibly bring the extra risk of slower fixed-point convergence than the non-average iterations. In the case where $\alpha$ is small, I wonder how efficient this (albeit provable) convergence is?

3. You may want to cite [4] as well, which is clearly related (but in Euclidean space). 

4. It seems to me that the results of Sec. 4 should be able to generalize even further to the case where $Ax$ is replaced by a non-linear transformation $\Lambda(x)$, where $\Lambda$ is everywhere differentiable. In that case, you only need to replace the $A$-based results in the conclusion with $D\Lambda$. Is there any reason for not doing so in theory and in practice? E.g., the matrix measure of $D\Lambda$ would be hard to compute?


[1] https://arxiv.org/pdf/2103.12263.pdf
[2] https://hal.archives-ouvertes.fr/hal-01313105/document
[3] https://link.springer.com/content/pdf/10.1007/978-3-540-72234-2.pdf
[4] https://openreview.net/pdf?id=VcB4QkSfyO

-----------
-----------

#### Post-rebuttal

I appreciate the authors' response. Overall, while I agree this paper has presented a solid work, I personally would love to see larger-scale, more practical, and more performant results of these provable implicit models and what we could achieve with them.
limitations_and_societal_impact: This is a theoretical work and I think the limitations are well-addressed (mainly in the form of assumptions and sufficiency analysis in theorems).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new well-posedness condition for DEQs that is less conservative than the l_\infty norm proposed in [El Ghaoui et al., 2019]. A Lipschitz regularization is also developed to improve the robustness to some classes of adversarial perturbations. Several experiments show the effectiveness of the proposed method.
___________________________________________________
The author responses address most of my concerns. So I raised the score and tended to acceptance. 
main_review: Studying the well-posedness and convergence of the fixed-point equations of DEQs is very important. Based on contraction theory for the l_\infty norm, the paper develops a new well-posedness condition for DEQs. The paper is well-written and organized. However, the advantage over MON is not clear. Note that MON does not consider the robustness.
limitations_and_societal_impact: I have two main concerns. 
First, how to choose \gamma in (16) for a DEQ training problem? Also, it is better to study the effect of different settings of \gamma. Why set \gamma = 0.5 in subsection 6.1 and \gamma=0.95 in subsection 6.2?

Second, it is better to plot the running time vs. test accuracy, e.g., in Figure 2. Does the proposed method outperform MON and l_\infty norm in training efficiency?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the implicit nn with non-Euclidean norms. In particular, the authors give the sufficient condition for the well-posedness of the fixed point problem under any norms, and provide the corresponding contraction factor. Consequently, the author derives the Lipschiz constant of their implicit model induced by the infinity norm and use the model for robustness tasks.
main_review: # Strength
This paper studies an important and interesting area. Implicit modelling starts to gain more attention as it's a good method to save memory while achieving comparable performance. The particular problem tackled by this paper is also important as previous results mostly focus on l2 norms and it is important to extend the existing results to other norms like l_infinity norm. The derivation is non-trivial. Although I didn't check the proof detail, the claims do seem sound and the paper is written clearly. 

# Weakness
- In terms of writing, this paper has several big chunks of theorems but lack sufficient discussion of their significance. For example, the osLip is a weaker notion than the Lip constant, I think it's helpful that the author can provide some example where these two notions differ by a lot. 
- A comparison of the matrix measure and largest eigenvalue may also be helpful. For example, in corollary 5, the sufficient condition for the uniqueness of fixed point is that u(A)<1. I think this coincide with the largest eigenvalue of A if the underlying norm is l_2 (correct me if I'm wrong). It is valuable to include such comparisons in the discussion. I do realize that the authors have discussed about the PF eigenvalue used in El Ghaoui et al., I would also like to see a comparison to the condition used in Winston and Kolter.
- The training problem is framed as a constrained optimization problem. To me this is not a desired property. I would guess that at every gradient step we have to project the updated parameters on the constrained set and it can be very time/resource consuming. It would be great if there's a way to re-parameterize the weights as done in Winston and Kolter.
- More training details can be added. For example, the dimensions of A, B, C, D are missing in section 6. I would also want to see two more results: how many iterations does it take for forward and backward damped iterations, and what's the wall-clock time to train these models.


limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper originally got 2 "Marginally above the acceptance threshold"s and 2 "Marginally below the acceptance threshold", all with relatively high confidences. The major challenges include a number of comparisons to existing works being lacking both in the theory and experiments, relatively weak experiments, missing some important details, etc. The authors did heavy rebuttals, including presenting extra experiments, and they seemed to take effect. Reviewer xt3G raised his/her score from 5 to 7. Reviewer ivrZ also raised to 7. Considering that the extra experiments and clarifications can be easily incorporated in the revision, the AC deemed that the paper is acceptable, thus recommended acceptance. 
Decision: Accept (Poster)