Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate

We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.

Regarding the weakness, we emphasize that the two-layer neural network studied in this paper still achieves the sharp risk bound of $O(\epsilon^2)$, supporting the claim in[ Bietti & Bach, 2021] that shallow over-parameterized neural networks with ReLU activations exhibit the same approximation properties as its deeper counterpart.

Regarding the suggested reference and the wording suggestion, we will discuss [Yuan et al. 2007], and use “early stopping” consistently in the final version of this paper.

Below is our response to the questions.

(1) "What does "preconditioned" in Section 4 heading "Preconditioned Gradient Descent" refer to?"

The "preconditioned" in Section 4 heading is a typo, and we have fixed it which will be reflected in the final version of this paper.

(2) "It seems that in the literature the EDR remains to be $d/(d-1)$ for varous data distributions. Can you provide concrete examples of other EDRs of the NTK under some distribution?"

Theorem 10 of [Li et al., 2024] suggests that the polynomial eigenvalue decay rate (EDR) of $\lambda_j \asymp j^{-(d+1)/d}$ is achieved by learning the bias in a neural network, which is different from the EDR of $\lambda_j \asymp j^{-d/(d-1)}$ discussed in this paper. In this case, the main results (Theorem 5.1 and Corollary 5.2) can be applied to obtain the minimax optimal nonparametric regression risk of the order $O(n^{-(d+1)/(2d+1)})$.

(3) "Regarding the simulation, what is the performance of the neural network under the theoretical stopping time $\hat T$?"

In the following table we report the minimum test loss and the test loss at the theoretical stopping time $\Theta(\hat T) = 9 n^{d/(2d-1)}$ of the neural network trained in our simulation study (in Section D of the appendix) with the training data size $n$ ranges within $[100,1000]$ with an increment of $100$. It can be observed that the test loss at the theoretical stopping time $\Theta(\hat T)$ is only marginally higher than the minimum test loss for each training data size $n$, justifying the good generalization of the model at the stopping time $\Theta(\hat T)$.

References

[Li et al., 2024] Li, Y., Yu, Z., Chen, G., and Lin, Q. On the eigenvalue decay rates of a class of neural-network related kernel functions defined on general domains. JMLR 2024.

We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.

(1) “Can the results be extended to deeper neural networks? If so, what additional challenges arise in the analysis?”

Yes, this work can be extended to deeper neural network. The key roadmap is presented as follows. (1) We can establish the uniform convergence to the NTK of the deeper neural network using the existing uniform convergence results in [Li et al., 2024] and still apply the proof strategy in Theorem C.8 of this paper to decompose the neural network function $f$ by $f = h+e$, where $h \in \mathcal H_K$ is the “kernel part” of $f$ and $e$ is the error function. (2) Lemma C.9 of this paper then can still be used to bound the local Rademacher complexity of all such neural network function, and we can use Theorem C.10 of this paper together with the convergence results about the training loss of the deeper neural network widely studied in the literature such as [Li et al., 2024, Allen-Zhu et al. 2019] to prove the sharp nonparametric risk bound of $O(\epsilon_n^2)$, where $\epsilon_n$ is the critical population rate of the NTK of the deeper neural network.

We would like to emphasize that the two-layer neural network studied in this paper still achieves the sharp risk bound of $O(\epsilon_n^2)$, supporting the claim in [ Bietti & Bach, 2021] that shallow over-parameterized neural networks with ReLU activations exhibit the same approximation properties as its deeper counterpart.

(2) "The assumption that $f^* \in \mathcal H_K$ may not hold in practice. How robust are the results if this assumption is relaxed? Are there any results for target functions outside the RKHS?"

We would like to point out that our generalization results can be extended to the relaxed case that the target function $f^* \in \mathcal H_K(\mu_n)$ with $\mu_n$ diverges, that is, $\mu_n \to \infty$ as $n \to \infty$. In this relaxed case, $f^*$ is not in the RHKS of constant norm, that is, $f^* \notin \mathcal H_K(\mu_0)$ with $\mu_0$ being a positive constant considered in this paper. We remark that in this relaxed case, the RKHS norm of $f^*$ goes to $\infty$ as $n \to \infty$, which is close to the setup considered in [Bordelon et al., 2025] where the RKHS of $f^*$ goes to $\infty$ (with $\beta < 1$ in their work). We note that Theorem C.10 still holds with $B_h = \mu_n+1+\sqrt 2$ and $B_0 = (B_h+\mu_n)/{\sqrt 2} + 1$, and Theorem C.10 with such new $B_0$ can be used to prove the main result, a new version of Theorem 5,1, for this relaxed case. The new version of Theorem 5.1 would have a nonparametric regression risk bound, $Q(B_0) \epsilon_n^2$, which has a multiplicative factor $Q(B_0)$ depending on $B_0$ before $\epsilon_n^2$, and this risk bound still converges to $0$ if $Q(B_0) \epsilon_n^2 \to 0$ as $n \to \infty$. For example, when $P$ is the spherical uniform distribution, we have $\epsilon_n^2 \asymp n^{-d/(2d-1)}$, and such risk bound converges to $0$ if $Q(B_0) n^{-d/(2d-1)} \to 0$.

(3) "The paper suggests that a constant learning rate can be used. Are there any conditions under which a varying learning rate might be beneficial, or is a constant rate always sufficient?"

Varying learning rate could be beneficial compared to constant learning rate in the nonconvex optimization literature such as the optimization of DNNs, which will be discussed in the final version of this paper. In this paper, we state that the constant learning rate $\eta = \Theta(1)$ leads to an empirically faster convergence speed for training the neural network than the literature where the infinitesimal learning rate $\eta \to 0$ is used.

Furthermore, we will fix the typos, and $r’$ should be $r$ in line 409. We will also discuss the suggested works in “Essential References Not Discussed” in the final version of this paper.

References

[Li et al., 2024] Li, Y., Yu, Z., Chen, G., and Lin, Q. On the eigenvalue decay rates of a class of neural-network related kernel functions defined on general domains. JMLR 2024.

[Allen-Zhu et al., 2019] Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over-parameterization. ICML 2019.

[Bietti & Bach, 2021] Bietti, A. and Bach, F. R. Deep equals shallow for ReLU networks in kernel regimes. ICLR 2021.

[Bordelon et al., 2025] B. Bordelon, A. Atanasov, C.Pehlevan. How Feature Learning Can Improve Neural Scaling Laws. ICLR 2025.

We appreciate the review and the suggestions in this review. The raised issues are addressed below.

(1) "Can the authors provide any other examples as extensions of Theorem 5.1? For example, if the target function belongs to an RKHS ball induced by the Gaussian kernel, what should be the convergence rate of the expected risk?"

It is known that the eigenvalue decay rate (EDR) of the Gaussian kernel on the unit sphere in $\mathbb R^d$ is $\lambda_j \asymp j^{-C j^{2/d}}$ ( the super-geometric decay in [Scetbon et al., 2021]) where $C$ is a positive constant depending on $d$, and the kernel regression with the Gaussian kernel has a regression risk of the order $O(\log n/n)$ by Theorem 3.1 of [Scetbon et al., 2021]. Furthermore, Theorem 10 of [Li et al., 2024] suggests that the polynomial eigenvalue decay rate (EDR) of $\lambda_j \asymp j^{-(d+1)/d}$ is achieved by learning the bias in a neural network, which is different from the EDR of $\lambda_j \asymp j^{-d/(d-1)}$ discussed in this paper. In this case, the main results (Theorem 5.1 and Corollary 5.2) can be applied to obtain the minimax optimal nonparametric regression risk of $O(n^{-(d+1)/(2d+1)})$.

(2) "If one does not know which RKHS the target function $f^*$ lies in (or more specifically, if one has no information on the behaviour of eigenvalues $\lambda_i$), how should one estimate $\hat R_K$"?

We respectfully point out that $\hat R_K$ in Eq. (7) is defined in terms of the (empirical) eigenvalues $\hat \lambda_i$ ($i \in [n]$) of the kernel gram matrix $\mathbf K \in \mathbb R^{n \times n}$ defined on the training data. In the case that one does not know the behavior of the population eigenvalues $\lambda_i$ for $i \ge 1$, one can still estimate the stopping time $\hat T$ by the fixed point of $\hat R_k$ with the eigenvalues $(\hat \lambda_i )_{i=1}^n$ of the gram matrix $\mathbf K$. To do so, we can estimate the fixed point by approximating the numerical solution to the equation $\hat R_K(\hat \epsilon) = \hat \epsilon^2/\sigma_0$.

References

[Scetbon et al., 2021] M. Scetbon, Z. Harchaoui. A Spectral Analysis of Dot-product Kernels. AISTATS 2021.

We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.

(1)"... It seems like the authors here are trading off one somewhat restrictive assumption (uniform spherical data) for another (fix the second weight layer to random +1/-1 weights)."

We respectfully point out that the training setup (fixing the weights of the second layer to random +1/-1 weights) is not an assumption, and such training setup reduces the training cost by not training the second-layer while obtaining a neural network with sharp risk bound. Such training setup has also been used in the prior analysis of the generalization of two-layer neural network such as [Du et al., 2019].

(2)"The paper Ko & Huo (2024)…"

In this paper, we focus on the generalization analysis of neural networks with algorithmic guarantees, that is, the generalization bounds for neural networks trained by gradient descent or its variants. Such analysis is of particular practical importance since the neural networks used in practice are mostly trained by GD or its variants. Although the work mentioned in this review, Ko & Huo (2024), provides certain risk rates, as mentioned in lines 181-182, it does not provide algorithmic guarantees and the neural networks achieving such rates are not trained by GD or its variants.

Novelty of This Paper

We would like to emphasize the novelty of this paper, which gives the first sharp nonparametric regression risk bound without distributional assumptions on the unit sphere. Our analysis introduces new proof techniques including the new uniform convergence results for NTK and the novel local Rademacher complexity based analysis (acknowledged by Reviewer EyzF Reviewer JB4U) which lead to the distribution-free generalization bounds with spherical covariate. Our results also give better lower bound for the network width compared to the existing literature. Furthermore, in our response to Reviewer JB4U (points (1) and (2)), we provide detailed discussions about (1) how to extend our work from a two-layer neural network to a deeper neural network, and (2) how to relax the assumption that the target function $f^*$ is in a ball RKHS of constant radius. The current novelty and contributions together with such extension and relaxation would benefit the theoretical deep learning literature with new insights and proof strategies.

References

[Du et al., 2019] Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over-parameterized neural networks. ICLR 2019.