Sharp Generalization for Nonparametric Regression in Interpolation Space by Shallow Over-Parameterized Neural Networks with Channel Attention

Yingzhen Yang; Ping Li

stat.MLNov 1, 2026

Sharp Generalization for Nonparametric Regression in Interpolation Space by Shallow Over-Parameterized Neural Networks with Channel Attention

Authors: Yingzhen Yang, Ping Li

Organizations: Arizona State University, 699 S Mill RD, Tempe, AZ 85281, USA · VecML Inc., Bellevue, WA 98004, USA

Abstract

We study nonparametric regression using an over-parameterized two-layer ReLU neural network with fixed covariance-based channel attention, trained by gradient descent with both layers updated simultaneously. The spherical covariates follow an arbitrary fixed non-atomic distribution, and the target function lies in an interpolation space with spectral bias widely studied in the statistical learning literature. We prove that early-stopped training achieves regression risk $\cO(\eps_n^2)$ , where $\eps_n$ is the critical population rate of the attention kernel $\Kattn$ . Its positive eigenvalues are $λ_j^{s'}$ , where $λ_j$ are those of the ReLU feature covariance kernel $K$ and $s'=2s+3$ for $s\ge1$ . Under polynomial eigenvalue decay $λ_j\asymp j^{-2α}$ with $α>1/2$ , the regression risk bound $\cO(\eps_n^2)$ specializes to the minimax optimal rate $\cO(n^{-2αs'/(2αs'+1)})$ . Our analysis is based on two new technical results on the optimization and generalization of the attention network. First, the neural network function after every gradient descent iteration admits a decomposition into a function with bounded Reproducing Kernel Hilbert Space (RKHS) norm and a uniformly small residual. Second, local Rademacher complexity converts this decomposition into a regression risk bound. Kernel gradient descent on the same ball attains the same rate, while our theorem gives explicit sufficient width and auxiliary-sample conditions for simultaneous network training. Our analysis is further extended to covariates supported on $\RR^d$ through a novel normalization method. Under a sub-Gaussian covariate distribution, the attention network achieves a nearly optimal regression risk $\cO((\log n)n^{-s'(d+3)/(s'(d+3)+d)})$ without a density assumption.

Figures & tables

Existing works and our results	Distribution and target assumptions	Positive spectrum	Regression risk
Spherical input space ${\cal X}\subseteq\mathbb{S}^{d-1}$
[ 13 , Theorem 5.2] and [ 14 , Theorem 3.11]	Uniform distribution on $\mathbb{S}^{d-1}$ , $f^{*}\in{\cal H}_{\tilde{K}}(\mu_{0})$	$\tilde{K}$ : $j^{-d/(d-1)}$	Order $n^{-d/(2d-1)}$ in probability
[ 16 , Theorem 5.1]	Arbitrary continuous distribution on the sphere, $f^{*}\in{\cal H}_{\tilde{K}}(\mu_{0})$	No EDR assumption	${\cal O}(\varepsilon_{\tilde{K},n}^{2})$
[ 16 , Corollary 5.2]	Spherical covariates, $f^{*}\in{\cal H}_{\tilde{K}}(\mu_{0})$ , polynomial EDR with $\alpha>1/2$	$\tilde{K}$ : $j^{-2\alpha}$	${\cal O}(n^{-\frac{2\alpha}{2\alpha+1}})$
Theorem III.1	Arbitrary non-atomic spherical $P$ on ${\cal X}$ , $f^{*}\in{\cal H}_{{K}^{\mathop{\mathrm{}}{(att)}}}(\mu_{0})$	No EDR assumption	${\cal O}(\varepsilon_{n}^{2})$
Theorem III.2	Non-atomic spherical $P$ on ${\cal X}$ , $f^{*}\in{\cal H}_{{K}^{\mathop{\mathrm{}}{(att)}}}(\mu_{0})$ , polynomial EDR with $\alpha>1/2$	$K$ : $j^{-2\alpha}$ ${K}^{\mathop{\mathrm{}}{(att)}}$ : $j^{-2\alpha s^{\prime}}$	${\cal O}(n^{-\frac{2\alpha s^{\prime}}{2\alpha s^{\prime}+1}})$

TABLE I : Comparison with existing regression risk bounds. The positive spectrum and target class belong to the kernel identified in each row. All target classes have a fixed norm bound.

	PGD [ 29 ]	Present paper
Width $m$	$\gtrsim T^{25/2}d^{5/2}$	$\gtrsim\max\left\{T^{3}d\log m,n^{1/(2d)}\right\}$
Auxiliary size $N$	$\gtrsim T^{4}\log(n/\delta)$	$\gtrsim T^{3}\log(2/\delta)$

TABLE II: Sufficient size conditions with comparison to [ 29 ] . The symbol

T

denotes the stopping time in the respective analysis.

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 319 papers

Jul 16, 2024

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

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.

Yingzhen Yang, Ping Li

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

Neural Network Generalization Nonparametric Regression Overparameterized Neural Network Gradient Descent Neural Tangent Kernel

Ask PDF

Mar 22, 2026

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

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.

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

Ask PDF

Mar 30, 2026

Minimum Norm Interpolation via the Local Theory of Banach Spaces: The Role of $2$ -Uniform Convexity

The minimum-norm interpolator (MNI) framework has recently attracted considerable attention as a tool for understanding generalization in overparameterized models, such as neural networks. In this work, we study the MNI under a

2

-uniform convexity assumption, which is weaker than requiring the norm to be induced by an inner product; in this setting, the MNI typically does not admit a closed-form solution. At a high level, we show that this condition yields an upper bound on the MNI bias in both linear and nonlinear models. We further show that this bound is sharp for overparameterized linear regression when the norm's unit ball is in isotropic or John's position and the covariates are i.i.d.\ sub-Gaussian, for example, when each covariate vector has i.i.d. Rademacher entries. Finally, under the same assumption on the covariates, we prove sharp generalization bounds for the

\ell_p

-MNI when

p \in \bigl(1 + C/\log d, 2\bigr]

. To the best of our knowledge, this is the first work to establish sharp bounds for non-Gaussian covariates in linear models when the norm is not induced by an inner product. This work is deeply inspired by classical work on

K

-convexity and recent work on the geometry of

2

-uniformly convex and isotropic convex bodies.

Gil Kur, Pierre Bizeul

Institute for Machine Learning, ETH Zürich · Department of Mathematics, Weizmann Institute of Science

Generalization Bounds Linear Regression

Ask PDF

Abstract

Neural Network Generalization

Explore similar work

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

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

Minimum Norm Interpolation via the Local Theory of Banach Spaces: The Role of 222-Uniform Convexity

Minimum Norm Interpolation via the Local Theory of Banach Spaces: The Role of $2$ -Uniform Convexity