Separation and Bias of Deep Equilibrium Models on Expressivity and Learning Dynamics
Authors: Zhoutong Wu
Yimu Zhang
Cong Fang
Zhouchen Lin
Venue: NeurIPS 2024 poster (2024)
Keywords: Deep Equilibrium Models
separation
bias
expressivity
learning dynamics
Primary area: learning_theory
TL;DR: This paper characterizes some provable separations and bias of DEQ over FFN in lens of expressivity and learning dynamics.

Abstract: The deep equilibrium model (DEQ) generalizes the conventional feedforward neural network by fixing the same weights for each layer block and extending the number of layers to infinity. This novel model directly finds the fixed points of such a forward process as features for prediction.  Despite empirical evidence showcasing its efficacy 
compared to feedforward neural networks, a theoretical understanding for its separation and bias is still limited.  In this paper, we take a step
by proposing some separations and studying the bias of DEQ in its expressive power and learning dynamics.   The results include: (1) A general separation is proposed, showing the existence of a width-$m$ DEQ that any fully connected neural networks (FNNs) with depth $O(m^{\alpha})$ for $\alpha \in (0,1)$ cannot
approximate unless its width is sub-exponential in $m$; (2) DEQ with polynomially bounded size and magnitude can efficiently approximate certain steep functions (which has very large derivatives) in $L^{\infty}$ norm, whereas FNN with bounded depth and exponentially bounded width cannot unless its weights magnitudes are exponentially large; (3) The implicit regularization caused by gradient flow from a diagonal linear DEQ is characterized, with specific examples showing the benefits brought by such regularization. 
From the overall study, a high-level conjecture from our analysis and empirical validations is that DEQ has potential advantages in learning certain high-frequency components.

Separation and Bias of Deep Equilibrium Models on Expressivity and Learning Dynamics
Zhoutong Wu ztwu@stu, .ku. edu. cn
Yimu Zhang² zym240stu. pku. edu, cn
Cong Fang 2.37
Zhouchen Lin 2,3,4" zlin@pku, edu, cn
Fangcongépku. edu. en
Academy for Advanced Interdisciplinary Studies, Peking University 2 State Key Lab of General AI, School of Intelligence Science and Technology, Peking University
Institute for Artificial Intelligence, Peking University
Pazhou Laboratory (Huangpu), Guangzhou, Guangdong, China
Abstract
The deep equilibrium model (DEQ) generalizes the conventional feedforward neural network by fixing the same weights for each layer block and extending the number of layers to infinity. This novel model directly finds the fixed points of such forward process features for prediction. Despite empirical evidence showcasing its efficacy compared to feedforward neural networks, a theoretical understanding for its separation and bias is still limited. In this paper, take a step by proposing some separations and studying the bias of DEQ in its expressive power and learning dynamics. The results include: (I) A general separation is proposed, showing the existence of a width-m DEQ that any fully connected neural networks (FNNs) with depth (mm)) for E (0, 1) cannot approximate unless its width is sub-exponential in m: (2) DEQ with polynomially bounded size and magnitude can efficiently approximate certain steep functions (which has very large derivatives) in - norm, whereas FNN with bounded depth and exponentially bounded width cannot unless weights magnitudes are exponentially large; (3) The implicit regularization caused by gradient flow from a diagonal linear DEQ is characterized, with specific examples showing the benefits brought by such regularization. From the overall study, high-level conjecture from our analysis and empirical validations that DEQ has potential advantages learning certain high-frequency components.
Introduction
Implicit deep learning 1. paradigm that generalizes the recursive principles of traditional explicit models, has gained renewed interest with the advent of novel neural network architectures. Among these. deep equilibrium model (DEQ) [ stands out as a commonly utilized model. In contrast to explicit neural network that derives features through forward propagation, DEQ computes features directly by solving an equilibrium equation induced by the implicit layer. Since the equilibrium state is also the limit point of the infinitely recursive iterations of the implicit layer, DEQ can be regarded as new neural network that models the limit of multi-layer weight- tied neural network with the depth going to infinity.
*Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Nowadays, DEQ has become popular and widely studied model in the field of machine learning. On the empirical side, competitive performances against explicit feedforward neural networks have been achieved in various real applications such as natural language processing [2]. computer vision 3 image generation [4] and solving inverse problems []. On the theoretic side, main research line is to study the well-posedness of DEQ. This line aims to analyze when unique equilibrium can be guaranteed by DEQ and some weight parameterization and initialization techniques have been proposed to ensure the well-posedness 6
However, despite wide studies on DEQ, an understanding of the basic learning theory for its sep- aration and bias against explicit feedforward neural networks is still limited. For the expressivity, a preliminary study about the connections between DEQ and fully-connected" network (FNN) is provided in the seminar work (2), where it is proved that every FNN can be reformulated as large DEQ under a specific weight ce-parameterization, whereas, a deeper study on the provable and quantitative advantage of DEQ in its expression power is still lacking. Besides, there is another research line that studies the learning properties of DEQ using the so-called neural tangent kernel (NTK) view [9] originating from analyzing FNNs 1O II] It has been shown that under suitable initialization, the dynamic of over-parameterizeed DEQ can be approximated by a linear kernel model
12 13, therefore the global convergence of gradient descent algorithm and possible generalization can be achieved under some regimes. However, in the NTK regime, it is shown that DEQs are almost equivalent to not-so-decy explicit FNNs for high dimensional Guassian mixtures [4], and it is still not known whether DEQs have potential advantages over FNNs in more general settings. A study on the separation and bias of DEQ over FNN
provide with clear and intuitive suggestions about when DEQ is preferred in practice thus it is strongly desired. In this paper, we initialize the study by analyzing the expressive power and learning dynamics of DEQs. The main results are sketched as follows.
1. We first propose a general separation showing that there exists a width-m DEQ which cannot be approximated to a constant accuracy by an FNN with depth O(m") for a E (0, unless its width is exp(X(m that the two networks can generate. Based on the result, further prove that width-m DEQ can generate at most 2n linear regions, which has provable advantages than FNNs.
This is achieved by comparing the the number of linear regions
2. We then propose another separation, where a steep function in [o, 1]d being the solution fixed point equation is considered the target function. We show that a DEQ with size and magnitude bounded by ((s-1) can approximate this function to ((E)-acuuracy in I norm, whereas an FNN with bounded depth and exponentially bounded width cannot unless its weights is exp (s))). For the technical contribution, we manage to show that an approximation of the fixed point mapping by the implicit layer can also guarantee the approximation the solution defined by the fixed point equation even if the Lipschitz constant of the fixed point mapping is very close to 1 by a new observation as shown in Lemma 3
3. Finally, we study the bias of DEQ from the perspective of learning dynamics. We propose a general characterization of regularization for gradient flow in an overparameterized setting. We further analyze the dynamics of both gradient flow and gradient descent, showing that under mild conditions, convergence is guaranteed, and the model tends to produce 'dense" features. Then we offer a concrete example on a specific aut-of-Distributin (OOD) task, demonstrating that this bias can help reduce the OOD error.
Finally, we conduct experiments to validate our theoretical results. From the overall study, a high-level conjecture is that DEQ has potential advantages in learning certain high-frequency components.
Notations. We use standard notation O()) and 2(()) to hide constants. We use o to denote the ReLU function, i.e., (I) max(0, 2.,, and we sgn(-) denote the sign function. We use diag(-) to transform a vector into a diagonal matrix with the vector's 's elements on the diagonal. We denote by || Ilp the S vector norm or the subordinate matrix norm, and by [[\]]=>()) the 1.P-norm of function on a compact set K. For a vector or vector-values function v, we denote v; the i-th entry of the vector the function. For a function u : R -> IR, we denote nn the n-fold composition of u.
2 Related Works
In this section we briefly review the literature that are most related to us.

---

Theoretical Studies on DEQs. Theoretical research on DEQs has primarily focused on ensuring
their well pell-posedness 6 7 To guarantee vell-posedness, strategies like new parameterizations [6] 7l. regularization [1] and special initialization
[ were proposed. Another research line delves into
the learning properties of DEQ. The expressivity of DEQ is preliminarily studied in (2. Regarding
learning dynamics, some works [66 13] couple the dynamics of wver-parameterized DEQs with a linear kernel using the NTK method. They manage to prove the global convergence and study the generalization [17]. Other studies examine DEQs in a linear framework or infinite- limit. For instance, Kawaguchi []6 studies the convergence linear DEQ, while Gao al. [88] explore information propagation in DEQ and show its equivalence to a Gaussian process in the infinite-wide limit. Nevertheless, an in-depth study on the potential or quantifiable advantage of DEQ over FNN is still lacking.
Separations on Expressivity of Neural Networks. The separation on expressivity of neural networks is fundamental study characterizing functions that can be approximated efficiently by one neural architecture but cannot by another. These architectures include FNNs [19] 20] CNNs (21].
etc. Since DEQ can be viewed as an infinitely deep weight- network, depth separation 23 most relevant to our study. A key study by Telgarsky [24] constructs a saw-tooth function with many oscillations to give a separation, which further inspires a series separations [25] 26 27). In
RNNs 22
addition to depth, some recent works study the separation regrading the overall number of neurons [28] or the magnitude of parameters (29] of the networks. In this paper, the first separation is also inspired by Telgarsky's 's construction, whereas we focus the separation between DEQ and FNN and provide a more refined analysis of networks' depth. The second separation is new.
Implicit Bias of Learning Dynamics on Neural Networks. The implicit bias of learning dynamics plays a key role in determining what particular optima can be found by the algorithms when there are multiple optima. series of papers study the implicit regularization of gradient- baaed methods, showing that under varying settings, these algorithms bias towards solutions with specific properties
30, 31], such as norm minimization [32), sparsity
(3 and low complexity [34 35 36). Due to
the theoretical barrier in analyzing nonlinear neural networks 37 most existing works focus on
simplified models such as random feature models [38 32), networks with quadratic activations (39]
and diagonal linear networks [33]. This paper follows similar strategies and analyzes the implicit
bias of a simplified diagonal linear DEQ from learning dynamics.
3 Preliminaries of DEQ
The DEQ is an implicit-depth model [2] that employs the same weights in each layer block of feedforward neural network and extends the number of layer to infinity. The layer blocks used in
DEQ can be fully connected, convolutional, or Transformer blocks, resulting in different variants of deep equilibrium networks. In this paper, we consider a vanilla DEQ with ReLU activation as the generalization of an FNN for the separation result and simplified linear diagonal DEQ for the bias analysis. Specifically, an L-layer FNN from Rd to Iº can be expressed as
z' x; z t+1 ( b.), 1sis 2: y W2z
(1)
where x E Rd and y E R In DEQ. each W, and b, in Eq. I replaced by the same weight W and bias b, and a linear transform of the input U x is added to each layer, i.e., z = o(W z + +x b) for all By extending the layer to infinity, the feature and the prediction of this DEQ can be expressed as
a a( 2 Ux
y A
where W E RR U E RRxxd b e Rm, and A E =x We call a z + +U -b) -x--bb layer and m the width of DEQ. this paper, we mainly consider i... DEQ scalar function on Rdd
the implicit
In (2) the authors show that every FNN can be reformulated as a large DEQ with specific weight reparameterizattion. Specificallyy the depth-L FNN described in Eq. ①I is equivalent to DEQ in the
3

---

form of Eq. 2 with
0
bi
W2
0
b
= (0,
WE.. W
W
0
U
b
(3)
: b
WL-1
4 Separation on the Expressivity of DEQ
In this section, we focus on the separations on the expressivity of DEQ with ReLU activation. We follow the common ways to compare the expressivity from the actual size (width and depth) of the networks. More explanations on the fairness of the comparison are provided in Appendix [A.4] We will show that DEQ more parameter-efficient in approximating specific target functions than FNN.
4.1 General Separation over FNNS
The following theorem states a general separation between DEQ and FNN from the size of networks. The motivation behind the theorem is common observation that functions with many linear pieces are typically hard to be approximated by functions having fewer linear pieces.
Theorem 1. Let m N+. Assume that L S m for some
< 1. Then there exists a function Na [0, _ + R computed by width-m ReLU-DEQ, such that for any function N, [0, 1]e - IR
computed by depth-L ReLU- FNN with width at most 2
holds that
J p..j0 [Na(x)) - (x(x))xx 16'
1
The proof is provided in Appendix A. It involves quantifying the number of linear regions generated by a DEQ compared to an FNN. Specifically, we show in the proof that there exists a DEQ producing 2d linear pieces whereas no-so-deep FNNs, i.c., FNNs with depth (mm)) cannot generate such a large number of linear regions unless the width is sub-exponentially large.
Moreover, the example of the hard-to-approxte to-apprxximate DEQ enables us derive exact bound on the number of linear regions that a DEQ can generate. This result is of independent interest and is stated in the proposition below.
Proposition 1. Let m > 0. A width-m ReLU-DEQ has at most 2 linear regions in the imput space. Moreover, this upper bound is attainable, i.e., there exists width-m ReLU-DEQ that computes function with 2 linear regions on IRd.
Remark As a comparison, the work of (40] analyzes ReLU-FNNs. It shows that for a ReLU-FNN with total of Ñ neurons of arbitrary depth, the maximal number of linear regions is bounded above by 2Ñ To the best of our knowledge, is yet to be determined whether this bound is achievable. Moreover, there is evidence suggesting that this upper bound is not achievable for FNNs that when the input dimension is (See Lemma 5 in Appendix(A. ffor details). Consequently, width-m DEQs can potentially generate a larger number of linear regions compared to FNNs with neurons, as DEQs have been shown to achieve their upper bound.
Theorem shows that there exists a width-m DEQ that is hard to be approximated by FNN with depth (m,)). This theorem along with Proposition I reveals that, although DEQ computes features by solving equilibrium function induced by a shallow implicit layer, its complexity in terms of expressing linear regions of DEQ can be larger than that of not-so-deep FNN.
4.2 Separation on Certain Steep Functions
In this section, we present another separation concerning both the size and parameter magnitude of neural networks, which more explicitly reveals the bias and potential advantages of DEQ on
'We follow the definition of linear regions in 40 For any piecewise linear function F:: RR + R, linear
region of function a connected subset D C 00 satisfying 1) is linear D;2) If F' linear on some connected set D 5 D, then ò D.

---

expressivity. The separation is based on the observation that the fixed point of DEQ can be rewritten as the solution to an optimization problem under certain conditions.
To be specific, consider a simple quadratic optimization problem with the optimization variable E IR and parameter E Rd:
min 2² (x
where A (x) is a positive definite matrix parameterized by x and 11I > A(x) > O for some ? O. Approximating
z(x), i.e., the optimum function of the parameter x, serves useful primitives in various applications. Directly approximating 2(x) by FNN requires the approximation of (x) (x) b(x). On the other hand, from the optimality condition, z(x) implicitly defined through fixed point equation
1 (A(x) b
1]
Hence, approximating (xx by DEQ may only require the approximation of the fixed point mapping (A z + b(x)) by the implicit layer. To some extent, the approximation problem is 'altered' due to the model difference, which possibly leads distinctive division in approximation.
Now, we construct workable instance. The objective function of our central interest a special case of Eq. (4) given by:
min(1 + 5 x=)=² 8012,
[0, 1]
(5)
where 5 = 2-d The solution function is calculated as
8z1
g(x)
2(1 (11+6-x)) x E [0, 1jM,
(6)
and it can also be determined by the following fixed point equation
= (2, x) = (x) 8) + _zz1
(7)
Note that g(x) has very large derivative when #1 is near 1. can be regarded as a continuous version of the common indicator function of the first entry 1 12, (x). The separation is presented as follows.
Theorem 2. Let g(x) be defined as Eq. for x E [0, 1]d and 1 2 & >
A. For any function (1)( implemented by FNN with depth L and width k where L S C
and 2 for some constant C 0(1). If
1
[N]me(x) g(x)]le>(001))) S
16'
then there exists a weight parameter Way of the FNN 1 s i S L and 1 S S k. such that
W
2
B. There exists a function Nazg implemented by a DEQ with width bounded by 56 and weights bounded -1, such that
[NNeggX) g(x)]l (10.114) Se.
The inapproximability result of FNN in Theorem 2 is stated from the perspective of weight magnitude, which holds practical significance. Exponentially large weight often results in exponential iterations of optimization algoritiums in learning with this model, as also noted in [41). Additionally, neural networks in practice rypically have small weights due to techniques such as (standard) small initialization, normalization, and gradient clipping.
Remark 2.
The proof shown in Appendix A.2 Theorem the inapproximability of FNNs is relatively simple: Direct calculation shows that the derivative of the target function g(x) is exponentially large when æ1 > 8. To approximate (xx) 7 norm requires FNNs to have large derivative in certain region, resulting in exponentially large weight for FNNs with bounded depth. On the other hand, the

---

proof of the approximability of DEQs is more technical. While I in Eq. seems more benign, it not clear how to construct the approximation using the implicit layer in Eq. 2 that resembles an 1-layer FNN with very limited expressive power. Moreover, even if we manage approximate ğ in Eq. 77). it will not necessarily imply good approximation between the fixed point of DEQ and the solution of = 0(2, x). i.e., the target function due to the Lipschitz constant of Ò with respect to being very close to 1 when 21 is around 1 according to Eq. (7.. We provide a proof sketch this result in Section 4.3
Further insights and implications can be gleaned from Theorem 2 First, it suggests that DEQ may excel in approximating functions induced by exed-point iterations. In other words, DEQ may be better suited for representing algorithms. Second, Theorem 2 implies that functions with large derivative, or high- frequency components, may be approximated more efficiently by DEQ, as the function to be approximated by the implicit layer can have much smaller derivative.
4.3 Proof Sketch of B. in Theorem 2
we want to approximate ğ using the implicit layer of DEQ. Due to the limited expressive power of the implicit layer, we propose an equivalent reparameterizatioo of DEQ Lemma 1. Consider a revised DEQ defined as
As discussed in Section 4.2
z = Vo z Ux+b),
(8)
y Bz,
where x E E W E Raxm U E Boxd V Rmxg b E R', B E R and W Vlla S
1. Then any revised DEQ can be represented by a vanilla DEQ defined as in Eq. @ with width 9.
Lemma 1 enables us to approximate ğ(z, x) using the revised implicit layer, denoted by Ti(z, x).
Then the crux of the proof centered in bounding the error between the equilibria of two fixed-point h(2, x) and consider
equations. To begin, for every x we denote û(z)
O(z, x), 6(z)
(z) - (z)]. Suppose that ú(z) is La Lipschitz, then we have
(z) 002 (x)) 112 (2) â d(2) + | o 0(2) 8 (z) s (Lg + 1)) - 6(2) 6(=))-
Thus if La 1, by recursion, we can bound distance the between the infinitely composition of ú(=) and 6(z), from which the error of the two fixed points can be bounded.
Lemma 2. Let Ω C R.. be a compact set, and u(2, x), u(2, x)) Ω x [0, 10 - Ω be two functions. Assume that for all x E [o, 11s, ul., x) and v(-, x) are Lipschitz continuous with Lipschitz constant Lu Lo < 1, respectively. Then any x E [0, 1]d, holds that
[zu(x) - 2x)x S min((1 -,, ",,)) (1
L.)) L max |u(z, x) v(2, x));
=ell
where zu (x) and zu (x) are the fixed point of u(z, x) and = v(2,x) x), respectively.
In our case, u(2, x) and u(z, x) in this Lemma represent 0(2, and h(z, x). respectively. When 3i < 1 1-poly(dd poly(d)-1, by calculating 05(x.)) we have (1 - Lg) poly(d). Leveraging this and Lemma we just need I عo|0c S poly(d)-1 to achieve a final accuracy of O(e). However, when 1- 5, we only have (1 Lg) 1 < exp(S2(d)), which may necessitate exponential width for the implicit layer to achieve O(e) accuracy.
0=
fact, xx2xx) = z;z gives an example that even assuming l - ol S exp( -1 is not sufficient to achieve O(e) accuracy since 2 (1) (1) 3- So seems difficult to bound the error without a specific structure of h. To observe novel property that enables us effectively bound the error. Lemma 3. Let 5 > O. Under the conditions in Lemma 2 for any interval T C Q with diam(T) > g. x(2,x) = 022 x) has a zero in T for all x, then it holds that
overcome the issue,
Izu (x) 2x)l S. Vx 10,
The intuition behind Lemma 3 is that if for any univariate functions w.r.t. Z can take the same value at frequent intervals, then their zeros will also be close to each other. By using this Lemma, suffices to construct such hi(2, x) that equals ğ(2, x) at frequent interval of length OEE) for every x.
u(2, x) and v(2, x) as two monotone

---

The Bias on Learning Dynamics of DEQ
In this section, we study the implicit bias of simplified linear diagonal DEQ and present concrete example illustrating how such an implicit bias may improve generalization. Specifically, we focus on the overparameterized setting and our analysis is beyond the lazy training regime.
To ensure tractability, we follow the common techniques (e.g. see 3 39] to reduce a matrix problem vector problem by considering only the diagonal elements of the weight matrix. Our primary focus is on the following model:
f(w, Σ
Σ J. : (B,x), B w
1
The model can be regarded as diagonal linear DEQ in Eq. with activation Id, weights
W diag(w,; W2, ... W2). Ia. b and = 1,, 1)2 E RR4 Although simplified. this model is essentially nonlinear model and retains the implicit nature of DEQ.
Our primary focus lies minimizing the expected square loss:
1
min L(w) - [B f(w,x))
(10)
We are given access to set of i..dd training examples {xx; ) and we denote the (half) square loss on these examples by L(w) = Em f(w,,:))? As mentioned above, we focus on the overparameterized setting that S d. Moreover,
X = (X1, xN)": M'min Amin (XX"). Mmmx
Amax
(XX7
where Mmin > O can hold when N S d and the data matrix X is of full rank. We mainly consider
the dynamics of gradient flow (GF) and gradient descent (GD) with fixed stepsize rj on minimizing [(w), expressed as follows
(GF) w(t)= = vtt==-Vi[(w(())
(GD) w w V
(11)
The main theorem below gives a general characterization of the bias of diagonal linear DEQ in the overparameterized regime. The proof based on the technique proposed in [3I]
Theorem 3. Let Bg in Eq. 9 be initialed 3,(0) 0 for all i. Suppose that gradient flow for the parameterization problem in Eq. (10) converges to some 3 satisfying X,3 y, then
β = argmin (B3), s.t. X3 y,
(12)
9
where Q(B) -EA,, (Bi) and q:(x) 2े + (,(0))5
Remark 3. In Theorem 3 our proof shows that (()) remains positive for all entries throughout the training process. Within the space where B 0. Q(3) is convex and has a unique minimum. The restriction to positive entries arises from our simplification on A in Eq. (9) to be an all-one vector. To accommodate negative entries, one could assign -1 to the corresponding entry. In this case, qi (x) 2n² 3:(0)=3, with (0) < O, which is convex for < 0.
becomes q: (z)
All the proofs in this section included in Appendix A.3 The theorem implies that the bias of the (simplified) DEQ significantly differs from that of conventional linear models and two-layer linear network which tends to give a minimum 4--norm interpolator
[42]. Specifically, the predictor / hardly admits parameters of small magnitude due to the penalty term 2 >E 8 Meanwhile, the
predictor can endure parameters of greater magnitude as the penalty (z(z) increase almost linearly when x: is large.
We then study the implicit bias from the learning dynamics of GF and GD. We show that when Mmin > O. under mild conditions, the convergence of both algorithms is guaranteed. Moreover, in this case, a positive lower bound of the foo norm the iterates can be derived, indicating that the model inclines to produce 'dense" features in learning process.
Assumption 1. Denote by Bo the initialization of B of the model Eq. D There exists an optima 0r, ie.. 3 y and a constant e > O, such that
||اا loc
1133 - BBll2 2 0.
7

---

Theorem 4. Let {3(t)} be the process following GF in Eq. 11) and (3)) } the iterates following GD in Eq. (T). Assume that pmin and the initialization ((0 and 3 satisfy Assumption 7 with an optima 3
A. (B(1)) converges to an optima 3 with 11 Iloc 2 c. Moreover, for any 2 0, we have e S [1B()) S 11 + 1113 90
B. If there exists a constant C > O such that 1133 1lcc S for all k. then (B+ converges to an optima 38 with [1 11x 2 c. Moreover, for any k 2 O, we have e S |13 S.C. Remark 4. The assumption in Theorem 4 that 11,3 is uniformly bounded can be removed we manually incorporate a constraint on B and optimize the problem using projected gradient descent. In practice, certain reparameterization tricks 16 7 are proposed to ensure that I some m > 0, thus corresponding to the aforementioned assumption.
W 'cz ml for
Theorem does not require the updates to stay in a small domain near the initialization, so it is beyond the lazy training regime. Importantly, the 'dense' bias observed in /3 is direct consequence of our model assumption even though we only assume the diagonal elements to be nonzero. In fact, utilizing the diagonal elements can still lead to sparse features (e.g., see [39]. We believe that this bias in DEQs stems essentially from their network architecture. On the other hand, the current implicit bias holds for GF and GD, whereas other optimization algorithms may induce different implicit biases, which we aim to explore in future work.
results above, now provide concrete example to show the advantages brought by the bias of DEQ in out-of-distribution (OOD) tasks. This is motivated by the fact that diversifying spurious features can improve OOD generalization 443. Specifically, we focus on generalization on the unseen domain (GOTU) setting [36]. a rather strong case of OOD generalization where part of the distribution domain unseen training but used testing. As an example. we here utilize the setting in Theorem 3.1 in [36). Consider the sample space S = function f : S + IR defined
Based
{ {-1, 13d and linear boolcan
f(x) = f(0) + Σ ((1))),
(13)
where f({i}) = Ex (a.f f(0) = -f and will refers to uniform sampling from 24. In training, the k-th component of every accessible sample is fixed 1, i.e. the unseen domain is L = {x [+1]a: æ -1.. Denote by fsyu the function learned on S SYM. The GOTU error is the defined as the generalization completely on the unseen domain, i.e.,
GOTU f. f,4) = Ex-eull ((f fxx)),
where / is the quadratic loss function. It is shown in (36] that learning this function with diagonal linear network results in GOTU error of 4f(x)))2 + O(e) for infinitesimal e. On the other hand, the following proposition shows that under mild conditions, learning such function with DEQ achieves smaller GOTU error, where we consider DEQ in Eq. ( with bias term, i.e.,
f(w, x) Ei=1 T-w; I4 +
Proposition 2. Let fxx be defined in Eq. (3). Assume that
f((i)) > O, visisd d, f(()))>, (f(0) S 2)((()))
Consider learning f using gradient flow on population los los on linear diagonal DEQ with bias initialized by w;( = b(0)= = 0 for all i with unseen domain = (x E {+1]d, ag = 11.. Then the loss converges to O, and it holds for the generalization error on the unseen that
+) <f((()))
GOTU S
In this setting, the function x + Iy has a higher frequency component (i.e., degree) compared to the constant function 1. Consequently, the inductive bias of DEQ enables the model capture some information about the high sehh-rreuency components. We further conduct experiments to study the potential advantages of DEQ in learning high-frequency components in Appendix B.2
II is identical to the setting in Theorem 3.11, 111.1. [36]. Note that optimizing the population loss in generalization cannot reduce the OOD error.

---

060
DIGM-5S
FMk Ish
Trak
7WNLL-200-10
GCTU
BIQN-12
East 1015
FNLU-220000
Looz
600
13
205
koration
soraton
(a) Sawtooth function I.
(h) ((x) with 2-
(c) OOD function ft.
PWIL 2
PW 3NNL00300000
B10 Now42
FS8 COTU
test losa
Loce
Text:
Beration
Iteration
Serrtion
(d) Sawtooth function II.
(e) (x) with 8
2 20
(f) OOD function f2.
Figure 1: Test losses of FNN and DEQ networks with various width W and depth L. (a) and (d) apply Sawtooth function I and II with 2 and 210 linear regions, respectively. (b) and (e) apply function g(x) defined in Eq. (5) with 5 = 2-10 and 5 = 2 2-20, respectively. (c) and (f) show the train loss and the GOTU error of FNN and DEQ on the boolean function fi, f2 with unseen domain given by
Eq. [14 and Eq. 15
Experiments
In this section, we conduct experiments on FNNs and DEQs based on our theoretical results. We first evaluate the expressivity of both networks on the functions proposed in our two separation results. Then we experiment on specific OOD tasks. Several additional experiments on audio representation and mutiscale DEQ are provided in Appendix [.22
The target function is designed as saw-tooth function, as defined in Lemma 4 in Appendix A. which can be exactly computed by DEQ. We set the number of linear regions of the saw-tooth function to 2 and 2 and experiments on other sawtooth functions can be seen in Appendix B.1 According to Proposition [ DEQ with
Piecewise functions. We first verify the results in Section 4.
width 5 and 10 can compute the above functions.
Figure M a) and Figure T(d) show that DEQ can achieve nearly zero test loss, demonstrating the saw-tooth function with 2 linear regions can be computed by DEQ. On the other hand, a not-so-deep and not-so-wide FNN fails achieve test loss low DEQ, thus verifying the separation results between FNN and DEQ.
Solution to quadratic optimization problem. We then validate the ability of DEQ to approximate the solution function to certain optimization problems. We empirically demonstrate that DEQ can approximate such function better than an FNN with a similar number of parameters. We consider the objective function g(x) defined in Eq. (6) with the input dimension 10 and 20, and thus 8 in target function being 2- and 2 2-20 The input space x E [0, 1] with the sampling distribution p(x) = 2(1-85 for 0 < < 1 5 and p(x) = 23 for 1 - ô < 21 < 1. To verify results under different network parameters, adjust the layer number and hidden dimension of FNN and the layer width of DEQ while keeping the total number of parameters of both networks similar.
As shown in Figure [b) and Figure ee), for different network parameters and target functions, DEQ consistently achieves a lower test loss than FNN, demonstrating the superiority of DEQ to approximate and represent functions solutions certain optimization problems.

---

vansuse iarra
(a) Features of diagonal DEQ.
(b) Features of vanilla DEQ.
(c) Features of FNN.
Figure 2: The heatmaps of diagonal DEQ, vanilla DEQ and FNN. We dispaly the magnitude of feature z of DEQ and the magnitude feature before the fully-connented layer of FNN. The x-axis represents features 1-20 and darker colors indicate smaller features.
tasks. We further perform experiments on the implicit bias of DEQ to verify the advantage of DEQ on OOD tasks. We consider linear boolean functions f S - R in the form of Eq. (13) and unseen domains U C {+1]d The first function is an example of the mean function and the second function is part of DTFT. Experiments on other OOD functions can be found in Appendix B.1
fi (x) 1.253z 1.25%m 1.25xz .... 1.25.110 4= fx (+1) -1},
(14)
f2(x)
Σ x=0
sin
10
T7
In.
u (= [=13 m =-1
(15)
For each experiment, we generate all binary sequences in (=1)d for training. We employ AdamW optimizer with & loss and cosine annealing scheduler. We can observe Figure (c) that the GOTU error of f1 is below the threshold of generalization error based on the Proposition 2 As shown in Figure] (c) and FigureT the training loss converges to and the generalization error on the unseen is bounded, which empirically demonstrates the advantage of DEQ on OOD tasks.
In Figure 2 display the heatmap of the features of diagonal DEQ, vanilla DEQ and FNN trained on the target function with the unseen domain defined in Eq.(14) As the darker colors indicate smaller magnitude of features, we can confirm that the learned features of DEQ are indeed 'denser' than those of FNN.
Conclusions and Future Directions
In this paper, we provide two separations of DEQ and FNN and analyze the bias of DEQ through the lens of learning dynamics. Our theoretical results provably show the advantage of DEQ over FNN in specific problems and quantify certain learning properties of DEQ. Overall, conjecture that DEQ may be advantageous in learning certain high-frequency components.
There are many directions that remain study. First, it is expecting to study the expressivity and bias of more general DEQs. Second, extending our bias analysis under gradient methods to stochastic methods is intriguing. Additionally, it remains promising to incorporate the advantages of DEQ in commonly used networks real applications. Besides, we also aim to explore DEQ's potential in representing algorithms for reasoning in-context learning, evidence suggests the learned networks perform algorithms in some of these tasks.
Acknowledgements
C. Fang and Z. Lin were supported by National Key R&D Program of China (2022ZD0160300) C. Fang was also supported by the NSF China (No. 62376008). Z. Lin was also supported and the NSF China (No. 62276004).
10

---

References
[1] L. EI Ghaoui, F. Gu, B. Travacca, A. Askari, and A. Tsai, "Implicit deep learning." SIAM Journal Mathematics of Data Science, 2021.
[2] Bai, J. 7. Kolter, and V. Koltun, "Deep equilibrium models," Advances in Neural Information Processing Systems, 2019.
[3] S. Bai, V. Koltun, and J. Z. Kolter, "Multiscale deep equilibrium models," Advances in Neural Information Processing Systems, 2020.
[4] A. Pokle, Z. Geng, and J. Z. Kolter, "Deep equilibrium approaches to diffusion models," Advances in Neural Information Processing Systems, 2022.
[5] D. Gilton, G. Ongie, and R. Willett, "Deep equilibrium architectures for inverse problems in imaging." " IEEE Transactions on Computational Imaging, 2021.
[6] E. Winston and J. Z. Kolter, "Monotone operator equilibrium networks," Advances in Neural Information Processing Systems, 2020.
[7] M. Revay, R. Wang, and I. Manchester, "Lipschitz bounded equilibrium networks," arXiv preprint arXiv:2010.0173 2020.
[8] A. Agarwala and S. Schoenholz, "Deep equilibrium networks are sensitive to initialization statistics," in International Conference on Machine Learning, 2022.
[9] A. Jacot, F. Gabriel, and C. Hongler, "Neural tangent kemel: Convergence and generalization in neural networks," Advances in Neural Information Processing Systems, 2018.
[10] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai, "Gradient descent finds global minima of deep neural networks," in International Conference on Machine Learning, 2019.
[11] Z. Allen-Zhu, Y. Li, and Z. Song, "A convergence theory for deep learning via over- parameterization," in International Conference on Machine Learning, 2019.
[12] Gao, H. Liu, J. Liu, H. Rajan, and H. Gao, "A global convergence theory for deep relu implicit networks via overrparaametrrizatonn"" in International Conference on Learning Representations, 2022.
[13] Z. Ling, X. Xie, Q Wang, Z. Zhang, and Z. Lin, "Global convergence of over over-pareus werr-paameterizee deep equilibrium models," in International Conference on Artificial Intelligence and Statistics, 2023.
[14] Z. Ling, L. Li, Z. Feng, Y. Zhang, F. Zhou, R. C. Qiu, and Z. Liao, "Deep equilibrium models are almost equivalent to not-so-deep explicit models for high-dimensional gaussian mixtures," " in International Conference Machine Learning. 2024.
[15] Bai, V. Koltun, and J. Z. Kolter, "Stabilizing equilibrium models by jacobian regularization," in International Conference Machine Leurning, M. Meila and T. Zhang, Eds., 2021.
[16] K. Kawaguchi, "On the theory of implicit deep learning: Global convergence with implicit layers," in International Conference on Learning Representations, 2021.
[17] T. Gao and H. Gao, "On the optimization and generalization of overparameterrize implicit neural networks," arXiv preprint arXiv:2209.15566 2022.
[18] T. Gao, X. Huo, H. Liu, and H. Gao, "Wide neural networks as gaussian processes: Lessons from deep equilibrium models." Advances in Neural Information Processing Systems, 2023.
[19] R. Eldan and O. Shamir, "The power of depth for feedforward neural networks," in Conference on Learning Theory, 2016.
[20] M. Telgarsky, "Representation benefits of deep feedforward networks." arXiv preprint 1rXiv:1509.08101, 2015.

---

[21] Z. Wang and L. Wu." "Theoretical analysis of the inductive biases in deep convolutional networss Advances in Neural Information Processing Systems, 2024.
[22] M. Emami, M. Aadaaee- P. Pandit, S. Rangan, and A. K. Fletcher, "Implicit bias of linear rnns," in International Conference on Machine Learning, 2021.
[23] A. Daniely, "Depth separation for neural networks," in Conference Learning Theory, 2017.
[24] M. Telgarsky, "Benefits of depth in neural networks," in Conference on Learning Theory, 2016.
[25] I. Safran and O. Shamir, "Depth-widhe tradeoffs in approximating natural functions with neural networks," in International Conference on Machine Learning, 2017.
[26] V. Chatziafratis, S. G. Nagarajan, and I. Panageas, "Better depth-width trade-off's for neural networks through the lens of dynamical systems," in International Conference on Machine Learning, 2020.
[27] E. Malach, G. Yehudai, S. Shalev-Schwartz, and O. Shamir, "The connection between approx- imation, depth separation and learnability in neural networks," in Conference on Learning Theory, 2021.
[28] G. Vardi, D. Reichman, T. Pitassi, and O. Shamir, "Size and depth separation in approximating benign functions with neural networks," in Conference on Learning Theory, 2021.
[29] G. Vardi and O. Shamir, "Neural networks with small weights and depth-separation barriers"" Advances in Neural Information Processing Systems, 2020.
[30] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro, "Characterizing implicit bias in terms of optimization geometry," in International Conference on Machine Learning, 2018.
[31] B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro, "Kernel and rich regimes in overparametriied models," in Conference on Learning Theory, 2020.
[32] P. L. Bartlett, A. Montanari, and A. Rakhlin, "Deep learning: statistical viewpoint," Acta Numerica, 2021.
[33] E. Moroshko, B. E. Woodworth, S. Gunasekar, J. D. Lee, N. Srebro, and D. Soudry, "Implicit bias in deep linear classification: Initialization scale vs training accuracy," Advances in Neural Information Processing Systems, 2020.
[34] Y. Cao, Z. Fang, Y. Wu, D. Zhou, and Q. Gu, "Towards understanding the spectral bias of deep learning," in International Joint Conference on Artificial Intelligence, Z. Zhou, Ed., 2021.
[35] N. Rahaman, A. Baratin, D. Arpit, F. Draxler, M. Lin, F. Hamprecht, Y. Bengio, and A. Courville, "On the spectral bias of neural networks," in International Conference on Machine Learning. PMLR, 2019.
[36] E. Abbe, S. Bengio, A. Lotfi, and K. Rizk, "Generalization on the unseen, logic reasoning and degree currieulum," in International Conference on Machine Learning, 2023.
[37] G. Vardi and O. Shamir, "Implicit regularization in relu networks with the square loss." in Conference on Learning Theory, 2021.
[38] A. Jacot, B. Simsek, F. Spadaro, C. Hongler, and F. Gabriel, "Implicit regularization of random feature models," in International Conference on Machine Learning, 2020.
[39] Y. Li, T. Ma, and H. Zhang, "Algorithmic regularization in pver-parameterized matrix sensing and neural networks with quadratic activations," in Conference On Learning Theory, 2018.
[40] G. F. Montufar, R. Pascanu, K. Cho, and Y. Bengio, "On the number of linear regions of deep neural networks," Advances in Neural Information Processing Systems, 2014.
[41] G. Yehudai and O. Shamir, "On the power and limitations of random features for understanding neural networks," Advances in Neural Information Processing Systems, 2019.
12

---

[42] A. V. Varre, M.-L. Vladarean. L. Pillaud- Vivien, and N. Flammarion, "On the spectral bias of two-layer linear networks," Advances Neural Information Processing Systems, 2024.
[43] Y. Lin, L. Tan, Y. Hao, Wong, H. Dong, W. Zhang, Yang, and Zhang, "Spurious feature diversification improves out-of-distribution generalization, arXiv preprint arXiv:2309.17230 2023.
[44] D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," arXiv preprint arXiv=1412.6980, 2014.
[45] R. Selvaraju, M. Cogswell, A. Das, Vedantam, D. Parikh, and D. Batra, "Grad-cam: Visual explanations from deep networks via gradient-base based localization," in Proceedings of the IEEE International Conference on Computer Vision, 2017.
[46] Deng, W. Dong, R. Socher, I..J. Li, K. Li, and Fei-Fei, "Imagenet: A large- scale hierarchical image database," in 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
[47] Z. Huang, S. Bai, and J. Z. Kolter, "(Implicit) Implicit layers for implicit representations," Advances in Neural Information Processing Systems, 2021.
13

---

A Proofs and Discussions
A.1 Proofs in Subsection 4.1
In following technical lemma, we show that there exists width-m ReI.U-DEQ computing function with 2 linear regions.
Lemma 4. Let N+. For all m consider the following function on [0,1]":
{ 2=
01 - 2i,
E
2
26+1
S i i 2 - 1,
(xm) = 2"'x1 + 24
2 2
21 E
2:+1
2 n
M i 2<is2-11 - 1.
2
Then there exists a DEQ with width m that exactly computes - (p(m)(( + x= on [0, 1]d, Moreover the DEQ has 2 linear regions on [0, 1]6.
Proof. Since 21 is linear function with respect to 21, by definition, -x(m)(x) + 21 has 2 2i 2i+22
linear regions on 2
x [0, 1]=- for all 0 < i < 2 - 1. Thus has 2n linear regions on [0, 1] It suffices to show that existence of DEQ computing (m() + 21.
2
Consider width-m DEQ with weight matrices as follows:
2
4
0
m
4
AT
W
8
0
U =
=
2
2
2
22m-1
-2
where U1 denotes the first column of and U (U, 0). When a DEQ equipped with the above weight matrices, direct calculations show that the fixed point satisfy
Σ 211 (x) + +2'm1 +--mm-1))) -1).
(x) o(2m1 1), 2xx)
22515 m. (16)
Note that (x)} admits a recursive expression:
((++1) 20(mm) (x) 20((2 (x) 1),
Vm 2
(17)
for ((0)( = T1. We now show by induction that (x) (2 - 1) for all < L < m.
When is true immediately from Eq. (16) and Assume it true for some < m, then
by Eq. (16) we have
2--1 (x)
21-1+2 22(2x + + x1 -1
2 1-12 i+2 0 (2 (0-1)) (x) 1) + 2 x1 -1)
(x)
-2 -+2 1+2
(x)
+ 2 -1
= =
(0) (x) + (0) (x) + + 1 - 11) = (20 1),
where we use the induction in the second line, Eq. 17 in the third line, and (0(0 = - in the last line. Thus the induction holds.
14

---

Using the induction and Eq. (7 for the DEQ, we have
A Az(x)
2m+1-12:
i=
2m+1-
-0(( -1)
i=1
(xi-11(x)= (2((1(x)
22m+1-i
2nd 2 (x) + ((()) = -6(m) (x) -2"xx1
and the lemma follows.
To prove the theorem, we also need the following lemma which is proved in (20].
Lemma 5 (Lemma 2.1 in (20)) Lel k N+, 2 2 and p(x) IR R be a piecewise affine linear function with pieces. Then every I R - implemented by an FNN with depth I,, width k and activation function p has most (pk) linear regions.
Note that the in Lemma 4 the function computed by DEQ is variant of the saw-tooth function that has many linear regions. On the other hand, Lemma provides an upper bound the number of linear regions generated by FNN. Combining these two lemmas and using a technique similar to that in Theorem 1.1 in 24]. are able to prove Theorem
Proof of Theorem 7 Let Na(x) be the DEQ in Lemma 4 that computes 2 ((m) (x) and denote
the width of the FNN that computes Ny (z) by h. For any y [0, 1] define Py(x) [0, 1] [0, 1] Py = (x).y). Then for N2 o Py (x) [0, R, by Lemma the number of linear regions
upper bounded by
(pk) <
2
where p- 2 denotes the number of linear pieces of ReLU activation function. Therefore, Ny Py (z) 2 has at most 2 linear regions on [o, 1].
Note that (5(m only depends the first entry of x, for simplicity, define ( RR - R as (p(m) (x:) (((m) (x))) Now claim that there exists at least 3 2m-3 2 small intervals (Ti)
on [0, 1] with diam = 2-m,, such that for any y. it holds that
1 2 # sgn N oy 2 1 -
sgn 0 (m) (x)
Vo Th VL.
For simplicity, denote (px)) ((m) (x) 1 and N2 = N, Py (z) 2" Denote Ps and Py the partitions of [0, 1] into intervals so that sgn (f(z)) and sgm (N)(x)) remains constant within each interval, respectively. Let Ig be the set of all intervals partitioned by Pa and IN be the set of all intervals partitioned by Px. By definition, [ppl 2 + 1. Since N (x) has at most n linear regions, the number of the boundary points of the intervals in IN is upper bounded 2 1. So 1) 3 2 intervals in I, that do not intersect with any boundary points of intervals, i.e., lie completely in an interval in IN. Denote this set of intervals by Tz-- On the other hand, since sgn( (N, remains constant every interval in IN. for every In that contains i, intervals in T there will be frt1 intervals when i, odd and 1/ intervals when é, is even, which sgn(}(=)) (x)) Note that EJEIN ? 2 3 m Therefore, among the sets in T the number of sets on which sgn({(x))) sgn(N)(x)) (z)) is at least
there are at least 2 - (2
2
Σ i 2m-3
3 3
JEIN
where we use the fact that Inl < 2 + 1. Note that except for two intervals, every T E I' can be represented
1++1 1643 or 20 1T
1i-1 1++1
for some i, thus diam(Ti) 2-m, which proves the
FT: 1 FT
15

---

claim. Moreover, on each Tí, direct calculations show fn (z(m)(() - 2/ dz 2 2 mm- Therefore, by using the claim, we have
1 10.14 [Na(x)-NN(xx) - -Nx(x))xx
2 (x1) - Ny py ( dxndy
10.1/0-1 10.11
2n (x1)
N2 oy dridy
10,1/--1 U.
1
(lm) dxidy
[0.1ja-1 J T7
2
[Til 2 2-
10,1/a-1
2m-
-2) 2-m-2
>
16
Next we turn to proof Proposition 1 We use Diag(-) :) to extract the diagonal elements of a matrix into vector. The proof of Proposition I relies on following explicit expression of ReLU DEQ.
Lemma 6. Let W, U,U.b. b be the weights of a DEQ with || W ll < 1. Then for any x E R there exists a diagonal matrix D E RRdxd whose diagonal entries are either or O, such that
(on(diag(II-W)))) -WD) +b) b)) Diag(D).
(18)
Moreover, fix D, for all x that Eq. 18) holds, we have
z z(x) (I -D(Ux+t)
(19)
Proof. Recall that the fixed point xx) satisfies
o W zw Ux+b)
(20)
For each if the i-th entry of (W z Ux+ b) is smaller than 0, then 2; = 0. Without loss of generality, we assume that the first S m) entries (W z + Ux+ b) are greater than 0, and the rest m / entries are smaller than 0. Denote by v Ux + b and the corresponding block matrices z, W, v by
00 0
W
WI1 11 W21
W12 Wn
V1 V2
(21)
where ă Rt, Wn E pixt and V1 E R. Then, Eq. 20 is equivalent to
z W W + VI,
W2 0,
2>0. 0.
(22)
I 0 and show that the desired matrix. Note that W l < and
Now we define D
0
||D||2 we have
W = W w < W |||||| < 1,
showing that I, W1 is invertible. Thus Eq. (2 gives
à = (I. Wn) W'v > 0, Wa1 Wn) + V22 S
(23)
Additionally, by simple calculation, we have
-I- -W) (I. - Wnn) (I. - - )
I
(24)
(I, W Wn) -1 0)
II WD (Wi(I, Wn)
16

---

Combining Eq.
21
and 24
we have
WH1 Vi WD) (Ux+b) (21 Wu) -0-vvv1 +
(1.
Win) (i--wi)-vv = -W- +D 0
Finally, since the output of the implicit layer is unique, in the sense of permuting the entries of D, there always exists matrix D such that the lemma follows.
1
Note that there are at most 2 diagonal matrix whose diagonal entries are either or 0, the upper bound of the number of línear regions is 2 Thus Proposition | follows straightforwardly from Lemma and
A.2 Proofs Subsection 4.2
A.2.1
Inapproximability of FNNS
The goal of this section is to prove the following proposition, which is an extended version of the inapproximability result Theorem
Assumption 2.
The activation function 5 is of (IR and continuous differentiable except for at most finitely many points. And there exists an absolute constant Ca >> O, such that (1(x) S Ca for all on which ā is differentiable.
Proposition (Inapproximability of FNN). Let (m) ) be computed by an FNN with depth L, width k. and an activation function ā satisfying Assumption
2 on x E [0, 1] Let g(x) be defined as in
Eq.(6) and
O. [l (x) -g(x)llu==((0 ((0.11))
then there exists weight parameter W st
of the FNN for 1 I S. and 1 S j S k, such that
Wol
2
d=1
Caki
Proof. By assumption, (x) of CO and continuous differentiable except for at most finitely many points, then by the intermediate value theorem, we have
NN (x)
(1) -1 8)
5(1-5)
2
max [)
85 -1 2d-4
(25)
dz
where
(N)m())) Ox
refers to the subgradient on the non non-differentiable points. Additionally, by definition,
Nino (x) = W WW--oō(..-öWW, ....) + b
Then direct calculation gives
V (x) WTDD ... Di-
(26)
where D, diag(ō' diag(G'(Wiā( (W. ( bi) ...) + b:)) for 1 <1 L 1. By Assumption 2 it holds that
Dilloo S Ca.
Then combining Eq.
(5
and
26
we have
2d
N Ynn (x)ll
II D. W.
c II bo
i=1
Therefore, there exists at least one W, for
$ i < L. such that
W 2 C:=11 2
Finally, by the definition of -loce there exists an entry W5 with 1 S < k. such that
1
Wyl >
C₂K
17

---

Remark 5. Assumption is mild and one can verify that most commonly used activation functions such ReLU, GeLU, sigmoid and tanh satisfy the assumption.
To prove the inapproximability of FNNs in Theorem and derive
2
we take C3 = in Proposition 3 as o
r'(2)) S
W 2 k 2 d=4
22 +
22
which finishes the proof.
A.2.2 Approximability of DEQs
This section centers around the upproximability result of DEQs. We restate the approximability result of Theorem 2 as the following proposition.
Proposition 4 (Approximability of DEQ). Let g(x) be defined as in Eq.(O) on [0, 1] t = 0, there exists DEQ Náeq with width bounded by 5e and weights bounded by 2,-1, such that
|N (x) 9(x)ll 9(x)]l==<(0011))) Se.
The proof of the proposition requires some intermediate steps regrading the constructing approxima- tion by DEQ and bounding the fixed-points' error. For simplicity, in the rest of the section, for any function f which continuous differentiable except for at most finitely many points, we denote f' the derivative of f on the differentiable points, and the subgradient of f on the non-differentiable points.
The next lemma considers approximating the square function using 2-layer FNN.
Lemma 7. For any E N+ there exists a function & implemented by a 2-layer ReLU FNN with width 2N such that
1 N Vo [-1,]]
[d(x) - x31 2 SN 4N
[0'(z) 2
Proof. Denote N by for simplicity. Let |=1 be 2N points on R be defined as follows:
2N+1 11 = - t T2N = 1 - 1, J2N+1 =
We consider the following function c(x) that interpolates x² on all (x,))2T+1
N Σ o--2tr - 2it²).
(<x) σ ((x) + to(-xr) Σ (21x - 2il²)
(27)
i=
It can be seen that x(x) can be implemented by a 2-layer ReLU FNN with width 2N and weight bounded by 21. By the interpolation property of (xx). on every (ır 1) it holds
max (x(x)) -x Φ x=(2,,0,_1]
Ø +
2 + Tj+1
2
2
4
Thus have lx(x)) =22 4N-2 for all [-1,1]. Moreover, since ((x) is convex, have
[d'(x)) 1 (1 1)2
2
We now move to prove the equivalence between the revised DEQ and vanilla DEQ.
Proof of Lemmal 7 For any d0 T. we define sequence (2*) as
k+1 o (W V + Ux b).
Since || W V 2 < 1, {2*} converges and the limit 2n is the fixed point of 2 Ux+
Now we set z Vy and define another sequence {z*}
+ *+1 Vo Ux+b), vk 0.
18

---

It follows immediately by induction that z" V2 for all k > 0. Note that {z*} converges and the
limit z" is exactly the fixed point of the revised DEQ Eq. Therefore, holds that
z
lim z²
lim Vz V2*. R-000
100000
The desired DEQ is constructed
2 = o V2 Ux+
y = (BV)
In the following we turn to bound the error between the equilibria of two fixed-point equations. We start with the proof of Lemma
Proof of Lemma The existence of zu and By follows from the fixed point theorem since u(,, x) and v(-, x) are contraction mappings. For simplicity, we denote ux ux(=)) = u(2, x) and ux(2) = v(2, x).
Note that the range of ux and 8x are in Q. Then Vn N+, we have
1xx 2x 100 <
"x
Ux
(o(n-1))
xxx
+
Uxx
10 (12(m-1)) - xx
00
S
Teu
4
o(n 1)
xxx
(n (2 1)
+ Ulx Uxlloc
<
La
(x--2) - (n
+ || exllo0) + 1|ux - exllo
< ...
<
(1 + Lu, ... - 11 1x0
L
Uxx
-xxlooo
Lu
By definition, v(2,x) E 12 [0, 1]dd zn (x) = lim ux (2). and (x) = lim, (z). Hence,
we have
[zu(x) - xx)]
lim | (z) on (=)l 1-+000
1 1 L
lim
max |1(2,xx v(2,x)]
L,,
senl
max (u(z, x) - v(2,x)) x))- zE
La
Finally, by the symmetry of u and v, we also have (za(x) zo(x)) S - maxxea (u(z,x)
0(2, x)]. The proof is finished.
We also need Lemma 3 to bound the error.
Proof of Lemma We use the intermediate value theorem to proof the lemma. Define q(2, x) x). The fixed point 2, (x) is the unique zero of q(2,x) 0. Since v(2,x) is L, Lipschitz with respect to z and L, < 1, 4(2,x) x) is monotonically increasing with respect to z for all x.
Fix 2g, the proof proceeds by discussing the following 2 cases:
If x(z,,x) < 0, i.e., u(z,,x) 2, S v(2n, x), we consider T [zu 2n E] C. Ω. By assumption, there exists =" E T, such that u(z".x = v(2", x). Note that g(, x) is monotonically increasing, thus we have q(=", x) O. By the continuity of q(2, x) w.r.t.
z and the intermediate value theorem, g(2, x) must have zero in [2w, 20] C T, which is (x) by definition. Hence, it holds that 2zu zyl S g.
If q(zu, x) 2 0, i.e., u(2n,x) zu 2 v2z, x), we consider T = [zv. E, C Q.
follows from similar deductions that Izu 2vl < E in this case.
19

---

We finish the proof.
The proof is sketched as follows: First, we consider fixed point equation 0(2, x) that induces the target function g(x). We show that there exists function x(2 Rd+1 I computed by a 2-layer FNN with width (e that can approximate ğ(2, x) in sup-norm to an accuracy of OE=²). Moreover, 2 h(2, x) a well posed fixed point equation and induces a revised DEQ. Second, we bound the error between g(x) and h(x), where h(x) is the fixed point of = 1(2,x). The proof is further divided into two parts: When 1 21 > 2: by using Lemma 2 can bound the error ||h gll by E 11 øll- When 21 < 2. we show that the conditions of Proposition 4 holds for { = E. thus ||h gll is upper bounded by E.
With the results above, we begin our formal proof of Proposition +
x):
Proof of Proposition 4 fixed point equation
Let g(x) be defined as in Eq. Recall that g(x) is the fixed point of the
x = ū(2,x) == 201 + 5 21 ( -) 2).
Approxímate I using 2-layer FNN. By Lemma VN E N+, there exist a IR,2N, b E R2N, W 22N and function d(x)
= a o [wr r + b). such that for all x E [-1, 1], holds
(ΦN(z) - 23 s AN
(x((1) 2 N
(28)
Now, we define
x(,,x)
1 2 ΦN 2 11 ON (z
2) ]] + 6 11 -2)
2 2)
1. h(z, x) can be implemented by a 2-layer ReLU FNN with width 4N + 2 for (z, E
8, 2
11
x [0. 1]a. To see this, when (2, x) E [-8, 11 x [0, 1jd, it holds 2 + 21 E [0,
2
z #1 E [-1,0]. Then
2
W
b
2
A
AT
5
8
W
0
+
b
1
0
2
x-1 1
-1
0
W (z + + b)
W (2 +b
a
8 6)
(2
(29)
(2 )
T
W
2
+ +b)
+ aT
(w/6 (:
I1
+ +b)
2
2
2
2
+8
0
1 +
31
0
2
51
2
2
1
ΦN (2+ +
ΦN
22- 2
+
21
2 =) = h(2,,))
2
where the first line resembles a function implemented by an FNN with width 4N +
2. 7((2, x) approximate 8(2, x) well on (2,x) E [-5, 2] x [0. 1jd Since 2 + 2 E [0. 1] and
= -/2 E 1-1, 0]. from Eq. (88. we have
1m( x) x(,,,)
ΦN
+
(2 +
27
ØN
2
31
(z
J1 2
2
2
2
2
(
Σ1
xx
+ 31
+
1
ΦN
2
31
2
2
2
2
2
2
2
2
(2)
<
+
2
1
1
(30)
20

---

3. The fixed point equation = ((2xx) is well-posed on
[-6, 2] x [0, 1]d. for the partial
derivative 0h(2,x) we have
dz
ah(z x)
31 2
(z (2- 211
0N
Oz
2
- 2
NN
= +
21
Φ'
(a+ 21 - 1) - 8
2
2
< 1 8 < 1,
where the second line holds because o' (x) is monotonically increasing and æ1 < 1. There- fore, the fixed point equation 2 = h(2, x) has a unique solution for all x.
4. Note that h(2, x) can be computed by revised DEQ defined in Eq.
with
W
a"
a² 2
-
8).
W
W
B=1
2
And it can be verified that || W Vlla =
28 S 1. By Lemma D the fixed point of 2 = M[2,, x) can be computed by DEQ with width 4N + 2, which we denote by (x).
Further calculations show that the weight of the DEQ is also bounded by 21.
Approximate g using the induced DEQ. We will bound ||Naeq (x) (xx)]l==(0000)))) using Lemma
2 and Lemma Let Q = [-6, 2 and assume that 1. > 105. It can be easily verified that both the range of ((2, x) and h(2,x) are in Ω when (z,x) E Ω x [0, 1|
1. When T1 S 1 $. by definition, the Lipschitz constant of g(,xx) is upper bounded by 07(2.x) 0=
max
Leveraging Lemma and (3), we have
|Nac (x) g(xx) S Ög(z,x)
2 12
[k(2,x) x(2
- t 4
Oz
2
2. When 1 >
x > 1 $1 if + 4 = ntt for some
N 2
1-15
11 n S N, we have
T1
N
N / -)-)
2
nt
E
n
2
Note that xxx(x) > x for all x E [0, 1]] (N and @N(Z)) = x for all x E [o, 1] N Thus,
when nt 2. we have
h(2, x) < 2
( 2 + 31 2 -
2 2
+ 2
11
2
F1
2) = =)(2,x).
For every T C Ω with [T| S I, there exists 2g E T, such that Zg = nll
21
Thus, from the
2
above analysis, know that h(zg, x) 0(2y, x).
On the other hand, if = 2 kt for some 0 S k S N 1, we have
2
21 kt +
x1
1:
N
-1 1 1
t,
k (-1++
N
2)
2 ))
2
Similarly, we have
h(2,x) > (( 2 21
2 2
(2
1 2
+ ))
2 -2) 2) [(222
2
For every C Ω with [T] S l, there exists 2 E T, such that 21 = -/- kl. Thus we have
h(zz x) > [(2g, x). From the intermediate value theorem, there exists 2" E T, such that
h(2", xx) = 0(2", x). Thus it follows from Lemma 3 immediately that
dN (x) g(x) S
21

---

Additionally, when 1, by simple calculations, we have (2.x) (2,x) Nacg(2 (x) = g(x) 1.2 Combining all the results above, we have
1 indicating that
[Nee 5(x)l S [Ø(x) - S4, [0
By choosing t t= E, we finish the proof.
A.3 Proofs in Section 5
We start with the proof of Theorem
Proof of Theorem 3 Denote { the process that follows the gradient flow dynamics wr(t)
-V -Vw(((()) initialized by ((0) > O. Recall that the empirical loss is 1 X 3 y l1 then the dynamics of (3(1)} can be computed as follows:
d,((t) V VwB(tt) duo(t)
dt
dt
VwB(1)) (-Vm
1
x x(((1) y11
2
(31)
(-Va =- =x(Xir(t)) O B(t) 00
vwB((t)
_ x((()) y 12
where r(() X (()) denotes the residual. For any O, it can be verified easily from Eq.
31
that
3 3(100-3 + -(00)-33 =-x J. r(s)ds.
(32)
For simplicity, denote vtt 10' rs))ds. Then from Eq. 32 we have
(()) (3x" v(I) + =(0) c-
(33)
By assumption, (t)) converges to some 0 Rd when + co, thus v(t) converges to some
00 Jo r(s)ds. By letting + oc in Eq. 33 we have
8 (3x + 3(0) ((0)0-3)0-3
(34)
Next we want to show that - satisfies the KKT condition of the optimization problem Eq. Given access the expression of Q(3), the KKT optimality conditions can be expressed as
12)
x y, VQ(3") = X Xv,
for some E RRd, By the definition of Q(9). vQ(=)=((()0)--))-0))))))>))))))) x" v is equivalent to
(x" v): (VQ($*)); = o (8T) - + 3, Vi.
On the other hand, from Eq. 34p. can be verified that
- + (0 - - v
(,) (() -3
Vi.
Thus holds that VQ(3*)) = x Combining this with the assumption that X 7 = y, we derive that 8 satisfies the KKT condition. Moreover, it can be observed that Q(3) is convex, which makes 8 an optimum of the problem.
Proof of Theorem Gradient Flow. We first show that the distance between (()) and 3 bounded. From the dynamic of ((1)) shown in Eq. 31). we can derive that the gradient flow of [|)((1) 3 below:
de [i((t) - -3-11 (dB(t) dt ) T
d
2
(3(t) - 3*) = x - B*) o 0())2
S 0. (35)
22

---

Therefore, (t 3 2 is monotonically non -on-inceaasing and upper bounded by [| - 3 l1 for all By Assumption have
|B( 10 - [[ 3 xc + 11,3
< (1((() 30 + 11
$ 1100 +11B- -
On the other hand, we also have
x 2 |0 (1 12 1 11 - ( 2c
(36)
for all t. To prove the convergence, we denote r(t) 3(t)) y. The gradient flow of [|r(t]
d
<d,((t) T x" x'r(t) = (x)))) o 3(t)a4.
dt |rtt =
(37)
dt
Combining this with the fact that /Amin
and the lower boundedness of
|13(())l || then have
de |1r(012 - -c² - (
which proves the convergence of gradient flow. Thus (t)) converges optima 37. By letting t oo and using the lower boundedness of [I,((t)ll we know that || 2 c.
Gradient Descent. The proof of gradient descent follows from similar strategy. We first give an explicit expression the update on 3 In the following we denote r²t = x y. Recall that the gradient descent iterate w; is
R+I w
W. '1 (1 w
where x; denotes the i-th column X. Then by the definition of B, we have
1
1
1 1- w
gk+1
w. 1+1
w
wi
w + +
8 3 gk+1
(1,5) 3 r
Equivalently, the update of ,3 can be expressed as
g = 3h n Ou, u² ==== 03 gh+
(38)
We now show that with appropriate choice of i7, the distance between 3 and 3 is bounded. By we have
Eq. 38
|1gh+1 - 30-12 - -11,* - -3-113 = ||gttt1 - 3 2-( 3T 1 Bt)
= XT uutl 2n ||, @ (ut)o
S Mmax 1/ Σ (2 2n (
(39)
i=1
(Mmaxt) 2 (
Assume 3 > 0 for all & so that uf > 0 for all i. Now we set 17 < Uprns holds for each i that
With these conditions, it
Mmax (u 27u < 0.
Combining this with Eq. 139.. we have || 33113 S |1 3- Similar to Eq. 36 by Assumption can be shown that || ||@*||cc ol 2 >> for all k: We then turn to analyze the update of ||r Note that the square loss function is -mmo-Smooth w.r.t. B, thus have
|| + 1 < | + 2(r X((a++1 - -3* + Mmax g 11.
23

---

Substituting the update of 3 in Eq. 338
into the above equation, we have
+++ - |r^1 2n(r*) - X (x"r* @ (Bhtt)3 @ 3²)
+ Mmax |x' (ght2)8 の 0
=|r=112 2n Σ Puf + ni Mmax Σ E(GuN)
(40)
where we denote X 1lt for simplicity. For every fixed 14 the quadratic function f(
-2m(1) + +1 Mmux u2 attains its minima at uf = TPass > C, from which we know that f (u,)
monotonically decreasing for up C. Hence, by the fact that u > G, holds that
-2n(11))u u + Mmax (1/ S (-2nje + Mmmx 21 I 0,
visism (41)
Note that 11, 1| xr113 S Pmax || 112- Leveraging this and Eq. (40) and Eq. we have
1 11 s (1 (-2nje + 1f Umar )|r
Moreover, to ensure 3
1 1+" X rD
for all we choose
7 S
X 112111"112 S
| 1 xf
ro
031
Umax ||=0
With this choice of 17, prove by induction that the assumption 3 >> 0 holds for all k. Indeed, follows immediately from assumption. If 3' > 0 holds, then from update g++1, we have
8
3 X
8 1 Px!
2 1 (
2
2 0. 1|
x 12 12/1=1|12
C
Thus the induction holds. Finally, we set r7 = min C"
then 3 converges to an || Imx 2 c. We finish the proof.
C jameell |
optimal _ It follows from || 2 c that
Next, move prove Proposition| 2 For completeness, we formally introduce the definition of GOTU in (36] as below.
Definition (Generalization on the Unseen, [6)). Let :
be a loss function and S be given sample spuce. During training, purt of S is not sumpled, which we cull the unseen domain U,
while in testing, we sample from the full set S. Let f be the target function and fsyu the function learned by a learning algorithm on S.. The generalization on the unseen for an algorithm f and target function function J. is defined
GOTU - =Exmul((fsu(X),,
where well refers to uniform sampling from u.
Proof of Proposition We first give an explicit expression of the expected loss and gradient flow dynamics. Denote
d Σ 3,0 + f(w,
fo(x)
W; I; + b.
i=1
By definition, the half &2 loss on any sample x is
1 ((f(x),,(())) = - (f(()) f(x)) = 2
b f(0) + Σ (B.- (B--)((0)) 1=1
Denote the distribution on the training set by Ud=11 Note that {1, -1, raf are orthogonal in the Hilbert space S (=1] equipped with the inner product (g. h) Ex 1= (g(x)/(xx)) Denote
24

---

the distribution on the training samples by U_ By using Parseval's Theorem, the expected loss on the training set can be expressed as:
E (x4=, - ] u (1- [(0) + Σ (3. (a- oz) )1
xi Σ (Bc - ((0)))
i=1
b f(0) Ba )((33)))
Then we can derive the gradient flow for 3 and as below
db(t)
dt (b(t) f(0) + Bx(t) f((K))),
d,3g (1)
(b(t) f(0) + (x(t) ((E))))
dt
dt, (3.(1) ((1)))),(0)) W
dt
For simplicity, denote B = f(0) + f((K)). Using the above, we have
d (b(t) + (x(() - B)2 2(b(t) + 3x()) () + (L(()*),
dt
(42)
(8.(1)
-((,())) -(1))))0-(0)))00))))
which shows that (b(() + B&(() B12 and (3:(1) - 2( is monotonically nonincreasing. Since (,(0) and f(fi)) greater than O. from the monotonicity know that (t()) for all t.
Therefore, the convergence of gradient flow follows from Eq. (42) that both [6(1) + (1) - BI and
(t) - 1( decrease linearly.
Denote the limit of (t(t) and b(t) by 3.0 and bo respectively. We now turn to estimate the GOTU error.
1. When B > 1, it holds that 6(0) + (0) B < 0, thus b(() and B&(() is monotonically increasing. Using the fact that (1) (0) 1, we know that
a (Ba(t) - b(t)) 2(b(t) + (c(() (Bx(()))) - 1) <.
Combing this with 3% + 800 B, can be verified that S > and Parseval's theorem, the GOTU loss is
B+1
Then by definition
2
d Σ (
Gf = - 1}) = (6x- f(0) - 3 + F((K)))2
#
-4((((+))) - -220)
where the convergence of the flow in the second line. Leveraging the bound of gr we derive that
( < (F((E))-
B B+1) !)
2
(43)
By the assumption that f(0) < 2f((())) we have B+1
< 3f((k))+1 2
2f((1)) Leverag-
2
ing this in Eq. (33 know that
GOTU J, (xx -1) < (f((k) + 1)3
(44)
2. When B < 1, similar to the proof Theorem
we have from the dynamic of (t) that
(a(1) -3 - 1= f (b(s) + (x B)ds s 3(1 - B),
25

---

where we use the monotonicity of b(s) + (x(t) - B and the convergence of the flow.
Therefore, it holds that 3x 2 (3(1 - B3 + +)= 3. We can bound the GOTU error
4(f(()))) -, - 4(f(()))) (3(1 - B) +)
(45)
By using the assumption that f(0) > - -f(())), Eq. 445 gives
- (4+ (((1)))((4+331))) (4+35(133)) 2
GOTUU, -xx= -m) 4
(46)
Then the proposition follows from Eq. and 46
A.4 Discussion on Comparison Fairness
In this section, we provide a detailed discussion on the fairness of the comparison in the separation results between the expressivity on DEQs and FNNs.
Concerns may arise regarding the fairness of comparing finite-depth FNNs to DEQs, which resemble infinite-dppth weight-tied FNNs. However, as stated in Section 4 our separation results are mainly stated from the actual size of the network (Theorem 2 also considers the parameter magnitude). Characterizing expressivity in term of the depth and width of the network is common approach as these dimensions can be manipulated in practice. From a theoretical perspective, one primary goal for the comparison is to investigate how the DEQ architecture influences the model capacity with the same number of parameters as FNN 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. Our separation results provide concrete examples of functions that DEQs can approximate more purameter-effiienlly. Thus, we believe that it is reasonable to compare the expressivity from the actual size as well as the number of parameters of the networks.
Another concern is whether our separation remains valid when considering the actual memory and computational costs associated with training DEQs. If a DEQ needs exponentially more computational cost than FNN, it could be justifiable to compare a DEQ to an FNN of exponentially larger depth. Nevertheless, considering these issues is beyond the scope of this paper since they are also determined by the forward and backward algorithms used. For completeness, we provide some comparisons based on the computational cost of the forward propagation of DEQs as follows.
For the DEQ in Theorem L we claim that it needs one step converge using fixed-point iteration. This is achieved by initializing iteration point z" according to Eq. (T6) (While it may seem tricky to initialize z" as the fixed point, the logic here is that we first observe such convergence under this initialization that we claim this z to be the fixed point). Then from the definition of W, U and b, each entry of z can be calculated as
(-
t-1
0 + Ue1 -by by de) =0 WHi 2/ = o Σ
2 24 + +2'x11 -
i41
=
i=1
showing that it converges in one iteration. Additionally, if we set z0 = 0. which may be considered less ad hoc, and denote the fixed point by z². Then using the trianulrryyyy of W, we can show by induction that 2 2 for all 1 < k. Thus, the convergence is achieved in at most m iterations, which still remains far from exponential.
For the DEQ in Theorem 2 we claim that it needs 1o-)(= + lbgg(b- - a) iterations to achieve an O(e)-solution using bisection method. Given the DEQ, we can derive revised DEQ, i.e., z Vo Ux + b) based on our Lemma [ can inversely derive the revised DEQ through rank- one decomposition, and we admit any version of it). Then for the function = Vo(W: + Ux b). we choose some (a", b7] as the initial interval such that this function has opposite signs on a² and 6". Then after k iterations the solution z will lie within an interval {a 66*. From the definition
of the algorithm, we know that Ji+1 a i+1 = 2- (b' a²), leading to b² a² < 2 >-((0 a²).
To achieve an O(e) O()-ssoluo i.e., 2 a²) ) S E, we can require k 2 log, e1 + log, )²). which proves claim.
26

---

000
DS0.M PELLINE WHITE PRELIIN WNOE
FAN (nL.R01 (HG
(a) 2a lincar regions.
(b) 2 linear regions.
(c) 21 linear regions.
Figure 3: Test loss of FNN and DEQ trained on sawtooth functions with 21, 23, 215 linear regions.
wiQui
12
FNN-1-3,W-50
Infinity W
10
Figure 4: Results on steep target functions applying DEQ and FNN with comparable performance on loss. We plot the infinity norm of the weights of DEQ and FNN with 6,8, 10, 12, 14, 16, 18, 20.
For the memory cost, DEQ's memory usage is comparable to that of constant-depth FNN. Since the DEQs we consider in theorems have fewer parameters, they are more advantageous than the corresponding FNNs in memory consumption. Consequently, our comparisons are likely to remain valid even when actual memory and computational costs are taken into account.
B Experiment Details
B.1 Supplementary Experiments on Separation Results
More experiments piecewise functions. We first experiment other sawtooth functions with varying number of linear regions in the setting of Figure further validate our theoretical results. Figure 3 presents the test loss for sawtooth functions with 2 2 and 2 linear regions. For all experiments, we execute our programs on Nvidia GTX 1660 and all the programs occupy less than 10M memory and run for less than 2 minutes. Consistent with results in Section 6 observe that DEQ outperforms FNN with similar size of network on every sawtooth function in our experiment and the test loss of DEQ converges closer to zero loss.
Additionally, we conduct an experiment to investigate the performance DEQ and FNN on sawtooth function with similar actual computational cost to further strengthen the fairness as discussed in Appendix A.4 Following the standard setting, all models in our experiment are trained using lz loss with AdamW optimizer [44), with learning rate of 5c-4, weight decay of lc-4 and cosine annealing scheduler for 1000 iterations. Table Tindicates that when training on sawtooth function I
under similar computational cost, DEQ also performs better than FNN.
More experiments on steep target functions. To verify the statements of the magnitude of weights we add an experiment to examine the infinity norm of the weights of DEQ and FNN when training on steep target functions with varying d, as shown in Figure 4 In this experiment, we train a 3-layer FNN and a 50- width DEQ model using the & loss. Following standard settings, we employ mini-batch SGD optimizer with learning rate of 0.005, weight decay of le-4 and a cosine annealing scheduler for all models. The infinity norm of the weights of DEQ remains approximately
in Theorem 2
27

---

Model
Parameter number
layer
hidden dimension
Average FLOPs/Ite
Loss
DEQ
251
3.44e5
0.078 = 0.004
FNN
2401
30
3. 3.18
0.094 + 0.006
FNN
2281
3
40
3.03e5
0.082 + 0.004
FNN
2801
200
3.84e5
0.085 + 0.007
Table Training settings of experiment. We apply DEQ with width- 10 and FNN trained on sawtooth larget function with 2 linear regions while keeping FLOPs per iteration similar.
4.
GOTU
PCQ SOTU
L,555
02-
00
276
490
1080
Reration
Reration
(a) OOD function
fi-
(b) OOD function fz.
Figure 5: Train and test loss of DEQ and FNN trained on OOD tasks f1 and f2.
constant when d increases, while the infinity norm of FNN rises with d, verifying the theoretical claims that DEQ with polynomially bounded size and magnitude can efficiently approximate certain steep functions in infinity norm while FNN cannot.
B.2 Experiments on the Bias on Learning Dynamies
More experiments on Distr--Distiituttion tasks. We conduct more out-of-distribution (OOD) experiments on the following 2 functions and unseen domains. The first function is higher- dimensional extension of Eq. (14) which is a form of mean function. The second function is the majority function for 3 bits with maximum degree of 3. The mathematical expressions of these functions are presented below.
(x) = 1.25 * zo + 1.25 * 21 + ... + 1.25 * T20
u= fx E [ x1 = -
1
f2(x)= 2 To +
2)3)3,,, -1)25))) u = =x
[=1]
J6 -1..
For all experiments, we generate all binary sequences in === (=1 for training. Figure 5 a) shows that the GOTU error does not increase significantly compared to Figure I where the ambient dimension is 10. In consistency with our results in Section O we can learn from Figure 5(a) that when learning linear boolean function on population loss on DEQ, the training loss converges to zero and the generalization error on the unseen is bounded. As shown in Figure 5)), when learning the unlinear boolean function, DEQ can also achieve nearly zero train loss with smaller GOTU error compared with FNN.
Experiment on salinecy map. We further provide a visualization experiment investigate whether the 'dense' bias property still holds for more general DEQs, particularly those with inner structures resembling ResNet or Transformer architectures. Specifically, we conduct an experiment using Grad-CAM [5] to generate the saliency map of Multiscale DEQ (MDEQ B3), which is variant of ResNet-DEQ and compare with that of ResNet-50 trained for image classification on ImageNet
46). The saliency map highlights the regions that are crucial for the model's 's prediction, which can be regarded as the features. It is shown in Figure 6 that MDEQ allocates attention to more features such as the fences and trees in the background, indicating that MDEQ may generate dense features. The intuitive experiment suggests that our bias results may be applicable to a wider array of DEQs with general architectures.
28

---

(a) Raw image of horses.
(b) MDEQ's saliency map. (c) ResNet's saliency map.
(d) Raw image of dogs.
(e) MDEQ's saliency map. (l) ResNet's saliency map.
Figure 6: The saliency map of Multiscale DEQ (MDEQ) and ResNet.
820 ceovruciinn
FM comsiration
6.4
04-
0.0
0.-
-6.3
-8.
-66
20003
200000
:30boo
230000
50000
120000
130003
230003
(a) Audio reconstruction using DEQ.
(b) Audio reconstruction using FNN.
Figure 7: The reconstruction results with DEQ and FNN and the error computed by subtracting the original signal.
Experiment on audio representation. Inspired by the overall studies, we conduct an experiment real task of audio representation to verify the potential advantage of DEQ in learning functions with feeh-freyeency component. We utilize the setting of experiments in [47]. where the very-high- frequency audio signals network, which is a variant of DEQ employing a neural block with three layers and specific activation functions such si)( Although Huang al. 47 show that (implicit) network outperforms conventional explicit networks audio representation (47), revealing the advantage of DEQ to an extend, it is unclear whether the superiority of the (implicit)² network is attributed solely to the carefully-des dessgned block. In contrast, we apply DEQ and FNN in their basic forms to represent the audio signal in our experiment further explore the potential advantages of DEQ in real scenarios.
represented using conventional explicit network and an (implicit)
For our audio representation task, we aim to train a function that can reconstruct an given audio signal period of time. The spectrum of an audio signal contains many high fighfrreueecc components, making it difficult to reconstruct the audio signal for a not-so-large FNN.
Following the setting in 47 we train the models to fit 7-second music piece. We set the width of DEQ to 20, the layer FNN to 3 and the hidden dimension of FNN to 20. This setting enables the model to exactly fit the audio signal based on experiments.
29

---

In Figure 7 we show the reconstruction results with DEQ and FNN and the enror computed by subtracting the original signal. We observe that DEQ outperforms FNN with noticeable error, verifying the advantages of DEQ in representing high-frequency components.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Abstract and Introduction, where enumerates the contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: See Related Works and Section 5 We mention that we study a simplified DEQ due technical issues.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification:
For assumptions, see Section 5 For proofs, see Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Section 6 We provide details of our experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
Justification:
We will provide the open access to the code after the paper publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
coiioooooolylll for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //ippe.cc/pullic/guiii wwwpc//ggue////eeeecoooc CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section 6 and Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: This paper does not include experiments on large real datasets.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
33

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix B.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /aapas:///uripps/ http///urrs.cccppuii/i/e httppp//sccppp..ttttttccccceeeea
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper mainly focus on the theory of neural networks.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
34

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses on theory.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: See Section and Appendix B Although experiments in Appendix B.2 utilize another experiment, the code, data and models created by ourselves.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsspipetattteeeeee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
35

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "mD7fAKgOvh", "reviewer": "Reviewer_qjxV", "summary": "This paper studies the expressivity and inductive bias of deep equilibrium models. First, the authors generate a separation result for expressivity between a fully connected deep model model and a deep equilibrium model, showing that if the depth of the fully connected model scales as $m^{\\alpha}$ for width $m$ and $\\alpha \\in (0,1)$, that there are more linear regions in the DEQ model of width $m$ which can achieve the full set of $2^m$ linear regions. Second, the authors provide an example of a \"steep\" target function that depends on a single dimension of the inputs and approximates a step function. For this target function, the FNN would require weights with large $\\infty$-norm (that scales exponentially in the dimension) while the DEQ can achieve error $\\epsilon$ with weights that scale as $1/\\epsilon$. Lastly, the authors provide a study of diagonal linear DEQs and characterize the type of min-norm solution obtained by running gradient flow on this model, a norm $q(\\beta) \\sim 1/\\beta^2 + C \\beta$ for constant $C$ which penalizes both small and large parameters. This model is also evaluated on a special OOD task.", "questions": "1. 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? 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)?\n2. In Remark 1, it is stated that an FFN could in principle achieve $2^{ m L }$ 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? Do the authors' results provide evidence that suggests that $2^{mL}$ linear regions cannot be achieved? \n3. Should line 255 be $\\sum_i \\beta_i^{-2}$ instead of $\\sum_i \\beta_i^{-1}$ ?", "limitations": "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.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper addresses an interesting architecture, deep equilibrium models, which have received less study than traditional feedforward architectures. The paper is therefore well motivated and timely. The analysis of the inductive bias (norm that is minimized) due to gradient flow training is quite interesting and novel to my knowledge.", "weaknesses": "Some aspects of the comparison between deep FFN and DEQs were a bit unclear. Specifically, for the approximation result, I was wondering whether the comparison between depth $L \\leq m^\\alpha$ FFNs and DEQs was a fair comparison. (See my questions below). \nThe experiments that the authors provide do show some situations where DEQs outperform FFNs. 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and thoughtful questions and comments. Please see our response below.\n\n> I was wondering whether the comparison between depth $L\\leq mα$ FFNs and DEQs was a fair comparison. (See my questions below).\n\nPlease see our response for the question Q1 below.\n\n> 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).\n\nThanks 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.\n\n> 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? \n\nWe think that our comparison of the expressivity of DEQ and finite-depth FFN is fair. \nOne 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.\n\n> 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)?\n\nWe 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.\n\n> 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? \n\nThanks 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.\n\n> Do the authors' results provide evidence that suggests that $2^{mL}$ linear regions cannot be achieved?\n\nThe 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.\n***\n[1] Bounding and Counting Linear Regions of Deep Neural Networks, ICML 2018.\n\n> Should line 255 be $\\sum_{i}\\beta_{i}^{−2}$ instead of $\\sum_{i}\\beta_{i}^{−1}$?\n\nWe 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. \n\n> 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.\n\nThanks for your suggestion. We will add a discussion about our limitations in the conclusion section in the final version.", "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": "", "extra_scores": {}}, {"review_id": "aZlBVPOrgv", "reviewer": "Reviewer_HjzA", "summary": "This paper explores the theoretical foundations of Deep Equilibrium Models (DEQ) and their advantages over Fully Connected Neural Networks (FNNs). It demonstrates DEQs have superior expressive power compared to FNNs of similar sizes, particularly in generating linear regions and approximating steep functions; and it also analyzes the implicit regularization and biases effects of DEQs in learning dynamics, which can lead to improved generalization, especially in out-of-distribution tasks. The paper supports these theoretical findings with empirical results.", "questions": "- DEQs differ from FNNs in three distinct ways: shared weights, input injection, and infinite depth. While the paper claims that DEQs are superior to FNNs in terms of expressivity due to their infinite depth, 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?\n- Comparing to FCN, actually DEQ has 3 distinct propoaretis, that is shared weights, input injection, and infinitely depth. The authors claim DEQ is better than FCN in terms of expressivity simply because of the infinitely depth. Can authors comments or envision the significance of the other 2 features?\n- How do the authors envision the practical applications of their findings? Are there specific domains where DEQs could significantly outperform FNNs?\n- Could the authors elaborate on the potential limitations of DEQs, especially in terms of computational complexity and training stability?\n- 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?\n- Can the authors conduct experiments to show that the learned features are indeed dense? These experiments may include both the diagonal models in Equation (9) and the general models using the entire weight matrices $W$", "limitations": "See the weakness and questions.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper addresses a significant gap in the literature by providing a detailed theoretical analysis of the expressive power and learning dynamics of DEQs, which is a relatively new model in the field of machine learning. By providing a deeper understanding of DEQs' expressivity and learning dynamics, the paper opens new avenues for research in neural network architectures and their applications.", "weaknesses": "The assumption in Equation (9) that DEQs favor dense features might be misleading. The model only updates the diagonal in the weights while keeping the rest as zeros, effectively constraining the model to be sparse. It is straightforward to claim that the diagonals are dense since that is the only part of the model being utilized.\n\nThe paper misses citing some important related works, such as [1] which studies the convergence of linear DEQ, and [2] which explores information propagation in DEQ and shows its equivalence to a Gaussian process in the infinite-width limit.\n\n[1] On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers, ICLR 2021\n[2] Wide Neural Networks as Gaussian Processes: Lessons from Deep Equilibrium Models, NeurIPS 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and thoughtful questions and comments. Please see our response below.\n\n> 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.\n\nWhile 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.\n\n> The paper misses citing some important related works.\n\nThanks for your feedback. We will include the papers you mentioned in related works in our final version of the paper.\n\n> 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?\n\nOur 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. \n\n\n> How do the authors envision the practical applications of their findings? Are there specific domains where DEQs could significantly outperform FNNs?\n\nA 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.\n\n> Could the authors elaborate on the potential limitations of DEQs, especially in terms of computational complexity and training stability?\n\nThe 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. \n\n> 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?\n\nOur 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.\n\n> Can the authors conduct experiments to show that the learned features are indeed dense? \n\nThanks 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.", "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": "", "extra_scores": {}}, {"review_id": "ublv3z8sHF", "reviewer": "Reviewer_j6dr", "summary": "- The authors study the expressive power of the ReLU-based deep equilibrium model (DEQ) and the learning dynamics (including implicit bias, convergence, and generalization) of linear DEQ.\n- The first separation result shows that there exists a width $m$ ReLU-DEQ that cannot be well-approximated by a ReLU-based fully-connected neural network (FNN) with sub-linear depth and sub-exponential (super-polynomial) width.\n- The second separation result shows that a rational function, which can be $\\epsilon$-approximated by a RELU-DEQ with $O(\\epsilon^{-1})$ width and weights, cannot be well-approximated by a RELU-FNN with constant depth and sub-exponential depth (in dimension) unless its weights are exponentially large (in dimension).\n- They also proved a certain implicit bias result for linear DEQ. They claim that the implicit bias implies that GF (or GD) learns a dense feature.\n- Under the generalization on the unseen domain (GOTU) setting, they proved that linear DEQ with a bias term achieves a smaller GOTU error than a diagonal linear neural network.\n- Overall, they hypothesize that DEQ is beneficial for learning certain high-frequency features.", "questions": "- Q1. Can you explain what $f(\\emptyset)$ is in Equation 13? Is it an arbitrary number?", "limitations": "The main paper does not clearly provide its limitations. However, as provided in the checklist, the main limitation is the simplified models for theoretical analyses. This barrier is difficult to overcome, which is understandable given the paper’s novelty.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and well-organized. If the reader has knowledge about the expressive power of neural networks and the implicit bias of diagonal linear networks, the paper is easy to follow.\n- The contribution seems clear if all the proofs are correct. The authors propose novel theoretical results on the properties of DEQ. Also, their result explicitly shows the advantage of DEQ over FNN.", "weaknesses": "- W1. It is unclear whether the comparison between DEQ and FNN is fair.\n    - Of course, in terms of memory consumption, DEQ is comparable to a constant-depth FNN of the same width. However, it might be unfair to compare them if a DEQ requires a lot more computational cost than FNN during training. For example, suppose a DEQ needs exponentially more computational cost than FNN. Then it might be plausible to compare a DEQ with an FNN of exponentially large depth. 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.\n- W2. Issues in the proof of Theorem 2(B). (Section 4.3)\n    - The proof repeatedly uses an inequality $| \\hat{u}(\\hat{v}(z)) - \\hat{v}(\\hat{v}(z)) | \\le | \\hat{u}(z) - \\hat{v}(z) |$. However, I cannot understand why this is true. If it isn’t wrong, the authors should provide proof of this. For the same reason, I am a bit suspicious about the verity of Lemma 2.\n- W3. Critical issues in Section 5 (Implicit bias part).\n    - If you want to discuss the implicit bias of a given model in Equation 9, the model must be over-parameterized ($N\\le d$) at first so that the model can fit all the data points. In other words, if the model is under-parameterized ($N>d$), the model can never fit all the training examples and the training loss cannot even reach zero. However, I cannot find any such discussion. (Please correct me if I am wrong.)\n    - You can find that the function $q(x)$ is nonconvex and unbounded below unless $x>0$. However, the solution space (defined as $X\\beta = y$) may include a vector $\\beta$ with negative components. Then can you guarantee that the function $Q(\\beta)$ 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.\n- W4. The main paper must provide pointers to the proofs of the theorems.\n- W5. Minor comments on typos & mistakes\n    - Equation (1): “$1\\le i \\le L-1$”, “$y = W_L z^{L}$”\n    - Equation (3): “$A = (0, \\cdots, W_L)$”\n    - Theorem 1 must include that $m\\ge 3$; otherwise, it allows the width (of FNN) less than 1. Also, the function $N_f$ must be defined on $[0, 1]^d$.\n    - Proposition 1 must specify $\\sigma=$ReLU.\n    - Since the paper focuses on linear DEQ from Section 5, the authors must make clear that they consider ReLU-DEQ in Section 4. This must be considered in the explanation in Section 3 (especially in line 112).\n    - Lemma 1 must include the size of $\\mathbf{b} \\in \\mathbb{R}^q$.\n    - The last sentence of Lemma 2 is a bit awkward because it has two “for all” phrases. You may replace “Then for any $x \\in [0,1]^d$,” with “Then,”.\n    - Line 197: “$x_1 < 1-\\text{poly}(d)^{-1}$”.\n    - Lines 212-213: it would be better to mention that $\\sigma$ is no longer a ReLU.\n    - Line 219: “initialized”\n    - Line 221: the function $q(x)$ must have a dependency on the index $i$. For example, write as $Q(\\boldsymbol{\\beta}) = \\sum_{i=1}^d q_i (\\beta_i)$.\n    - Line 225: “$\\tfrac{1}{2} \\sum_{i=1}^d \\tfrac{1}{\\beta_i^2}$”\n    - Line 233: a full stop (’.’) is missing.\n    - Line 239: “constraint”.\n    - Line 248, see the line next to Equation (13): it seems that $X$ (next to the expectation symbol) must be a small, bold letter ($\\mathbf{x}$).\n\nI will definitely raise my score if all my concerns are properly addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful review and thoughtful questions and comments. Please see our response below.\n\n> 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.\n\nWe 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.\n\nHowever, 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. \n\n\n> W2. Issues in the proof of Theorem 2(B). (Section 4.3)\n\nWe 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})|. $$” \nAnd 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. \n\n> Critical issues in Section 5 (Implicit bias part).\nIf 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. \n\nWe 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. \n\n\n> 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.\n\nTheorem 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.\n\n> The main paper must provide pointers to the proofs of the theorems.\n\nThanks for your valuable suggestions. We will provide pointers to the proofs for all theorems in the final version of the paper. \n\n> Minor comments on typos & mistakes. \n\nThanks for your careful review. We will revise all the typos and confusions in the final version of the paper. \n\n> Q1. Can you explain what f(∅) is in Equation 13? Is it an arbitrary number?\n\n$\\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.", "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": "", "extra_scores": {}}, {"review_id": "lcIGofEWUb", "reviewer": "Reviewer_QS3W", "summary": "This paper offers a comparative analysis of DEQ and FNN, examining their differences in terms of structure and performance. By investigating the learning dynamics, the authors provide insights into the implicit bias of DEQ. Their theoretical findings demonstrate the advantages of DEQ over FNN in specific scenarios and quantify key learning properties unique to DEQ.", "questions": "- Can the implicit bias of DEQ be understood from a lazy training perspective?\n- In Theorem 4.1, how is $\\alpha$ defined? For example, if $\\alpha$ is large and close to 1, then $m^{1-\\alpha}$ would be particularly small, implying that $N_f$ would have almost no width.\n- 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? \n- Additionally, does the conclusion hold for various downstream tasks of DEQ, including classification, regression, or other tasks?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is well-written and has a clear logic.\n\n- There is relatively little theoretical research on DEQ, and this paper serves as a valuable contribution.\n\n- From the perspective of separation, the authors discuss the relationship between the width of DEQ and the number of layers in FNN. They also use gradient flow and gradient descent to explore DEQ's implicit bias, clearly explaining the properties of DEQ.", "weaknesses": "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.\n\nBesides, the following relevant papers should be cited and discussed:\n[1] Deep equilibrium networks are sensitive to initialization statistics, icml 2022\n[2] GEQ: Gaussian Kernel Inspired Equilibrium Models, neurips 2023\n[3] Wide Neural Networks as Gaussian Processes: Lessons from Deep Equilibrium Models, neurips 2023\n[4] Deep Equilibrium Models are Almost Equivalent to Not-so-deep Explicit Models for High-dimensional Gaussian Mixtures, icml 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and thoughtful questions and comments. Please see our response below.\n\n> 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.\n\nThanks 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.\n\n> Besides, the following relevant papers should be cited and discussed.\n\nThanks for your valuable feedback. We will include all papers you mentioned in the final version of the paper. \n\n> Can the implicit bias of DEQ be understood from a lazy training perspective?\n\nWe 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.\n\n> 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.\n\nWe 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.\n\n> 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? \n\nIt 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. \n***\n[1] Grad-CAM: Visual Explanations from Deep Networks via Gradient-Based Localization, ICCV 2017.\n\n[2] Multiscale Deep Equilibrium Models, NeurIPS 2020.\n\n> Additionally, does the conclusion hold for various downstream tasks of DEQ, including classification, regression, or other tasks?\n\nThe 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.", "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": "", "extra_scores": {}}]

Author rebuttal:
We express our sincere gratitude to all reviewers for the valuable and constructive comments.  Many of the suggestions will be incorporated in the final version of the paper. 

Some reviewers have raised questions regarding the fairness of our comparison between DEQ and FFN and the validity of our simplification of the diagonal linear DEQ. We emphasize that our comparison is fair in terms of the number of network parameters, which is essential for understanding the model capacity and the parameter efficiency for certain functions. Its analysis provides intuitions for understanding the model bias of DEQ. We study for what kind of function, DEQ is provably better than standard FFN. Even when considering the extra cost in the forward propagation of DEQ, our comparisons remain valid (see our response to Reviewer j6dr for W1). 

Regarding our model simplification in understanding the implicit bias of the Gradient Descent algorithm, it is mainly for ensuring solvability because we aim to analyze the bias of DEQ beyond the lazy training regime.  Similar kinds of simplification have been commonly considered in studying two-layer neural networks (e.g., see [29, 37] in our References). Our obtained results are not a direct consequence of our model assumption. The linear diagonal model preserves the implicit nature of DEQ and is essentially a nonlinear model. Thus, our results reveal the bias of general nonlinear DEQ to an extent.

Additionally, in response to the concerns raised, we have conducted additional experiments and included the results in the attached PDF file. It includes:

* Review qjxV: (1) Evaluation of the norm of weights of DEQ and FFN for approximating the steep function with varying $d$; Fig. 1. 
* Review HjzA: An experiment on evaluating the density and norm of features; Fig. 2.
* Review j6dr: Comparison of DEQ with various FFNs having similar FLOPs per iteration; Table 1.
* Review QS3W: A saliency map experiment for a variant of ResNet-DEQ trained on image classification tasks; Fig. 3.

We hope that these additional results will address the reviewers’ concerns and strengthen our paper. Please let us know if you have any further questions!

Meta-review: The paper uncovers a number of interesting properties of Deep Equilibrium Models. The authors all lean towards acceptance.
Decision: Accept (poster)