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

Yingzhen Yang; Ping Li

stat.MLMar 22, 2026

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

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 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})$ is $Θ(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.

Figures & tables

Existing Works and Our Result	Finite-Width NN is Trained	Sharpness of the Regression Risk
( Ghorbani et al., 2021 , Theorem 4)	No	Only matching the lower bound for pointwise kernel learning, not minimax optimal
( Bai and Lee, 2020 , Theorem 7)	Yes	Not minimax optimal
( Nichani et al., 2022 , Theorem 1)	Yes	$\Theta(\sqrt{d^{k_{0}}/n})$ , not minimax optimal
( Damian et al., 2022 , Theorem 1)	Yes	$L^{1}$ -norm regression risk $\tilde{\Theta}(\sqrt{dr^{k_{0}}/n}+\sqrt{r^{p}/m})$ , not minimax optimal
Our Result (Theorem 3.1 )	Yes	Nearly minimax optimal, $\log{\frac{6}{\delta}}\cdot\Theta\left(\frac{d^{k_{0}}}{n}\right)$

Table 1: Comparison between our result and the existing works on learning low-degree polynomials on the spheres of

\mathbb{R}^{d}

by training over-parameterized neural networks with or without algorithmic guarantees. Almost all the results here are under a common and popular setup that

f^{*}\in{\cal H}_{\tilde{K}}

where

\tilde{K}

is the NTK of a specific neural network studied in each work, and the responses

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

are corrupted by i.i.d. Gaussian or sub-Gaussian noise with zero mean, with Nichani et al. (2022) being the only exception where the responses are noise-free. It is remarked that the sample complexity can be straightforwardly obtained from the regression risk. The regression risk of Damian et al. (2022, Theorem 1) is for the risk less than

1/\sqrt{\log d}

, with the meaning of

r

explained in Section 3.1 , and

\tilde{\Theta}

hides a logarithmic factor of

\log(mnd)

Low-Degree Polynomial Method

See all 15 papers

Oct 4, 2026

Beyond Overparameterization: Provable Learning of Input-Convex Multi-Layer Polynomial Networks with Active Queries

The theoretical understanding of multi-layer neural networks is largely confined to overparameterized settings, which obscure parameter identifiability and incur high sample complexity. Neural tangent kernel (NTK) provides a general theory for wide networks, but does not offer efficient sample-complexity guarantees. Recent feature-learning results go beyond kernel methods for single-neuron, multi-index, and hierarchical targets. However, the analysis is often restricted to shallow or specific architectures and to the overparameterized regime. We break this paradigm to achieve parameter-level recovery of deep target networks, albeit by using active data queries. Specifically, we study

L

-layer polynomial networks with even degree-

k

monomial activations and nonnegative higher-layer weights. This structure makes the target network input-convex, while the optimization landscape remains highly nonconvex with respect to the parameters. Leveraging input convexity and active queries, we propose ASPIRE (Active SamPling for Iterative Recovery via Eigendirections), a layerwise sampling-based diagonalization algorithm that recovers all network parameters to

δ

-accuracy with sample complexity

\widetilde O_{k,L}\left(d^{L^2+O(L)}δ^{-2e}\right)

in polynomial time. To our knowledge, this is the first parameter-recovery guarantee for deep target networks whose exponent grows only polynomially with depth, as well as the first justification for the effectiveness of using high-quality data in neural network training, with a remarkably exponential separation.

Jinqi Tang, Qian Chen, Shihong Ding +1

Peking University

Polynomial Neural Networks Input Convex Neural Networks Neural Network Approximation Theory

Ask PDF

Jul 7, 2026

A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

A persistent empirical observation is that trained neural networks outperform their neural tangent kernel (NTK) limit on tasks with compositional structure, yet a quantitative account of

\textbf{when}

and

\textbf{by how much}

has been lacking. Working on the unit circle, we give such an account through a dichotomy between two complexity measures of the target: its

\textbf{Fourier complexity}

, which controls NTK kernel regression, and its

\textbf{architectural complexity}

, which controls learning over depth-

L

, width-

w

ReLU networks with the variation norm of the weights bounded by

R

. We first characterize the minimax rate of the architecture class

\mathcal{C}_{L,w,R}

, pinning it down up to a single factor of

L

: between

Ω(Lw^2R^2/n)

and

\tilde{O}(L^2w^2R^2/n)

. We then show the NTK estimator sits

\textbf{exponentially}

above this floor whenever the two complexities decouple: for the depth-

L

iterated sawtooth, NTK regression needs

Ω(4^L)

samples while the minimax floor is polynomial in

L

. Numerical experiments confirm the theoretical claims: on bandlimited smooth targets, the NTK is competitive or better, while on the hypercube sparse-parity model, a standard two-layer network beats the NTK by four to six orders of magnitude in test error. The gap is thus a function-space property, a mismatch between the kernel's smoothness bias and the target's compositional structure, rather than a generic kernel-versus-network phenomenon.

Arkaprabha Ganguli, Emil Constantinescu

Mathematics & Computer Science Division, Argonne National Laboratory, Lemont, IL, USA

Neural Network Generalization Kernel Regression ReLU Neural Networks Neural Network Approximation Theory Neural Tangent Kernel

Ask PDF

Jun 4, 2026

Generalization in Deep Neural Networks: Minimax Rates for Gradient Methods

Understanding the generalization performance of over-parameterized neural networks has become a central topic in deep learning theory. While recent advances, particularly works under the Neural Tangent Kernel (NTK) regime, have shed light on the behavior of shallow architectures, the statistical generalization properties of deep neural networks (DNNs), especially in regression tasks, remain far less understood. In this paper, we make significant progress toward closing this gap by providing a comprehensive generalization analysis of DNNs trained using gradient-based methods. First, we establish, for the first time, a crucial connection between the learning dynamics of a DNN with smooth activation functions trained via gradient-based methods and those of kernel methods, showing that gradient-based methods on over-parameterized DNNs can fully inherit the favorable learning dynamics of their kernel counterparts. Building on this connection and the well-established optimality of kernel methods, we derive the first known minimax-optimal rates for the excess population risk of both gradient descent (GD) and stochastic gradient descent (SGD), under the assumption that network width scales polynomially with the sample size. Our results demonstrate that, with sufficient width, DNNs trained by GD or SGD can achieve generalization performance comparable to kernel-based methods.

Junyu Zhou, Puyu Wang, Yunwen Lei +2

Mathematical Institute for Machine Learning and Data Science, Catholic University of Eichstätt-Ingolstadt · Department of Computer Science, RPTU Kaiserslautern-Landau · Department of Mathematics, The University of Hong Kong +1

Neural Network Generalization Gradient Descent Dynamics Stochastic Gradient Descent Generalization Bounds

Ask PDF

Abstract

Low-Degree Polynomial Method

Explore similar work

Beyond Overparameterization: Provable Learning of Input-Convex Multi-Layer Polynomial Networks with Active Queries

A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

Generalization in Deep Neural Networks: Minimax Rates for Gradient Methods