Separation and Bias of Deep Equilibrium Models on Expressivity and Learning Dynamics

Thank you for your careful review and thoughtful questions and comments. Please see our response below.

Factors influencing DEQ's separation and bias need further discussion. For instance, is DEQ's implicit bias caused by initialization, the use of implicit differentiation in solving DEQ, or different gradient descent methods? The reasons behind its differences from FNN should be explained in detail.

Thanks for your suggestion. Our result of the bias of DEQ is indeed influenced by the optimization algorithms, the initialization, and possibly by the use of implicit differentiation (Although we do not consider the use of implicit differentiation in this paper). It is interesting to study the bias caused by other gradient algorithms such as Adam. We believe that different gradient algorithms may bring different biases on DEQ as it has been shown empirically that different gradient algorithms cause different implicit biases on FNNs in many works. The initialization is also an important factor and our Theorems also need assumptions on the initialization. We consider the Gradient Descent algorithm and a usual initialization in this paper since the paper proposes the first analysis for the implicit regularization of DEQ beyond the NTK regime. Different algorithms and initializations will be studied in future works. Regarding reasons why DEQ has different expressive power and bias from FNN, we believe that it is mainly because of the difference in architecture. We will add discussions to elucidate these issues in the final version of the paper.

Besides, the following relevant papers should be cited and discussed.

Thanks for your valuable feedback. We will include all papers you mentioned in the final version of the paper.

Can the implicit bias of DEQ be understood from a lazy training perspective?

We think that our result on the bias of DEQ is beyond the lazy training regime because the diagonal linear DEQ we consider is essentially a nonlinear model, albeit with some simplifications. Unlike the lazy training scenario, we do not require the DEQ to be sufficiently wide, nor do we require the updates to stay in a small domain near the initialization. Therefore, our result of the bias of DEQ is beyond the lazy training perspective. Nevertheless, our proofs of the convergence of DEQ indeed utilizes some techniques similar to those of NTK. We show that the simplified DEQ is convex in a relatively large domain under some assumptions of the initialization and we use induction to ensure the updates remain within this domain throughout the training. Thank you for your valuable question and we hope our response address your concerns.

In Theorem 4.1, how is α defined? For example, if α is large and close to 1, then m1−α would be particularly small, implying that Nf would have almost no width.

We are sorry for the confusion in the statement of Theorem 4. In our proof, we actually assume that the width $k$ is upper bounded by $2^{m^{1-\alpha}-1}$ instead of $2^{m^{1-\alpha}-2}$ (see the equation before line 424 in Appendix) so that $k$ can take value $1$ even when $\alpha$ is large and very close to 1. Although the original statement is not wrong as the inapproximability pertains to a shallower FNN with less expressive power, it does lead to a problem of defining $\alpha$ to avoid FNN having no width. We will address this issue in the final version of the paper. In this case, $\alpha$ is an integer in $(0,1)$, making $2^{m^{1-\alpha}}-1$ sub-exponentially large when $m\to \infty$. Thank you very much for your valuable feedback.

Will the conclusion differ under different circumstances of DEQ? For instance, if the inner structure is a ResNet or Transformer, will the conclusion change? Could the authors provide more experiments testing different backbones?

It is very interesting to consider the expressivity and bias of DEQ when the inner structure is a ResNet or a Transformer. The expressivity and bias of DEQ depends on the specific inner structure so that the conclusions may change. However, this paper aims to provide the first analysis for the implicit regularization of DEQ beyond NTK regime, so we focus on the fundamental FFN as the inner structure. We will analyze the properties of DEQ with other inner structures in the future. To further investigate this issue, we use Grad-CAM [1] to generate the saliency map of Multiscale DEQ (MDEQ [2], which is a variant of ResNet-DEQ) and compare it with that of ResNet-50 trained for image classification on ImageNet. The saliency map highlights the regions that are crucial for the model’s prediction, which can be regarded as the features. It is shown that MDEQ allocate attention to more features such as the fences and trees in the background, indicating that MDEQ may generate dense features. Please see our attached PDF file in Author Response for details.

[1] Grad-CAM: Visual Explanations from Deep Networks via Gradient-Based Localization, ICCV 2017.

[2] Multiscale Deep Equilibrium Models, NeurIPS 2020.

Additionally, does the conclusion hold for various downstream tasks of DEQ, including classification, regression, or other tasks?

The conclusions for the expressive power of DEQ is not influenced by downstream tasks. However, the bias of DEQ may differ depending on the specific downstream tasks. For example, in classification tasks, the loss function is typically chosen as logistic loss or cross-entropy loss, which may lead to different analyses compared to the $L^2$ loss in regression problems. The implicit bias for linear models in classification problems and regression problems has been studied separately in numerous works. We think that it is interesting to further investigate the bias of DEQ in various tasks such as classification or sequence modeling and we leave them as future directions.

Thank you very much for your careful review and thoughtful questions and comments. Please see our response below.

W1. It is unclear whether the comparison between DEQ and FNN is fair. …. Therefore, the authors must provide a comparison in terms of both memory consumption and computational cost (during training) to justify the separation results and claim that DEQ is better than FNN.

We admit that memory consumption and computational cost are vital in determining the model performance in real applications. However, considering these issues is beyond the scope of the expressivity of DEQ since they are also determined by the optimization and forward and backward algorithms used. The main goal for our comparison is to study the bias and potential advantage of DEQ compared to FFN on expressivity with a comparable number of parameters. This analysis provides intuitions for understanding the model bias of DEQ.

However, to address your concerns, we also provide some comparisons based on the computational cost of the forward propagation of DEQs. In our separation result (Theorem 1), the DEQ only need one iteration to converge in the forward propagation using fixed-point iteration, making its computational costs comparable to that of a constant-depth FFN with the same width. The DEQ in Theorem 2 needs $\log_2(\varepsilon^{-1}) + \log_2(b-a)$ iterations to achieve an $O(\varepsilon)$-solution using bisection method starting from an interval $[a,b]$ with constant length, resulting in a cost comparable to that of $O(\log(\varepsilon^{-1}))$-depth FFN with the same width. For the memory cost, DEQ’s memory usage is comparable to that of constant-depth FFN. Since the DEQs we consider in our theorems have fewer parameters, they are more advantageous than the corresponding FNNs in memory consumption. It is interesting to consider the computational and memory cost in a more general setting, and we will explore them in the near future. Additionally, we add an experiment showing that DEQ can achieve better performance with similar FLOPs per iteration compared to various FFNs. Please see our attached PDF file in Author Response for details.

W2. Issues in the proof of Theorem 2(B). (Section 4.3)

We are sorry for the confusion. Lemma 2 should be stated as: “Then for any $\mathbf{x} \in [0,1]^d$, it holds that |z_u – z_v| \leq \min \left\\{ (1-L_u)^{-1}, (1-L_v)^{-1} \right\\} \cdot \max_{z\in \Omega}|u(z,\mathbf{x}) – v(z, \mathbf{x})|. ” And the inequality you mention should be $|\hat{u}\circ \hat{v}(z) - \hat{v} \circ \hat{v}(z)| \leq \max_{z\in \Omega}|\hat{u}(z) - \hat{v}(z)|$. This is why we need the range of $u(z,\mathbf{x})$ and $v(z,\mathbf{x})$ to be in $\Omega$ in Lemma 2. This will not influence the proof of Theorem 2 since we construct approximation in the sense of infinity norm to achieve $\lVert \tilde{h}-\tilde{g}\rVert _{\infty} \leq \text{poly}(d)^{-1}$, where $\tilde{h}$ and $\tilde{g}$ correspond to $u$ and $v$ in Lemma 2. We will carefully revise the statement of Lemma 2 and all related statements in the final version of the paper.

Critical issues in Section 5 (Implicit bias part). If you want to discuss the implicit bias of a given model in Equation 9, the model must be over-parameterized (N≤d) at first so that the model can fit all the data points.

We agree that the model must be over-parameterized to fit all data points. In Section 5, we also consider the over-parameterized setting by taking it as a condition or assumption for the theorems. For example, Theorem 3 states, “Suppose the gradient flow converges to some \hat{\bm{beta}} satisfying $\mathbf{X}\hat{\mathbf{\beta}} = \mathbf{y}$ “, which assumes that the model can fit all training examples. We will add clarifying statements at the beginning of 5 to emphasize that we consider over-parameterized DEQ in this Section to avoid any confusion.

Then can you guarantee that the function Q(β) is convex (and bounded below) over the solution space with ease? For this reason, I strongly believe that the validity of Theorem 3 must be reconsidered.

Theorem 3 assumes that the model is initialized as $\beta_i(0)>0$ and the gradient flow converges to a global minimum $\hat{\mathbf{\beta}}$. From our proof, the dynamic of $\mathbf{\beta}(t)$ is $\dot{\mathbf{\beta}}(t) = -(\mathbf{X}^T \mathbf{r}(t)) \odot \mathbf{\beta}(t)^{\odot 4}$. Thus, $\mathbf{\beta} (t)$ will always remain positive for every entry in the training process since the trajectory cannot cross over $0$ by the continuity of gradient flow. In the space of $\mathbf{\beta}>0$, $Q(\mathbf{\beta})$ is convex and has a unique minimum, therefore, we believe that Theorem 3 is valid. As for why Theorem 3 only admits solutions with positive entries, it is because we simplify the model by setting the linear transformation in the last layer of DEQ to be an all-one vector for tractability and simplicity. To consider solutions with negative entries, we can set the corresponding entry (say entry $i$) in the linear transformation to be $-1$, and the corresponding $q_i(x)$ in Theorem 3 will still be $q_i(x) = \frac{1}{2x^2} - \beta_i(0)^{-3}x$ with $\beta_i(0)<0$, which is convex in the space of $x<0$. We will include a remark and a discussion on these issues in the final version of the paper.

The main paper must provide pointers to the proofs of the theorems.

Thanks for your valuable suggestions. We will provide pointers to the proofs for all theorems in the final version of the paper.

Minor comments on typos & mistakes.

Thanks for your careful review. We will revise all the typos and confusions in the final version of the paper.

Q1. Can you explain what f(∅) is in Equation 13? Is it an arbitrary number?

$\hat{f}(\emptyset)$ is the Fourier coefficient of $f$ on $\emptyset$, which is defined as $\hat{f}(\emptyset) = \mathbb{E}_{\mathbf{x} \sim \\{-1,1\\}^d}[f(\mathbf{x})]$. We will add a statement to clarify it in the final version of the paper.

Thank you for your time and effort in preparing the author's rebuttal. Still, I have some minor remaining questions/comments.

• W1: I am mostly happy with your response. But could you provide some references or simple proofs for your claims about computational costs?

• W2: This response answers my question.

• W3-1: In fact, after posting the review, I found there was already a remark about "overparameterized regime" in the paper (Line 218). Thus, I want to withdraw my statement "I cannot find any such discussion." Nevertheless, it would be meaningful if the authors clarified that they are only interested in the case where $N\le d$ in order to study the implicit bias of diagonal DEQ. Also, putting a comment about "$\mu_{\min}>0$ can hold when $N\le d$ and the data matrix $\boldsymbol{X}$ is of full rank" would strengthen the writing. Moreover, I recommend putting a remark like "the current implicit bias holds for GD... other optimization algorithms may lead to different implicit biases, which we leave as an interesting future work...". I don't think that not studying other algorithms than GD is a weakness of the paper.

  • By the way, can we even train a usual DEQ with GD? If it isn't, it might be a problem because the paper's implicit bias result can be seen as an artificial result just for writing a paper. Nonetheless, I understand it is difficult to study the implicit bias of the true learning algorithm for DEQ and I don't want to decrease my score.

• W3-2. This might be a stupid question, but could you explain why $\beta(t)$ remains positive (for every coordinate) in more detail?

Thank you again for your reply. After getting responses to these additional questions, I will reconsider my score. Also, if there are missing details for the response above due to the space limit, please leave them as a comment here, then I'll happily read them all.

Thank you for your careful review and thoughtful questions and comments. Please see our response below.

The assumption in Equation (9) that DEQs favor dense features might be misleading. …. It is straightforward to claim that the diagonals are dense since that is the only part of the model being utilized.

While our simplified model in Eq. (9) has some limitations to ensure solvability, we do not agree that our result is a direct consequence of the model assumption. In fact, updating only the diagonal entries does not necessarily lead to dense diagonals. As a counterexample, it is known that for matrix sensing or one-hidden-layer neural networks with quadratic activation (see Theorem 1.2 in [37] in our references for details), Gradient Descent will converge to a low-rank (diagonal sparse, not dense) solution. Specifically, consider the model $f_U(x) = \mathbf{1}^T q(U^Tx)$ with labels $y= \mathbf{1}^T q((U^*)^T x)$, where $q(\cdot)$ is the quadratic activation, $U$ is diagonal and the ground truth $U^*$ is sparse diagonal. It is shown that $\lVert UU^T-U^*(U^*)^T\rVert _F$ can be sufficiently small after some gradient steps by adjusting the initialization scale of $U$. Thus, the diagonal entries of $U$ are sparse even if they are the only part of the model being utilized. So we argue that the bias of DEQs in our paper is essentially due to the network architecture, rather than the model assumption in Eq. (9). Unlike FNNs that often have the so-called simplicity bias (prefer learning minimum norm or sparse solutions), DEQ tends to learn some hard problems. We will add more explanations in the revised version.

The paper misses citing some important related works.

Thanks for your feedback. We will include the papers you mentioned in related works in our final version of the paper.

Can the authors comment on or envision the significance of the other two features (shared weights and input injection)? How do these contribute to the overall performance and expressivity of DEQs?

Our separation results have leveraged all three distinct properties. Theorem 2 uses both the shared weights and infinite depth so that the feature of DEQ can be characterized as the solution to a fixed-point equation. And without the input injection, the fixed point is not even a function of the network input. As for the separate significance of shared weights and input injection on expressivity, the shared weights enhance the parameter efficiency of the model in approximating certain functions. The input injection can be regarded as a skip connection for the weight-untied model, potentially improving the expressive power, much like how skip connections in ResNet enhance its expressive power. These properties together enable DEQ to be efficient in approximating specific functions such as those as solutions to fixed-point equations or those with relatively large derivatives.

How do the authors envision the practical applications of their findings? Are there specific domains where DEQs could significantly outperform FNNs?

A high-level conjecture from our analysis is that DEQ has potential advantages in learning certain high-frequency components. In Appendix B.2 in our paper, we conduct an experiment on audio representation. We observe that DEQ outperforms FNN with a noticeable error, preliminarily validating our findings and hypothesis. Based on our results, we envision that DEQs may outperform FNNs in the area of audio. We will discuss this in the revised version. However, we leave the full study as a future work.

Could the authors elaborate on the potential limitations of DEQs, especially in terms of computational complexity and training stability?

The limitations of DEQs in terms of computational complexity and training stability are not the main consideration of this paper. Because the paper mainly studies the bias of DEQ caused by its architecture and learning dynamics. However, we will add more review in the related work section for the limitations. From our understanding, one stability issue of training DEQ is ensuring the existence a unique fixed-point throughout training. The well-posedness may be violated for vanilla DEQ when $\lVert W\rVert _2$ is large, especially when trained using a large learning rate. Another stability issue is gradient explosion, similar to that in training RNNs. Specifically, the gradient w.r.t. $W$ involves $(I-W)^{-1}$. If $(I-W)$ is nearly singular, the gradient may explode.

How do the authors address the sparsity constraint in their model assumptions? Can they provide more justification for why the diagonals should be considered dense?

Our model assumption in Eq. (9) is primarily for ensuring the tractability of the model due to the technical issues arising from the non-commutativity of matrices, especially as we aim to analyze the bias of DEQ beyond the NTK regime. This is a commonly considered tool that simply reduces a matrix problem to a vector problem (e.g., see work [29, 37], all these works start from analyzing vector problem and then consider matrix version). Again, we emphasize that diagonalization does not necessarily lead to dense diagonals. Therefore, we believe that this simplified model can still reveal the bias of general nonlinear DEQ to an extent. We hope this along with our response to the weakness above can address your concerns.

Can the authors conduct experiments to show that the learned features are indeed dense?

Thanks for the suggestions. In the revised version, we add experiments to evaluate the feature density of a depth-$3$ FFN, a diagonal DEQ, and a vanilla DEQ for the GOTU task in Eq. (15). We generate heatmaps of the features of both DEQ and the feature before the last layer of FFN. It is shown that both the heatmap of diagonal DEQ and the heatmap of vanilla DEQ are lighter than that of FFN, indicating the features are indeed dense. Please see our attached PDF file in Author Response for details.

Thank you for your careful review and thoughtful questions and comments. Please see our response below.

I was wondering whether the comparison between depth $L\leq mα$ FFNs and DEQs was a fair comparison. (See my questions below).

Please see our response for the question Q1 below.

However, I think it would be more compelling theoretically if the experiments could be used to support the theoretical claims made in the paper (ie varying d in the steep target function and showing infinity norm of FFNs increases but not the DEQs, etc).

Thanks for your feedback. In our experiment in Figure 1 for approximating the steep function in Theorem 2, we vary the input dimension $d$ from $10$ to $20$ as we set $\delta = 2^{-10}$ and $\delta = 2^{-20}$. To further support the theoretical results of Theorem 2, we add experiments varying $d$ from $5$ to $20$ for the steep target function and showing the infinity norm of weights of both networks. Our results show that the infinity norm of FFNs increases as we apply larger $d$, while the infinity norm of DEQs remains lower than that of FFNs, consistent with Theorem 2. Please see our attached PDF in Author Response for details.

A DEQ could be viewed as the result of applying an infinite depth network with shared weights. If depth were to be unrestricted, then this hypothesis class should be contained within the set of all infinite depth FFNs. Is it fair to compare finite depth FFNs to DEQs?

We think that our comparison of the expressivity of DEQ and finite-depth FFN is fair. One primary goal for the comparison is to investigate how the DEQ architecture influences the model capacity with the same number of parameters as FFN whose weights are not tied. This analysis provides intuitions for understanding the model bias of DEQ. Note that one conceptual understanding here is no free lunch. Under the same number of parameters, we study for what kind of function, DEQ is provably better than standard FFN. This paper follows the common ways to characterize expressivity and separations. Our separation results are mainly stated from the actual size of the networks (Theorem 2 also considers the parameter magnitude). Specifically, Theorem 1 compares the expressive power of DEQ with $O(m^2+md)$ parameters with a class of FFN (i.e., $L\leq m^{\alpha})$ with sub-exponentially many parameters by providing a separation result showing that DEQ is much more parameter-efficient in approximating certain target function. We will add more discussions to emphasize the fairness and importance of our comparisons in the final version of the paper.

Would it perhaps be more interesting to compare the solutions identified by gradient flow in the FFN (where weights are not tied) to DEQ (where weights are tied)?

We agree that it is a very interesting problem. However, analyzing the FFN optimized by gradient flow is beyond the scope of model expressivity to an extent. The solvability of multilayer FFN remains widely open except for some special cases such as in the lazy regime of NTK. In this regime, the model requires to be heavily over-parameterized and approximates just a linear model. The analysis would mainly concern traditional methods, such as studying the decay rate of kernels. However, in Section 5, we take a further step by studying the dynamic bias (trained by GF and GD) of a simplified DEQ in comparison to that for FNN. Here though the model is simplified, it is non-linear and actually beyond the NTK regime. We leave the study in the NTK regime as future works. So we do have some results for studying the dynamic bias (implicit regularization) for DEQ.

In Remark 1, it is stated that an FFN could in principle achieve $2^{mL}$ linear regions. Supposing this could be achieved, wouldn't we expect a width $m$ and depth $L>1$ FFN to have more linear regions than a DEQ model?

Thanks for the valuable question. As stated in Remark 1, our comparison of the number of linear regions between FFN and DEQ is actually stated in terms of the number of neurons (the input neurons are not counted in). Note that a DEQ with $mL$ neurons has width $mL$, thus it can generate $2^{mL}$ linear regions according to our Proposition 1. So an FFN with width $m$ and depth $L>1$, i.e., $mL$ neurons, cannot generate more linear regions than that of DEQ with the same neurons. Therefore, we claim that DEQ is can potentially generate a larger number of linear regions compared to FFNs with the same number of neurons.

Do the authors' results provide evidence that suggests that $2^{mL}$ linear regions cannot be achieved?

The Lemma 5 in our Appendix A.1 may provide some evidence. It shows that when the input dimension is $1$ and the width of each layer is $m$ for a depth-$L$ ReLU-FFN, the number of linear regions is $O(m^L)$, strictly smaller than $2^{mL}$. Through our further investigation, it is shown in Theorem 1 in [1] (See the statement in Page 4 in [1]) that when the input dimension $m_0=O(1)$ and the width of each layer is $m$ for a depth-$L$ ReLU-FFN, the asymptotic upper bound is of $O(m^{Lm_0})$, which is of smaller order in magnitude compared with $2^{mL}$. We will add a statement to include the evidence in the final version.

[1] Bounding and Counting Linear Regions of Deep Neural Networks, ICML 2018.

Should line 255 be $\sum_{i}\beta_{i}^{−2}$ instead of $\sum_{i}\beta_{i}^{−1}$?

We are sorry for the typo. It should be $\sum_{i=1}^d \beta_i^{-2}$ in line 225 (I think you refer to line 225 instead of 255). We will revise it in the final version.

The authors mention briefly that they study a diagonal linear DEQ for tractability, but they could include more limitations in the conclusion/discussion sections. They could also point out that some of their results are about approximation of particularly chosen target functions.

Thanks for your suggestion. We will add a discussion about our limitations in the conclusion section in the final version.