Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: **Overview**

This paper purports to study training deep equilibrium models by studying the optimization dynamics of deep *linear* equilibrium models. The original deep equilibrium model is formalized as follows: Given a training dataset $(x_i,y_i)$ for i = 1,...,n where $x_i \in \mathcal{X}\subseteq \mathbb{R}^{m_x}$ and $y_i\in \mathcal{Y}\subseteq \mathbb{R}^{m_y}$ are the $i$-th input and output, respectively. The goal is to learn a predictor from a family $\mathcal{H} = \\{\{ f_\theta : \mathbb{R}^{m_x} \rightarrow \mathbb{R}^{m_y} | \theta\in\Theta\}\\}$. Then, instead of trying to map $x$ to $y$ using finite amount of layers, deep equilibrium models assume infinite number of layers, and the output $z^*$ of the last hidden layer is defined by
\begin{equation}
    z^* = \lim_{l\rightarrow \infty} z^{(l)} = \lim_{l\rightarrow \infty} h(z^{(l-1)};x,\theta) = h(z^*;x,\theta)
\end{equation}
where $h$ is some continuous function of choice. 

In particular with deep equilibrium **linear** models, $h$ is constrained as follows:
\begin{equation}
    h(z^{(l-1)};x,\theta) = \gamma\sigma(A)z^{(l-1)}+\phi(x)
\end{equation}
where $\phi(x)$ is a feature map of $x$ and transforms $x\in\mathbb{R}^{m_x}$ into $\phi(x)\in\mathbb{R}^m$. $\theta = (A,B)$ are two trainable matrices, where $A\in\mathbb{R}^{m\times m}$ is for computing each hidden output and $B\in\mathbb{R}^{m_y\times m}$ is for computing the final output of the network. $\gamma \in (0,1)$ is some positive real number, and $\sigma$ is a nonlinear function to ensure the existence of the fixed point $z^*$. This model is linear in z. The objective function of this deep equilibrium linear model can be written as follows:
\begin{equation}
    L(A,B) = \sum_{i=1}^n \ell\left( B\left( \lim_{l\rightarrow\infty}z^{(l)}(x_i,A)\right),y_i\right)
\end{equation}
where $\ell$ is some choice of loss function.

Then this paper provides some motivations behind studying the dynamics of these deep equilibrium linear models by presenting some interesting comparisons between deep equilibrium linear models and "normal" linear models and additional, less interesting comparisons with fully-connected feed-forward deep neural networks (FNN), using standard image datasets CIFAR-10, CIFAR-100 and Kuzushiji-MNIST. In their tests, the deep equilibrium linear models outperformed both linear models and FNNs. 

The main results from this paper is uncovering the dynamics behind these deep equilibrium linear models. This paper provided a sequence of proofs that shows linear convergence of these models step by step, under the assumption that the loss functions $\ell$ are differentiable, which is satisfied by some standard loss functions, such as square loss, losgistic loss, and smoothed hinge loss $\ell(f_\theta(x),y) = (\max\{0,1-f_\theta(x)y\})^k$ with $k\geq 2$. Also, despite of non-convexity of the loss functions, it is shown in this paper that a global minimum $L^*$ always exists and under their assumptions, the deep equilibrium linear models will always converge to the global minimum linearly.

**Strengths**

The main strength of this paper is that it brought  some interesting insights into deep equilibrium  models, and they showed their results rigorously. The definitions and propositions are clear enough for readers with some analysis and machine learning background to fully understand. 

Since the dynamics of deep learning models is an open field of research and isn't discovered fully, this paper will definitely contribute to the deep learning field in understanding the dynamics and convergence theory of these deep equilibrium linear models, and potentially benefiting researches on understanding more general deep learning models.

**Weakness**

Although this paper brought some nice ideas, some of the methodologies are not quite convincing. For example, in the experiments shown in this paper, they  compare performance of deep equilibrium linear models with linear models and deep neural networks. Especially in the comparison with the deep networks, it doesn't seem that the networks are deep enough for the comparison to be compelling. Also in the same experiments, they assumed the true data distribution is approximately given by a deep equilibrium linear model and generated data according to this model -- i.e. the data is only semi-"real". It would be better to show that the deep equilibrium linear model outperforms other models under a more general setting.

Throughout the entire paper, it's unclear what are the contributions. To be specific, in the first two sections, it's unclear whether they want to show the trainability of the deep equilibrium linear models or learn the dynamics of these models. Also, some of the interesting aspects of this paper were missing some details. For example, one would be interested in seeing why exactly can the deep equilibrium linear models outperform linear models, since they are both linear and the only difference is how they are trained. In the last two sections of this paper, they also brought up *implicit bias*, which would be another interesting topic to dive into. It would be great seeing more comparisons on those aspects.
review_title: Nice framework but not addressing the central question

final_score: rating: 7: Good paper, accept
review_content: The paper discusses the theory of deep equilibrium models with linear activations. The model weights are softmaxed to ensure that inference converges to a fixed point, a necessary condition for training deep equilibrium models. The paper then analyzes the gradient flow dynamics of such models. The main result is that linear-rate convergence is guaranteed for a class of loss functions, including quadratic and logistic losses, when training with gradient flow. This conclusion is supported by experiments conducted in a teacher-student-like setup, where the labels are generated by a teacher deep equilibrium model, showing that training does converge in practice.

Deep equilibrium models represent a novel way to train neural networks, and not much is known about them yet theoretically. It is important that we understand the dynamics of such models better, and this paper is a good step in that direction.

Suggested improvements:

1. Definition 1 has a typo: On the right-hand side of the inequality there shouldn't be a gradient.

2. The main results are presented clearly, and the paper is generally easy to read. The only exception is section 3.2 on the connection with trust region Newton methods, which I did not understand. I recommend clarifying the intuition behind Theorem 2, as well as the main message of this section.

review_title: Convergence guarantees for linear deep equilibrium models

final_score: rating: 7: Good paper, accept
review_content: This submission studies the dynamics and convergence properties of "deep equilibrium models", which are parametric fixed-point iterations corresponding to the infinite depth limit of "weight-tied" neural networks. As the authors point out, these networks differ from deep linear networks and networks in the NTK scaling in that the optimization remains nonlinear w/r/t the parameters. The authors prove two results: first, they establish linear convergence to the global minimum under the relatively strict assumption of a "local" PL-inequality; secondly, they show that the dynamics of the deep equilibrium models differs from gradient descent dynamics and, in fact, is related to a trust region Newton method.

The first theorem is nice and well-presented, but I think the issue of the radius over which the PL-inequality holds could be better discussed. I could not tell whether or not the convergence depends on starting within the locally smooth and quadratically bounded region of the loss. 

The second theorem, regarding the nature of the dynamics, lacks a clear interpretation. Basically, all that is said is that the dynamics is distinct from what would be seen in a linear model, and it's not clear that this dynamics has anything to do with implicit regularization, as the authors suggest. I would recommend the authors clarify the discussion of this result. 

The experiments are somewhat bizarre and I felt that they were a little misleading about the representative power / potential of these models, but perhaps I did not fully understand the set-up and intent. The authors randomly sample a deep equilibrium model and then use it to represent a conditional probability distribution where the conditioning is with image data. Then, the authors fit various models to this distribution and show that the deep equilibrium models (which is precisely the underlying function representing the distribution) has better performance than other classes of functions. I think the description in this section could be vastly improved, perhaps presenting this more akin to a student-teacher problem. 

 
review_title: a clear analysis of deep equilibrium models

final_score: rating: 7: Good paper, accept
review_content: > Summary: This work focuses on the study of (global) convergence and gradient dynamics of a recently proposed family of models, the deep equilibrium  (linear) models (DELM) under common classes of loss functions. Exploiting the Neumann series convergence and the PL inequality analysis, the authors proved convergence to global optima of DELM without prior assumption on the width m of the model (relative to the number of data n). 

Here is my general opinion:

While deep linear models in general (as the authors acknowledged) has been widely studied, and despite the extreme simplicity of the DELM when compared to the original DEQ model that Bai et al. [1] studied, I found this work *interesting and important* in establishing a solid foundation for the theoretical study of this class of implicit-depth models. The authors managed to demonstrate that the gradient dynamics and convergence assumptions of DELM is __indeed__ different from typical "stacked" deep linear models that prior approaches study, such as deep linear ResNet. And throughout the arguments of the paper and the proof in the appendix, I can tell how the "equilibrium" property of DELM is making the story different, and think this paper sets a good starting point for future similar in this direction for general implicit-depth models. But still, the paper has a limited scope in terms of the structure it studies.

Pros:
1. One of the first theoretical works on the gradient dynamics and convergence properties of the deep equilibrium models [1] (and implicit models in general [2,3]), which are quite different from conventional deep networks.
2. Clear notation and theoretical insights, with proof relatively easy to follow. The proof seems overall correct (there are some that I didn't check closely though).
3. Clear discussion of the relation, including (and especially) the differences of the prior analysis on deep linear neural networks.

Cons:
1. The very definition of DELM, which the author provided a particular formulation of, is of limited scope (see my comment below that expands on this point).
2. The empirical studies to validate the conclusion of the theoretical results could be strengthened.

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

I have some comments/questions for the authors, detailed below:

1. The major limitation that I found while reading the discussion and the proof of this paper is that while the authors claim to study deep equilibrium **linear** models, the insights mostly only apply to the models converging with Neumann series guarantee, and can be written in the form $BU^{-1} \phi(x)$. I understand the motivation for fixating a provably convergent equilibrium model formulation. But:

    a) A provably convergent deep equilibrium linear model doesn't need to be Neumann (for its Jacobian) for the implicit function theorem to work. In the simplest case, the fixed point of a function $h(x)$ on 2D can have a local derivative with absolute value > 1. This certainly implies that repeatedly unrolling the function $h(x)$ may not converge, and yet **there still is** a unique fixed point and one can reliably solve for it (see [4]). However, without the nice Neumann series form, which allows one to write $(I-\gamma \sigma(A))^{-1}$ as a closed-form representation for the "infinite-depth" network forward pass, I don't think the theorems will hold directly. Typically, the $(I-J)^{-1}$ term should only appear in the implicit function theorem, which is used for the backward pass. I expect the authors to clarify this further.

    b) The very design of $\sigma(A)$ in the model the authors study is a bit bizarre to me. Why applying a "softmax" on the weight? Is it just to ensure that proposition 1 holds (i.e., that you have a handy, provably-convergent linear model)? The authors stressed a few times that the $h(\cdot)$ function is thus "non-linear" w.r.t. $\sigma(A)$, but I fail to directly see why it matters so much as the model is still linear w.r.t. the input (it's really a one-linear layer; though the inverse from Neumann does make a difference on A), and in terms of the gradient dynamics, the major difference this makes will merely be $\frac{\partial \sigma(A)}{\partial A}$. I might have missed something here and would appreciate if the authors can clarify.

2. I didn't quite get the specific point the authors were trying to make in Section 3.2 in terms of the implicit bias. Could you expand on that?

3. Overall, I feel that the empirical support of the theoretical findings can be stronger, for instance, by inspecting different initialization $(A_0, B_0)$, or validating the radius discussion at the end of Section 3.1 for the logistic loss. Like in Zou et al. [5], some synthetic data could probably work just fine. What is the reason for only using 200 images from the MNIST/CIFAR datasets? Is it to keep the size of $\Phi$ small (but I didn't see the authors report anything about it in Section 2.2). And since the primary purpose of Sec. 2.2. is to "discuss whether the model would also make sense in practice" (which I take to mean that you only want to compare the test accuracies coming out of these models), wouldn't a 200-sample version of MNIST/CIFAR too small to draw a robust conclusion on this?

4. One that I think could be useful for further thought is the convergence property not just for GD, but also SGD, like Zou et al. provided in [5] (up to a probability).

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

Minor things:

  - i) Page 3: "the outputs of the deep equilibrium linear models $f_\theta(x)= \cdots$ are nonlinear and non-multilinear in the optimization variables $(A,B)$." Non-linear in even $B$?
  - ii) Page 14: $V_{q*}$ --> $B_{q*}$
  - iii) Page 16: $\nabla_F L(A,B)$ --> $\nabla_A L(A,B)$

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

- [1] https://arxiv.org/abs/1909.01377
- [2] https://arxiv.org/abs/1908.06315
- [3] https://arxiv.org/abs/2009.06211
- [4] https://arxiv.org/abs/2006.08591
- [5] https://arxiv.org/abs/2003.01094
review_title: R1: Important theoretical study of deep implicit models, though with limited scope

Meta-review: The paper analyzes the gradient flow dynamics of deep equilibrium models with linear activations and establishes linear convergence for quadratic loss and logistic loss; several exciting results and connections, solid contribution, accept! 
Decision: Accept (Spotlight)