Research map / Learning theory and algorithms / Kernels and regression theory
Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that an over-parameterized two-layer ReLU network trained by GD with early stopping achieves the sharp nonparametric regression rate O(ε_n^2) under distribution-free spherical covariates, matching minimax rates without distributional assumptions.
Problem
Obtaining sharp (minimax-optimal) nonparametric regression rates for over-parameterized neural networks trained by gradient descent with early stopping, without distributional assumptions on the covariate beyond lying on the unit sphere.
Approach
Decomposes the GD-trained network function into an RKHS function of the NTK plus a small-L∞ error term, and uses local Rademacher complexity to bound the complexity of all GD-reachable networks, yielding an O(ε_n^2) risk bound with width depending only on d and ε_n (not on the empirical NTK minimum eigenvalue).
Key results
- Theorem 5.1: GD with early stopping on an over-parameterized two-layer ReLU network achieves risk O(ε_n^2) distribution-free for covariates on the unit sphere, matching kernel regression rates.
- Under polynomial EDR λ_j ≍ j^{-d/(d-1)}, the risk rate is O(n^{-d/(2d-1)}), the minimax rate, with width m ≳ n^{80α/(3(2α+1))} d^{8/3}.
- Stopping time scales as T̂ ≍ ε_n^{-2} and the learning rate can be constant η ∈ [1,2) rather than infinitesimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train an over-parameterized two-layer NN by GD with early stopping | Two-layer ReLU NN · Nonparametric regression, spherical covariate | risk: O\(\epsilon_n^2\) | Helped |
| Train an over-parameterized two-layer NN by GD with early stopping | Two-layer ReLU NN · Nonparametric regression, polynomial EDR | risk: O(n^{-\frac{d}{2d-1}}) | Helped |
| Use early stopping for GD | Two-layer ReLU NN · Nonparametric regression, spherical covariate | risk: O\(\epsilon_n^2\) | Helped |
Surprising findings
- Training only the first layer of the two-layer network (second layer fixed at random ±1) suffices for sharp rates, and the width requirement is smaller than in prior multi-layer analyses.
Limitations
- Requires target function in RKHS ball H_K(µ0) of the NTK.
- Requires covariates on the unit sphere and fixed dimension d ≥ 4.
- Width lower bound of order n^{80α/(3(2α+1))} is large in practice; only the first layer is trained.
Experimental setup
Metrics: nonparametric regression risk (L2 expected squared error)
Baselines: Hu et al. 2021 Suh et al. 2022 Li et al. 2024 Kuzborskij & Szepesvári 2021 Raskutti et al. 2014 kernel regression
Builds on: Neural Tangent Kernel Raskutti et al. 2014 kernel regression early stopping Hu et al. 2021 Suh et al. 2022 Li et al. 2024
Closest papers by meaning
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.89)
- Generalization error of spectral algorithms (ICLR 2024 · similarity 0.87)
- Out of the Ordinary: Spectrally Adapting Regression for Covariate Shift (ICML 2024 · similarity 0.87)
- High-Dimensional Analysis for Generalized Nonlinear Regression: From Asymptotics to Algorithm (AAAI 2024 · similarity 0.87)
- Deep linear networks for regression are implicitly regularized towards flat minima (NeurIPS 2024 · similarity 0.86)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.