cs.LGOct 8, 2024

Benign Overfitting for Regression with Trained Two-Layer ReLU Networks

Authors: Junhyung Park, Patrick Bloebaum, Shiva Prasad Kasiviswanathan

Organizations: *ETH Zürich, Switzerland · †Amazon · ‡Amazon

Abstract

We study the least-square regression problem with a two-layer fully-connected neural network, with ReLU activation function, trained by gradient flow. Our first result is a generalization result, that requires no assumptions on the underlying regression function or the noise other than that they are bounded. We operate in the neural tangent kernel regime, and our generalization result is developed via a decomposition of the excess risk into estimation and approximation errors, viewing gradient flow as an implicit regularizer. This decomposition in the context of neural networks is a novel perspective of gradient descent, and helps us avoid uniform convergence traps. In this work, we also establish that under the same setting, the trained network overfits to the data. Together, these results, establishes the first result on benign overfitting for finite-width ReLU networks for arbitrary regression functions.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Mar 3, 2025

The Mathematical Theory of Double Descent as Shrinkage, not Overfitting: Matching Bounds for Path-Regularized Multilayer Neural Networks

We give a nonasymptotic generalization theory for multilayer fully connected neural networks trained with path regularization, for general Lipschitz losses and without assuming the loss bounded, the architecture sparse, or any width or depth limit. Approximation error is modelled explicitly, and along the way we settle an open problem of E et al. on approximation rates in generalized Barron spaces. We treat the underparameterized and overparameterized regimes separately, which is what allows the resulting curve to be non-monotone in the width. We then prove lower bounds on the error itself, valid at every target and at every local minimizer, and combine them with the upper bounds into a theorem asserting that the error - not merely our bound on it - descends, rises and descends again as the width grows, with a peak exceeding the final plateau by a factor diverging in the sample size. Having both sides of the bound also identifies what drives the ascent, and it is not overfitting: once the regularization exceeds the dual norm of the noise, which the prescribed schedule does at every width, a slow-rate oracle inequality controls the error with no variance term at all. The rise is instead the shrinkage demanded by the regularization that the underparameterized regime requires, and we show it cannot be removed by any width-independent regularization under which the theory's guarantees hold. This mechanism is a property of the estimator analyzed here; we do not claim it accounts for the double descent reported for unregularized training.
Nov 1, 2026

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

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(\epsn2)\cO(\eps_n^2), where \epsn\eps_n is the critical population rate of the attention kernel \Kattn\Kattn. Its positive eigenvalues are λjs′λ_j^{s'}, where λjλ_j are those of the ReLU feature covariance kernel KK and s′=2s+3s'=2s+3 for s≥1s\ge1. Under polynomial eigenvalue decay λj≍j−2αλ_j\asymp j^{-2α} with α>1/2α>1/2, the regression risk bound \cO(\epsn2)\cO(\eps_n^2) specializes to the minimax optimal rate \cO(n−2αs′/(2αs′+1))\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 \RRd\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))\cO((\log n)n^{-s'(d+3)/(s'(d+3)+d)}) without a density assumption.
Sep 27, 2026

Benign Overfitting for General Norms and Distributions

Understanding why predictors can generalize despite interpolating noisy training data is a central puzzle in machine learning. Most work on such "benign overfitting" studies minimum-2-norm linear regression, reflecting the inductive bias of gradient descent. However, modern optimizers such as Adam and Muon use non-Euclidean update geometries, favoring solutions associated with other norms. Analyzing regression for non-Euclidean norms is substantially more difficult, with known results essentially limited to Gaussians. In this paper, we develop a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions. As a special case, we prove that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions. Perhaps surprisingly, for the 1-norm, benign overfitting does not hold in general for well-behaved (but non-Gaussian) distributions, showing that existing positive 1-norm results rely crucially on Gaussianity. Our proof analyzes the geometry of the dual optimization problem, using concentration and central limit tools to show it is approximately Euclidean in many high-dimensional cases.