Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This submission considers a good problem but contributes a little. 
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.

1. 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.
2. 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)$.
3. 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].
4. 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.

[1] Gradient Descent Provably Optimizes Over-parameterized Neural Networks.
summary_of_the_review: consider a important problem, but heavily rely on the the results in the previous work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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:

1. 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?)
2. For sufficiently large $m$ (over-parameterization), the random initialization $G(0)$ is close to the infinite-wide $G^\infty$.
3. 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.

Despite 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.

**PS:** Thank the authors for the detailed response!
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: [Strength]
- 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.
- 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.
- 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.

[Weekness]
- 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 
In 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)$). 
main_review: 
Pros. 
1.  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)$. 

2.  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.  

 3. The paper is well organized and clearly written. 

Cons.

1. 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 

$ \boldsymbol{y}_{t+1} = h( \boldsymbol{D}^\top_t\boldsymbol{x} +  (\boldsymbol{I}-\boldsymbol{D}^\top_t\boldsymbol{D}_t)\boldsymbol{y}_t   )$ 
with  

$\boldsymbol{y}_{0} = \boldsymbol{0}$

When 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).

2. 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? 

Minor

Typos.   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  )$.

Lyu et al.  Neural Optimization Kernel Towards Robust Deep Learning. 
summary_of_the_review: 
Overall,  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.
review_title: null

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)