Implicit NNs are Almost Equivalent to Not-so-deep Explicit NNs for High-dimensional Gaussian Mixtures

We thank the reviewer for his/her feedback and positive assessment of our work.

1. more explanation about related work: We thank the reviewer for the valuable suggestion. We have added more discussions on the CK and NTK in the related work section, and in (the current) Remark 1 to better motivate the GMM in Eq. (7) and Assumption 3 A summary of the results in (Gu et al., 2022) is also included. Due to space limitation, the summary is placed in Section D of the revised supplementary material. Moreover, we have fixed the typos pointed out in your minor comments.

2. dependence on K and p. In this paper, we consider $K$ to be fixed and of order $O(1)$ for $n,p$ both large. So in particular, the data dimension $p$ is not significantly small than the sample size $n$. The assumption of $n,p \to \infty$ with $p/n \to c \in (0,\infty)$ in Assumption 3 is imposed so that the present analysis is performed in a (mathematically rigorously) high-dimensional asymptotic setting. The conducted analysis here does not demand that $n,p$ be growing variables but merely that they be both large (for the large $n,p$ asymptotics to be accurate, say). As such, one may freely assume $p$ large but fixed and $n$ growing, without altering the conclusions of our present study (the approximation error for our results would then be of the order $O(p^{-1/2})$ instead of $O(n^{-1/2})$ in Theorem 1 and 2). This is in complete adequacy with modern machine learning practice where the data dimensions are generally in hundreds or even thousands. The GMM under Assumption 3 has been extensively studied in the literature of high-dimensional ML for a wide class of models ranging from kNN, LDA, SVM, and shallow neural network models, see [D1], Section 2 of [D2], and Section 4.1 of [D3]. We have added the current Remark 1 in the revised version for further discussion on this point.

[D1] Couillet, R., Liao, Z., & Mai, X. (2018, September). Classification asymptotics in the random matrix regime. In 2018 26th European Signal Processing Conference (EUSIPCO) (pp. 1875-1879). IEEE.

[D2] Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of data science. Cambridge University Press.

[D3] Couillet, R., & Liao, Z. (2022). Random matrix methods for machine learning. Cambridge University Press.

We thank the reviewer for his/her careful reading and valuable feedback. In the following, we provide a step-by-step response to all comments raised by the reviewer. We hope in light of our responses the reviewer will consider raising the score accordingly.

1. Code: We have uploaded the code; please see the INN\_Equiv\_ENN folder in the supplementary material.

2. Interest of CK and NTK: The CK and NTK have been studied extensively in the literature to assess the convergence and generalization properties of deep neural networks models. In short, NTK is a specific kernel defined in the context of (deep) neural networks. During (gradient descent) training, the network parameters change and the NTK also evolves over time. It has been shown by (Jacot et al. 2018) and follow-up work that for sufficiently wide neural networks trained on gradient descent with small learning rate, (i) the NTK is approximately constant after initialization and (ii) running gradient descent to update the network parameters is equivalent to kernel gradient descent with the NTK. This duality allows one to assess the training dynamics, generalization, and predictions of wide neural networks as closed-form expressions involving eigenvalues and eigenvectors of the NTK. As already mentioned in Section 1.1, the NTK has been studied for different types of DNN ranging from convolutional, graph, to recurrent and implicit NN, see (Feng and Kolter, 2020). We have also expanded the related work discussion on NTK in Section 1.1 on how it applies to assess DNN models.

3. Bias in INNs: We thank the reviewer for pointing this out. This is indeed a limitation of the present analysis in INN. For the moment the proposed theoretical framework is not able to cover deterministic and/or random bias. To the best of our knowledge, the only work on precise high-dimensional asymptotics of DNN models that has taken the bias into account is [C1], but only on a single-hidden-layer explicit neural network model. It would be of future interest to extend the proposed analysis framework to cover deterministic or random bias, which may lead to further improvement on the network performance.

4. Assumption 3: The assumption of $n,p \to \infty$ with $p/n \to c \in (0,\infty)$ is imposed so that the present analysis is performed in a (mathematically rigorously) high-dimensional asymptotic setting. The conducted analysis here does not demand that $n,p$ be growing variables but merely that they be both large (for the large $n,p$ asymptotics to be accurate, say). Precisely, our derivations and results use this technically convenient means to approximately quantify the INN performance achieved for all large $n,p$ pair. As such, one may freely assume $p$ large but fixed and $n$ growing, without altering the conclusions of our present study (the approximation error for our results would then be of the order $O(p^{-1/2})$ instead of $O(n^{-1/2})$ in Theorem 1 and 2). This is in complete adequacy with modern machine learning practice where the data dimensions are generally in hundreds or even thousands. The GMM scaling (by $\sqrt p$) and the growth rate in Assumption 3 are commonly used in the literature of high-dimensional ML for a wide class of models ranging from kNN, LDA, SVM, and shallow neural network models, see [C2], Section 2 of [C3], and Section 4.1 of [C4]. We have added the current Remark 1 in the revised version for further discussion on this point.

5. Explicit NNs: In Section 4, we have compared in Figure 3 the performance of INNs, L-ReLU-ENNs and ReLU ENNs with the same width $m$. We have added the sentence "Implicit and explicit NNs share the same network width $m \in { 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 }$" to further clarify this setup. Moreover, as suggested by the reviewer, we compared the time costs of the inference and training of INNs and ENNs. The inference time cost of an INN is about $25\times$ that of an ENN with the same dimension. This is due to the fact that it takes around 25 iterations for an INN to reach the iteration error threshold (1e-3). Additionally, we observe that ENNs have remarkable advantage over INNs in terms of the training speed. We report a brief result in the following table (each NN is trained for $150$ epochs).

I would like to thank the authors for engaging in the rebuttal process. I will answer point by point subsequently:

• Code: the code has indeed been provided now, but it's not runnable as is (with the default instructions, for mnist it runs): I get the following error FileNotFoundError: [Errno 2] No such file or directory: './pretrained/cifar10_vgg.pth'. It seems that the pretrained directory has not been included, and probably shouldn't be because of its size. It would be better to give a way to obtain the weights from the internet (anonymously). Moreover, I would suggest removing all potential sources of de-anonymization like comments in the original language. Furthermore, I think it's important to follow the NeurIPS guidelines established here, in particular point 7: for now we don't know what the dependencies are, and we don't know how to reproduce the figures because the code is not present.
• Questions about the code: 1) It seems that the 2 classes Explicit (which is used for the leaky relu experiment) and Explicit_relu (used for the relu experiment) are the same. I therefore think that the difference between the 2 that is noticed in the paper might only be due to a different seed, indeed no seeding mechanism is used in w_matrix = torch.randn(input_dimension, dim).to(args.device). It is very important to address this point because it is one of the main arguments of the paper that the ReLU network is less performant. 2) The experiments are not run over multiple seeds. It is therefore difficult to know if the observed gap is significant or not. 3) I am not sure I understand the implementation of the explicit NNs: the inner weight matrix is fixed and not learned. Why this choice? How does it correspond to the paper?
• Construction of the explicit NN: It became apparent to me after reading the code that actually this part of how to exactly construct the explicit NN was not clearly laid out in the paper. How are the weights set? The paper just mentions the activations part.
• Bias: I apologize: apparently Feng and Kolter also do not use a bias. Still I think it is important to comment on why this is problematic in the proof. I also think it's important to mention it clearly in the paper.
• Assumption 3:

As such, one may freely assume $p$ large but fixed and $n$ growing, without altering the conclusions of our present study (the approximation error for our results would then be of the order $O(p^{-\frac12})$ instead of $O(n^{-\frac12})$ in Theorem 1 and 2). This is in complete adequacy with modern machine learning practice where the data dimensions are generally in hundreds or even thousands

I think this is a misleading proposition. $O(p^{-\frac12})$ only makes sense when $p \to \infty$, otherwise it's just a constant and does not give the intended result which is that the approximation error should be small when the number of data points increases. In modern machine learning practice the data dimension is generally fixed (although it may be huge). I think however, that as other works (for example Mei and Montanari's), it would be useful to comment on the rate of the 2 limits. It would be interesting also to comment on why it is needed intuitively to use high dimensional asymptotics.

• Experiments: I think it's nice to see this result: how can I reproduce it with the code? Further as I mentioned in my original review, could it be possible to do the same with real data? To me this result should replace Figure 1. which does not show anything quantitative and does not illustrate Theorem 1.
• Text duplication: I do not think this paper is a severe case of plagiarism, as indeed I only saw the introduction being copy-pasted. However, I would say that even in the current revised version, it's problematic that the introduction is so similar to Ling et al. : it's now not copy-pasted but slightly reworked.

We thank the reviewer for his/her reply. We are glad that some of the reviewer's concerns have been successfully addressed. We would like to further emphasize that our major contribution is:

1. to build a mathematically rigorous and explicit connection between explicit and implicit network model by focusing their CK and NTKs (that depends on the network design, activation, and data statistics, all in a rather explicit fashion); and
2. to provide empirical evidences to support the theoretical insight obtained from the aforementioned theory. This explicit theory comes (of course!) at the cost of some technical assumptions, for example the high-dimensional GMM setting, the NTK (that is computed from random weights), etc. Given that said, we believe it is of interest and important to present this result to the INN community, which, to the best of knowledge, is the first explicit result on the equivalence between explicit and implicit NN to the community.

The remaining comments mainly involved the definition and implementation of CK and NTK, the high-dimensional asymptotic setting considered in this paper, as well as some details to reproduce the figures. They are addressed respectively as follows.

Clarifications on CK, NTK and their implementations: We would like to further clarify that, per their definition in Eqn. (4)-(6), the CK and NTK matrices are defined and computed for network having random weights, for both implicit and explicit networks, see Assumption 1 and the sentence "As in Assumption 1, we assume that weights matrices Ws have i.i.d. entries ..." after Eqn. (20). This is in perfect accordance with the line of works on NTK, see (Jacot et al., 2018) and (Feng and Kolter, 2020), in which the NTK has been shown to be approximately constant (over time) after random initialization for wide networks trained on gradient descent with small learning rate, see also the related work discussion in Section 1.1 of the revised version.

In our experiments, we compare the eigenspectral behaviors of CK/NTK matrices with their approximations and/or with their explicit counterparts.
By definition (and as stated explicitly in the caption), these matrices are computed for network having random weights (with expectation numerically estimated from sample means). For Figure 3, we have added a clarification sentence that "only the final readout layer of both implicit and explicit networks are trained, with all intermediate layer weights fixed at random, as in line with the NTK literature." We are running additional experiments that train all weights (instead of only the last readout layer) of the network. Note that such additional experiments is of (empirical) interest only to networks of small width $m$ since, for wide networks, the NTK convergence results established in (Jacot et al., 2018) and (Feng and Kolter, 2020) ensure the closeness of the performance between networks with random or trained inner weights matrices.

Assumption 3: We thank the reviewer of his/her further comment. We apology if our previous reply has introduced further confusion to the reviewer, below are some further clarifications:

1. the present work is in the same vein as (Mei and Montanari, 2021) in the sense that here, in the high-dimensional asymptotics setting $n,p \to \infty$, the two dimensions retain a constant ratio $p/n \to c \in (0,\infty)$ as in (Mei and Montanari, 2021);
2. for the reviewer to have a better grasp of the implications of our theoretical result, we would like to argue that the number of data points cannot go to infinity either. In fact, in ML practice and for a given problem, the number of data points itself cannot increase (or at least, cannot increase to go beyond a certain prefixed number). And the approximation errors given in this paper (as well as in, e.g., Mei and Montanari, 2021) should be understood a (concentration-type) bounds saying that, with high probability, the error is bounded by some expression that is a decreasing function of both $n$ and $p$. A detailed description on how such bound explicitly depends on $n,p$ is beyond the scope of this paper. Here, we only proved that in the high-dimensional limit as $n,p \to \infty$ with $p/n \to c \in (0,\infty)$ as in (Mei and Montanari, 2021), the approximation error vanishes at a rate of $O(p^{-1/2})$ or $O(n^{-1/2})$.

We thank the reviewer for his/her careful reading and valuable feedback that helps us improve the paper. In the following, we provide a step-by-step response to all comments raised by the reviewer. We hope in light of our responses the reviewer will consider raising his/her score accordingly.

1. ambitious claim: We definitely agree with the reviewer that our proposed analysis is specific to implicit neural networks built upon contractive mapping, e.g., DEQs, and the term "any implicit neural network" can indeed be misleading. In the revised version, we have added the sentence "by focusing on a typical implicit NN, the deep equilibrium model (DEQ)" in the introduction to clarify. And we have replaced "any implicit neural network" with a given DEQ model in the paper to make our statements more precise. We would also like to point out, as consolidated by the reviewer, that our Condition 1 on the variance parameter is commonly used and is consistent with previous studies on over-parameterized DEQs, see [B1-B3].

2. requirement on the input data following Gaussian mixtures: We would like to kindly point out that the Gaussian mixture model (GMM) in Equation (7) is nothing but standard multivariate Gaussian distribution $\mathcal{N}(\mu,C)$ in $\mathbb{R}^p$ normalized by $\sqrt{p}$. This is to ensure that the data vectors are of bounded Euclidean norm (with high probability), and is in line with previous studies on over-parameterized explicit or implicit NNs, see [B1-B2] and [B4-B5]. Indeed, the GMM in Equation (7) and Assumption 3 have been studied in the literature of high-dimensional statistics and have been shown solvable for a wide class of machine learning (ML) models ranging from kNN, LDA, SVM, and shallow neural network models, see, e.g., [B6], Section 2 of [B7], and Section 4.1 of [B8]. In particular, it is known (see [B6] and Section 2 of [B7]) that different ML methods with different hyper-parameters can lead to different classification performance under Assumption 3. Such theoretical results, as also in the case of our paper, can be exploited to the design of ML models and/or hyper-parameter tuning. We have added the current Remark 1 to provide further discussion on this point.

3. transitions in Eqs. (1) and (2) and network structure: We thank the reviewer for this valuable suggestion. In the revised paper, we have clarified, after Eq. (2), that the network's output is given by $f(\mathbf{x})=\mathbf{a}^\top\mathbf{z^*}$ with readout vector $\mathbf{a}\in \mathbb{R}^m$. This, together with Eq.(1) and (2), provides a complete definition of a fully-connected DEQ model.

4. We have fixed typos in the revised paper.

5. simulations on finite-width networks: In Section D of the supplementary material of the revised paper, we provide in Table 1 additional experiments on the spectral norm difference $\|G^*-\Sigma^{(2)}\|$ for finite-width INNs. The experiment is conducted on GMM data under the same setting as Figure 4 and is repeated follows.

We particularly observe that (i) the difference $\|G^*-\Sigma^{(2)}\|$ for finite-width ploy-ENN decreases with the increase of the network width $m$, and (ii) the approximation saturates at a low level ($\sim 0.12$) and this is due to the finite $n, p$ as opposed to our asymptotic theoretical results in Theorem 1 and 2.

We thank the reviewer for his/her careful reading and valuable feedback. In the following, we provide a step-by-step response to all comments raised by the reviewer.

1. text can be improved to become more accessible: We thank the reviewer for this helpful suggestion and we have moved the proof of Corollary 1 to Section D in the supplementary material and provide only a proof sketch in the main text of the revised paper.

2. about the assumption on GMM data: We would like to kindly point out that the Gaussian mixture model under study in Equation (7) and Assumption 3 is not degenerate for $p$ large. Instead, it is nothing but standard multivariate Gaussian distribution in $\mathbb{R}^p$ normalized by $\sqrt{p}$. This normalization is in line with the previous studies on over-parameterized explicit or implicit NNs, see [A1-A2] and [A3-A5], and more generally with the literature of high-dimensional statistics and random matrix theory. This is necessary to ensure that (with high probability) the Euclidean norm $\| \|x_i\|\|$ of data vectors remains bounded in the high-dimensional limit as $n,p \to \infty$ (also for large but finite $p$, see Section 2 of [A6] and Section 4.1 of [A7]). Under the normalization in Equation (7), the growth rate in Assumption 3 is necessary and can in fact be shown to be optimal in a Neyman–Pearson sense (e.g., Gaussian mixture with closer means is indistinguishable for large $p$), see [A8]. We have added the current Remark 1 to further elaborate on this point.

3. randomness in $\bar{G}$ and $\bar{K}$: The expectations in the definition of CK $G$ and NTK $K$ are taken with respect to the random weights, and the randomness from the input GMM data still exists. Consequently, $G$ and $K$, as well as their approximations $\bar{G}$ and $\bar{K}$, are still random matrices for random input GMM data. We have added the current Footnote 1 to clarify.

[A1] Mei, S., & Montanari, A. (2022). The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4), 667-766.

[A2] Bubeck, S., & Sellke, M. (2021). A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34, 28811-28822.

[A3] Ling, Z., Xie, X., Wang, Q., Zhang, Z., & Lin, Z. (2023, April). Global convergence of over-parameterized deep equilibrium models. In International Conference on Artificial Intelligence and Statistics (pp. 767-787). PMLR.

[A4] Truong, L. V. (2023). Global Convergence Rate of Deep Equilibrium Models with General Activations. arXiv preprint arXiv:2302.05797.

[A5] Feng, Z., & Kolter, J. Z. (2023). On the neural tangent kernel of equilibrium models. arXiv preprint arXiv:2310.14062.

[A6] Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of data science. Cambridge University Press.

[A7] Couillet, R., & Liao, Z. (2022). Random matrix methods for machine learning. Cambridge University Press.

[A8] Couillet, R., Liao, Z., & Mai, X. (2018, September). Classification asymptotics in the random matrix regime. In 2018 26th European Signal Processing Conference (EUSIPCO) (pp. 1875-1879). IEEE.