Sharp Generalization for Nonparametric Regression in Interpolation Space by Over-Parameterized Neural Networks Trained with Preconditioned Gradient Descent and Early Stopping

Yingzhen Yang; Ping Li

stat.MLJul 16, 2024

Sharp Generalization for Nonparametric Regression in Interpolation Space by Over-Parameterized Neural Networks Trained with Preconditioned Gradient Descent and Early Stopping

Authors: Yingzhen Yang, Ping Li

Organizations: School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA · VecML Inc., Bellevue, WA 98004, USA

Abstract

We study nonparametric regression using an over-parameterized two-layer neural network trained with algorithmic guarantees in this paper. We consider the setting where the training features are drawn uniformly from the unit sphere in $\RR^d$ , and the target function lies in an interpolation space commonly studied in statistical learning theory. We demonstrate that training the neural network with a novel Preconditioned Gradient Descent (PGD) algorithm, equipped with early stopping, achieves a sharp regression rate of $\cO(n^{-\frac{2αs'}{2αs'+1}})$ , where $α$ parametrizes the polynomial eigenvalue decay of the regular Neural Tangent Kernel (NTK), $λ_j\asymp j^{-2α}$ , and $2α=d/(d-1)$ under the spherical uniform design considered here. The target function is assumed to belong to the interpolation space $\bth{\cH_K}^{s'}$ with $s'\ge3$ . This rate is even sharper than the currently known nearly-optimal rate of $\cO(n^{-\frac{2αs'}{2αs'+1}})\log^2(1/δ)$ ~\citep{Li2024-edr-general-domain}, where $n$ is the size of the training data and $δ\in (0,1)$ is a small probability. Our analysis is based on two key technical contributions. First, we present a principled decomposition of the network output at each PGD step into a function in the reproducing kernel Hilbert space (RKHS) of a newly induced integral kernel, and a residual function with small $L^{\infty}$ -norm. Second, leveraging this decomposition, we apply local Rademacher complexity theory to tightly control the complexity of the function class comprising all the neural network functions obtained in the PGD iterates. Our results show how PGD changes the effective kernel in the reference training dynamics, inducing an integral kernel with lower complexity than the regular NTK arising from vanilla GD.

Figures & tables

Existing Works and Our Result	Distributional Assumptions	Target-Function Assumption	Eigenvalue Decay Rate (EDR)	Rate of Nonparametric Regression Risk
( Hu et al., 2021 , Theorem 5.2) , ( Suh et al., 2022 , Theorem 3.11)	$P$ is ${\mathop{\mathrm{}}{Unif}}\left({\cal X}\right)$	$f^{*}\in{\cal H}_{\tilde{K}}(\mu_{0})$	$\lambda_{j}\asymp j^{-d/(d-1)}$	${\cal O}(n^{-d/(2d-1)})$
( Li et al., 2024 , Proposition 13)	$P$ is sub-Gaussian	$f^{*}\in\left[{\cal H}_{K}\right]^{s^{\prime}}(\mu_{0})\cap L^{\infty}$ for $s^{\prime}>1/(d+1)$	$\lambda_{j}\asymp j^{-d/(d-1)}$	${\cal O}(n^{-ds^{\prime}/(ds^{\prime}+d-1)})\log^{2}(n)$
( Yang, 2025 , Corollary 5.2)	$P$ supported on ${\cal X}$ admits the polynomial EDR $\lambda_{j}\asymp j^{-d/(d-1)}$	$f^{*}\in{\cal H}_{\tilde{K}}(\mu_{0})$	$\lambda_{j}\asymp j^{-d/(d-1)}$	${\cal O}(n^{-d/(2d-1)})$
Our Result (Theorem 5.1 )	$P$ has full support on ${\cal X}$ and admits the polynomial EDR $\lambda_{j}\asymp j^{-d/(d-1)}$	$f^{*}\in{\cal H}_{{K}^{\mathop{\mathrm{}}{(int)}}}(\mu_{0})=\left[{\cal H}_{K}\right]^{s^{\prime}}(\mu_{0})$ for $s^{\prime}=s+2\geq 3$	${\lambda}^{\mathop{\mathrm{}}{(int)}}_{j}\asymp j^{-d(s+2)/(d-1)}$	${\cal O}(n^{-2\alpha s^{\prime}/(2\alpha s^{\prime}+1)})={\cal O}(n^{-ds^{\prime}/(ds^{\prime}+d-1)})$
Our Result (Corollary 5.4 )	$p(\mathbf{x})\lesssim(1+{\left\\|\mathbf{x}\right\\|}_{2}^{2})^{-(d+1)/2}$ for every $\mathbf{x}\in\mathbb{R}^{d}$	$f^{*}\in{\cal H}_{{K}^{\mathop{\mathrm{}}{(int)}}}(\mu_{0})=\left[{\cal H}_{K}\right]^{s^{\prime}}(\mu_{0})$ for $s^{\prime}=s+2\geq 3$	${\lambda}^{\mathop{\mathrm{}}{(int)}}_{j}\asymp j^{-d(s+2)/(d-1)}$	${\cal O}(n^{-2\alpha s^{\prime}/(2\alpha s^{\prime}+1)})={\cal O}(n^{-ds^{\prime}/(ds^{\prime}+d-1)})$

Table 1: Comparisons with existing results on risk rates and assumptions for nonparametric regression by training over-parameterized neural networks with algorithmic guarantees. The target-function assumptions are stated separately because the rates are class-dependent. The responses

\left\{y_{i}\right\}_{i=1}^{n}

are corrupted by i.i.d. Gaussian or sub-Gaussian noise. Here

P

is the distribution of the training features and, for the RKHS-based results,

\tilde{K}

is the kernel induced by the neural architecture and optimization method in the corresponding work. It is the regular NTK for all such works except ours, for which

\tilde{K}={K}^{\mathop{\mathrm{}}{(int)}}

. We use

s^{\prime}=s+2

with

s\geq 1

and

\alpha=d/(2(d-1))

. The notation for the target class in Li et al. (2024, Proposition 13) is adapted to ours. Its displayed rate is expressed under matching source and spectral parameters. The original result uses a different, biased NTK with EDR

\lambda_{j}\asymp j^{-(d+1)/d}

. The row substitutes our EDR

\lambda_{j}\asymp j^{-d/(d-1)}

for this exponent comparison and does not assert that the original theorem applies unchanged to our architecture. The rates of that result and ours hold with probability at least

1-\Theta(1/n)

Figure 1: Left: illustration of the test losses by GD and PGD for varying

n

[100,1000]

with a step size of

100

for a linear target function. The shaded area in each plot indicates the standard deviation across

10

random initializations of the neural network. Right: illustration of the ratio of early stopping time.

Figure 2: Illustration of the test losses by PGD for a linear target function, which are averaged over

10

random initializations of the neural network.

Figure 3: Left: illustration of the test losses by GD and PGD for varying $n$ in $[100,1000]$ with a step size of $100$ for a quadratic target function. The shaded area in each plot indicates the standard deviation across $10$ random initializations of the neural network. Right: illustration of the ratio of early stopping time.

Figure 4: Illustration of the test losses by PGD for a quadratic target function, which are averaged over

10

random initializations of the neural network.

\displaystyle\left[{\textup{vec}\left(\mathbf{W}_{\mathbf{S}}(t+1)\right)}-{\textup{vec}\left(\mathbf{W}_{\mathbf{S}}(t)\right)}\right]_{[(b-1)Sd+1:bSd]}=-\frac{\eta}{n}\mathbf{M}_{[(b-1)Sd+1:bSd]}\mathbf{Z}_{\mathbf{S}}(t)(\widehat{}\mathbf{y}(t)-\mathbf{y})

(40)

Algorithm 3 Memory-Efficient PGD

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Roadmap of Major Results Leading to Theorem 5.1 .

Neural Network Generalization

Neural network generalization studies why trained models perform well on unseen data and how architecture, data, and training shape that ability.

See all 311 papers

Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate
Mar 22, 2026Yingzhen Yang, Ping LiLow-Degree Polynomial Method Neural Network Generalization
School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA · VecML Inc., Bellevue, WA 98004, USA
Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit
May 8, 2026Konstantin Riedl, Konstantinos Spiliopoulos, Justin SirignanoOverparameterized Neural Network Neural Network Optimization
Mathematical Institute University of Oxford · Department of Mathematics & Statistics Boston University
Grokking through the Lens of Minimum-Norm Interpolation
Sep 29, 2026Gil Kur, Ileana Rugina, Clémentine Carla Juliette Dominé +1Statistical Learning Theory Implicit Regularization
ETH Zürich · Institute of Science and Technology Austria · Harvard University

Mar 22, 2026J/K move · Enter open · S save

Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate

Yingzhen Yang, Ping Li

School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA · VecML Inc., Bellevue, WA 98004, USA

Low-Degree Polynomial Method Neural Network Generalization Nonparametric Regression Shallow Neural Networks Gradient Projection

Open paper AskPDF arXiv

We study the problem of learning a low-degree spherical polynomial of degree

k_0 = Θ(1) \ge 1

defined on the unit sphere in

\RR^d

by training an over-parameterized two-layer neural network with augmented feature in this paper. Our main result is the significantly improved sample complexity for learning such low-degree polynomials. We show that, for any regression risk

\eps \in (0, Θ(d^{-k_0})]

, an over-parameterized two-layer neural network trained by a novel Gradient Descent with Projection (GDP) requires a sample complexity of

n \asymp Θ( \log(4/δ) \cdot d^{k_0}/\eps)

with probability

1-δ

for

δ\in (0,1)

, in contrast with the representative sample complexity

Θ(d^{k_0} \max\set{\eps^{-2},\log d})

. Moreover, such sample complexity is nearly unimprovable since the trained network renders a nearly optimal rate of the nonparametric regression risk of the order

\log({4}/δ) \cdot Θ(d^{k_0}/{n})

with probability at least

1-δ

. On the other hand, the minimax optimal rate for the regression risk with a kernel of rank

Θ(d^{k_0})

Θ(d^{k_0}/{n})

, so that the rate of the nonparametric regression risk of the network trained by GDP is nearly minimax optimal. In the case that the ground truth degree

k_0

is unknown, we present a novel and provable adaptive degree selection algorithm which identifies the true degree and achieves the same nearly optimal regression rate. To the best of our knowledge, this is the first time that a nearly optimal risk bound is obtained by training an over-parameterized neural network with a popular activation function (ReLU) and algorithmic guarantee for learning low-degree spherical polynomials. Due to the feature learning capability of GDP, our results are beyond the regular Neural Tangent Kernel (NTK) limit.

Abstract

Neural Network Generalization

Explore similar work

Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate

Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit

Grokking through the Lens of Minimum-Norm Interpolation