On the Impacts of the Random Initialization in the Neural Tangent Kernel Theory

Thank you for your careful reading and for raising these questions. We will summarize our main technical contribution and address the questions:

Summary of our technical contribution

"The result in Theorem 4.2 appears novel and interesting, but it is a bit difficult to position this in the existing literature on kernel methods or deep neural networks. I believe that the authors should make more efforts to make the message of this paper clearer."

Thank you for your review and thoughtful comments. Your intuition is correct. Our paper discusses the impact of initialization on the generalization ability of network under NTK theory, with the most critical technical contribution being Theorem 4.2. This theorem addresses the smoothness of the Gaussian process approximated by the initial output network function with respect to the NTK. Now we discuss the challenges and contributions of Theorem 4.2:

• Challenge of Theorem 4.2:
  • If the input is uniformly distributed on the sphere $\mathbb{S}^d$ instead of $\mathcal{X}$, both NTK and RFK are inner-product kernels and their Mercer's decomposition shares the same eigen-function (i.e., spherical harmonic polynomials). In this situation, simple calculations on the eigenvalues would show that $f^{\mathrm{GP}}\in [\mathcal{H}^{\mathrm{NT}}]^{\frac{3}{d+1}}$.
  • However, when the data is a general distribution supported in a bounded open set $\mathcal{X} \subset \mathbb{R}^d$. NTK and RFK will not possess the nice property anymore which makes the claim if $f^{\mathrm{GP}}\in [\mathcal{H}^{\mathrm{NT}}]^{\frac{3}{d+1}}$ unclear.
• Solution and Technical Contributions:
  • Before we clarify our solution and technical contributions, we first recollect some notations. For a sub-region $S\subset \mathbb{S}^d$, let $\mathcal{H}_0^{\mathrm{NT}}(\mathbb{S}^d)$ be the RKHS associated with the homogeneous NTK defined on $\mathbb{S}^d$ and $\mathcal{H}_0^{\mathrm{NT}}(S)=\mathcal{H}_0^{\mathrm{NT}}(\mathbb{S}^d) |_S$ be its restriction on the sub-region $S\subset \mathbb{S}^d$. We define $\mathcal{H}_0^{\mathrm{RF}}(\mathbb{S}^d)$ and $\mathcal{H}_0^{\mathrm{RF}}(S)$ similarly.
  • We first show that, on a general $\mathcal{X}$, $\mathcal{H}^{\mathrm{RF}} \cong [\mathcal{H}^{\mathrm{NT}}]^\frac{d+3}{d+1}$ (where the $\cong$ is isomorphic as Hilbert space not RKHS).
    • Let us fix a continuous and isomorphic mapping from $\mathcal{X} \subset \mathbb{R}^d$ to a sub-region $S \subset \mathbb{S}^d$. We then show the equivalence (as RKHS): $$\mathcal{H}^{\mathrm{\mathrm{RF}}}\cong \mathcal{H}_0^{\mathrm{\mathrm{RF}}}(S), \quad \mathcal{H}^{\mathrm{NT}}\cong \mathcal{H}_0^{\mathrm{NT}}(S).$$ This equivalence is not as trivial as it appears.
    • We then need to show that $[\mathcal{H}_0^{\mathrm{RF}}(S)]\cong [\mathcal{H}_0^{\mathrm{NT}}(S)]^{\frac{d+3}{d+1}}$. Notice that the Mercer's decomposition of RFK and NTK share the same eigenfunctions (i.e., the spherical harmonic polynomials), we know that $[\mathcal{H}_0^{\mathrm{RF}}(\mathbb{S}^d)]\cong [\mathcal{H}_0^{\mathrm{NT}}(\mathbb{S}^d)]^{\frac{d+3}{d+1}}$. If the restriction $\mid_S$ and the interpolation $[]^{\frac{d+3}{d+1}}$ are commutative, then we are done. Unfortunately, this commutativity is not easy to verify in general.
    • Fortunately, by a recent result [haas2023mind], we have $\mathcal{H}_0^{\mathrm{RF}}(\mathbb{S}^d) \cong W^{\frac{d+3}{2},2}(\mathbb{S}^d)$ and $\mathcal{H}_0^{\mathrm{NT}}(\mathbb{S}^d) \cong W^{\frac{d+1}{2},2}(\mathbb{S}^d)$ where $W^{s,2}$ denotes the usual fractional Sobolev space. Since Sobolev space is a more tractable object, we then carefully verify that $\mathcal{H}_0^{\mathrm{RF}}(S) = [\mathcal{H}_0^{\mathrm{NT}}(S)]^{\frac{d+3}{d+1}}$ and finish the proof. We would like to emphasize that there are several different definitions for the fractional Sobolev spaces and there are no similar results explicitly stated in the literature.
  • By Lemma H.5, we have $[\mathcal{H}^{\mathrm{RF}}]^{\frac{3}{d+3}} \cong [[\mathcal{H}^{\mathrm{NT}}]^\frac{d+3}{d+1}]^{\frac{3}{d+3}} (\cong [\mathcal{H}^{\mathrm{NT}}]^{\frac{3}{d+1}})$.
  • If we denote $\mathcal{H}^{\mathrm{RF}} = \left\lbrace \sum_{i \in \mathbb{N}} a_i \lambda_i^{\frac{1}{2}} e_i \mid \sum_{i \in \mathbb{N}} a_i^2 < \infty \right\rbrace$, then the K-L expansion gives us that $f^{\mathrm{GP}} = \sum_{i \in \mathbb{N}} Z_i \lambda_i^{\frac{1}{2}} e_i$ where $\lbrace Z_i\rbrace_{i \in \mathbb{N}}$ are i.i.d. standard Gaussian variables. We can verify that $\mathbf{P}( f^{\mathrm{GP}}\in [\mathcal{H}^{\mathrm{RF}}]^{t}) = 1$ for $t < \frac{3}{d+3}$ and that $\mathbf{P}( f^{\mathrm{GP}}\in [\mathcal{H}^{\mathrm{RF}}]^{t}) = 0$ for $t \geq \frac{3}{d+3}$. i.e., we have
  $$\mathbf{P}( f^{\mathrm{GP}}\in [\mathcal{H}^{\mathrm{NT}}]^{t}) = 1 \text{ for } t < \frac{3}{d+1} \text{ and } \mathbf{P}( f^{\mathrm{GP}}\in [\mathcal{H}^{\mathrm{NT}}]^{t}) = 0 \text{ for }t\geq \frac{3}{d+1}.$$

Response to the Questions:

1. Proposition 2.2: Proposition 2.2 is a direct corollary of Theorem 1 in [zhang2023optimality]. Theorem 1 in [zhang2023optimality] provides an upper bound on the generalization error for general spectral algorithms. We directly applied this to the kernel gradient flow, a special type of spectral algorithm.
2. Consistency in Notation: Thank you for your correction. We will use the expectation symbol $\mathbf{E}$ consistently.
3. Theorem Designation: Thank you for pointing out the issues with Theorem 3.3 and Theorem 4.1. These two theorems respectively provide conclusions on uniform convergence and the impact of the initial output function in kernel gradient flow. The proofs of them are standard and we will change their designation from Theorem to Proposition.
4. Explanation of Theorem 4.2: The explanation of the technical contribution of Theorem 4.2 is detailed in our response above. Thank you again for your valuable feedback.

(We apologize for the rebuttal reaching the 6000-word limit. We will provide the references below and appreciate your understanding for any inconvenience caused.)

References

[haas2023mind] Haas, M., et al. (2023). “Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension”.

[zhang2023optimality] Zhang, H., Li, Y., and Lin, Q. (2023). “On the optimality of misspecified spectral algorithms”.

I thank the authors for their detailed reply and clarification. This helps me have a better grasp of this presented results, I will increase my score accordingly.

I would like to ask the authors to carefully include the above discussions in a revised version of the paper, as also suggested by Reviewer 43yC.

Thanks a lot for your valuable suggestion. It greatly helps us re-interpret our main results. More precisely, Theorem 4.3 and 4.4 actually tell us that the generalization ability depends on the smoothness of the target function $f^*$ and the initialization function. In particular, given the target function $f^* \in [\mathcal H]^{s}, (s \geq \frac{3}{d+1})$,

• The mirror initialization $f_0 = 0 \in [\mathcal H]^{\infty}$ and thus the generalization error is $n^{-\frac{s(d+1)}{s(d+1)+d}}$ ([li2023statistical]);
• The standard initialization $f_0 \in [\mathcal H]^{\frac{3}{d+1}}$ and thus the generalization error is $n^{-\frac{3}{d+3}}$ (our result).

Thus, the $L^2$ generalization error with mirror initialization is $n^{-\frac{s(d+1)}{s(d+1)+d}}$ (which is minimax optimal) and even if the target function $f^*$ is sufficiently smooth, the $L^2$ generalization error with standard initialization is $n^{-\frac{3}{d+3}}$ (which suffers the curse of dimensionality). i.e., the implicit bias introduced by initialization significantly impacts the generalization ability and we should prefer mirror initialization in practice.

We reviewed previous literature and found that [zhang2020type] compared mirror initialization with standard initialization. In Section 7.2.3 and 7.2.4 of [zhang2020type], Figures 3 and 4 show experiments on the Boston house price dataset and the MNIST dataset, demonstrating that mirror initialization (i.e., referred to as Anti-Symmetric Initialization in his notation) indeed outperforms standard initialization in terms of generalization ability. This confirms that NTK theory correctly predicts the impact of initialization in real applications, and we will emphasize this point in our paper.

In summary, we appreciate your highly valuable suggestion. We will revise our paper to emphasize the impact of different methods of initialization in the NTK theory. Thank you again for your insightful comments.

References

[li2023statistical] Li, Y., et al. (2024). “On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domains”.

[zhang2020type] Zhang, Y., et al. (2020). “A type of generalization error induced by initialization in deep neural networks”.

Minors

Thank you for your thorough review and for pointing out the typos and grammatical errors in our paper. We appreciate your feedback, and we have made the necessary corrections as follows:

1. Proposition 2.2: The typo "satisfis" has been corrected to "satisfies".

   • Original: "...noise term $\epsilon$ satisfis..."
   • Corrected: "...noise term $\epsilon$ satisfies..."

2. Lines 126-127: The typo "reall" has been corrected to "recall".

   • Original: "...let us reall the concept..."
   • Corrected: "...let us recall the concept..."

3. Line 233: The grammatical error "an generalization" has been corrected to "a generalization".

   • Original: "This is an generalization..."
   • Corrected: "This is a generalization..."

4. Lines 266-267: The phrase "on longer" has been corrected to "no longer" to clarify the meaning.

   • Original: "...the network on longer generalizes well..."
   • Corrected: "...the network no longer generalizes well..."

5. Line 314: The phrase has been corrected for clarity and grammatical correctness. The article "the" has been added before "real world" and "function" has been pluralized to "functions".

   • Original: "...datasets from real world and estimate the smoothness of function."
   • Corrected: "...datasets from the real world and estimate the smoothness of functions."

We have carefully reviewed the entire manuscript to ensure that no additional errors are present. Thank you for your attention to detail, which has helped us improve the quality of our paper.

Response to Questions

1. Meaning of $C(\mathcal{X},\mathbb{R})$: $C(\mathcal{X},\mathbb{R})$ includes all continuous functions from $\mathcal{X}$ to $\mathbb{R}$ with norm defined as $\lVert f \rVert = \sup_{x \in \mathcal{X}} |f(x)|$ for $f \in C(\mathcal{X},\mathbb{R})$. In fact, Lemma 3.2 on Line 186 is the Theorem 1.2 in [hanin2021random]. The definition of $C(\mathcal{X},\mathbb{R})$ is consistent with that of $C^0(T,\mathbb{R}^{n_L+1})$ in the latter. For more information on weak convergence of continuous random processes, we can refer to Section 7 of [billingsley2013convergence].

2. NNK: The Neural Network Kernel (NNK) we define here is indeed the standard empirical NTK defined in some other literature. Thank you for your feedback and we apologize for the confusion caused by our notation. We will specifically mention this point in the main text to avoid potential confusion caused by the name.

3. Why Remove the Bias Term When Obtaining the Lower Bound: This technical setting is for convenience in the derivation of our proof. After removing the bias term in network structure and further assuming the data is distributed on the sphere, the NTK is a dot-product kernel defined on sphere and the corresponding RKHS meets the so-called Regular RKHS condition (refer to Assumption 2 and Example 2.2 of [li2024generalization]). In general, this technical setting helps us obtain the lower bound of the generalization error.

References

[billingsley2013convergence] Billingsley, P. (2013). “Convergence of probability measures”.

[hanin2021random] Hanin, B. (2021). “Random neural networks in the infinite width limit as Gaussian processes”.

[li2024generalization] Li, Y., et al. (2024). “Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay”.

(We apologize for reaching the word limit earlier, and we provide the second half of the rebuttal here.)

Summary of the Theoretical Significance of the Paper

"The bulk of the paper is really just setting...... the experiments within the main text."

Thank you for your suggestion. We will summarize the theoretical significance of the paper within the background of NTK theory.

• Background of our work: For a long time, NTK theory has played an important role in the study of network. Under NTK theory, a series of works tried to explain the remarkable generalization ability of network [lai2023generalization], [li2023statistical], [lai2023generalization2], which applied mirror initialization and derived the minimax optimality of network.
• Impact of standard initialization: However, we wonder how the actual results would be if the standard initialization are considered. Under standard initialization, our result shows that the generalization ability of network under NTK theory is actually quite poor. It is a surprising result and prompts us to think further.
• Significance of our work: On one hand, this tells us that the generalization ability of network is not only influenced by the smoothness of the goal function but also by the way of initialization. Thus, we have to carefully take the way of initialization into consideration. On the other hand, we can consider whether the inconsistency between the theory and reality is due to the overly strong assumptions of NTK theory (e.g., the width of network is sufficient large). In the future, it may be worthwhile to explore how NNK changes during training under finite width to advance the existing NTK theory.
• Experiment: In the experiment of Section 5.1, we chose a single-layer network with width $m =20n$ to ensure the width is sufficiently large. At each $n$, we conducted 10 experiments with a learning rate of 0.6, and each training was run for 10n epochs to ensure sufficient time. We will add these details to the main text. Thank you for your suggestion.

The Problem of Fig 1

"The synthetic experiments (Fig 1) only cover ..... theory could have trouble with."

Thanks for pointing this out and we appreciate your correction. Indeed, the range of our $n$ is not large enough. In kernel theory, it is common for the generalization error to decrease polynomially with respect to $n$ (e.g., Fig 1 in [li2024saturation]). In Fig 1, we aim to demonstrate a similar phenomenon. However, in fact, it indeed may encounter the problem of double-descent as you mentioned. To ensure the convergence of NTK, the width of the network $m$ needs to increase with $n$, but it will result in a high computational cost. The reasons above are why we didn't increase $n$. Thank you for correction again.

Response to Questions

1. The notation $\sum a_i \lambda_i^{s/2}e_i(x)$ is mainly because $\lbrace\lambda_i^{s/2}e_i(x)\rbrace$ forms an ONB of the interpolation space. Thank you for pointing this out. We will explain this in more detail.
2. Under mirror initialization, for $f^*\in[\mathcal{H}^{NT}]^s$ ($s \geq 1$), the generalization error of network is $n^{-\frac{s(d+1)}{s(d+1)+d}}$, as shown in [li2023statistical]. We appreciate your reminder and we will add this point to the discussion of Theorem 4.3 for the convenience of comparison by readers.
3. Thank you for suggestion on the notations in the experimental part. We estimated the smoothness of real datasets with respect to the NTK of single-layer fully connected network. We will add this point in our paper.
4. Regarding the estimation of decay rate in the log-log plot, there may be some miscommunication. As a function of $n$, e.g., in Fig 1, we denote the experimentally measured generalization error as $e_i(n)$, where $n$ is the sample size and $i$ represents the $i$-th experiment. Then $e_i(n)$ is approximately of the form $e_i(n) \propto n^{-\alpha}Z_{n,i}$, where $Z_{n,i}$ denotes a random variable with values around 1, and $\alpha$ is the decay rate to be estimated. In this case, a linear fit after a log transformation may not be a bad choice. We found that Clauset et al. studied estimating $a$ through i.i.d. samples $x_{i} \sim p(x) (\propto x^{-a})$, which is slightly different from our problem. We guess there may be some miscommunication here.
5. Thanks for your careful reading again. We apologize for our annoying typos. We have tried our best to read through the paper and will make several modifications in the new revision.

Impact of Network Architecture on Our Results

Our results indeed focus on fully connected network. Thanks for pointing this out. For other architectures, like ResNet or CNN, if we know the properties of the corresponding NTK, RFK, and initial output function, it is also reasonable to apply our framework. This requires considerable preliminary work, but in the future, we are willing to explore whether our results hold under different network settings. Again, thank you for highlighting this point.

References

[haas2023mind] Haas, M., et al. (2023). “Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension”.

[lai2023generalization] Lai, J., et al. (2023). “Generalization ability of wide neural networks on $\mathbb{R}$”.

[lai2023generalization2] Lai, J., et al. (2023). “Generalization ability of wide residual networks”.

[li2024saturation] Li, Y., Zhang, H., and Lin, Q. (2024). “On the saturation effect of kernel ridge regression”.

[li2023statistical] Li, Y., et al. (2024). “On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domains”.

Brief Introduction of Mirror Initialization

"In the introduction and experimental sections, the standard and mirror initializations are contrasted. ...... what is known about the mirror initialization."

Thank you for your suggestion. Here we provide a brief introduction of the existing theoretical results on mirror initialization.

• Under mirror initialization, [lai2023generalization], [li2023statistical], and [lai2023generalization2] studied the generalization ability of single-layer fully connected, multi-layer fully connected, and multi-layer residual network, respectively, and proved the minimax optimality of network. For example, [li2023statistical], which studied the generalization ability of multi-layer fully connected mirror-initialized networks, concluded that for $f^* \in [\mathcal{H}^{NT}]^s, (s \geq 1)$, the $L^2$ generalization error is $n^{-\frac{s(d+1)}{s(d+1)+d}}$. This differs significantly from the $n^{-\frac{3}{d+3}}$ we obtained, reflecting the theoretical differences between different initialization.

More Explanation of Our Contribution

"As someone who is fairly familiar with kernel theory of neural networks, I still found ...... I would suggest that the authors clarify this."

Before the response, we apologize for a typo. As mentioned in Theorem 4.2, the smoothness of the Gaussian process is $\frac{3}{d+1}$. Therefore, the smoothness in lines 250, 260, and 281 in the Theorem should also be $\frac{3}{d+1}$ instead of $\frac{1}{d+3}$. This typo does not affect our results.

Thanks for your reminder and we are willing to respond to your questions. Since NTK and Gaussian process are well-studied objects, we do need to clarify what the novel contribution we have done here.

The major contribution appears in Theorem 4.2 where we showed that $P(f^{GP} \in [\mathcal H^{NT}]^{t}) = 1_{t \textless \frac{3}{d+1}}$. Consequently, the generalization error of the gradient descent with standard random initialization is $n^{-\frac{3}{d+3}}$.

To the best of our knowledge, this cannot be simply concluded from classical Sobolev theory.

• Challenge of Theorem 4.2:
  • If the input is uniformly distributed on the sphere $\mathbb{S}^d$ instead of $\mathcal{X}$, both NTK and RFK are inner-product kernels and their Mercer's decomposition shares the same eigen-function (i.e., spherical harmonic polynomials). In this situation, simple calculations on the eigenvalues would show that $f^{GP} \in [\mathcal{H}^{NT}]^{\frac{3}{d+1}}$.
  • However, when the data is a general distribution supported in a bounded open set $\mathcal{X} \subset \mathbb{R}^d$, NTK and RFK will not possess the nice property anymore which makes the claim if $f^{GP} \in [\mathcal{H}^{NT}]^{\frac{3}{d+1}}$ unclear.
  • Before we clarify our solution and technical contributions, we first recollect some notations. For a sub-region $S \subset \mathbb S^d$, let $\mathcal{H}_{0}^{NT}(\mathbb{S}^d)$ be the RKHS associated with the homogeneous NTK defined on $\mathbb S^d$ and $\mathcal{H}_0^{NT}(S)=\mathcal{H}_0^{NT}(\mathbb{S}^d) |_S$ be its restriction on the sub-region $S \subset \mathbb{S}^d$. We define $\mathcal{H}_0^{RF}(\mathbb{S}^d)$ and $\mathcal{H}_0^{RF}(S)$ similarly.
  • We first show that, on a general $\mathcal{X}$, $\mathcal{H}^{RF} \cong [\mathcal{H}^{NT}]^\frac{d+3}{d+1}$ (where the $\cong$ is isomorphic as Hilbert space not RKHS).
  • Let us fix a continuous and isomorphic mapping from $\mathcal{X} \subset \mathbb{R}^d$ to a subregion $S \subset \mathbb{S}^d$. We then show the equivalence (as RKHS) $\mathcal{H}^{RF} \cong \mathcal{H}_{0}^{RF}(S), \mathcal{H}^{NT} \cong \mathcal{H}_0^{NT}(S).$ This equivalence is not as trivial as it appears.
  • We then need to show that $[\mathcal{H}_0^{RF}(S)] \cong [\mathcal{H}_0^{NT}(S)]^{\frac{d+3}{d+1}}$.
  • Notice that the Mercer's decomposition of RFK and NTK share the same eigenfunctions (i.e., the spherical harmonic polynomials), we know that $[\mathcal{H}_0^{RF}(\mathbb S^d)] \cong [\mathcal{H}_0^{NT}(\mathbb{S}^d)]^{\frac{d+3}{d+1}}$. If the restriction $\mid_S$ and the interpolation $[]^{\frac{d+3}{d+1}}$ are commutative, then we are done. Unfortunately, this commutativity is not easy to verify in general.
  • Fortunately, by a recent result [haas2023mind], we have $\mathcal{H}_0^{RF}(\mathbb{S}^d) \cong W^{\frac{d+3}{2},2}(\mathbb{S}^d)$ and $\mathcal{H}_0^{NT}(\mathbb{S}^d) \cong W^{\frac{d+1}{2},2}(\mathbb{S}^d)$ where $W^{s,2}$ denotes the usual fractional Sobolev space. Since Sobolev space is a more tractable object, we then carefully verify that $\mathcal{H}_0^{RF}(S) = [\mathcal{H}_0^{NT}(S)]^{\frac{d+3}{d+1}}$ and finish the proof. We would like to emphasize that there are several different definitions for the fractional Sobolev spaces and there are no similar results explicitly stated in the literature.
  • By Lemma H.5, we have $[\mathcal{H}^{RF}]^{\frac{3}{d+3}} \cong [[\mathcal{H}^{NT}]^\frac{d+3}{d+1}]^{\frac{3}{d+3}} (\cong [\mathcal{H}^{NT}]^{\frac{3}{d+1}})$.
  • If we denote $\mathcal{H}^{RF} = \left\lbrace \sum_{i \in \mathbb{N}} a_i \lambda_i^{\frac{1}{2}} e_i | \sum_{i \in \mathbb{N}} a_i^2 < \infty \right\rbrace$, then the K-L expansion gives us that $f^{GP} = \sum_{i \in \mathbb{N}} Z_i \lambda_i^{\frac{1}{2}} e_i$ where $\{Z_i\}$ are i.i.d. standard Gaussian variables. We can verify that $\mathbf{P}(f^{GP} \in [\mathcal{H}^{RF}]^{t}) = 1$ for $t < \frac{3}{d+3}$ and that $\mathbf{P}(f^{GP} \in [\mathcal{H}^{RF}]^{t}) = 0$ for $t \geq \frac{3}{d+3}$. i.e., we have $\mathbf{P}(f^{GP} \in [\mathcal{H}^{NT}]^{t}) = 1$ for $t < \frac{3}{d+1}$ and that $\mathbf{P}(f^{GP} \in [\mathcal{H}^{NT}]^{t}) = 0$ for $t \geq \frac{3}{d+1}$.

(We apologize for the inconvenience, due to the 6000-word limit, the second half is provided in the comment.)

Thanks for your responses. I think it would be good if you used this time to clarify things in the final paper. I suggest you strengthen this context in the intro when you discuss related work and how your results fit in. I hope you plan to do this. I'll keep my score the same.