On the Neural Tangent Kernel of Equilibrium Models
Authors: Zhili Feng
J Zico Kolter
Venue: Submitted to ICLR 2023 (2023)
Keywords: Equilibrium model
neural tangent kernel

Abstract: This work studies the neural tangent kernel (NTK) of deep equilibrium (DEQ) model, a practical ``infinite-depth'' architecture which directly computes the infinite-depth limit of a weight-tied network via root-finding. Even though the NTK of a fully-connected neural network is stochastic if its width and depth both tend to infinity simultaneously, we show that contrarily a DEQ model still enjoys a deterministic NTK despite its width and depth going to infinity at the same time. Moreover, such deterministic NTK can be found efficiently via root-finding.

Under review as a conference paper at ICLR 2023
ON THE NEURAL TANGENT KERNEL OF EQUILIBRIUM MODELS
Anonymous authors
Paper under double-blind review
ABSTRACT
This work studies the neural tangent kernel (NTK) of the deep equilibrium (DEQ) model, a practical "infinite-depth" architecture which directly computes the -efit limit of weight- tied network via root-finding. Even though the NTK of a fully-connected neural network can be stochastic if its width and depth both tend to infinity simultaneously, enjoys a deterministic NTK despite its width and depth going to infinity at the same time under mild conditions. Moreover, this deterministic NTK can be found efficiently via root-tinding.
show that contrarily DEQ model still
INTRODUCTION
Implicit models form new class of machine learning models where instead of stacking explicit "layers", they output s.t g(r, 2) O, where g can be either fixed point equation (Bai al., 2019), a differential equation (Chen et al., 2018b), or an optimization problem (Gould et al., 2019). This work focuses on deep equilibrium models, a class of models that effectively represent a "infinite- depth" weight-tied network with input injection. Specifically, let fa be network parameterized by 0, let æ be an input injection, DEQ finds 2 such that f(=", 22) z², and uses 2" as the input for downstream tasks. One interesting question to ask is, what will DEQs become if their widths also go to infinity? is well-known that at certain random initialization, neural networks of various structures converge to Gaussian processes as their widths go to infinity (Neal, 1996; Lee et al., 2017; Yang, 2019; Matthews et al., 2018; Novak et al., 2018; Garriga-Alons et al., 2018). Recent deep learning theory advances have also shown that in the infinite width limit, with proper initialization (the NTK initialization), training the network fo with gradient descent is equivalent to solving kernel regression with respect to the neural tangent kernel (NTK) (Arora al., 2019; Jacot et al., 2018; Yang, 2019 Huang et al., 2020). These kernel regimes provide important insights to understanding how neural networks work.
However, the infinite depth (denote depth as d) regime introduces several caveats. Since the NTK correlates with the infinite width (denote width as n) limit, question naturally arises as how do we let d - oo? Hanin & Nica (2019) proved that as long as d/n. (0, oo), the NTK of vanilla fully-connected neural network (FCNN) becomes stochastic. if we first take the FCNN converges either to a constant (freeze), or to the Kronecker Delta (chaos). this work, prove that with proper initialization, the NTK-of-DEQ enjoys limit exchanging property lim&-+00 1im @ (a. v) lim lim ( (x. y) with high probability, where @. de- notes the empirical NTK of neural network with layers and neurons each layer. Intuitively, we name the left hand side "DEQ-of-NTK" and the right hand side "NTK-of-DEQ" The NTK-of- DEQ converges to meaningful deterministic fixed points that depend the input in non-trivial way, thus avoiding the freeze vs. chaos scenario. Furthermore, analogous to DEQ models, we can compute these kernels by solving fixed point equations, rather than iteratively applying the updates as for traditional NTK. We evaluate our approach and demonstrate that it matches the performance of existing regularized NTK methods.
the other hand, oo, then d + oo', Jacot et al. (2019) showed that the NTK of
'The computed quantity is lima-zoc lim (!!!) (Iz, y)-

---

Under review as a conference paper at ICLR 2023
2 BACKGROUND AND PRELIMINARIES
A vanilla FCNN has the form g()) o (WW"))(t))) + b(t for the i-th layer, and in princi- ple t can be as large as one wants. A weight-tied FCNN with input injection (FCNN-IJ makes the bias term related to the original input and ties the weight in each layer by taking the form 2(t) == f(2(t-1), x) = (W2((t)) + Ur + 6). Bai et al. (2019) proposed the DEQ model, which can be equivalent to running an infinite-depth FCNN-IJ, but updated in a more clever way. The for- ward pass of DEQ is done by solving f(=
=². For a stable system, this is equivalent to solving lim ((*) (0) z². The backward iteration is done by computing df (x)""))/dd /x)/d2* directly through the implicit function theorem, thus avoiding storing the Jacobian for each layer. This method traces back to some of the original work in recurrent backpropagation (Almeida, 1990; Pineda, 1988), but with specific emphasis on: 1) computing the fixed point directly via root-finding rather than for- ward iteration; and 2) incorporating the elements from modern deep networks in the single "layer", such self-attention transformers (Bai et al., 2019), multi-scale convolutions (Bai et al., 2020), etc. DEQ models achieve nearly state-of-the-art performances on many large-scale tasks including the CityScape semantic segmentation and ImageNet classification, while only requiring constant mem- ory. Although a general DEQ model does not always guarantee to find a stable fixed point, with careful parameterization and update method, monotone operator DEQs can ensure the existence of a unique stable fixed point (Winston & Kolter, 2020).
The study of large width limits of neural networks dates back to Neal (1996), who first discovered that a single-layered network with randomly initialized parameters becomes a Gaussian process (GP) in the large width limit. Such connection between neural networks and GP was later extended to multiple layers (Lee et al., 2017; Matthews et al., 2018) and various other architectures (Yang, 2019; Novak et al., 2018; Earriga-Alonss et al., 2018). The networks studied in this line of works are randomly initialized, and the GP kernels they induce are often referred to as the NNGP.
A line of closely-related yet orthogonal work to ours is the mean-field theory of neural networks. This line of work studies the relation between depth and large-width networks (hence GP kernel in limit) at initialization. Poole et al. (2016); Schoenholz et al. (2016) showed that at initialization, the correlations between all inputs on an infinitely wide network become either perfectly correlated (order) or decorrelated (chaos) as depth increases. They suggested we should initialize the neural network on the "edge-of- ofaoooosschhooeooo to make sure that signals can propagate deep enough in the forward direction, and the gradient does not vanish or explode during backpropagation (Raghu et al., 2017; Schoenholz al., 2016). These mean-field behaviors were later proven for various other structures like RNNs, CNNs, and NTKs as well (Chen et al., 2018a; Xiao et al., 2018; Gilboa et al., 2019; Hayou et al., 2019). We emphasize that despite the similar appearance, our setting avoids the order vs. chaos scheme completely by adding input injection. The injection guarantees the converged NTK depends nontrivially on the inputs, as we will see later in the experiments.
While previous results hold either only at initialization or networks with only last layer trained, analogous limiting behavior was proven by Jacot et al. (2018) to hold for fully-trained networks as well. They showed the kernel induced by a fully-traince infinite-width network is the following:
{ (or(0.0) af(0.)) v) 00
x)
)
O v) = Egnas
(1)
00
where A represents the Gaussian distribution. They also gave a recursive formulation for the NTK of FCNN. Arora et al. (2019); Alemohammad et al. (2020); Yang (2020) later provided formulation for convolutional NTK, recurrent NTK, and other structures.
One may ask what happens if both the width and the depth in a fully-trained network go to infinity. This question requires careful formulations as one should consider the order of two limits, as Hanin & Nica (2019) proved that width and depth cannot simultaneously tend to infinity and result in a deterministic NTK, suggesting one cannot always swap the two limits. An interesting example is that Huang et al. (2020) showed that the infinite depth limit of a ResNet-NTK is deterministic, but if we let the width and depth go to infinity at the same rate, the ResNet behaves in a nag-Gausiian fashion (Li et al., 2021). Meanwhile, the infinite depth limit of NTK does not always present favorable properties. It turns out that the vanilla FCNN does not have a meaningful convergence: either gives constant kernel or the Kronecker Delta kemel (Jacot al., 2019).
2

---

Under review as a conference paper at ICLR 2023
Our contributions. We first show that unlike the infinite depth limit of NTK to FCNN, the DEQ- of-NTK does not converge to a degenerate kernel. This non-trivial kernel can be computed efficiently using root-finding. Moreover, the -fK- coincides with the DEQ-of-NTK under mild condi- tions. Although the proofs here involved infinite limits, we also show numerically that reasonably large networks converge to roughly the same quantities as predicted by theory, and show the NTK-of-DEQ matches the performances of other NTKs on real-world datasets.
2.1 NOTATION
We write capital letter W to represent matrices or tensors, which should be clear from the context, and use [W]; represent the element of W indexed by i. We write lower case letter represent vectors or scalars. For a Z,,. let [a] {l,...,a)) a). Denote (xx) v2 max(0, .)) the nor- malized ReLU and ā its derivative (which only needs to be well-defined almost everywhere). The symbol of with subscript is always used denote the variance of random variable a. We write (H, Σ) as the Gaussian distribution with mean μ E R' and covariance matrix I E Raxd We let gd-1 be the unit sphere embedded in R. We use n, denote width and depth respectively, and write G(d) to stress G has depth and width n, where G can represent either a kernel or a (0.5) 80 )
neural network. We use the term empirical NTK to represent (0.x)
We write denote limits taken.
80
((d) = lim,- G Gn lim Gh and G lim (d) All missing proofs can be found in the appendix.
3 NTK-OF-DEQ WITH FULLY-CONNECTED LAYERS
In this section, we show how to derive the NTK of the fully-connected DEQ.
Let m be the input dimension, 25, S be pair of inputs, be the width of the h-th layers where h E [d]. Let (0) 0 R². Define the depth-d approximation DEQ the following:
(x) Le whi (x) g U x Th (())
nh (x) = o (() f1 p(a+1) = o. o" (x) (x),
where h E [d]. (N)) E R (M) E Ruxm v E R are the internal weights and ((h)) R are the bias terms.
The actual DEQ effectively outputs fkر²) a. o gn (00) == o o (lima- gh (x)) The
forward pass is solved using root-finding fixed point iteration, and the backward gradient is cal- culated using implicit function theorem instead of backpropogation.
One thing note is that usually DEQs require tied- weights: W(A) W. ( U. and ((h) for all h. It turns out for the infinite width regime, DEQ with tied weights and DEQ without tied weights will induce the same NTK. We will discuss this point in more detail later.
Let (d) (Ix y) be the empirical NTK of f| In Section 3.1, we will derive for an arbitrarily fixed d, the "finite depth iteration to DEQ-of-NTK" ((d) lim (!)) In Section 3.2, we show that (d) converges to deterministic DEQ-of-NTK. Furthermore, we prove that lima- lim (()) =
lim,- lim ((d)) with high probability, that is, the DEQ-of-NTK equals the NTK-of-DEQ.
3.1 FINITE DEPTH ITERATION DEQ-OF-NTK
Under the expressions in the beginning of Section 3, let us pick dw, du.ab E IR arbitrarily in this section, and require the following NTK initialization.
NTK initialization. We randomly initialize every entry of every W, U, b, v from from, (( 1).
3

---

Under review as a conference paper at ICLR 2023
W
W(3)
W(2)
g(2.0) (x)
g(2.10(2)
g
g (x)
(1
(
(2
will
W(()
W(1)
(x)
g g0,1000 (a)
g0.2)
g
g0.8)
(1)
(1(2)
(00)
(1(2)
221
22
Figure 1: Visualization of simple RNN from Alemohammad et al. (2020). The green area highlights DEQ.
21, I2,... are equal.
The finite depth iteration the DEQ-of-NTK can be expressed as the following:
Theorem 3.1. Recursively define the following quantities for h E [d]:
( (x, x²
(2)
(1)) (z. v) ow
E
[ō(u)o(u)]
(5)
(u.v)~
10-1 (y.
(x.
((O,A
(2,9)
(3)
(d(+1) (x, = o
[o(u)o(u)] (6)
( v) ow
E (a,0)~
[o(u)o(u)]
(a
(h),)(h))
((d+1)(x (x.
[a(u)(()] (7)
+ xt y of
(4)
(a
N(
Then the d-depth iteration to the DEQ-of-NTK can be expressed as:
d42
442
(
Σ
(yth-1)) (2.)))))))))
(a.0))
II h==h
2(h) (a.0)
(8)
h=1
where by convention set 1(d+2) (5r, y)
One can realize that the derivation is done as if the weights in each layers independently drawn from the previous layers, thus violating the formulation of DFQs. Nonetheless, has been proven that under certain conditions, the tied-weight NN and untied-weight NN induce the same NTK, Remark 3.2.
Remark 3.2. While our derivation is done untied weights, the NTK of its weight-tying counterpart converges to the same point. This formally done using the Nestor program introduced Yang (2019; 2020). The neural architecture needs to satisfy gradient independent assumption. One simple check that the output layer weights are drawn from a zero-mean Gaussian independently from any other parameters and not used anywhere in the interior of the network. This is clearly satisfied in our setting. In fact, Alemohammad et al. (2020) has presented the recurrent NTK case with tied weights. Using their notation, by letting (2.0) (x) 0 E R", x be T copies of x, and T d represents the depth, we exactly recover the current (fiite-depth)) DEQ formulation. See Figure for a visual explanation. Therefore. their conclusion directly applies to our setting. We should emphasize that work is not trivial extension to the recurrent NTK, because mainly study the infinite-depth limit.
3.2 NTK-OF-DEQ EQUALS DEQ-OF-NTK
Based on Equation (8), we are now ready to show what the DEQ-of-NTK lim (d) is. Then we
present the main takeaway of our paper: limg-soo ( lim, lima-roe O By convention, we assume the two samples x, y E gd-1, and we require the parameters of o of obey the following DEQ-NTK initialization:
4

---

Under review as a conference paper at ICLR 2023
DEQ-NTK initialization. Let every entry of every W, U, U,b,y follows the NTK initialization de- scribed in Section 3.1, as well as the additional requirement By + o + +o
Let the nonlinear activation function a be the normalized ReLU: (x) = v2 max(0, x) from now on.
Using normalized ReLU along with DEQ-NTK initialization, we can derive the main convergence theorem:
Theorem 3.3. Use same notations and settings in Theorem 3.1, the DEQ-of-NTK
0.p0" E' (x, - (xr
(xx A lim ( (x,))
+ +
(9)
d=400
where (2, v) p¹ is the root of (p) -p
[v1 p2 + (x cos- p)
(p) ow
+ +or + 0
(10)
and
π COs -1 (p*)
(11)
Σ Ex y) A lim (Th) v) h
(12)
Remark 3.4. Note our E (x, y) always depends on the inputs x and y. so the information between two inputs is always preserved, even if the depth goes to infinity. On the contrary. as pointed out by Jacot et al. (2019), without input injection, (1)) (x, y) always converges to as + co, even if + y.
Theorem 3.3 provides us way to direct calculate the DEQ-of-NTK by using root-finding algo- rithms. In practice, we can solve Equation (10) by using any optimization method. Then Σ and O' can be computed in constant time. Since each pair of input (z, y) is independent of all the other pairs, we can easily parallelize this computation process. Our derivation can be extended to more complicated structures like DEQ with convolution layers, see appendix for more detail.
One caveat of Theorem 3.3 is the order of limits, notice that we first take the limit of the width, then the limit of the depth. Nonetheless, with sufficient conditions, one can indeed show that the limits can be exchanged, and the NTK-of-DEQ and the DEQ-of-NTK are equivalent.
Theorem 3.5. Let ow S 1/8, 0 (x,g) -n=1 1
@f(0.)) af(0.u) 0003
be the empirical NTK with
80
depth and width n. Then 1om lima- ).d)) lima- lim in probability.
O.0) with high probability
Proof sketch. We first use a well-established random matrix result conclude that of 1/8 guarantees us that a o /ow/ is a contraction with high probability. Using this contraction property, we can then show that the empirical NTK ( converges. More importantly, it presents an "uniform convergence" property in n: a larger does not need a larger for the limit to converge.
This is the crucial difference between this result and the results in untied-wedt weight network. Intuitively, suppose contrarily our network has untied weights, to make our proof work we would need every layer's weight becomes a contraction. As d increases, this clearly needs larger n to use a union bound, which breaks if d + co.
Finally, we prove a probabilistic version of Moore-Osgood theorem to conclude that our limit ex- change result holds.
Remark 3.6. In Theorem 3.5, for fixed depth d, ((d) = lim O converges almost surely, hence we can view θ == lim (dd) as a constant. On the other hand, for a fixed n, O == lim (d) exists with probability at least 1 - e e oe"n for some constant c, and A 1-2, 20t Formally, for any 0, have
2
- o(n).
which converges in probability by definition.
5

---

Under review as a conference paper at ICLR 2023
Remark 3.7. We remark that Theorem 3.5 requires more stringent di than Lemma B.1. This indeed expected. For the actual DEQ to converge, one usually needs I W ž ml for some 0. It seems that ow I 1/2 exactly reflects I - W O, we leave this as interesting future work. While Hanin & Nica (2019) also discussed about the relation between width and depth, and they concluded that the NTK may not even be deterministic if d/n > our result does not contradict with theirs because their n has to depend on d, but our proof decouples the dependency using uniform convergence thanks weight-tying.
CASE STUDY: LINEAR DEQ
Theorem 3.5 shows quite surprising result that we can safely exchange the limits, which is not at all straightforward to see. Consider the following linear DEQ case:
In Ow (h- (x) + L fl n
L n
- v g))g(
(13)
In x =
Assuming the iteration converges (this can be guaranteed with high probability picking suitable ow). Equivalently, we can also write this network as
[n(x) = Ut OF(T
W
OU
Ur.
(14)
n
n
Following the same derivation in Section 3, one can easily see that (x. v) = -o for all h However, taking the infinite width limit of the network fn it does not obey Gaussian nature owing to the inverse shifted Gaussian matrix. It is not straightforward to see the limit exchange argument works. In this section, we aim to solve this linear DEQ case as a sanity check. In Section 5 we include numerical approximation that indicates the -f DEQ- behaves as we expect.
a"a"=" " and show that lima-+o lim O (z,y) (1-0w + 1-
Theorem 4.1. Let fn(x) be defined as in Equation (14) and 6 be the empirical NTK associated with the finite depth approximation of fn. Equation (13). Let oi < 1/4 and ow of 1. We have
02
200020
lim lim ((())
lim lim 0000
d 100
a n-000 d
(1 ow 1 ow
with high probability.
Proof sketch. Let H == 1- V
Such H is well-defined with high probability ow <
1 1/4. A straightforward derivation gives:
af(() (x) af (v) ow
oo ofv (Ho(HU))),HoHUUa)
lim d
aw
n
n
(HUx, HUX) o? (Hv. Ho) 2s o
(1 t- H (r((HT
(15)
+ oz (dauls))
where the first convergence happens with high probability (Arora et al., 2019), and the second con- vergence holds for almost every realization of a sequence of W. This follows from the weak con- vergence of probability measure Pan 4 jl a.s. and Portmanteau lemma, where An is the empirical (1 (1-v The (&w W.) More precisely,
V1- n
distribution of the eigenvalue of the matrix
[h, Σm 8x 6x. is the delta measure the ith eigenvalue X

---

Under review as a conference paper at ICLR 2023
Next, show that / ddp( - From Capitaine & Donati-Martin (2016), we learn that the
Stieltjes transform g of μ is root to the following cubic equation:
For z E C+ (x(=)= (1 (l-wwg
(
We then apply the inverse formula of Stieltjes transformation to derive the density
dı((A) lim Im (u(A + ib).
(16)
क b-++
This now involves a one-dimensional integration, which can be computed numerically and shown to be identical the desired quantity. Similarly, we can compute that
05
0f (v)
o, ow
10 (z)
0fn
(d) (2)
2
lim d-000
lim d0000
P
aU
8U
dv
Ov
1
ow
Summing the three relevant terms and use the fact that of + tow 1, we get the claimed result.
SIMULATIONS
ww0...0...... ver b-0.8
var WwC44 bw0.d
0.53
0.30
0.25
0.80
0.23
20.00
bapth
0.5
F9bta CEa
vor
0.4
0.47
0.39
0.34
0.33
Fiita Dupth XTC
Fisrs Deat NIK
0.25
Dighh cfr.att bathecie
Figure 2: Finite depth NTK vs. finite depth iteration of NTK-of-DEQ. all experiments, the NTK is initialized with ow and of in the title. For NTK-of-DEQ we set of of 0.1 in the title, and of 0.1. All models are trained on 1000 CIFAR-I0 data and tested on 100 test data for 20 random draws. The error bar represents the 95% confidence interval (CI). As expected, as the depth increases, the performance of NTKs drop, eventually their 95% CI becomes singleton, yet the performance of DEQs stabilize. Also note with larger ofy the freezing of NTK takes more depths to happen.
In this section, we perform numerical simulations on both synthetic data and real-world datasets including MNIST and CIFAR-IO to demonstrate our arguments. particular, we show that (a) The NTK-of-DEQ and DEQ-of-NTK coincides, for both linear and non-linear cases, (b) A vanilla NTK of FCNN degenerate while NTK-of-DEQ escapes the freeze vs. chaos scheme, (c) The NTK-of-DEG delivers reasonable performances real-world datasets further evidence to its nondegeneracy.
5.1 NTK-OF-DEQ VS DEQ-OF-NTK
Recall in Section 4, the distribution y in Equation (16) is that of the eigenvalues of H - A (T /ow//W/> /ow//nW)
The exact limiting eigenvalue distribution μ when

---

Under review as a conference paper at ICLR 2023
+0
5.20
64
43
01
47
Figure 3: The empirical eigenvalue distribution of an instance of a 1000 x 1000 random matrix
(1 V ///w)) v /nW) with ow = 0.25, 0.5, 0.75, respectively.
65
(a) The limiting eigenvalue distri- bution of (I Vol (n////W
(b) The empirical and expected trace. The simulation is run 10 times the error bar denotes the standard deviation.
/ow/wW).
Figure 4: Demonstrations of the limiting eigenvalue distribution of H-T and its approximation.
w. 0.25, 0.5, 0.75 is shown in Figure 4a. Keep in mind that du depicts the probability density of how large an eigenvalue of our random matrix can be.
For ow 0.25, 0.5, O, 75 we include an empirical eigenvalue distribution of -- H- g=x* for n = 1000 in Figure 3. One can see that the empirical density is sufficiently close to the limiting distribution for large enough n, verifying the computation in Equation (16).
We calculated the empirical trace of 1 tr H H where H is of size 5000 x 5000. This expression the key element for Equation (15). The simulation samples H i.idd 10 times and the results are presented in Figure 4b. We can see that the variance of the estimator 1/(1 ofv) is negligible for small oW.. Note that in the proof we require that /awy//// < with high probability, which holds when aw < 1/4. However, empirically the convergence of empirical trace holds for much larger of as well.
We also test the difference between the empirical NTK-of-DEQ O, and the DEQ-of-NTK O numer- ically, for both linear DEQ and nonlinear DEQ with normalized ReLU. We initialize both networks at variable width, with of = 2, of 1/8, and o 7 7/8. O, is calculated by taking the inner product between the exact gradients the DEQ-of-NTK formula in Theorem 3.3. pair input (xr,)) y) is randomly sampled and fixed throughout the simulation. For each width n, 10 trials are run, and we draw the mean of log [e- Figure 5. The convergence of the relative residue indicates that the NTK-of-DEQ and the DEQ- of-NTK coincide as proven.
2 of finite-width DEQ on two inputs, and θ is computed using
5.2 SIMULATIONS ON CIFAR-10 AND MNIST
Hyperparameter sensitivity. We have three tunable parameters: oi, of. We try three ran- dom combinations listed in Table 3. As the results suggest, the performances of ofK-of-DEQ insensitive to these parameters. This observation aligns with the description in Lee et al. (2020).
Thhe gradient is taken via implicit function theorem, see details in Bai al. (2019).
8

---

Under review as a conference paper at ICLR 2023
-14
-12
-35
-45
Figure 5: The deviation between the empirical NTK-of-DEQ and the exact DEQ-of-NTK on log scale. The result of linear DEQ is on the left and the result of nonlinear DEQ is on the right. We randomly sample one pair of (I, y) on the unit sphere, and for each width n, 10 trials are done with freshly sampled network weights, then we record the mean of relative residues in each setting. The convergence shows that NTK-of-DEQ and DEQ-of-NTK coincide.
BBO NTX depthd
Table I: Performance of NTK-of-DEQ on MNIST and CIFAR-10 dataset.
KIX depat110
1.55
Parameters
Dataset
Acc.
By oj = 0.25, og = 0.5
CIFAR-10
59.08%
ow 0.6, ; 0.4, =
CIFAR-10
59.77%
ow 0.8, i 0.2,
CIFAR-10
59.43%
x7hy
2 ow 0.6, ot 0.4
MNIST
98.6%
Figure 6: Relation between O(r, v) and xF
Training details and results. For NTK-of-DEQ, following the theory, we normalize the dataset such that each data point has unit length. The fixed point 2 (z, y) is solved by using the modified Powell hybrid method (Powell, 1970). Notice these root finding problems are one-dimensional, hence can quickly solved.
After obtaining the NTK matrix, apply kernel regressions (without regularization unless stated otherwise). For any label y E {1...., n). denote its one-hot encoding by ey. Let E R" be an all-1 vector, train on the new encoding -0.1 1 + ey. That is, change the "1" to 0.9, and the "O" to -0.1, as suggested by Novak et al. (2018). The results are listed Table 3. These results prove that the NTK-of-DEQ is indeed non-degenerate.
On a smaller dataset with 1000 training data and 100 test data from CIFAR-10, we evaluate the performance of NTK and the finite depth iteration of NfK-of-DEQ. depth increases. See Figure 2. When the depth increases, the performance of finite depth NTK gradually drops, eventually to 0.1 with 0 standard deviation. Also with larger o the degeneration NTK occurs slower. This shows that large ow preserves information from previous layers. Figure 6 also shows that the vanilla NTK becomes independent of the input inner product z² e''y as the depth increases. As proven in Jacot et al. (2019), the NTK will always "freeze" using the sets of parameters in Figure In this scenario, the NTK Gram matrix becomes linearly independent as the depth increases, and its kernel regression does not have unique solution. To circumvent this unsolvability, we add regularization term r x (((,.)) where n is the size of the training data.
6 CONCLUSION
We derive NTKs for DEQ models, and show that they can be computed efficiently via root-finding based on limit exchanging argument. This argument is proven theoretically for non-linear DEQs and an extra sanity check is done on linear DEQs, exploiting random matrix theory. Numerical simulations performed demonstrate that the limit exchanging phenomenon holds for both linear and non-linee non-linear ofK-of-DEQs. Our analysis also shows that one can avoid the freeze and chaos phenomenon in infinitely deep NTKs by using input injection. Additions experiments

---

Under review as a conference paper at ICLR 2023
conducted to show that NfK-of-DEQs are non-degenerate real-world datasets, while finite depth NTKs gradually degenerate as their depth increases.
REFERENCES
Sina Alemohammad, Zichao Wang, Randall Balestriero, and Richard Baraniuk. The recurrent neural tangent kernel. arXiv preprint arXiv:2006. 10246, 2020.
Luis B Almeida. A learning rule for asynchronous perceptrons with feedback in combinatorial environment. In Artificial neural networks: concept learning, pp. 102-111. 1990.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pp. 8141-8150, 2019.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, pp. 690-701,
Shaojie Bai, Vladlen Koltun, and J Zico Kolter. Multiscale deep equilibrium models. arXiv preprint arXiv:2006.08655 2020.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013.
Mireille Capitaine and Catherine Donati- Spectrum of deformed random matrices and free probability. arXiv preprint arXiv: 0,500, 2016.
Minmin Chen, Jeffrey Pennington, and Samuel S Schoenholz. Dynamical isometry and mean field theory of rnns: Gating enables signal propagation in recurrent neural networks. arXiv preprint arXiv:1806.05394 2018a.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In Advances in neural information processing systems, pp. 6571-6583, 2018b.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances In Neural Information Processing Systems, pp. 2253-2266 2016.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional net- works as shallow gaussian processes. arXiv preprint arXiv:1808.05550 2018.
Dar Gilboa, Bo Chang, Minmin Chen, Greg Yang, Samuel S Schoenholz. Ed H Chi, and Jeffrey Pennington. Dynamical isometry and a mean field theory of Istms and grus. arXiv preprint urXiv:/901.000 2019.
Stephen Gould, Richard Hartley, and Dylan Campbell. Deep declarative networks: A new hope. arXiv preprint arXiv: 0406666666..... 2019.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. arXiv preprint arXiv:1909. 05989, 2019.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. Mean-field behaviour of neural tangent kernel for deep neural networks. arXiv preprint arXiv:/905. 10005.1654,, 2019.
Kaixuan Huang, Yuging Wang, Molei Tao, and Tuo Zhao. Why do deep residual networks gener- alize better than deep feedforward networks?-a neural tangent kernel perspective. arXiv preprint arXiv:2002.06262 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl:: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
10

---

Under review as a conference paper at ICLR 2023
Arthur Jacot, Franck Gabriel, and Clément Hongler. Freeze and chaos for dnns: ntk view of batch normalization, checkerboard and boundary effects. arXiv preprint arXiv:190.005715, 2019.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv:1711.00165. 2017.
Jaehoon Lee, Samuel S Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. arXiv preprint arXiv:2007. 15801, 2020.
Mufan Bill Li, Mihai Nica, and Daniel M Roy. The future is log-gaussian: Resnets and their infinite- depth-and-widhh limit at initialization. arXiv preprint arXiv:2106.04013 2021.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint arXiv:1804.11277 2018.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. arXiv preprint arXiv: 1810.05 00..00000085..... 2018.
Fernando J Pineda. Generalization of back propagation to recurrent and higher order neural net- works. In Neural information processing systems, pp. 611, 1988.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. In Advances in neural informa- tion processing systems, pp. 3360-3368, 2016.
Michael JD Powell. A hybrid method for nonlinear equations. Numerical methods for nonlinear algebraic equations, 1970.
Maithra Raghu. Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the ex- pressive power of deep neural networks. In international conference on machine learning, pp. 2847-2854. PMLR, 2017.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein, Deep information propagation. arXiv preprint arXiv:1611.01232. 2016.
Roman Vershynin. High-dimensional probability.. 2019.
Ezra Winston and J Zico Kolter. Monotone operator equilibrium networks. arXiv preprint arXiv:2006.08591, 2020.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S Schoenholz, and Jeffrey Penning- ton. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. arXiv preprint orXiv:1806.05333 05393, 2018.
Greg Yang. Tensor programs i: Wide feedforward recurrent neural networks of any architecture are gaussian processes. arXiv preprint wet.iv//90..// 2019.
Greg Yang. Tensor programs ii: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006.1 240.2400..1448.. 2020.

---

Under review as a conference paper at ICLR 2023
A FORMAL DERIVATION OF WEIGHT-TIED NETWORK
In this section we formally derive the NTK of a DEQ (weight-tied) model, and show that they converge the same limit as derived in Section 3. The argument is nearly identical to that of Alemohammad et al. (2020), which heavily depends on the NESTER program (Yang, 2020), We will first give a brief introduction, and then adapt to our setting.
Definition A.1. NESTERT program is a program (as type system) of which the variables take three-types: A-vars, G-vars, and H-vars. Any variables are generated by one of the rules in MatMul (matrix multiplication), NonLin (nonlincarity), LinComb (linear combination), or Trsp (matrix transpose). We also sometimes explicitly express the dimensionality of variable in the following way:
If æ E IR", and is of type G, H. we write x: G(n) or x H(n).
If E Rexm, we write : A(n, m).
The program goes as following:
Input set of Gavars and A-rars.
Body
Any variable is introduced by the following rules:
Trsp. If A A(n, m), then A Amm,n).
MatMul. If A (n, m) and x H(m), then Ar G(n).
LinComb. Ifg .... G(n) and a. a.....,a E R, then Σ a'g' G(n).
NonLin, af ,..., x* G(n), and Φ R IR is coordinate-wise nonlinear function, then <(x', ...., "(x),...,,"' x²) H(n).
Output
The program outputs a scalar of the form
V h1 hh....,hht
for 12 b..... k (n).
For example, a depth-d approximation to DEQ model is provided in Algorithm 1. For simplicity, we left out the scaling / / (as was done in Yang (2020)).
Algorithm NESTERT T program Depth-d approximation to a DEQ model
Require: UR, Uy G(n), W A(n,n), G(n),v G(n). Polynomially-bounded coordinate-
wise nonlinear function d. for 1,..., d do
for 2 E {x, y) do
f(b) (z) = W og +U= U2 G(n).
g (x) = (( H(n).
// The network outputs ((++)) == T. (x) but we don't express this in the program.
// Backprop, for varible u, let du == VnV, v. (d++)(2))
(z) v: G(n).
(f()(2) = d'(f(( (z)) @ (z) H(m).
D We use @ for Hadamard product.
dg (2) WT () G(n).
df (z) = o' (z) o (M) H(n).
end for
end for
12

---

Under review as a conference paper at ICLR 2023
One express many neural network architectures into NESTERT program, but not all. The required regularity condition is the so-called BP-like: Definition A.2 (BP-like). A NESTERT program is BP-like if there exists non-empty set of input Gva)-vars v², ,..... u s.t:
1. If WWTa is used in the program for some 2 H(m), and W A(n, m)) is an input A-var, then 2 must be an odd function of v' ,.,...,"' ot That is,
(- ................................ v. all other G-vars = -2 (v) ....,, v all other G-vars)
2. If Wa is used in the program for some H(m), and W A(n, m) is an input A-var, then 2 cannot depend on any of v² v
3. ut.... .'....," v are sampled with zero mean and independently from all other G-vars. We say function f R RR is syynommaally-bounde
Definition A.3 (Polynomially-ounddeer if [6(x)| < C/||=||| + for some C.p > O, for all E RR Note that ReLU and inner product are oolynoimially-bonndee
Recall that the simple gradient independence assumption (GIA) check we give Section 3:
Condition A.4 (Simple GIA check). Gradient independence assumption is heuristic that for any matrix W, we assume W used in backprop is independet from W used in the forward pass. We can regard this assumption holds in the NTK computation the following simple check holds: the output layer is sampled independently with zero mean from all other parameters and it not used anywhere else in the interior of the network, that is, if the output of the network is v then v is independent of x.
Apparently DEQ formulation satisfy the simple GIA check, notice that by formulation, the second and third condition in Definition A.2 are trivially satisfied. Also since v is the last layer weight, any G-var of the form W only shows up in the backpropogation, and is linear (thus odd) in v as well. Hence the first condition is also satisified. So any network structure that satisfies the simple GIA check is automatically Bi-like.
Setup A.5. For NESTERT program, we assume that each entry in W : A(n, m) is sampled from (O, ow /n), and any imput G-vars x ~ NNn"" E. We remark that this does not contradict with the parameterization that we mentioned in the main text where the entries of imput A-vars W, U are standard Gaussians. One just needs to properly scale their variables.
Theorem A.6 (BP-like NESTERT program Master theorem). Fix any BP-like NESTERT T program that satisfies Setup A.5, and all its nonlinearities are polynomially-boune bounded... If gg .g......'' are all G-vars in the program, then for any wolynomially-boundee v RRM + IR, as T - oc, we have
n
Σ
3 ga. 9a....,
a...
E Z~N(HE)
(Z)
E Z~N(NE))
V (Zo'.... ....,,"').
where Z (70'
7 70
MR 1 (m(g") E RM == {Elg', .g M RMM
are given by
1" (g)
if imput, if Ei d'g' otherwise
m(g)
Σ ii d'
Eie
(9
if inpuls
(17)
Σ ('
ifg = Σ ==1 a² g² k
E(g.g)
Σt a'E(o,g')
if Σ Di=1 gg' if = Wh, 9 = Wh,
Ez)())0
otherwise.
We are now equipped to derive the NTK of depth-d approxiation to a DEQ. Particularly, we have
V W (z)
h=1
13

---

Under review as a conference paper at ICLR 2023
hence
(x)) T (v) glh (x)) (11
(w Vw ((d+t)())) ow Σ
1,==1
From this point, need calculate
Ew (x) (w) and Ew (o ga-
In the end, applying the Master theorem with (x y) = x y on dfth)) aret and 2t (w)" (v)
shows that these empirical averages converge to the expectations.
Remark A.7. Notice that the Master theorem talks about G-vars, while dy and (h) are H-vars. We can always compose v = th Ø. where & is the inner product and Φ is coordinate-wiss nonlinearity (such ReLU), and apply the Master theorem on v long it is still oolynomially-bounder
Ew dflh (x) (F) = ( (3))
(
( dg d0))
E
(d'(s(()))) T' (d
E ( T' (() (v)) E (z) dg
(z) dg)
By the Master theorem and GIA, )(((()) and dg are introduced by different A-vars (W and WT), hence their coviance is O. This justifies the last step above.
When h,d < d, by the Master theorem we have
= of Eldf (x)
Notice that this gives recursive expression, WLOG we assume that h < I, this induction will lead to
Elaf(h+0)))) (f =E ( (x))
(x) (d'(f((())
0, for some 0. The reason why this zero is still due to the Master theorem, as (f()+)) and (f (y) are G-vars involved with different A vars W and v.
This shows that when à 1, Ew (x)))) ag( (v) O. Hence only have consider the case h = L. By the Master theorem we have
A En,v [d'(w))'()) Ew gx) Eu,v [d(u)((1]]
where
(1h-1) 1(A-1) y) 1(h- (,) I(h-1) v)
(u,v) ~N 0,
Notice this exactly recovers the calculation of NTK when the weights are un-tied. The exact same argument can be applied to Vuf and V.f. Since such equivalence holds for all depth d, it also holds in the limit of + cc.
Key takeaway The NESTERT program allows us to calculate the NTK of a weight-tied network in exactly the same way the weight-untied network.
14

---

Under review as a conference paper at ICLR 2023
B DETAILS OF SECTION 3
In this section, we give the detailed derivation of DEQ-of-NTK, There are two terms that are differ- ent from NTK: E
(z. y) and the extra Eg
0f(0.z)) 0f(0.w) a0
in the kernel.
30
Let us restate the depth-d approximation to DEQs here:
Let mn the input dimension, z; y IRm be pair of inputs, n be the width of the h hidden layers. Define the depth-d approximation to DEQ as follows:
(x) V T w(h g (x)
+
o x
U
o +
p(h,
h E [Z]
n
n
n
g00) (z) o of (x))
(x))
(((+)) (x) o 98
(d+1) (z)
where (()) R (hh) m and R" are the internal weights, and ((h) R are the bias terms. These parameters are chosen using the NTK initialization. Let us pick ow ou, os e IR arbitrarily in this section.
Theorem 3.1. Recursively define the following quantities for h E [d]:
0 (z. y) xT
(2)
(T v/ ow
E (u.))
[a(u)((u)
(5)
(2,0) = Em (g)
(x, (a,
(3)
((O..
Σ [(d+1) (2r+))(r,))))))))))))) o
[o(u)((1)] (6)
()() (x =ow ow
[o(u)o(v)]
(u
(u.0)
((0,A
D(d+1) (x, = [a(ud((1]] (7)
+ ozxx y of
(4)
(u.))~
Then the d-depth iteration to the DEQ-of-NTK can be expressed as:
Old (I. = Σ
d+2
(IIA-D) (x.0))
II W/
d+2
((²) (z.0)
(8)
hml
where by convention we set 5id+ (s. =
Proof of Theorem 3.1. First we note that
[pentts (ontt sau]
E
o Σo ([11)c)))) a ((res) + ot Σ j=1
+ o
Ø=1
(++++1) (x, y) a.s
where the first line is by expansion the original expression and using the fact that W. U, b are all independent. The last line is from the strong law of large numbers. This shows how the covariance changes as depth increases with input injection.
15

---

Under review as a conference paper at ICLR 2023
Recall the splitting:
@f(0,x)
af(0.v) (10.))
(1, = Eg
00
00
0f @ff(0.)) x)
y)
0f(0. x) 0f 1)
Es
+ Eg
oW
OW
0U
0U
(0f(0,z) x)
0f(0. y)
{ /0f(0,2)) xt)
0f y)
+ Es
+ Eg
Øb
ab
dv
Ov
The following equation has been proven in many places:
d++1
d+1
d+1
d+
Ow
E
[o(w)(()))
II
(MM) (x, v)
3
o
(x, v)
1=1
M=A
1=1
and
(o())o For instance, see Arora et al. (2019). So we only need to
deal with the second term Eg
@5(0.w)
2s(0.)) 00
Write f == fo(x) and f fB(),, by chain rule,
80
have
0f 0f
OU(h) aU
Of 0f(h)
of oFm)
O aUTN
af(h) aU()
0f aj(h)
0s os Of(s: ofm
aUeh) QU(N)
d+1
II
5000
W==h
ar af where the last line uses the existing conclusion that (5fl5 5 convergence almost surely holds when + 0o by law of large numbers.
d++ II (10((z,))) v), this
Finally, summing <
Of aUUNT BUINY
Of over
[d] we conclude the assertion.
Lemma B.1. Use the same notations and settings in Theorem 3.1. With input data x. E Sd-1, parameters Py. ot of following the DEQ-NTK initialization, ( y) in Equation (8) converges absolutely if ifow <
Proof. Since we pick v.y E gd-1, and by DEQ-NTK initialization, we always have (x") < for x # y. Let = (x, y). by Equation (5) and Equation (19), if o < 1, then there exists such that (x)) y) < < 1 for finite number of pairs æ + y sd-11, and large enough h. This is because lim (x, v) (x, (2, 1.
Use comparison test,
L+1 II W=h
lim L-xoc
1) (2,
(M)) (a, v) < lim 1-+00
-+1-A
Since с < 1, the geometric sum converges absolutely, hence (d)) y) converges absolutely dw 1, and the limit exists.
16

---

Under review as a conference paper at ICLR 2023
Theorem 3.3. Use same notations and settings in Theorem 3.1, the DEQ-of-NTK is
(az,y) - lim (1,) = (x,
+ topp0
(9)
d-000
(1,
where E" (z, v) 2 p² the root of (p( - -p.
[I 111 p² + (xr cos p)p)
Ro ow
2ox y 0og
(10)
and
Cos (0-)
0² -
(11)
(x,,0) lim (x, - (12) 10000
π
Proof of Theorem 3.3. Due to the fact that æ E Sd-1, a being normalized, and DEQ-NTK initializa- tion, one can easily calculate by induction that for all h [A]: (x)) .)) = oy Eu-AV(o.1)) ( oi x + of = 1 This indicates that in Equation (3), the covariance matrix has a special structure
A (x, v) p 1 ) where P = (x, 3) depends on h, y. For simplicity we omit the
h, in A (1) (I, y). As shown in Daniely et al. (2016):
[o(()o())] v1 1² + (N cos -(p))
(18)
(v..)~~((O.))
π
E [u())(()) = cos (p)
(19)
(v.o)~N((.A))
Adding input injection and bias, we derive Equation (10) from Equation (18), and similarly, Equa- tion (12) from Equation (19). Notice that iterating Equations (2) to (4) to solve for 11h (x,z) y) is
equivalent to iterating (R, o...o R. (p) with initial input p x: y. Take the derivative
dR, (p)
oi 1 cos cos-'(p)
1, if of < 1 and -
dp
For x * y we have < p < for some e (this is because we only have finite number of inputs 3) and by DEQ-NTK initialization we have ow < 1, so the above inequality hold. Hence R2 (p) contraction on [0, c). and we conclude that the fixed point p² attractive.
By Lemma B. if ofy < 1, then the limit of Equation (8) exists, so we can rewrite the summation form in Equation (8) in a recursive form:
10) (x, u) Σ (x.
( (x. = S(d+1) (ar, v) o (I. + Ixd+1) (x, v).
Directly solve the fixed point iteration for the internal representation:
lim ((d+)((x
d+00
lim (((+1((x,))) (z, + (xd+1((x.))
d=000
lim (x(+1)(x.)))
10000
(20)
(x, w)
lim e (I, + (x, d
lim ( v)
(x, (x, v) lim e ( (α, +
17

---

Under review as a conference paper at ICLR 2023
Solving for limg->o ( y) get (*,
[x, Finally, we process the classification
1-1"
layer and get θ == Σ. O + E, where 5 0zi0² and = opp" p .This concludes the proof
B.1 DEQ-OF-NTK VS. NTK-OF-DEQ
In this section we discuss Theorem 3.5 in detail. Recall that the NTK is the kernel matrix formed by an infinitely-wide network. To be more precisely, if the network has depth d, then
e (z. Eg ( af(0,x)
(5(0.u)
00
00
It is straightforward to define its width-n approximation:
@f((0.z) 0f(0.y) 80(h) 00Ch)
(
where g(h) is the parameter of the hth layer with width n. The name of limg-roc limm- O being the DEQ of NTK is intuitive: because we first 3 bring width to infinity, that is, the NTK is first derived. Then we talk about the NTK's infinite-depth limit. This is in distinction to our desired quantity, lim,- limæ- 0,4 which is the NTK of DEQ naturally. In this section we show they indeed equivalent under certain conditions.
First we introduce some notations. Consider a finite depth iteration of a NTK with depth d d++ 1, and for simplicity let the bias term ((a) for all [d + 1]. A straightforward calculation show that
(0, x)) dW(h)
p (x)) (g (2))-1(2)) T
For h E [L + 1]:
df
= p (x) T E R" ofy No
(U(
h=
where (x))
diag à (F()))))) (wratt)) ((0+
V
h h d
Here diag á ((())))))) E N.N. Let N₁ = for all h. and w(++1) == u. Notice that
diag o (1()))))) (w(htt)) (()t)())) = à (FW) @ ((1ra)))) T (())
and we use these terms interchangeably. For simplicity, omit all the in the terms and write p(h) == (()) etc. Write (h)) = (x)). Notice that applying a(-) or Hadamard product with (b) only decreases norms.
Lemma B.2 (Probablisite Moore- Osgrod for double sequence). Let an, be a random double se- quence complete space. Assume for any e >> 0, (0, 1), there exists N > and D(e) such that for all n. >> N and d > D, with probability at least 1 - ê we have |0n.d an < 6 (we may refer to this property as uniform convergence with high probability). And for any d E we have
lim an og almost surely, then with high probability:
lim lim and 11
lim lim an.d-
d= R24000
Proof. We sometimes also write (n) stress that consider the sequence function of n.
By assumption, for any 5 E (0, 1), > 0, there exists N, D such that for all n > N, d, > D,
Here by "first" we meant the order when you calculate the limits: you first fix d and take the limit of n. Not the actual order from left right.
18

---

Under review as a conference paper at ICLR 2023
(a)(n) - (n)) < with probability at least 1 1- 6. Since here N does not depend D, let n we get the following statement holds almost surely:
d D = lad ael < e with probability at least - 8.
This shows that 0, == lim an,d is Cauchy sequence and have finite limit lima- L. Now define a(n) = On = l dn for D(c):
(a(n) L - (a(n) ad(n)) + (ad(n) adl + ad L
B
By assumption, pick large enough n, we have < with probability at least 1 By the Cauchy sequence argument above, we have C' < with high probability. Finally since aa(n) + ag pointwise for every d, we can choose n large enough such that < c. This concludes our proof. O
We want remark that the above Lemma B.2 relies on a more general notion of "conditional almost sure convergence". In particular, we only assume that annd anl < e almost surely conditioned on an event with probability least 1- d:
P lim andd = an (E) = where P(E) > for all large enough n. d-+00
Notice here we are not explicit about how ó evolves with When we use this lemma in Theorem 3.5, we have o(n) which will instead gives us convergence in probability result. To be complete, also provide the weaker result and its proof here.
Lemma B.3 (Another probablisite Moore-Osgood for double sequence). Let an be a random double sequence in complete space. Assume for any c > O, there exists D(c) > O such that for all > D, with probability at least - o(n) we have [nn - anl < And for any d E we have lim, On ag almost surely, then the following convergence holds in probability:
lim lim an,d lim lim Gn,d- n= d-+00
d-400 420
Proof. We sometimes also write aa(n) to stress that we consider the sequence as function of n. By assumption, let
get the following statement holds with probability 1:
d,e D =
lad
ael
<
This shows that Og := lim an, is a Cauchy sequence and have a finite limit limg-+00 ad = L.
Now define a(n) = On lim On,ds for d >> D(e):
[a(n) - T. (a(n) aa(n) + (aa(n) ad + ad
L
By assumption, pick large enough n, we have A e with probability at least 1- o(n). By the Cauchy sequence argument above, we have C < with probability 1. Finally since (n) - as pointwise for every we can choose large enough such that e with probability at least o(n). Overall this gives
P(la(n) L| > 3e) < o(n),
which concludes our proof
By standard high-dimenn sich-dimensional probability (Vershynin, 2019), the following lemma holds: Lemma B.4. Let E pR a random matrix whose entries are sampled from i.i.d standard Gaussian distribution, fhrnfor t 2 O, with probability at least 1 e -ct? for a constant e O, there is:
||A|22 S Vn + vm +
We now ready to give the formal proof.
Theorem 3.5. Let ofy < 1/8, e (x,v) Edt1
(81(6.)) as(e.)) 00(h) 00:n)
be the empirical NTK with
depth and width n. Then lim lima-soo (d)) lim lim ((!0) haalthih----bbbllle in probability.
19

---

Under review as a conference paper at ICLR 2023
Proof of Theorem 3.5. For any fixed d, we write O(d) lim, On notice this is just a finite- depth NTK (possibly with input injectionn. We condition on the event that limg O exists. A sufficient condition for this event to hold with high probability is By 1/8. With such o by Lemma B.4, o / //t / has Lipschitz constant less than with high probability. Recall that
(xx) = 22 m0, x is the normalized ReLU nonlinearity. Conditioned on such event, we have
0f(x) T Of(x')
OW(N) (W())
(x)² glh (x) & th (x) (h (x') (=)))*))))))))))))))))))))))))))
WLOG let ( gd-1 and ( be our base case. Note that Uth) x is fixed for weight- tied network, let's denote it as C, and also overload the notation that ||C|]| = C. By induction:
o (fth))
-0
o
th n
w(t) th + +0)
-
20
wr(lg (h-
C S
20 ((())
1 10 +|| op
n
By Lemma B.4, with probabiliy least 1 Ott", have || S 2 + t. This shows that for all e > O, let ow < 2222''
with probability at least 1 - e -(E'n) we have
20 ((h)
r
n
op
Consequently;
(0) S ( + C S rM
Cr
-=1
which is geometric and converges absolutely as h + co. Therefore, there exists a constant Q > s.t (00) < Q for h E N.
By the same spirit, using induction, we have
/20 Vn
000 <
|
op II (n (1-111 S (1pp))) s -d-h ( d-h
Combining the above two derivations, we have
0f(x) T af((')
af(a) owan)
OW( (W(A)
aww
x (x)
(+))
Σ ( (x'
<x.
Similar convergence result can be derived for of well.
Use the terminology introduced in Lemma B.2, lima e lima (10)
8f()) af(z') converges uniformly in with high probability. Σ
06(A) ag(a)
For fixed d, we know that lim O ((d) by the tensor program (Yang. 2019). Therefore
oy conditioned on the event that a V /nW has a Lipschitz constant less than 1, by Lemma B.2,
we can swap the limit and indeed lim lim,- (d) = lim, lim (..)) This shows that
the NTK-offDEO and the DFQ-of-NTK coincide.
20

---

Under review as a conference paper at ICLR 2023
One should note that it merely requires ow 1 for the DEQ-of-NTK to converge as in Theorem 3.3, but our above proof requires Bl < 1/8 to make sure that the of and DEQ-of-NTK are equivalent. Our current analysis relies heavily DEQ setting, it suffice to have W being strongly monotone to guarantee convergence. That is, one only needs the largest eigenvalue of W to be less than 1. This corresponds have dw < 1/2 (again, this is because we use the normalized ReLU, so there is an extra factor of v2) by the semicircular law. We leave the gap to future works.
contraction argument. However, in the actual
C DETAILS OF SECTION 4
Theorem 4.1. Let fa(x) be defined as in Equation (14) and O be the empirical NTK associated
with the finite depth approximation of Jn. in Equation (13). Let oy < 1/4 and ow où 1. We have
lim lim ((4) = lim lim @ o. x y
d-000 n-000
n-000 d=000
(1 oi )2
1 ow
with high probability.
-1 This inverse matrix exists
(
Proof of Theorem 4.1. Recall that we define H
W
with high probability if ow < 1/4, due to well-known random matrix theory result Lemma B.4.
straightforward derivation gives:
05 (d) (x)
a
lim d00
aW
aw Hu(HU)))
og ow
n n
owo
(HUx, HUx) oe (Hv, Ho)
n
2 4
= tr (HTHH tr((HHH)
00
W jit y
i 1 (fimes))
The first convergence happens with high probability (Arora et al., 2019). Note that B = Ev. [A]. One needs to apply the Gaussian chaos of order 2 lemma (Boucheron al., 2013) to show the concentration. This was done rigorously down in Arora et al. (2019) Claim E.2. Their proof works for our case well since we have H H|| bounded independently of and d with high probability.
The second convergence holds for almost every realization of a sequence of W. Recall that p4n is More w
the empirical distribution of the eigenvalue of the matrix (1-V Fix W
(1-v
V-
precisely, nh, - Em 8x 8x is the delta measure at the ith eigenvlue value A;. We can rewrite
tr ( = f 1
We will show that nn + weakly a.s 4, Then by Portmanteau lemma, we have f fdun f fd for every bounded Lipschitz function. Here we have f = 1/2 defined when has non-zero support in (A)). Since by Lemma B.4, our assumption oy 1/8 guarantees
W 1 w.h.p, the support of (aA) is bounded away from 0, and f is indeed Lipschitz and bounded its domain.
NNote here Pag is random measure
21

---

Under review as a conference paper at ICLR 2023
Next, we show that / ddp( - From Capitaine & Donati-Mani Martinn (2016), we learn that the Stieltjes transform g of μ is root to the following cubic equation:
For z E C+ (x(z))
(21)
Deducing the probability density from g by using the inverse formula of Stieltjes transformation, have
p(b)
lim 6-00
Im(g(a+
+
v3 (30f/b ofv02 30
1/8 +
22/ b (00) 62 20 180f 82 (Mot 20% 1804) + (30% of, Bork66
v pofple - 20ffb + 1808 + (M6g 20ff + 180f "20" (Joffb - ohe "or(
Finally we can compute Ji" {A)dd) Notice to let p() be well defined, we need 90 02 22 b3+ 180 b² 0, which amounts 1= = (-o + +20g Vot 240 1920 + 512a² + 8) and u- (-owy 200 Vo 24 1920 + 512a² - =8) This now involves a one- dimensional integral, which an be solved numerically for all values of ow, and shown be be arbi- trarily close the desired quantity 1/(1 oW)
Similarly, we can compute that
05 (x)
0f (d) (y)
P. o x" y ow
lim
d0000
0U
OU
and
5 (( (x)
a ( (1)
2 2.000000 2 x²
lim
Ov
Ov
ow
Summing the three relevant terms and use the fact that ot + to = 1, we get the claimed result.
D DEQ WITH CONVOLUTION LAYERS
In this section we show how to derive the NTKs for convolution DEQs (CDEQ). Although this paper only the CDEQ with vanilla convolution structure considered, remark that our derivation is general enough for other CDEQ structures as well, for instance, CDEQ with global pooling layer. The details of this section can be found in the appendix.
Unlike the fully comnection network with input injection, whose intermediate NTK representation is real number. For convolutional neural networks (CNN), the intermediate NTK representation is four-way tensor. In the following, we will present the notations, CNN with input injection (CNN-IJ) formulation, the CDEQ-NTK initialization, and our main theorem.
Notation. We adopt the notations from Arora et al. (2019). Let x,, R be pair of inputs, let E E+ be the filter size (WLOG assume odd as well). By convention, we always pad the representation (both the input layer and hidden layer) with 0's. Denote the convolution operation for
e [P]. [Q]:
[w I/i Σ > 2 3 -
[w] /w]++
[x]a+1.6+g.
Denote
Dij.yy (i +'))++ E x - (q--))/
Intuitively, Dij,ig' is a x g g set of indices centered (ij,i'j'). For any tensor T RxxxxxxQ let [T]p be the natural sub-tensor and let Tr(T) Σis Tizaz-
22

---

Under review as a conference paper at ICLR 2023
Formulation of CNN-IJ.
Define the CNN-I follows:
Let the input (0) = E PxQCxo, where Co is the number of input channels, and C₁ is the
number of channels in layer h. Assume WLOG that C₁ C for all [d]
For h 1,..., d, let the inner representation
((h)
(3)
Ch-1 Σ
Cp
(h) (a),()
*
(h-1) (a)
+ Σ
Co
i u Ch (a).
=(a)
(0)
(22)
a=1
a=1
(h)
I
for i E [P], E [Q]
(23)
(
where W w:(h) (a).(0) E Roxq represent the convolution operator from the th channel in layer h to the 8th channel in layer h. Similarly, (()),10) E 1898 injects the input in each convolution window. S RxQ a normalization matrix. Let W, U, be chosen by the CDEQ-
NTK initialization described later.
The final output is defined to be fo(x) EEe, ( (w(tt)) sampled from standard Gaussian distribution.
(a) [ where w(lt1) RRx is (a)
CDEQ-NTK initialization. Let 1g R X E RºxQ be two all-one matrices. Let X ((P+2)x(Q+2) be the output of zero-padding X. We index the rows of X by {0, 10,1,.., P + 1}
and columns by 1,. Q + l]. For position E [P], E [Q], let ([5]y) 2 [Lg * Xli in Equation (23). Let every entry of every W,U be sampled from (O, 1) and ow + to = 1.
Using the above-defined notations, we now state the CDEQ-NTK.
Theorem D.1. Let y, E RPXQXCo be s.t |ææyll 1 l2 1 for E [P], [Q]. Define the following expressions recursively (some v, are omitted in the notations), for (i,j, E (P) [Q] x PP] x (Q), h E [d]
ig.'' (5,u)= =
Σ aeECoo
F(aa) V(ii)
(24)
$1.88"
Tr ([x:0) (x, Desiess )
(25)
13.8'3
[S) 1' aml
1 (x, 2)
Exh-2) (xx v)
22x2 3 A G.
(x, =
ij.
"3.'""
(26)
1(h-1 1) (y,, x))
I(--1) (y. v)
2338888
[S]6 ow
+ [S] of 1S]y
K (1 (I,
E (0,0)
[o(u)o(U)]
(K(0) (0)
63.88''
SS]p
(27)
[Sky of |8
(Z,00)
[i((0]
E (u,0)
[o())((v)]
(28)
Tr ((
1888
(29)
Define the linear operator L PxQxXXQ - Pxxxxxx via (((M) = Tr (IMbsss)
23

---

Under review as a conference paper at ICLR 2023
Then the CDEQ-NTK can be found solving the following linear system:
(x, = K" (x. @ ((0 (x, + K (x,,))) y),
(30)
where K (r 3) = limg-=oo (())x,, (), K (2, = lim kid) (x, 1. The actual NTK entry is calculated by (x,
u). The limit exists if ow <
Theorem D.1 highlights that the convergence of CDEQ-NTK depends solely on the CDEQ-NTK initialization. The crucial factor here is the normalization tensor S, which guarantees the variance of each term is always across the propogation. This idea mimics that of the DEQ-NTK initialization. Our theorem shows that CDEQ-NTK
also be computed by solving fixed point equations.
We first explain the choice of S in the CDEQ-NTK initialization. In the original CNTK paper (Arora al., 2019), the normalization is simply 1/4². However, due to the zero-padding, l/9² does not normalize all (b) (z,zz) z)
expected: only the variances that away from the corners ij,''y'
normalized to 1, but the ones near the corner are not. [S] is simply the number non-zero entries
in
X
Du.i
Now we give the proof to Theorem D.I.
Proof of Theorem D.I. Similar to the proof Theorem 3.1, we can split the CDEQ-NTK in two terms:
(x, = Eo {
(010..) x)
()(0,))
}
00
00
(0f(0xx)
0f(0,y)
(00xx) x))
0f v)
Eg
+ E.
OW
aw
au
0U
2
Omit the input symbols æ; y. let
oi
(10
E
(a(u)o(o)).
[S]i -Sley NO. (.rl)))
As shown in Arora al. (2019), have
0So(z) O.
R(d R(ldd) o (.. k-()) (R (R+))R
Tr
OW(M) @W(h)
Write =o and f foly). Following the same step, by chain rule, we have
os oj (U(M) (U()
(...k())))) (.......' + Tr ((()) o k(d-1) @ e (...K( @ L (K(O))
Rewrite the above equations in recursive form, calculate the L-depth iteration of CDEQ-
NTK by:
For the first layer ((0) (I. v) (00) v).
For h I,...,d let
(e(N) (c, vi
19.13 1 = Tr (1:00) (I, ( @
(()00))))000 (2.0) + k(()) (Ir, (H, Diswer )
(31)
For h = d, let
(L)) (x. k(dd) (x, v) 2 (dd-1) (x. + k(h)) (x.1)
(32)
24

---

Under review as a conference paper at ICLR 2023
The final kernel value is Tr(e(d(a ())
Using Equation (31) and Equation (32), we can find the following recursive relation:
((d+1) (z. y) k((++)) (z. y) o c (x, (((+t))
(33)
The rest of the proof is stated in the main text. For readers' convenience include them here again.
At this point, we need to show that K (x,
lima-oo (I, and K (x, -
lima-+ K(d) y) exist. Let first agree that for all h E [d], (ij, (y) E [P] [Q] x [P] [Q],
the diagonal entries of " are all ones. Indeed, these diagonal entries are I's at h = 0 by ini-
tialization. Note that iterating Equations (26) (29) to solve for [Σ(h] (z, Vll is equivalent to iterating f - P PxQXXxX
plh+1) = s(p(t)) a L [S)sss Ro (p(lil)) ,p()) K(())
(34)
where
V Vi-
2 (piies) 1110d'
(p(t)
+
cos-
cos
(DD.))
p(h)
Ro (((PP1))))))) 2 ow Ra 15,0g))
+ oi
(35)
is applied to p(h) entrywise.
Due to CDEQ-NTK initialization, if Pi,.) 1 for [P], E [Q]. then (h) for all iterations h. This is true by the definition of S.
Now if we can show f is contraction, then E' "x, y) & lima (1 (z, y) exists, hence K* and K also exist. We should keep the readers aware that PxXxxxx + R PxQxPx so should be careful with the metric spaces. We want every entry of (,, to converge, since this tensor has finitely many entries, this is equivalent to say its 8oD norm (imagine flattenning this tensor into vector) converges. So can equip the domain co-domain of f with tr norm (though these are fiittedimensional spaces so we can really equip them with any norm, but picking 8o norm makes the proof easy).
R.
Now we have f= 1 Ru go0 + 8o0 If we flatten the four-way tensor p(h) into vector, then L can be represented by a (P x xxXxxxxxxxxxxxXxxxxxxxxxxxxxxxxx (P Q x Px Q) dimensional matrix, whose (kl, - entry in the (ij, f')) --th row is 1 if (fl, KT) Diy.sy and 0 otherwise. In other words, the Ed norm of the (ij, row represents the number of non-zero entries in Dij,t'', but by the CDEQ-NTK initialization, the row ll norm divided by [8] [S] is at most 1! Using the fact that | Theorem 3.3), we conclude that f is indeed a contraction.
El is the maximum El norm of the row, and the fact R, is contraction (proven in
With the same spirit, we can also show that Equation (32) is a contraction if oi < 1, hence Equa- tion (30) indeed the unique fixed point. This finishes the proof.
D.1 COMPUTATION OF CDEQ-NTK
One may wish to directly compute fixed point (or more precisely, fixed tensor) of ( PxxxPxx like Equation (10). However, due to the linear operator L (which is just the ensemble of the trace operator in Equation (29)), the entries depend on each other. Hence the system involves a (P x Q x P x Q) x (P x Q x P x -)-ddmeesionnll matrix that represents L. Even if we exploit the fact that only entries the same "diagonal" depend each other, L is least P x Q x P x Q, which is 324 for CIFAR-10 data.
Moreover, this system is nonlinear. Therefore cannot compute the fixed point Σ" by root-finding efficiently. Instead, we approximate using finite depth iterations, and we observe that in experi- ments they typically converge to 10-6 accuracy in eoD within 15 iterations.
25

---

Under review as a conference paper at ICLR 2023
Table 2: Performance of CDEQ-NTK on CIFAR-10 dataset
Method
Parameters
Acc.
CDEQ-NTK with 2000 training data CNTK with 2000 training data
ow 0.65, of = 0.35
37.49%
Depth 6
43.43%
CNTK with 2000 training data
Depth = 21
42.53%
Table 3: Performance of DEQ-NTK on CIFAR-10 10 dataset, see Lee et al. (2020) for NTK with ZCA regularization..
Method
Parameters
Acc.
DEQ-NTK DEQ-NTK DEQ-NTK
ow 0.25, of 00.55, oj 0.5
59.08%
oi 0.6, of: =0.4, 0 =
59.77%
ow 0.8, ot -0., of = 59.43% oW = 2, of = 0.01
NTK with ZCA regularization
59.7%
We test CDEQ-NTK accuracy on CIFAR-10 dataset with just 2000 training data. The result is shown in Table 2.
Table 4: Performance of DEQ-NTK on MNIST dataset, compared to neural ODE (Chen et al., 201 8b) and monotone operator DEQ, see these results from Winston Kolter (2020).
MNIST
Method
Model size
Acc.
DEQ-NTK
98.6%
Neural ODE
84K
98.2%
MON DEQ
84K
98.2%
26


Reviews:
[{"review_id": "lwoiJxIwZny", "reviewer": "Reviewer_TcTa", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "Two interesting machine learning models that are simultaneously of theoretical and practical interest are Deep Equilibrium Models (DEQs) and well-behaved infinite-width neural networks trained using gradient flow (Neural tangent kernel, NTK). The first is theoretically interesting, because it can *sometimes* be used to understand very deep weight-tied networks, and the second is interesting because it can *sometimes* be used to understand finite-width neural networks trained using gradient descent. This paper combines elements from DEQs and NTKs, showing how the NTK of a DEQ can be computed in a certain regime. ", "summary_of_the_review": "This paper analyses DEQs in the context of the NTK. My biggest concern is that as currently written, it is not clear that the weight-tied structure of DEQs is faithfully analysed (see section 3 first equation and remark 3.2). If this structure is indeed not faithfully analysed, the analysis reduces to a trivial known result. The writing in section 3 could generally be improved (the lack of precision of the assumptions and conditions in section 3 arguably makes them incorrect), as could the details of the experiments. The experiments do not seem to argue that the derived model is practically useful (which would not be an issue with the paper in itself, if its other merits could stand on their own).", "strength_and_weaknesses": "**Strengths:**\n- Studying the NTK of a DEQ is an interesting mathematical problem, and will help connect the two communities of implicit neural networks and infinite width neural networks.\n\n**Weaknesses**\n- A very critical part of the proof and intuition for this paper is that the NTK of a weigh-tied network is the same as the NTK of a corresponding network with independently sampled weights in each layer. This appears to be an existing result of Yang. However, as this a very central part of the paper (first equations in section 3), it needs to be thoroughly unpacked and explained in the main text. Currently, the way the analysis is presented is backwards (the unweight-tied version is introduced first), and remark 3.2 gives no hint of the machinery behind the statement. The proof of theorem 3.1 in the appendix seems to also not be helpful in this issue. As such, at the moment I can only see that this paper discusses infinitely deep networks with independently sampled weights in each layer, not DEQs. What are the conditions and/or assumptions required for the equivalence of weight tied and not weight tied networks?\n- Theorem 3.1 and 3.3 seem to give no conditions that ensure that that the fixed point is unique, or even that exists. In contrast, the condition in Theorem 3.5 that the standard deviation is less than 1/8 seems to be a contraction condition that ensures that a unique fixed point exists. I do not think Theorem 3.1 and 3.3 can be correct in general without some assumption ensuring that a fixed point is unique and/or is unique. But at the moment, the text preceding the theorem is not precise enough to even allow the theorem to be expressed in terms of such conditions or assumptions. Can you add the required assumptions and conditions into the relevant theorems?\n- There are some further issues around clarity (detailed below).\n- As far as I can tell (please correct me if I am wrong), the paper makes no attempt to argue that the derived NTK-DEQ is a practically useful model, only that it is a mathematical curiosity. Given the toy evaluation, it is unlikely that such a model will be useful in the broader context of machine learning.\n\n\n**Mathematical ambiguities and correctness:**\n- Section 3. In this equation block, this infinite depth limit does not always converge to the unique fixed point. Since this seems to be the main mathematical section of the paper, it is necessary to have some more precision in this section.\n- First equation in section 3. This is not a weight-tied network, so the text \"Define the ... DEQ as the following:\" is not appropriate. You mention later that DEQs require weight-tied networks and that the limit of this un weight-tied network will be the same as the weight-tied. If this is the case, why not introduce the DEQ with weight tying and then prove that this limit is the same as with weight-tying? As is, the sentence before the equation is not accurate.\n- In order to invoke the result of Yang, you mention that \"The neural architecture needs to satisfy a gradient independent assumption.\" Can you write down what this assumption is?\n- Proof of Theorem 3.3. For equations (17) and (18), it might be more appropriate to cite Cho and Saul than Daniely, since Cho and Saul were first.\n- Theorem 3.5. Please give a definition of \"with high probability\".\n\n**Experiments:**\n- Section 5.2. What is the model? I assume some kind of kernel method? Kernel logistic regression? SVM? In the text it says \"After obtaining the NTK matrix, we apply kernel regressions\", but these problems look like classification problems?\n- \"Notice these root finding problems are one-dimensional, hence can be quickily solved.\" Which problems are \"these\", and why are they one-dimensional? It is not obvious to me as currently written. For a dataset of size $n$, each data point will appear in the kernel matrix $n$ times (granted, it is a symmetric matrix). There is a typo in quickly.\n- Section 5.1. Are these $W$ trained in an NTK regime? (Non-stochastic) gradient descent? What is the data and task that the network was trained on?\n- Figure 5. Which nonlinearities are used in the figure on the right?\n\n**Minor:**\n- First sentence of introduction. There are also optimisation-based layers (Deep Declarative Networks: A New Hope), which implicitly define the output of a layer as the solution to a (possibly constrained) optimisation problem. Under sufficient regularity, this is equivalent to finding a root of the gradient. But not always. These are also mentioned in the implicit layer NeurIPS tutorial.\n- \"Bai et al. (2019) proposed the DEQ model, which is equivalent to running an infinite-depth FCNN-IJ, but updated in a more clever way\". This is not precise. A DEQ model *can* be equivalent to an infinite-depth FCNN-IJ. For example, if the mapping involved in each iteration is a contraction, the infinite-depth recursion converges to the unique fixed point. But a DEQ model is not necessarily *always* equivalent to an infinite-depth FCNN-IJ. You mention existence and uniqueness at the end of the paragraph, but this should come first.\n- Two periods on \"bias terms..\" in section 3.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "USdAuNrCn-", "reviewer": "Reviewer_fAKE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper showed that contrarily a DEQ model enjoys a deterministic NTK despite its width and depth going to infinity at the same time under mild conditions. The deterministic NTK can be found efficiently via root-finding.", "summary_of_the_review": "The paper showed that contrarily a DEQ model enjoys a deterministic NTK despite its width and depth going to infinity at the same time under mild conditions. The deterministic NTK can be found efficiently via root-finding. The main contributions of the paper lie in the theoretical aspects and simulations have demonstrated the performance. Some of the key proof builds upon existing work, the real new contributions should be made clear.", "strength_and_weaknesses": "Strength:\n\n+ The paper showed that unlike the infinite depth limit of NTK to FCNN, the DEQ-of-NTK does not converge to a degenerate kernel. This non-trivial kernel can be computed efficiently using root-finding.\n\n+ The NTK-of-DEQ coincides with the DEQ-of-NTK under mild conditions. The paper showed numerically that reasonably large networks converge to roughly the same quantities as predicted by theory.\n\n+ The paper showed the NTK-of-DEQ matches the performances of other NTKs on real-world datasets.\n\nWeaknesses:\n\n- Only simulation experiments are conducted to demonstrate the performance of the NTK-of-DEQ.\n\n- The paper is presented in a rather dense mannar. It is better to give a high-level overview of the proof pipeline.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PckAFTc6Dg", "reviewer": "Reviewer_4dFG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This work studies the NTK of the dee equilibrium model.  Contrast to the NTK of FCNN which can be stochastic if its width and depth both tend to infinity simultaneously, a DEQ model will have a deterministic NTK in this case under some mild conditions. Also this deterministic NTK can be found efficiently via root-finding.", "summary_of_the_review": "I'm not familiar with DEQ model, but in my perspective this paper made some theoretical, especially technical contribution for proving the existence of NTK-to-DEQ by proving an exchangeable nested limit. However I'm not sure what further theoretical or application results can be induced from this conclusion.", "strength_and_weaknesses": "Strength\n- This paper shows that unlike the infinite depth limiting case of NTK to FCNN, the DEQ-of-NTK does not converge to a degenerate kernel, and the non-trivial kernel can be computed efficiently using root-finding.\n- The forms of the final main theorems are compact, intuitive and easy to understand.\n\nWeakness and Questions\n- What is the significance or any application of the conclusion that the DEQ-of-NTK and NTK-of-DEQ are deterministic? I understand this is a theoretical work, but I think it is better to mention the usage or theoretical significance for the existence of a deterministic NTK-of-DEQ as I'm not familiar with the idea of DEQ.\n- What is the accurate meaning of \"high probability\" in Theorem 3.5. Is it somehow related to the distance between $\\sigma_w^2$ and 1/8?\n- I'm a bit confused about the definition of $\\sigma_W$ and the initialization process of $W,U,b,v$. The author mentioned in the beginning of Section 3.1 that pick $\\sigma_W,\\sigma_U,\\sigma_b$ arbitrarily . But it seems there is no constraint for $\\sigma_W$ in the beginning of Section 3.1. What is the difference between this one and that defined in Theorem 3.1.\n- What will happen if $\\sigma_W^2>1/8$ ? Will the NTK-of-DEQ definitely diverges or there be some possibility that both NTK-of-DEQ and DEQ-of-NTK converges but at different limits?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject