mlsanityData to 7 Oct 2026

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

arXiv 2603.21062 ↗First posted 22 Mar 2026stat.ML cs.LG math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning a low-degree spherical polynomial of degree k0 = Theta(1) ≥ 1 defined on the unit sphere in RRd 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 ∈ (0, Theta(d-k0)], an over-parameterized two-layer neural network trained by a novel Gradient Descent with Projection (GDP) requires a sample complexity of n asymp Theta( log(4/δ) · dk0/eps) with probability 1-δ for δ ∈ (0,1), in contrast with the representative sample complexity Theta(dk0 maxseteps-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/δ) · Theta(dk0/n) with probability at least 1-δ. On the other hand, the minimax optimal rate for the regression risk with a kernel of rank Theta(dk0) is Theta(dk0/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 k0 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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 31 of its 49 references that are in the map. First posted on arXiv 22 Mar 2026.

Builds on

31 of 49 references.

References · 31

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018On the Spectral Bias of Neural Networkscited by 1,321
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  4. 2018On Lazy Training in Differentiable Programmingcited by 671
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  8. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  9. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  10. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  11. 2019Towards Understanding the Spectral Bias of Deep Learningcited by 173
  12. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
19 more
  1. 2019Linearized two-layers neural networks in high dimensioncited by 155
  2. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  3. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  4. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  5. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 86
  6. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  7. 2013Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Ratescited by 64
  8. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  9. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  10. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
  11. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  12. 2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 30
  13. 2019On Learning Over-parameterized Neural Networks: A Functional Approximation Perspectivecited by 28
  14. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  15. 2022The Spectral Bias of Polynomial Neural Networkscited by 19
  16. 2015Minimax Optimal Rates of Estimation in High Dimensional Additive Models: Universal Phase Transitioncited by 13
  17. 2022Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomialscited by 13
  18. 2024Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspectivecited by 12
  19. 2024Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regressioncited by 2

Built on by

Not cited yet.