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

Yingzhen YangICML 2025 · OpenReview

Generalization analysis—understanding why a model performs well on unseen data—is a cornerstone of deep learning theory. For years, researchers have sought to prove that neural networks can match the optimal convergence rates of classical statistical methods. While significant progress has been made, most theoretical guarantees come with a catch: they only hold if the training data is distributed in a mathematically "nice" way, such as being perfectly uniform on a sphere.

A new paper presented at ICML 2025 changes this landscape. It provides a "sharp" generalization bound for over-parameterized neural networks that is distribution-free, meaning it holds regardless of how the data is spread out, provided it sits on a unit sphere.

The Challenge of Distributional Assumptions

In nonparametric regression, the goal is to learn a target function without assuming it follows a specific parametric shape (like a straight line). Statistical theory dictates a "minimax optimal" rate at which a model's error should decrease as more data is added.

While it is known that very wide neural networks operating in the Neural Tangent Kernel (NTK) regime can achieve these optimal rates, existing proofs usually rely on the data being uniformly distributed. In practice, data is rarely uniform; it clusters, exhibits gaps, and follows complex patterns. This paper bridges a major gap between theory and practice by proving that the optimal generalization rate holds for any continuous distribution on the sphere.

Methodology: NTK and Local Rademacher Complexity

The authors analyze a two-layer neural network with ReLU activations, trained using standard Gradient Descent (GD) with early stopping. Unlike previous work that required "gradient flow" (infinitesimal steps), this analysis works with a practical, constant learning rate. Their theoretical framework relies on two main technical pillars:

  1. Uniform Convergence to the NTK: The authors prove that during the entire training process, the neural network stays close enough to its "tangent kernel" approximation. This allows them to decompose the network's function into a "clean" part—residing in a specific Reproducing Kernel Hilbert Space (RKHS)—and a small error term with a tightly bounded $L^{\infty}$-norm.
  2. Local Rademacher Complexity: Instead of measuring the complexity of every possible function the network could represent, they employ "local" complexity measures. This focuses strictly on the functions the network is likely to reach during training, yielding much tighter and more accurate bounds.

Key Theoretical Contributions

The most significant breakthrough in this work is its distribution independence. The specific distribution of data on the sphere does not alter the fundamental convergence rate. Whether the data is heavily clustered or widely dispersed, the network learns at the same optimal rate.

Table 1: Comparison of risk rates and assumptions between this work and existing literature.

Key results include:

  • Sharp Risk Rate: The network achieves a nonparametric regression risk rate of $\mathcal{O}(\epsilon_n^2)$, matching the performance of classical kernel regression trained by GD with early stopping.
  • Minimax Optimality: In cases where the eigenvalues of the associated NTK exhibit polynomial decay (e.g., $\lambda_j \asymp j^{-\frac{d}{d-1}}$), the bound immediately simplifies to the minimax optimal rate of $\mathcal{O}(n^{-\frac{d}{2d-1}})$.
  • Practical Width Bounds: Previous theories often required astronomically large network widths. This paper provides a much smaller, more realistic lower bound for the number of neurons needed to guarantee optimal generalization. Crucially, this width depends only on the dimension $d$ and the error rate $\epsilon_n$, completely avoiding dependence on the minimum eigenvalue of the empirical NTK matrix.
  • Early Stopping Characterization: The paper formally characterizes the early stopping time ($\hat{T} \asymp \epsilon_n^{-2}$), proving it is essential for preventing the model from overfitting to noise.

Empirical Validation

While primarily a theoretical contribution, the authors include a simulation study to validate their findings. They sampled $n$ points (ranging from 100 to 1000) from a 50-dimensional unit sphere ($\mathbb{S}^{49}$) to learn a simple linear target function. Training the network on an NVIDIA A100 GPU and evaluating it on 1000 independently sampled test points, the simulations confirmed that the theoretically predicted stopping time is empirically proportional to the time that actually minimizes test loss in practice.

Limitations and Future Directions

While a major step forward, the paper acknowledges a few boundaries:

  • Spherical Constraint: The data must lie on a unit sphere. While common in manifold learning, real-world data often resides on more complex bounded domains.
  • Two-Layer Limit: The proof is specific to two-layer networks. Extending this distribution-free analysis to deep architectures remains an open challenge, though the authors argue shallow networks can match the approximation power of deep ones in this specific regime.
  • Fixed Dimension: The analysis assumes the data dimension $d$ is fixed. Future work could explore "high-dimensional" regimes where the number of features grows alongside the number of samples.

Summary updated

Abstract

Sharp generalization bound for neural networks trained by gradient descent (GD) is of central interest in statistical learning theory and deep learning. In this paper, we consider nonparametric regression by an over-parameterized two-layer NN trained by GD. We show that, if the neural network is trained by GD with early stopping, then the trained network renders a sharp rate of the nonparametric regression risk of $\mathcal O(\epsilon_n^2)$, which is the same rate as that for the classical kernel regression trained by GD with early stopping, where $\epsilon_n$ is the critical population rate of the Neural Tangent Kernel (NTK) associated with the network and $n$ is the size of the training data. It is remarked that our result does not require distributional assumptions on the covariate as long as the covariate lies on the unit sphere, in a strong contrast with many existing results which rely on specific distributions such as the spherical uniform data distribution or distributions satisfying certain restrictive conditions. As a special case of our general result, when the eigenvalues of the associated NTK decay at a rate of $\lambda_j \asymp j^{-\frac{d}{d-1}}$ for $j \ge 1$ which happens under certain distributional assumption such as the training features follow the spherical uniform distribution, we immediately obtain the minimax optimal rate of $\mathcal O(n^{-\frac{d}{2d-1}})$, which is the major results of several existing works in this direction. The neural network width in our general result is lower bounded by a function of only $d$ and $\epsilon_n$, and such width does not depend on the minimum eigenvalue of the empirical NTK matrix whose lower bound usually requires additional assumptions on the training data. Our results are built upon two significant technical results which are of independent interest. First, uniform convergence to the NTK is established during the training process by GD, so that we can have a nice decomposition of the neural network function at any step of the GD into a function in the Reproducing Kernel Hilbert Space associated with the NTK and an error function with a small $L^{\infty}$-norm. Second, local Rademacher complexity is employed to tightly bound the Rademacher complexity of the function class comprising all the possible neural network functions obtained by GD. Our result formally fills the gap between training a classical kernel regression model and training an over-parameterized but finite-width neural network by GD for nonparametric regression without distributional assumptions about the spherical covariate.
BibTeX
@inproceedings{yang2025sharp,
  author = {Yingzhen Yang},
  title = {{Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=fPOkujQBVb},
}
Figure