A global convergence theory for deep ReLU implicit networks via over-parameterization
Authors: Tianxiang Gao
Hailiang Liu
Jia Liu
Hridesh Rajan
Hongyang Gao
Venue: ICLR 2022 Poster (2022)
Keywords: Deep learning
Deep implicit learning
deep equilibrium model
gradient descent
stochastic gradient descent
over-parameterization

Abstract: Implicit deep learning has received increasing attention recently due to the fact that it generalizes the recursive prediction rule of many commonly used neural network architectures. Its prediction rule is provided implicitly based on the solution of an equilibrium equation. Although a line of recent empirical studies has demonstrated its superior performances, the theoretical understanding of implicit neural networks is limited. In general, the equilibrium equation may not be well-posed during the training. As a result, there is no guarantee that a vanilla (stochastic) gradient descent (SGD) training nonlinear implicit neural networks can converge. This paper fills the gap by analyzing the gradient flow of Rectified Linear Unit (ReLU) activated implicit neural networks. For an $m$ width implicit neural network with ReLU activation and $n$ training samples, we show that a randomly initialized gradient descent converges to a global minimum at a linear rate for the square loss function if the implicit neural network is over-parameterized. It is worth noting that, unlike existing works on the convergence of (S)GD on finite-layer over-parameterized neural networks, our convergence results hold for implicit neural networks, where the number of layers is infinite.

A GLOBAL CONVERGENCE THEORY FOR DEEP RELU IMPLICIT NETWORKS VIA OVER-PARAMETERIIZAION
Tianxiang Gao
Hailiang Liu
Department of Computer Science lowa State University gaotx0 i www.xeeisstttteeeee..
Department of Mathematics
Iowa State University h1 Aliue Lastate.edeee
Jia Liu
Hridesh Rajan
Dept. of Electrical and Computer Engineering The Ohio State University
Department of Computer Science lowa State University hridesh@ lastate,...... edu
liuBece. oooossuueee
Hongyang Gao
Department of Computer Science
lowa State University
hygaoê astate.eddeee.
ABSTRACT
Implicit deep learning has received increasing attention recently, since it gener- alizes the recursive prediction rules of many commonly used neural network ar- chitectures. Its prediction rule is provided implicitly based on the solution of an equilibrium equation. Although many recent studies have experimentally demon- strates its superior performances, the theoretical understanding of implicit neural networks is limited. general, the equilibrium equation may not be well-posed during the training. As result, there is no guarantee that vanilla (stochastic) gradient descent (SGD) training nonlinear implicit neural networks can converge. This paper fills the gap by analyzing the gradient flow of Rectified Linear Unit (ReLU) activated implicit neural networks. For an m--idth implicit neural net- work with ReLU activation and training samples, initialized gradient descent converges to a global minimum at a linear rate for the square loss function if the implicit neural network is over-paranee pere-aarmettrized. It is worth noting that, unlike existing works on the convergence of (S)GD on finite- layer werrparametterized neural networks, our convergence results hold for im- plicit neural networks, where the number of layers is infimite.
show that randomly
INTRODUCTION
1) Background and Motivation: In the last decade, implicit deep learning (El Ghaoui et al. 2019) have attracted more and more attention. Its popularity is mainly because it generalizes the recursive rules of many widely used neural network architectures. A line of recent works (Bai et al. 2019 El Ghaoui et al., 2019 Bai et al. 2020) have shown that the implicit neural network architecture wider class that includes most current neural network architectures as special cases, such as feed-forward neural networks, convolution neural networks, residual networks, and recurrent neu- ral networks. Moreover, implicit deep learning also well known for its competitive performance compared to other regular deep neural networks but using significantly fewer computational sources (Dabre & Fujital 2019 Dehghani et al. 2018: Bai et al. 2018).
Although line of literature has been shown the superior performance of implicit neural networks experimentally, the theoretical understanding still limited. To date, is still unknown if a simple first-order optimization method such as (stochastic) gradient descent can converge neural network activated by a nonlinear function. Unlike a regular deep neural network, an implicit neural network could have infinitely many layers, resulting in the possibility of divergence of the
implicit

---

forward propagation (El Ghaoui al., 2019 Kawaguchi 2021). The main challenge in establishing the convergence of implicit neural network training lies in the fact that, in general, the equilibrium equation of implicit neural networks cannot be solved in closed-form. What exacerbates the problem is the well -ell-poosd of the forward propagation. In other words, the equilibrium equation may have zero multiple solutions. A line of recent studies have suggested number of strategies to handle this well-posedness challenge, but they all involved reformulation or solving subproblems in each iteration. For example, [I Ghaoui et al. (2019) suggested to reformulate the training as the Fenchel divergence formulation and solve the reformulated optimization problem by projected gradient descent method. However, this requires solving a projection subproblem in each iteration and convergence was only demonstrated numerically. By using an extra softmax layer, Kawaguchi 2202 established global convergence result of gradient descent for a linear implicit neural network. Unfortunately, their result cannot be extended to nonlinear activations, which are critical to the lcarnability of deep neural networks.
This paper proposes global convergence theory of gradient descent for implicit neural networks activated by nonlinear Rectified Linear Unit (ReLU) activation function by using overparameteriza- tion. Specifically, we show that random initialized gradient descent with fixed stepsize converges to a global minimum of ReLU implicit neural network at a linear rate as long as the implicit neural network is overparamelerized. Recently, over-parametteizztion has been shown to be effec- tive in optimizing finite-depth neural networks (Zou et al. 2020; Nguyen & Mondelli] (2000) AArora al. 2019: Oymak & Soltanolkotabi] (020). Although the objective function in the training is non- smooth and non-convex, it can be shown that GD or SGD converge to a global minimum linearly if the width m of each layer is polynomial of the number of training sample n and the number of layers h, i.e, m poly(n, h). However, these results cannot be directly applied to implicit neural networks, since implicit neural networks have infinitely many hidden layers, i.e., + 00, and the well-posedness problem surfaces during the training process. In fact, Chen et al. (2018); Bai et al.) (2199] 2020) have all observed that the time and number of iterations spent on forward propagation gradually increased with the the training epochs. Thus, we have to ensure the unique equilibrium point always exists throughout the training given that the width m is only polynomial of n.
2) Preliminaries of Implicit Deep Learning: In this work, we consider an implicit neural network with the transition at the E-th layer in the following form (El Ghaoui et al. 2019 Bai et al. 2019):
A= f- + ((())
(1)
where & : Rd + R is a feature mapping function that transforms an input vector x E IRd to a desired feature vector Φ a o(x). x" E Ih" is the output of the b-th layer, A E mmm is a trainable weight matrix, ou)) max u} is the ReLU activation function, and y E (0, 1) is a fixed scalar to scale A. As will be shown later in Section 2. y plays the role of ensuring the existence of the limit z" limz-ro 2f. In general, the feature mapping function & is nonlinear function, which extracts features from the low-dimensional input vector x. In this paper, we consider a simple nonlinear feature mapping function o given by
1 [W(w), Vm
b(x)
where W E x is trainable parameter matrix. As é + oc, an implicit neural considered an infinitely deep neural network. Consequently, 2" not only the limit of the sequence {z( Je with zo = 0, but it is also the equilibrium point (or fixed point) of the equilibrium equation:
network can be
z" = +):
where 7. 7/vm. mm In implicit neural networks, the prediction و for the input vector x is the combination of the fixed point xn and the feature vector Φ, i.e.
U = uT 2" + u Φb
(4)
where u, 0 E Rd are trainable weight vectors. For simplicity, we use e & vec (A, W, u, v) to group all training parameters. Given training data set {(x,, 31) )r
want to minimize
12
L( Σ
(0r 2²
1 y/
(5)
2
2

---

where & and are the vectors formed by stacking all the prediction and labels.
3) Main Results: Our results are based on the following observations. We first analyze the for- ward propagation and find that the unique equilibrium point always exists if the scaled matrix 5.A in Eq. 3 has an operator norm less than one. Thus, the well-posednee problem is reduced to finding sequence of scalars {7x ) such that (kk) is appropriately scaled. To achieve this goal, show that the operator norm A(k) is uniformly upper bounded by a constant over all iterations. Consequently, fixed scalar 7 is enough to ensure the well-posedness of Eq. (3). Our second ob- servation is from the analysis of the gradient descent method with infinitesimal step-size (gradient flow). By applying the chain rule with the gradient flow, we derive the dynamies of prediction (t) which is governed by the spectral property of a Gram matrix. In particular, if the smallest eigen- value of the Gram matrix lower bounded throughout the training, the gradient descent method enjoys linear convergence rate. Along with some basic functional analysis results, it can be shown that the smallest eigenvalue of the Gram matrix at initialization is lower bounded if no two data samples are parallel. Although the Gram matrix varies in each iteration, the spectral property is preserved if the Gram matrix is close to its initialization. Thus, the convergence problem is reduced to showing the Gram matrix in latter iterations is close to its initialization. Our third observation is that we find random initialization, over weer-parameterizttinn and linear convergence jointly enforce the (operator) norms of parameters upper bounded by some constants and close to their initialization. Accordingly, we can use this property to show that the operator norm of A is upper bounded and the spectral property of the Gram matrix is preserved throughout the training. Combining all these in- sights together, we can conclude that the random initialized gradient descent method with a constant step-size converges a global minimum of the implicit neural network with ReLU activation.
The main contributions of this paper are summarized as follows:
(i) By scaling the weight matrix A with a fixed scalar y we show that the unique equilibrium point 2" for each x always exists during the training if the parameters are randomly initialized, even for the nonlinear ReLU activation function.
(ii) We analyze the gradient flow of implicit neural networks. Despite the non-smooth and non- convexity of the objective function, the convergence to a global minimum at linear rate is guaranteed if the implicit neural network is over-parameterized and the data is non-degenerate.
(iii) Since gradient descent is discretized version of gradient flow, with fixed stepsize converges to a global minimum of implicit neural networks at a linear rate under the same assumptions made by the gradient flow analysis, long the stepsize is chosen small enough.
show gradient descent
Notation: For a vector x. ||=|| is the Euclidean norm æ. For matrix A, ||A|| the operator norm of A. If A is square matrix, then Aunn (A) and Amax(A) denote the smallest and largest eigenvalue of A, respectively, and (A) ||A]]. We denote [n] (1,
2 WELL-POSEDNESS AND GRADIENT COMPUTATION
In this section, we provide simple condition for the equilibrium equation to be well-posed in the sense that the unique equilibrium point exists. Instead of backpropagating through all the intermedi- ate iterations of a forward pass, we derive the gradients of trainable parameters by using the implicit function theorem. In this work, we make the following assumption on parameter initialization.
Assumption 1 (Random Initialization). The entries A.j and Wij are randomly initialized by the standard Gaussian distribution (0, 1), and u, and v; are randomly initialized by the symmetric Bernoulli or Rademacher distribution.
Remark 2.1. This initialization is similar to the approaches widely used in practice (Glorot & Bengio 2010 He al. 2015). The result obtained in this work can be easily extended to the case where the distributions for A.j. Wij. ui and v, are replaced by sub-Gaussian random variables.
2.1 FORWARD PROPAGATION AND WELL-POSEDNESS
In a general implicit neural network, Eq. 3 is not necessarily well volsed, since it may admit zero multiple solutions. In this work, show that scaling the matrix A with >/ym guarantees
3

---

the existence and uniqueness of the equilibrium point 2" with random initialization. This follows from a foundational result in random matrix theory as restated in the following lemma.
Lemma 2.1 [Vershymin (2018), Theorem 4.4.5). Let A be an m x n random matrix whose entries A. are independent, zero-mean, and sub- Gaussian random variables. Then, for any > O, we have ||||| < CK(Vm + vn + t) with probability at least - 2e - Here C' > 0 is a fixed constant, and K = max., ||
Under Assumption ! Lemma 2.1
implies that, with exponentially high probability. |||||| < cym
for some constant c 0. By scaling A by positive scalar 5, show that the transition Eq. ① is contraction mapping. Thus, the unique equilibrium point exists with detailed proof in Appendix A.1
Lemma 2.2. If [|]] S cymm for some e > 0, then for any "o E (0, 1). the scalar _ minf 7o, 70.
uniquely determines the existence of the equilibrium =" for every and || S I-70 [| for all e.
Lemma 2.2 indicates that equilibria always exist if we can maintain the operator norm of the scaled matrix (7//m) less than during the training. However, the operator norms of matrix A are changed by the update of the gradient descent. It is hard to use a fixed scalar to scale the matrix A over all iterations, unless the operator norm of A is bounded. In Section 3 we will show || < 2cmmm always holds throughout the training, provided that [|A())]] S cv/m at initialization and the width mn sufficiently large. Thus, by using the scalar 7 = min 70/ (2c)) for any To E (0, 1),
equilibria always exist and the equilibrium equation Eq. 3 is well-posed.
2.2 BACKWARD GRADIENT COMPUTING
For a regular network with finite layers, one needs to store all intermediate parameters and apply backpropagation to compute the gradients. In contrast, for an implicit neural network, we can derive the formula of the gradients by using the implicit function theorem. Here, the equilibrium point 2 is root of the function f given by f(z, A, W) - 2 a (5 + Φ). The essential challenge is to ensure the partial derivative 0f/0z at x* is always invertible throughout the training. The following lemma shows that the partial derivative 0f /0z at z" always exists with the scalar y and the gradient derived in the lemma always exists. The gradient derivations for each trainable parameters are provided in the following lemma and the proof is provided in Appendix[A.2
Lemma 2.3 (Gradients of an Implicit Neural Network). Define the scalar y - min(%o. ///c]. If
||||] I cv/m for some constant e > 0, then for any % (0, 1), the following results hold:
(i) The partial derivatives of with respect to 2, A, and W are (f Gaaaglo((A440
0
Oz [mm 7 diag
+ の)) A'
(6)
& - 2 diag af d( + +))]
(7)
0A
0f
8 diag ((W))) diag(o'(FAs + d))T,
(8)
dW
m
where 5 2 7/ Vm.
(ii) For any vector v, the following inequality holds
Amin {T... i diag (a' (a(())) > 70 > 0. which further implies 0f 00/ is invertible at the equilibrium point ==.
(9)
(iii) The gradient of the objective function L with respect to A and W are given by
VuL
Σ (U+ v)
VoL = Σ (0s v)Φ.
(10)
im1
xm1
n
V VAL= Σ
7(i - 9i) D. IIm ;.A. T u
(11)
V
(0:
31 E { Imm - -5DAA- -T
u + xT"
(12)
4

---

where is the equilibrium point for the training data (2,, Mc), D, - diag(o Φ:)),
and E; - (W))))
3 GLOBAL CONVERGENCE OF THE GRADIENT DESCENT METHOD
In this section, we establish the global convergence results of the gradient descent method im- plicit neural networks. In Section [.T] first study the dynamics of the prediction induced by the gradient flow, that is, the gradient descent with infinitesimal step-size. We show that the dynamics of the prediction is controlled by Gram matrix whose smallest eigenvalue is strictly positive over iterations with high probability. Based on the findings in gradient flow, we will show that the ran- dom initialized gradient descent method with a constant step-size converges to global minimum at a linear rate in Section 3.2
3.1
CONTINUOUS TIME ANALYSIS
The gradient flow is equivalent to the gradient descent method with an infinitesimal step-size. Thus, the analysis of gradient flow can serve as stepping stone towards understanding discrete-time gradient-based algorithms. Following previous works on gradient flow of different machine learning
models (Saxe et al. [213 et al. 2019) Arora et al. 2018: Kawaguchi] (021) the gradient flow of implicit neural networks is given by the following ordinary differential equations:
dvec (A) at(t) dvec (W) dt
@L(t) du
aL(t)
du aL(t)
(13)
dl where L(t) represents the value of the objective function I((0) at time t.
0A
Ow dt
au
di
dv
Our results relies on the analysis of the dynamics of prediction (t). particular, Lemma 3.1 shows
that the dynamics of prediction (t) is governed by the spectral property of a Gram matrix H Ht).. Lemma 3.1 (Dynamics of Prediction (t))). Suppose |s) s c./m for all 0 I S t. Let
X Rnnx (s) RR" and (s) Ra** be the matrices whose rows are the training data æ;, feature vectors $,,, and equilibrium points z, time s, respectively. With scalar y & min(% %o/c}
for any "/o (0, 1), the dynamics of prediction (t) is given by
dÿ [()2(()) + I.) o (1)) + +(11) XXT +(1) (g y),
dt
A H(t)()-))))) - y).
(14)
where is the Hadamard product (i.e., element-wise product), and matrices M()) R and Q(t) E Raxn are defined as follows:
M())ig [T 4D:A) D.D (.D)) (Tm. (T AD;A)-TTn
(15)
1 Q(): (D,
-(na-))))--uu (mm u E (mm
v).
(16)
Note that the matrix H (t) is clearly positive semidefinite since it is the sum of three positive semidef- inite matrices. If there exists constant is positive definite, then the dynamics of the loss function L(t) satisfies the following inequality
such that Amin { (!) Z X > for all i.e., (()
L(t) S ex)
which immediately indicates that the objective value T((1) is consistently decreasing to zero at a geometric rate. With random initialization, we will show that H positive definite long as the number of parameters m is sufficiently large and no two data points are parallel to each other. In particular, by using the nonlinearity of the feature map o, we will show that the smallest eigenvalue of the Gram matrix Gtt) & (t) t (t)7 is strictly positive over all time with high probability. As a result, the smallest eigenvalue of Ht) is always strictly positive.
varying matrix. We first analyze its spectral property at its initialization. When = 0. it follows from the definition of the feature vector Φ in Eq. (2) that
Clearly, G(t)
G()) = क (0) (XW (X
Σ oXx (X)
m
5

---

By Assumption | each vector w,) follows the standard multivariate normal distribution, i.e., (0) ~ NO, [a). By letting oc, we obtain the covariance matrix Q E R as follows:
G
(17)
Here G is a Gram matrix induced by the ReLU activation function and the random initialization. The following lemma shows that the smallest eigenvalue of G is strictly positive as long two data points are parallel. Morcover, later in Lemmas 3.3 and 3.4 we conclude that the spectral property of Go is preserved in the Gram matrices (0)) and Gtt) during the training, long the number of parameter m is sufficiently large.
Lemma 3.2. Assume
|
= 1 for all i E [m]. If a; æy for all i + j. then Ao Amin ( > 0.
Proof. The proof follows from the Hermite Expansions of the matrix G and the complete proof provided in Appendix A.4
Assumption 2 (Training Data). Without loss of generality, we can assume that each æ; is normalized have unit norm, i.e., [x = for all E [n]. Moreover, we assume z; J/ z for all * j.
In most real-world datasets, it is extremely rare that two data samples are parallel. If this happens, by adding some random noise perturbation to the data samples, Assumption can still be satisfied. Next, show that at the initialization, the spectral property of G is preserved in G(0) if m is sufficiently large. Specifically, the following lemma shows that if m ((n²), then G(0) has a strictly positive smallest eigenvalue with high probability. The proof follows from the standard concentration bound for Gaussian random variables, and we relegate the proof to Appendix A..5
log (3) then with probability of at least Lemma 3.3. Let Ag Amin ( > 0. If m Ω 2
1 6, it holds that [G(()) - No and hence Amin (G(O)) 2 2 Ao-
During training, G(t) is time-varying, but it can be shown to be close to G(0) and preserve the spectral property of Go, if the matrices W has a bounded operator norm and is not far away from (0). This result is formally stated below and its proof is provided in Appendix A.6
Lemma 3.4. Suppose [[]] $ c/m, and Amin (G( 2
3 >>g. For any matrix W E mxd
1
that satisfies || I 2cmmm and |[ W <
- R. the matrix defined by G &
16c|| 1
(XX")) satisfies | G())
< da and Amin (G) 2 Ao.
4
The next lemma shows three facts: (1) The smallest eigenvalue of Gtt) is strictly positive for all t 0: (2) The objective value L(t) converges zero at linear convergence rate; (3) The (operator) norms of all trainable parameters are upper bounded by some constants, which further implies that unique equilibrium points in matrices Z (t) always exist. We prove this lemma by induction, which is provided in Appendix A.7
Lemma 3.5. Suppose that [0( = mm. [|0(0)] = mm. [W S c ||(())] S c.m, and
Amin (G))) 2 3 doo 0. If m Ω
c' [ (0((0) yll and < 7 S minf) 11, ), then for
X
2 de
any 2 0, the following results hold:
(i) Amin (G(()) >
Ag 2
( ||u(t)]| <
16e//n Ao
(0) y I.
(iii [|x([]] < Ao
ScyT
(0( v/1.
(iv) [[({)]] < 2cym.
(v) [[()]]] & 2cy/m.
(vi) (() - 1 < exp(->o0111p - 2
By using simple union bounds in Lemma 2.1 and 3.5 we immediately obtain the global convergence result for the gradent flow as follows.

---

Theorem 3.1 (Convergence Rate of Gradient Flow). Suppose that Assumptions and we set the number of parameter m = S2 xg probability least 1 over the initialization, we have vll?
2 hold. If 11 then with
log ( and choose 0 < 75 min
2 4e
(() 0/ exp(-
14 2
This theorem establishes the global convergence of the gradient flow. Despite the nonconvexity of the objective function L(0). Theorem 3.1 shows that if is sufficiently large, then the objective value is consistently decreasing to zero at a geometric rate. In particular, Theorem 3.1 requires m = (nn)), which is similar or even better than recent results for the neural network with finite
layers (Nguyen Mondelli 2020; Oymak & Soltanolkotabi] 2020, Allen-Zhu al., 2019 Zou & Gu 2019] Du et al.) 2019). In particular, previous results showed that is a polynomial of the number of training sample n and the number of layers h, i.e., m Q(n h12) with a 2 2 and
3 2 12 (Nguyen & Mondelli] 20200 Table 1). These results do not apply in our case since we have infinitely many layers. By taking advantage the nonlinear feature mapping function, we establish the global convergence for the gradient flow with m independent of depth h.
3.2 DISCRETE TIME ANALYSIS
In this section, we show that the randomly initialized gradient descent method with a fixed step- size converges global minimum linear rate. With similar argument used in the analysis of gradient flow, we can show the (operator) norms the training parameters are upper bounded by some constants. It worth noting that, unlike the analysis of gradient flow, do not have an explicit formula for the dynamics of prediction ÿ(t in the discrete time analysis. Instead, we have to show the difference between the equilibrium points Z Z(k) in two consecutive iterations are bounded. Based on this, we can further bound the changes in the predictions (k) between two consecutive iterations. Another challenge to show the objective value consistently decreases over iterations. A general strategy is to show the objective function is (semi-)smooth with respect to parameter O, and apply the descent lemma to the objective function (Nguyen & Mondelli [2020] Allen-Zhu al.] 2019 Zou & Gul 2019). In this section, we take advantage of the nonlinear feature mapping function condition (Karimi et al, 2016 guyen 202I), which allows to provide much simpler proof.
in Eq. 4. Consequently, we are able to obtain a
The following lemma establishes the global convergence for the gradient descent method with a fixed step-size when the operator norms of (()) and (0) are bounded and Amin (G(0) >> 0. The proof is proved in Appendix [A.8]
Lemma 3.6 (Gradient Descent Convergence Rate). Suppose [u(())| mm ||((0]| = mm.
[[)]
< c |O]] $ cymm, and Amiu (G(O)) 2 A > O. IF < S min 2 4c)
m = Ω x (0) y/(²) and stepsize a O (Ao/n²). then for any & 2 0, we have
(i) Amin (G(k)) 2 Aa 2
i |[(()]] < 32c/T (0) yll.
(iii) [|u(k)]] < Xo
16c (0) - yll.
(iv) || (k))l < 2m.
(v)
[|A]]]]] < 2e//m, m,
(vi)
(k) 2/ < (1 ad (1)(0) - 2
By using simple union bounds to combine Lemma 2.1 and 3.6 we obtain the global convergence result for the gradient descent.
Theorem 3.2 (Convergence Rate of Gradient Descent). Suppose that Assumption | and 2 hold. If
we set m Ω
n2 Xo log (1)). < 7 S min 1 1 and choose step-size a O (>o/n2 n2) then with probability at least 5 over the initialization, have
(k) 2 < (1 /2/ y11² Wk > O.

---

1.
18/0
02892
-13
01844
922
0188
(a) Training loss
(b) Test loss
(c) Operator norms
Ieae
Brck
01190
-10
11144
(d) Training loss
(c) Test loss
(f) Operator norms
1981 1os
opersior eam of
02012
2010
0,822
Training loss
(h) Test loss
Operator norms
2018
2010
010922
2010
-12
--12-
01810
-17
01800
(i) Training loss
(k) Test loss
Operator
Figure I: Results on MNIST, FashionMNIST, CIFARIO. 10, and SVHN, We evaluate the impact of the width m on the training loss, test loss, and operator norm of the scaled matrix (7/ h3/mmm/(8 on four real datasets.
EXPERIMENTAL RESULTS
In this section, we use real-world datasets MNST, FashionMNST, CIFARIO, and SVHN to evalu- ate our theoretical findings. We initialize the entries of parameters A, W, u, and v by standard Gaussian or symmetric Bernoulli distribution independently as suggested in Assumption [ For each dataset, we only use classes 0 and 1, and 500 samples are randomly drawn from each class to generate the training dataset with n = 1000 samples. All data samples are converted to gray scale and resized into 28 x 28 pixel image. We also normalize each data to have unit norm. two parallel samples are observed, Thus, Assumption 2 is also satisfied. We run 1000 epochs of gradient descent with a fixed step-size. We test three metries with different width m. We first test how the extent of vver-parameterizaaion
add random Gaussian noise perturbation one of them.
8

---

affects the convergence rates. Then, we test the relation between the extent of over- wwverrraattteiizationn and the operator norms between matrix A A(k) and its initialization. Note that the "operator norm" " in the plots denotes the operator norm of the scaled matrix (7/vm)] A(k)]l- Third, we test the extent of over-parameterivation and the performance of the trained neural network on the unseen test data. Similar to the training dataset, We randomly select 500 samples from each class the test dataset.
From Figure [ the figures in the first column show that as m becomes larger, we have better conver- gence rates. The figures in the second column show that as m becomes larger, the neural networks achieve lower test loss. The figures in the third column show that the operator norms are slightly larger for larger m but overall the operator norms are approximately equal to its initialization. The bell curve from the classical bias-variance trade-off off does not appear. This opens the door to new re- search direction in implicit neural networks in the analyses of generalization error and -ariina trade-off.
5 RELATED WORKS
Implicit models has been explored explored by the deep learning community for decades. For ex- ample, |Pineda| (1987) and [LLMEDAA (1987) studied implicit differentiation techniques for training recurrent dynamics, also known as recurrent paok-propagation (Liao et al. 20188). Recently, there has been renewed interested in the implicit models in the deep learning community (El Ghaoui et al. 2019: Gould et al., (2019). For example, Bai et al. (2019) introduces an implicit neural net- work called deep equilibrium model for the for the task of sequence modeling. By using implicit ODE solvers. (eeen et al. (2018) proposed neural ordinary differential equation an implicit resid- ual network with continuous-depth Other instantiations of implicit modeling include optimization layers (Djolonga & Krause 2017
2017|AAmss Ammss & Kolter 2017). differentiable physics engines (de Avila Belbute-Peres et al.] 2018: Qiao et al.) (0220). logical structure learning (Wang et al. 2019). and
continuous generative models (Grathwohl al. 2019).
The theoretical study of training finite-layer neural networks via wver-parameterization has been an active research area. Jacot al. (2018) showed the trajectory of the gradient descent method can be characterized by a kernel called neural tangent kernel for smooth activation and infinitely width neural networks. For a finite-width neural network with smooth or ReLU activation, |Arora et al. (2019) Du et al. (2019);(i [i & Liang (0018) showed that the dynamics of the neural network is gov- emned by a Gram matrix. Consequently, Zou et al. 2020); Du et al. (2019); Allen-Zhn et al. (2019); Nguyen & Mondelli (222)): Arora et al. (2019); Zou & Gu (2019) Oymak & Soltanolkotabi (2020) showed that (stochastic) gradient descent can attain global convergence for training a finite- neural network when the width m is polynomial of the sample size and the depth h. However, their results cannot be applied directly to implicit neural networks since implicit neural networks have infinite layers and the equilibrium equation may not be well-posed. Our work establishes the well posedeossssess of the equilibrium equation even if the width m is only square of the sample size n.
6 CONCLUSION AND FUTURE WORK
In this paper, we provided a convergence theory for implicit neural networks with ReL.U activation in the over-parameterizaaion regime. We showed that the random initialized gradient descent method with fixed step-size converges to a global minimum of the loss function at a linear rate if the width m = Q(n²). In particular, by using a fixed scalar E (0, 1) to scale the random initialized weight matrix A, we proved that the equilibrium equation is always well- cell-posed throughout the training. By analyzing the gradient flow, we observe that the dynamics of the prediction vector is controlled by a Gram matrix whose smallest eigenvalue is lower bounded by a strictly positive constant as long as m = 2(n?). We envision several potential future directions based on the observations made in the experiments. First, we believe that our analysis can be generalized to implicit neural networks with other scaling techniques and initialization. Here, we use a scalar 7//m to ensure the existence of the equilibrium point z" with random initialization. With an appropriate normalization, the global convergence for identity initialization can be obtained. Second, we believe that the width m not only improves the convergence rates but also the generalization performance. In particular, our experimental results showed that with a larger m value, the test loss is reduced while the classical bell curve of bias- variance trade-off is not observed.

---

ACKNOWLEDGMENTS
This work has been supported in part by National Science Foundation grants III-2104797, DMS1812666 CAREER CNS-2110255 102599, ENS-2112471, CNS-2102233, CCF-2110252, CNS-21- 20448, CCF-19-34884 and Google Faculty Research Award.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242 252. PMLR, 2019.
LB ALMEIDA, A learning rule for asynchronous perceptrons with feedback in combinatorial environment. In Proceedings, 1st First International Conference on Neural Networks, volume 2, pp. 609-618 618. IEEE, 1987.
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pp. 345. PMLR, 2017.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. convergence analysis of gradient descent for deep linear neural networks. arXiv preprint arXiv:/810.02281, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: /901. //955, 2019.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Trellis networks for sequence modeling. arXiv
preprint arXiv:/8// 118.8800.066... 2018.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. arXiv preprint 101.019999.1177... 2019.
Shaojie Bai, Vladlen Koltun, and Zico Kolter. Multiscale deep equilibrium models. urXiv preprint arXhv:2006.08655 08656, 2020.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differ- ential equations. arXiv preprint arXiv:1806.07336,, 2018.
Raj Dabre and Atsushi Fujita. Recurrent stacking of layers for compact neural machine translation models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 6292- 2019.
Filipe de Avila Belbute-Peres, Kevin Smith, Kelsey Allen, Josh Tenenbaum, and Zico Kolter. End- to-end differentiable physics for learning and control. Advances in neural information processing systems, 31:7178-7189, 2018.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03879 2018.
Josip Djolonga and Andreas Krause. Differentiable learning of submodular models. Advances in Neural Information Processing Systems, 30: 30:1013-1023, 2017.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, PMLR, 2019.
Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Y Tsai. Implicit deep learning, arXiv preprint wwXiv:190..06..0 2, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Stephen Gould, Richard Hartley, and Dylan Campbell. Deep declarative networks: A new hope. arXiv preprint arXiv: 9099999994666 2019.
10

---

Will Grathwohl, Ricky T. Q. Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. International Confer- ence on Learning Representations, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026- 1034, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. arXiv preprini
2018.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the -ojaskl-ojasiiiizz.. condition. Joint European Conference on Ma- chine Learning and Knowledge Discovery in Databases, pp. 795-811 811. Springer, 2016.
Kenji Kawaguchi. On the theory of implicit deep learning: Global convergence with implicit layers. arXiv preprint arXiv:2102.07346, 2021.
Erwin Kreyszig. Introductory functional analysis with applications,, volume 1. wiley New York, 1978.
Yuanzhi Li and Yingyu Liang. Learning overparameterizzed neural networks via stochastic gradient descent structured data. arXiv preprint arXiv:/808.01204 2018.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urta- sun, and Richard Zemel. Reviving and improving recurrent back-propagation. In International Conference on Machine Learning. pp. 5082-3091. PMLR, 2018
Barbara MacCluer. Elementary functional analysis, volume 253, Springer Science Business Media, 2008
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. arXiv preprint arXiv:2101.09612 2021.
Quynh Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. arXiv preprint arXiv:2002.07867, 2020.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization:: Global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-105, 2020.
Fernando Pineda. Generalization of back propagation to recurrent and higher order neural networks. In Neural information processing systems, pp. 602-611, 1987.
Yi-Ling Qiao, Junbang Liang, Vladlen Koltun, and Ming C Lin. Scalable differentiable physics for learning and control. arXiv preprint arXiv:2007.02166. 2020.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
Roman Vershynin. High-Dimen Digh--imensional Probability: An Introduction with Applications in Data Sci- ence. Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. ISBN 978-1-108-41511
Po- Ro-Wei Wang. Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and log- ical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning. pp. 6545-6554, PMLR, 2019.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. arXiv preprint arXiv: 1906.0404400 046.04488, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, (09(3):477-49) 2020.
11

---

A APPENDIX
A.1 PROOF OF LEMMA 2.2
Proof. Let to E (0, 1). Set y - min 70700/70/// ///c]. Denote ÿ = 7/ /m. Then
|| =11 = ol (7Az + +6) (5Az* + +]]l
SS || Az A=
2--1 -11,,
a is I-Lipschitz continuous
- A(z 2z|)||
* A All|e -111 ||
55c /5c/mlllz m
-2 2/11 ||||| S c/m
=ool2= -1
Applying the above argument f times, we obtain
|| 12tt1__ =111 < >ôll= 2 -66100)1 bbl
where we use the fact n² = 0. For any positive integers p, with S q, we have
||2 - 2 - =112" - 2 + || - 2011
<1110051 +... +.. 7g
S 11110111 (1 + 7a + r +...)
% ||01||.
700
Since Yo E (0, 1). we have ||2 20| + p - oc. Hence, 1=1 is a Cauchy sequence.
Since R" is complete. the equilibrium point x" is the limit of the sequence {=110 1 so that exists and is unique. Moreover, let + co, then we obtain || - 211l s ~ || so that the fixed-point iteration converges to z linearly.
Let p and q L, then we obtain || S - |Q
A.2 PROOF OF LEMMA 23
Proof. (i) To simplify the notations, we denote D & diag(d(AAAz + Φ)), and E - The differential of is given by
df =d Az + +()
=dz Dd(5A= + +
1m DAA dz D(dA) DdØ.
Taking vectorization both sides yields
vec (df) = [m DDA vec (dz) vec (FiddAz) Dvec (d()
= Im *DA] vec (dz) "12"" Dvvee (dA) Dvec (dØ).
Therefore, the partial derivative of f with respect to 2, A, and & are given by
0f Im "DA
0z
0f
- [ Ø D)"
0A
0s D
06
12

---

It follows from the definition of the feature vector in Eq. that
dΦ do W x)
m j
E(dW))
E
vec (dW).
m
Vm
vm
Thus, the partial derivative of & with respect to W is given by
dΦ
E
(18)
OW
By using the chain rule, we obtain the partial derivative of f with respect to W as follows
os dΦ 0f
T D
x
ow
ow dΦ
(ii Let be an arbitrary vector, and u an arbitrary unit vector. The reverse triangle inequality implies that
(1 7 (ddia(('())))) ull
|uu| 15 diag(o'(v)))
||u|| 7/1 diagga'
(
(0)
2 (1 -00
=1 - 70 O,
where (a) is due lo'(v) < left-hand side over all unit vector u yields the desired result.
and || I c.mm Therefore, taking infimum the
(iii) Since f(z", A, W) = 0, taking implicit differentiation of I with respect to A at =" gives us
Oz
of
0
0.
0A
dz
0A
The results in part (i)-(i) imply the smallest eigenvalue of 0f invertible. Therefore, we have
is strictly positive, so that it
U=
0z*
0f
05
D
D I. RDAI- (19)
0A
0z
Similarly, we obtain the partial derivative of with respect to W as follows
0z
0f
0f 0z
E
D I RDAI" (20)
aw
aw
To further simplify the notation, we denote be the equilibrium point by omitting the superscribe, i.e., z = x". Let ÿ = u" + v &b be the prediction for the training data (x, y).
The differential of ÿ is given by
dÿ = d (u" T z + DT ②) = n" dz + zdu + o" dØ + o" du.
The partial derivative of ý with respect to u. v. z. and & are given by Öyj
dÿ u,
Oj Φ
Oj
du z, dr
ds = v.
(21)
dz
Let f. = (5 2 Then 0
(ú y). By chain rule, we have
at Oğ de
=(ğ v).
(22)
du Du ōg
al Dğ de
Φ0 - v).
(23)
OΦ On Oij
By using
19
20
and chain rule, we obtain
0l
0z de
0A
0 Oz
dz Oÿ de
7/0 v)
2 8 D
In
-D-DDA TT u.
(24)
0. Oz Ōg
13

---

and
Oz
dy 0E
dqp 0y ot OW dΦ dÿ
OW
OW
Oz 09
1
& E T ADDA)
- -u uu
(25)
Vm
Since Ei= 4 with 4 = f(Di v1),, we have dL Ei=ı dl, and 0L/06, Therefore,
obtain
aL
0e:
7 - mi) - 8 Di] [m -5D;A) u.
[m
(26)
0A
0A
aL
0e,
1
(0: yo! E.J [D] (4m -DDAA) T +o),
(27)
OW
OW
Vm
OL
04
(0: y4 Zis
(28)
0u
pu
AL
0l,
Σ
(0r
(29)
dv
0v
1=1
A.3
PROOF OF LEMMA 3.1
Proof.
Let 2, denote the i-th equilibrium point for the i-the data sample æ,. By using
19
20
26 and (27 we obtain the dynamics of the equilibrium point z; follows
dz;
0z:
dvec (A)
θzi OW
dvec (W)
dl
0A
dl
di
0z:
OL
0z,
ÖL
+
0A
0A
aw
OW
(ūs
Uj)
[m "D,
& DJ & DJ]" [Im - -DDDA] u
/=1
1
(Ú) - 91) [m -DD.A] Dj x & E, 1 & 1 (Lm (m (mm +
(0s M3) -.DIA D.D [mm -5D;A| uuz zj
Σ (ū) U.) [... -DDDAAA-DEEE -
-DD,A) -T u
2) a. Zz.
m
By using
18 and
27
we obtain the dynamics of the feature vector d;
dΦ;
ae. aW
dvec (W)
dl
dt
0Φ.
T
aL
@W
aW
(is
Yi E.E,
D. (Tm
-D;A) Tu tu æ;.
m
14

---

By chain rule, the dynamies of the prediction is given by
dip
0ij
dzi
Pij
dΦ:
Oijs Eu
du
dv
dt
0z,
dt
:Φ:
dt
do
dt
7/
Σ (5) v3)
lu" (I 5D,A) D (Im
jD)
uu] (2 2,)
/=1
Σ (0s U1) (DD (I (m -DDA) E, (D) (Im -D; v) (at
Σ 05 (z)
j=1
Σ 9) (,)(oT Φ,).
Define the matrices (t) E Rux= and Q(t) E m= as follows
M() lt (Im -DD. (I -5D,A)
m
Q(t) (D. (I -mm--D;A) RD;A) uu w)² E,E (D) (mm u u
m
Let gaxd (t) E R"xm and (t) E R " the matrices whose rows are the training data T;, feature vectors Φi, and equilibrium points 2, time t, respectively. The dynamics of the prediction vector ý is given by
dÿ ((>2 + I.) Z(1)Z(1) + Q(1) xx" + (())((()) (Ø(1) y).
di
A.4 PROOF OF LEMMA 3.2
A.4.1 REVIEW HERMITE EXPANSIONS
To make the paper self-contained, we review the necessary background about the Hermite polyno- mials in this section. One can find each result in this section from any standard textbooks about functional analysis such as MacCCuer (2008); Kreyszig (978), most recent literature (Nguyen & Mondelli] 2020, Appendix D) and (Oymak Soltanolkotabi 2020 Appendix H).
We consider an -.p-space defined by (R, dP), where dPP is the Gaussian measure, that is,
dP = p(x)dx, where p(x)
22T
Thus, LR dP) a collection functions f for which
1f(z) (P()) = f 1f(z) p(x)dr Ex-N(..) 1f(x)) < co.
Lemma A.1. The ReLU activation a E L2 dP).
Proof. Note that
(xxx)) p(x)dr < /
00 |z| p(z)dr = 1212 Var(z) = 1.
15

---

For any functions f.g (R, we define an inner product
(f.9) = / (())g())dP(x)= =
= L f(=)g(=))(z)d===aa) -oo.
Furthermore, the induced norm || is given by
/ [f(x)] d((x) No. [f(x)]
Ilfl =
This I.2 space has orthonormal basis with respect to the inner product defined above, called normalized probabilist's Hermite polynomials ( that are given by
(x)z)) Vol 1 (11" 12 (e
12
where (e
d" 12
dr
Lemma A.2. The normalized probabilist's Hermite polynomials is an orthonormal basis of L (R, dP): (pms hn) 8mn-
Proof. Note that (" (2(e-=112) = for a polynomial with degree of and leading term (-1)"x". Thus, we can consider (z) Ail (-1)"
Assume m < n
(hay hm) -E, ((.
= =/o
hn (2(2))m
-² 12dx
V2T
(-1)
(e 1² 12/12/222222 12) (r)dr,
rewrite h, by its definition
V2
1
(-1)utm
(e (2n rewrite hm by the polynomial form
Vnt/nlvmm
(-1)2a4m
=0 ( integration by parts n times
VT
There is no boundary terms because the super exponential decay of ==²/2 at infinity. Since m n, then 1.
that (Dem: =0. If m n, then D,, (Pm) = (-1)"nn. Thus, (hny hn)
Remark: Since { is orthonormal basis, for every f E LRR dP)),, we have
f(x) = Σ (f, hnn (x(x))
in the sense that
N
N
2
lim
f(z)
Σ n=
(f, hnd (x()))
= lim (.w) f(x) Σ No
(f. hn.) hn (x)
=0
m=0
Lemma A.3. E (PRRRdP) if and only if Eoe [J,, hn)) co.
16

---

Proof. Note that
00 (f = dd(x)) dP(x)
Σ SUIN)ao)) (E aP(x) )ap())
(. J 00 (o)P()))))P((
Σ K
Lemma A.4. Consider Hilbert space H with inner product (,)) lI fll + and -191~9l +
0, then (f.g) lim (fn, 9n)-
Proof. Observe that
Kf.g) (fns 9n)) S k)f.g) (fn. g)و 1faa 9) (frs 9n)
fIlfIllg g..ll + Ilf..1lllg - In
Let - 0o, then the continuity of || implies the desired result.
Lemma A.5. Let (h, (2)) be the normalized probabilist's Hermite polynomials. For any fixed
number f, we have
21-
hx(x).
(30)
Proof. First, we show f(x) = ett E H A L2 (2
(1 = RxNN(1011 1
2xt-1"" 1
1--2/2
V2T
(x (((=2))²
exp
x ~ N(21, 1) } da,
V2T
2
00
= x0
Thus f(x) E H. Then f(I) = Ene (f, (un) (z))). Note that
hn) (oD))(
P11
(-1)me"² / 2/ Dr (212)) V2T" e
dx
(-1)
aa -1 Dn -02 -2212 12)
integration by parts n times
Vn!
V2n
000
(-1)2n
1
P22211241 - 12
Vn!
22T
-00
1
12- dr, x 1)1
Vnl -00
2
fn
Vn!
17

---

Lemma A.6. Let a. be E R with ||a|| ||b|] 1, then
E N [ (a, ) ((b, wn)) = (1, b)" 8mn.
Proof. Given fixed numbers and define two functions f(w) ela.w)t-8/22 and g(w)
g(b.w)sss /2 Let x = (a, w) and = (b, w). Then we have
f(w) =e -la,ww)e-812 p2t-1p22
h
(x)
e hn (ia, w))
nmn
nm0
20
8
8
g(w) =b(b, = 12
(1())
hn ((b, w))
n=0
Define a Hilbert space Ha LR dP), where dP is the multivariate Gaussian measure, equipped with inner product (J,9) & Bww.:wio.aal/((o)))(a)))) Clearly, f.g E Ha. Define se- quences } and {aN} } as follows
(N(W) = Σ
Nm ((a, w)) and gx(w) = Σ Vn!
nn ((b, w)).
Vn!
Since ||ʃ - SNll - and 11g gN + 0. we have
(ww..wo..t)l((()))(())))) = (f.g)
lim (fN, 9NN N
lim Bw [[r(w)aN(())
N-+00
lim
n,m==0 Vnlvm! Eu No. w)) ((b, w))]
Σ
N
Note that the LHSS is also given by
-c -12- F1-- Bww-Noraallaaaatttooo
=c 12 33 / Din w((atttbi))) (e
=e -1 -2 2/22
E So
i=1
12 1/2 8 /2
Mun, (ast bis)
i=1
(a, b) (st)*
n!
Since s and are arbitrary numbers, matching the coefficients yields
(0, (on uh (00mmm((b.)) ((b, w))] (a, b)" 8mn-
A.4.2 LOWER BOUND THE SMALLEST BIGENVALUES OF 6
The result in this subsection is similar to the results in (gguyen & Mondelli 2020
Appendix D) and OOymak& & Soltanolkotabij 2020 Appendix H). The key difference is the assumptions made on the training data. In particular, Oymak& & Soltanolkotabi (2020) assumes the training data is 6-separable, 0 for all * J, and Nguyen & Mondelli (2020) assumes the data 2; follows some sub- Gaussaausia random variable, while we assume no two data are parallel each other, iee,, æ; 1/ my for all i + j.
i.e, min || - æ, Il. ||,, + x; ||
18

---

Lemma A.7. Given an activation function of (R,, dP) and |
1 for all i e [n], then
G
No, hz)? (xx* .... XX*)
(31)
times
where is elementwise product.
Proof. Observe
Gij = -ww (()
(o, hx) (or, he) N [ x3) NeW s;))]
k.t=0
Σ
(o, ha) (o, he) (o xz)" on
k,8=0
(a, hx) 2g)*
R=
Note that the tensor product of æ. and o, is my 60 ay R x1
so that
(xi, 2)))
2;
k times
Here we introduce the (row-wise) Khatri-Rao product of two matrices A R.xm Then
B R
A @ B1-
A B
E RR
kxmm
Ak. ? Bk.
where A,, indicates the i-th row of matrix A. Therefore, the i-th row of X X A X
2; @ ... & Cs. As result, we obtain more compact form of (31) as follows
G -
(a, (X*t).
(32)
Lemma A.8. If (xx) is nonlinear function and |a(x)] S |a| and then sup(n h,.) 0)
Proof. It is equivalent to show (xx is not finite linear combination of polynomials. We prove by contradiction. Suppose a (xx) = 0p + aiæ .... + az Since (0) = 0 dg. then (x) aiæ + ... + r Observe that
0 + an
lim 20000
lim
a 8-000
[0||
lim
Q1 + an
x=000
00
which contradicts [a((z] |a]
for all + 0.
Lemma A.9. If xx 2/ for all + j, then there exists ky such that Amin [(x*)) for all & 2 ko. Therefore, Amin (Gx) > 0.
19

---

Proof. To simplify the notation, denote K= (X BRkdxx Since 2; VV 2, and || 1, then let 8 a max{ (2,, 2 max{[cor Bz and (0, 1), where Ogy is the angle between æ; and
Zj. For any unit vector v E IR", we have
0² (x T = K
K.
n
Uitiy (Kris Kay)
0g (xi,, 2z²) /
==1==1
x3
2k + Σ
Ui (ar 2z)²
==1
=1 Σ
Us (2 xzح}
*f
where the last equality is because
||>;|| || = and ||||| = 1. Note that
Σ
23)
lusl |u ( 2,)1
8
loal |0yl,
by Kac, (1,1, 2
2
<nok
by SchwarsSchwart's inequlity.
By inverse triangle inequality, we have
Kool 2 1 - nōt
Choose ki 2 log n/ log(1/)), then Amin (X+,)) > for all 2 ko-
A.5 PROOF OF LEMMA 3.3
Proof. Since |<:;| = 1 and w,) ~ A'(0 we have x: (0) ~ NN, for all i e [n]. Let
Xi [ w. (0)] and Z ~ NO0, 1). then for any |V| < 1/v2, we have
Eexp[X Ee [ar (0) X²3 < exp [2> 1/V1 2X s 21
where the first incquality is due tot [a(x) < |r]. and the last inequality is by using the numerical
inequality 1/(1 x) < 2²x Choose A < (log v2) 1/2 we obtain E{X < 2. By using
Markov's inequality, we have for any
PP , 2 t) = IP (x / log 22 2 // log v2] < 2exp { - lf log v2} < 2 exx /41
Therefore X,r is 2018 Proposition 2.5.2). Then X, is a sub-exponential random variable with sub-exponential Lemma 2.7.7). Observe that
random variable with sub-Gaussian norm || 2 Vershynin
norm [rlll, < 4 Veeshhnin 2018
1 m
1 Σ X
G1)(0) (0)) (0))
o (0) [z (0) m
20

---

Since Gū
E [G Veersyynn 2018
Exercise 2.7.10) implies that G1) Gyj is also
zero-mean sub- eaob-exponeniall random variable. It follows from the Bernstein's inequality that
do
Au
P
|G(0)
G
|| - G | 2
Ao
2
|[ - G || Σ
4
X
G25(0) - G z
4
W=
Gij(() - 1 N
oy
4n
1
p
([G - Giy
Au
2
4n
11=1
5 2ex
-cXBm/nn²
<d.
where c > 0 is some constant, and we use the facts | S [|,, and P(Σ
2
x
Σ P(x; 2 e/n].
A.6 PROOF OF LEMMA
Proof. By using the L-pishiitt continuity of (z), we have
1
GG - G(0)
||o "WW
m
1
|ooxX
-OW + 1
|
m
|o(XW o
1
X
X
W
W
x
w W [W]]
-
| W
(())
Aa
A.7 PROOF OF LEMMA 3.5
Proof. It suffices to show the result holds for y = min(ro, mon where 7o 1/2. Note that Lemma 2.1 still holds if one chooses larger Thus, we choose 2 |X] We prove by the induction. Suppose that for 0 < s 5 t, the followings hold
Amin (G(s)) N Aa
(ii [[](s]] < X
16c./D (0) - y||.
(iii) [|x(s)] <
8cy5
(0) v/l
Aa
21

---

(iv) [ (s) s 2eym,
(v) ||A(s)] - 20ym,
(vi) [g))) - y1 v
yyl?.
Since Amin (G(s)) 2 2/1 we have
d
((()) y122 --(((())
2(0(() y)² (()(((()) y)
dt
- --Aolli(1) - y1
Solving the ordinary differential equation yields
((:(t) - y11² S exp(- yl
By using the inductive hypothesis [ [s)] < 2c m. we have
1
||
o (W (s)z,)
( [< s 2c.
vm
follows from Lemma
2.2 with 70
1/2 that
|| 21) s 4c.
Note that
a
I| S Σ li((s) 3el [s)1l
2e Σ (8)(s) 3el
<2c ()) l4
<2c eexpl -dos/2] (1/(0) - 3/
and so
[|o(t) v(0) S / [[V.Lss)llds
<2c//1lly(00 -yll S// Supl-Nos/2jdl
4cvn (8(0) v/l.
Ao
Since (0) follows symmetric Bernoulli distribution, then ||x(0)] /mm and we obtain
[[]( S [|x(() x(0]]l + +|0))||||(00] S ScvT (1)(0) - yyl,>
Ao
where the last inequality is due to m S Similarly, we have
[ 2
(0) y|l²) and > ////|//
V I(s) <
[i(()) - 1211
<4c/ (ss) vll
<4c/nexxp >os/2)1l0(0) - yll.
22

---

so that
[u((t) -u())l !. [VvL(s))lds 1 8cy' (g((0) y/|-
Ao
Since (0) follows symmetric Bernoulii distribution, then ||2( = v m and we obtain
16c/ n (l)(0) yll-
[[((t)] |l((t) (a)ll ||,(0)]||
X
Note that
n
V
L(6]l
S
vil Es)]l (IU,(())+u(s))) u(()) + [|(()))] ||ay|| (0:())
64cyn n
(0)(0)
yll Σ (s)(s) y/l
Ao
64cn
(0) yl (1((s) yll
Ao
64cn
(()(0) y1 expl sxpl->os/2],
Ao
so that
- w()l < I. V L())ldss
128cn
l y112
X8vm
Duym
16c| X11
<R.
Therefore, we obtain
W(I) < (W()) (()1 [| S 2eym.
Moreover, it follows from Lemma 3.4 that Amin ( (G(t)} 2 èa
2
Note that
IV A())ll) <
(ii(s) wil will D.l (s))
32c
n (1)(0) yll Σ (5)(+) - vil
Au m
32en
(1)(0) vll (1((s) yll
dovm
32cn
< \oym
(0)(0) b/1² expl - >ns/2),
so that
[I(()) A(O)) < // | [
Ju
64cn
S
(l) 211
2gym
Then
|A(I) S [I(() A(O)]| + ||A(())| S 2cym.
23

---

A.8 PROOF OF LEMMA 3.6
In this section, we prove the result for discrete time analysis result for gradient descent. Assume A S cym and (()ll I cym. Further, we assume Amin (G(0)) 2 / d and we assume
m = Ω x (0)) yll and choose 0 < S min 1/4c.. Moreover, we assume the
stepsize O (>o/ We make the inductive hypothesis as follows for all 0 S 8 S k
(i) Amin Amin(G(s)) 2 Ae
n2c. (0) yll. (ii) ||[()]]] - Xo
(ii) [|o(s)]| & 1 |0(0) yll.
Ao
(iv) | (s)] < 2eym.
(v) ||A(s)] < m
(vi) [s)(s y| < (1 a2o y11..
Proof. Note that Lemma 2.1 still holds if one chooses a larger c. Thus, we choose e 2t Voo/|XXII.
By using the inductive hypothesis, we have for any 0 U k
[(v())) = vm - (s)xx)
x1)1
(s)
2c
mm
and
1/2
n1 Σ E((
(>)] < (2(s) =
$ 2cVn.
(33)
By using Lemma 2.2 we obtain the upper bound for the equilibrium point (s) for any S follows
$
1
z (s)] S 7o
[s)] (s)) < 4c,
where the last inequality is because choose 7o 1/2, and
1/2
Z [s)] < [
Σ
(x)]1
4cyn.
(34)
By using the upper bound of ()(s)) obtain for any 0 s < k
V.
(s)(s) - yel (s))l
<2c Σ 10:(s) - ysl
<20//ollis00 - y
52c/n(1 22) (1 al|-
Let 3 VI- -ao022 Then the upper bound of V (.)(ss) can be written as
|..(s))] < 2 110 vll.
(35)
24

---

and
*
|o 1) 200) - _
vu(s 1) x(s)] = a Σ
[s)l
==0
==0
Sa 2c/nnll((0)) - y|l Σ g
==0
2(1 B82)
2c/n//lll - yl 1 gh+1
Ao
3
80 nh [()(0) y|ر
Ao
where the last inequality we use the facts 3 < By triangle inequality, we obtain
(Io + 1)ll = ||ok + 1) x0) |I + ||(0)] - 16cy/2 - - yll.
Ao
which proves the result (iii). Similarly, we can upper bound the gradient of
[V S l0c(s) - yel || s 4cvn((ū(s)) - yll s 4cv yl
(36)
so that
160 n2
|u(k + -1-11)--(0 u(O)ll 5
11 - yll,
Ao
and
32c nn 10(0) yll-
(u(()) = (l((k) u(00 + ||((0)]]
Ao
The result (ii) is also obtained.
By using the inductive hypothesis, we can upper bound the gradient of W as follows
I 1(s) S 1=1
Σ
(s((s)
3il
|| Es)ll ((U)(()==((s))) + [[((s))) ||
Vm
128c \oym
(0) yll Σ li.(s)
128cn
(0)( yll (1((s) yll
\oym
128cn
())( y 2 8
(37)
doym
so that
W + 1) W() <a Σ
V W L(s)l
k
<a
128cn
(0)
y11
Σ
g
X m
s=0
512en
| y/
12 /
Vmdo
16c| X|
<R.
25

---

where the third inequality holds is because m is large, i.e. m = θ (- (=2nn|1 simplify the notation, we assume
(8((0) =11²)) To
Ag
CennI ( y||²
(38)
for some large number C' > 0. Moreover, we obtain
( 1)Il S [ + - [[]] S 20mm,
Therefore, it follows from Lemma 3.4 that Xmin (G(k 1)) 2 Aa Thus, the results (i) and (iv) established.
By using similar argument, we can upper bound the gradient of A follows Note that
[ S
lor(s)
yel | ||] [|]]
m
64cy n
(0) yl
(s)(s) yal
domm
64cn
(1)(0) - yl ( yll
dovm
64cn
|s](0) y/ 3",
\ovm
so that
A + 1) Sa Σ V ==0
k Σ
64cn
<a
[0)(0)
y11²
13
Ao Aoym
==0
256en
(0) y/1
Co"n||[11' [0) -y1l² and c, C > 0 are large enough, we have Ag
Since
| + 1) S A 1) - A(O)| + ||A]))]] S 2c/m.
Therefore, the result (v) is obtained and the equilibrium points 2; (k: + 1) exists for all i E [n].
To establish the result (vi), we need to derive the bounds between equilibrium points Z(k) and
feature vectors (k).. We firstly bound the difference between equilibrium points 2,(h + 1) and
(k).. For any & 2 1, we have
|| 12(+1(k+ 1)
(+) =|lo +
- (k))
| A(k + 11 o,
< + 11 (k)l..
where the first term can be bounded as follows
* A + 1) + A())
< A(A + -
2(())
<ha V (4))) (1)+ (+))
64acn (|)( - -1 + +1l23*+ (1/2) (1+ ((())
Anm
26

---

and the second term is bounded as follows
11 + 1) (k)))
1
lo lolW(s (A: + 1)x.} [ (k)==)]
1
W (A: + 1) (+)1la
Vm
V T((=)ll
Vm
128ach
(10(0) - y112.80
Aom
Thus, we obtain
25bach
2 +++ (A: + 1) - 2 (K)1 1) -))=
+
|1)(0)
yl .8
dam
256acn
80
<(1/2)||> (k+ +1 =+)]] +
|):(() y g
2-
Agm
$01/2)112((++) =1))l 512xcen
(l:(0) yl
3h.
Aam
By letting / + co, we obtain
512ach Aum
(k + () 2x)]] -
(Ø(0) y/12.
By using the Seuchy-Schwartee inequality, we have
512aen3/2
Z + [()] - ZZ (((++1)) Z(b)llF
(l - y112 Bt.
(39)
Aom
In addition, we will also bound the difference in o. 1) and (b)... Note that
(k (k+ + (.((l - loo 1)x,] a ( (k)a;)l <
128acn
[1)(0) 3
Aom
so that
128acn3/2
(b( (k)]l < | p S
(l)(0) y112 - gh
(40)
Aum
Now, we ready establish the result (vi). Note that
[k + 1) 2/12 = ( + 1) o(k) [k) y/1 = = + 1) (()) + (5( 1) g()))()))))))) ((k) y) + (1)((k) y112.
In the rest of this proof, we will bound each term in the above inequality. By the prediction rule of D. we can bound the difference between ý(k + 1) and (kk) as follows
(k 1) [(+) = Z + 1)
4 1) - 1)- (()) (k)) Z (k + 1) + 1) Z (k)) + [ 1)u(k + - (k))
where the first term can be bounded as follows by using 34 constant Co >0 0
36 38
39
hypothesis (ii), and large
Z (k: + () 1) u(k)] + 1Z +1
=a (1: + V.[()) + 1 + 1) - ((+))l]l
<aCac2nll$(00 yl ,hh
27

---

and the second term is bounded follows by using constant Co > 0
33
35
40
38
hypothesis (iii), and large
( + 1)]]]| + - + |
1) - (()]])))))
=a (k + +1)11l|. +
211 3
Therefore, we have
[b +1 - -1)+)())))] S aCoc²
- yl ,*,
(41)
where the scalar 2 is absorbed in Co and the constant Co is difference from C.
Let (k + 1) + 4 (k) + 1). Then we have
(0(++1) (()) (kk) y) = (Ø(k + 1) g. [(k) y) - (g- (()), y)
Let us bound each term individually. By using the Cauchy-Schward inequality, we have
(g(k + 1) - g. ((k)) y)
= (ZZ( + 1)) - y) + (( + ( + 1). (kk) - y)
+ 1), (1k) < <I +1) Z ((:) u(k + 1)ll [b(k +1
1) yll
{aCheen(ll(() - yll (0)(()) - all. by (3 36 38
39
SaCben - 1 - y
(42)
By using V (k) Z(k)² (i(k) y). Lk)( (b)) yy and Amin (G(k)) 2 20/2.
we get
ukk) y) = -a((()) y)² [Z(k) + (())0 (0(k) y)
S ado [kk) yl
(43)
2
By combining the inequalities
41
42
43
we obtain
[ + 1) 3/1²
< [1
1oo - Coc n acCc'n²1) 32 (l)(0) y11
aλo
< 1
32k ()) - 211²
ado
k+1
(0) - 3|
2
where the second inequality is by a
O
[g 12
). This proves the result (vi) and complete the proof.
28


Reviews:
[{"review_id": "Qyj_pnfcToa", "reviewer": "Reviewer_pFXH", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\nPros. \n1.  This paper makes a clear contribution to proving the convergence of gradient descent for an implicit neural network with ReLU activation with infinite layers and finite width. I think that using implicit differentiation for the partial gradient at the fixed point is interesting, enabling the proof of convergence by showing the strictly positive-definite of the Gram matrix $\\boldsymbol{G}(t)$. \n\n2.  To ensure the strictly positive-definite of the Gram matrix $\\boldsymbol{G}(t)$,   the required number  $m= \\tilde \\Omega(n^2)$ is competitive or better than recent results for the finite-layered neural network.  In addition,  the result in this paper hold for infinite layers.  \n\n 3. The paper is well organized and clearly written. \n\nCons.\n\n1. The  gradient $\\nabla _\\boldsymbol{A}L $ and $\\nabla _\\boldsymbol{u}L $  involves  equilibrium point $\\boldsymbol{z}$.  However, it is not easy to achieve the equilibrium point explicitly.  How to compute the gradient for training? Does it need an approximation or a solver for the equilibrium point? It seems to me that a solver demands a high time cost.  Does it scale to a large-scale problem?  It is interesting to discuss the relationship (advantage/disadvantage) compared with neural networks with explicit proximal mapping architecture.  e.g.,  (Lyu et al. 2021)  has a similar NN architecture \n\n$ \\boldsymbol{y}_{t+1} = h( \\boldsymbol{D}^\\top_t\\boldsymbol{x} +  (\\boldsymbol{I}-\\boldsymbol{D}^\\top_t\\boldsymbol{D}_t)\\boldsymbol{y}_t   )$ \nwith  \n\n$\\boldsymbol{y}_{0} = \\boldsymbol{0}$\n\nWhen sharing weight $ \\boldsymbol{D}_t=  \\boldsymbol{D}$, and set $ \\tilde \\gamma  \\boldsymbol{A} = \\boldsymbol{I}-\\boldsymbol{D}^\\top \\boldsymbol{D} $, it seems to be  a finite-step updated  NN   instead of the fixed point $\\boldsymbol{z}^*$ in  Eq.(3).\n\n2. ReLU function $f(x) = max(0,x)$ is not differentiable at point $x=0$. How does this influence the continuous time ODE analysis for the linear convergence? \n\nMinor\n\nTypos.   In the proof of Lemma 2.2 in Appendix A.1,  it should be $\\sigma (\\tilde \\gamma \\boldsymbol{A} \\boldsymbol{z}^{l-1} + \\phi  )$ instead of $\\sigma (\\tilde \\gamma \\boldsymbol{A} \\boldsymbol{z}^{l-1} - \\phi  )$.\n\nLyu et al.  Neural Optimization Kernel Towards Robust Deep Learning. ", "summary_of_the_paper": "\nIn this paper, the authors theoretically analyze the convergence of gradient descent for an implicit neural network with infinite layers with ReLU activation.  The authors show the unique fixed point of the infinite-layered mapping when the weight matrix $\\boldsymbol{A}$ has a properly bounded spectral norm.  Using implicit differentiation, the authors show the partial gradient at the fixed point.  Furthermore, the authors show the linear convergence rate by proving the strictly positive-definite of the Gram matrix $\\boldsymbol{G}(t)$  (and $\\boldsymbol{H}(t)$). ", "summary_of_the_review": "\nOverall,  I think this paper makes a clear contribution to proving the convergence of gradient descent for an implicit neural network with ReLU activation with infinite layers.  So I recommend acceptance. ", "strength_and_weaknesses": "", "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": {}}, {"review_id": "QnHUFg2_Y0S", "reviewer": "Reviewer_sNJZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The critical aspect of considering the convergence property for over-parameterized implicit networks is to show the non-singularity of the feature matrix $Z^*$, which is the fixed point of the non-linear equation $Z = \\sigma(AZ+\\phi(X))$, since we treat the final output as $Y= WZ^*$. This is a challenging and open problem for the community of theoretical implicit models. However, the submission considers a different output---$\\hat{Y}= UZ^* + V\\phi(X)$; hence there is no difficulty, and it is meaningless to get the smallest singular values as $\\Theta(\\lambda_0^{1/2})$, which is the same as previous over-parameterized explicit networks $\\phi(X)$ and cannot show any difference between implicit and explicit DNNs. Unfortunately, the submission just got the results in this way.\n\n1. The only difference between this submission and the previous works on explicit DNN convergence in the sense of proof roadmap is the additional proof for the existence of a fixed point at the initialization. However, constructing a shrink operator (which guarantees the existence of the fixed point) is not a complex task. We can even guarantee the well-posedness by setting $A(0)=0$. In fact, as the authors discussed in the submission, we need to prove that the operator $\\sigma(A\\cdot+\\phi(x))$ is shrink during training rather than at initialization. For guaranteeing this, the scaling factor may depend on the other term, such as step size,  rather than only $m$, since we need to bound the difference $A(t)-A(0)$. The author needs to deal with the existence more carefully.\n2. For the convergence speed, it is the same as the previous ones. Hence, it further verifies that the convergence guarantee comes from the explicit additional term $V\\phi(X)$---two-layer over-param ReLU DNN, instead of the implicit feature $Z^*$. A straightforward guess is that all the results still hold when we set $A=0$, or set $U = 0$, or even drop $Z^*$, i.e., $\\hat{Y}= V\\phi(X)$.\n3. When proving the non-singularity of $H$, the submission says that it utilizes a different data assumption---no two data are parallel to each other. However, the same setting and almost the same linear convergence results are given in [1].\n4. More importantly, the current convergence guarantee for over-params DNNs can be divided into two categories in the sense of activation settings-- ReLU and sufficient smooth activation function. For proving the PL-inequality, one relies on the smoothness of activation to provide the lower bound, while the others prove the flipping feature is small and the overall bound can hold during training.  Confusingly, this submission mixes these two roadmaps, utilizes the routine for a smooth activation function in the ReLU setting, which may cause the problem for the conclusion of some auxiliary lemmas.\n\n[1] Gradient Descent Provably Optimizes Over-parameterized Neural Networks.", "summary_of_the_paper": "This submission considers a good problem but contributes a little. ", "summary_of_the_review": "consider a important problem, but heavily rely on the the results in the previous work.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PzoX5AVBQmm", "reviewer": "Reviewer_tTX4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "[Strength]\n- The paper studies the very important problem of convergence of training for implicit models. The problem is non-trivial even given recent advances in relavent proofs for explicit forward-feeding because of the well-posedness issue in implicit models which presents because implicit models can be seen as infinitely deep neural networks.\n- The authors show that by puting a proper simple scaling factor to the weights, the well-posedness property can be maintained throughout the training process with no extra regularization or projection steps. This enables the proof of training convergence for implicit models.\n- Thorough mathematical proofs for both the continuous setting and the practical discrete setting are given in the paper to support the results which are then varified by numerical experiments.\n\n[Weekness]\n- There is a typo in the notations section. I suppose it is lambda_max(A) <= ||A|| since A is not assumed to be positive semidefinite?", "summary_of_the_paper": "The paper presents a proof of exponential convergence to global optimality in the over-parametrization settings for an implicit model with scaled weights parameters. Although existing work has established similar proofs for feedforward explicit neural networks, such methods don't work with non-linearly activated implicit models where the well-posedness issue poses challenges to the training process. The authors shows that by scaling the weights, well-posedness can be ensured. The convergence result is obtained first on continuous settings and is then extended to discrete settings. Numerical experiments on real datasets confirms the finding.", "summary_of_the_review": "The paper sets the foundation for the training theories for implicit models. Though some common techniques are employed to in the derivations, the authors successfully tackle the key issue of well-posedness to make the convergence result possible. The reviewer believes this result is significant for implicit models which have become increasingly popular in the community.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LGBWf5ELFSh", "reviewer": "Reviewer_XwkY", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "To be honest I am not familiar with both theorems and applications of implicit networks. Seems that it is empirically successful but lacks theoretical understanding, then I think this paper provides a good starting point. Under the form (1) and (2), the paper first shows the existence of the equilibrium point given $\\|A\\|$ is bounded. Then the proof of the convergence is similar to DNN:\n\n1. Write down the dynamics (15) and show that one of the terms in $H$ has lower-bounded eigenvalues. (The following calculation heavily relies on the form (2) of $\\phi$. Is this commonly used in applications?)\n2. For sufficiently large $m$ (over-parameterization), the random initialization $G(0)$ is close to the infinite-wide $G^\\infty$.\n3. The lower bound of $G(t)$ gives the linear convergence rate, then the fast convergence indeed guarantees that $G(t)$ is not far from $G(0)$ during the trajectory.\n\nDespite that the approach is sort of standard (and the dynamics seems to be simpler than DNN since all the layers share the same weights?), the proof is not trivial and the theorem is good as it gives the first theoretical optimization result for implicit networks. The paper also implements numerical experiments on several standard image dataset to show the effectiveness of the implicit networks.\n\n**PS:** Thank the authors for the detailed response!", "summary_of_the_paper": "This paper theoretically analyzes the optimization of deep ReLU implicit networks. It first shows the well-posedness of the problem, i.e., the existence and uniqueness of the equilibrium point, then proves that under over-parameterization, both continuous and discrete GD have global convergence in a linear rate, and the approach is similar to the standard proof for DNN.", "summary_of_the_review": "The paper proves the convergence of the optimizing nonlinear implicit networks. The proof techniques follow the standard approach for DNN, and I think it is a good starting point for the theoretical analysis of implicit networks.", "strength_and_weaknesses": "", "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:

Meta-review: This paper shows gradient flow of ReLU activated implicit networks converges to a global minimum at a linear rate for the square loss when the implicit neural network is over-parameterized. While the analyses follow the existing NTK-type analyses and there are disagreements among reviewers on the novelty of this paper, the meta reviewer values new theoretical results on new, emerging settings (implicit neural networks), and thus decides to recommend acceptance
Decision: Accept (Poster)