Research map / Optimization / Implicit bias and generalization
Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes
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 stable minima of gradient descent with large fixed step size in univariate two-layer ReLU networks with noisy labels are weighted-TV1-bounded smooth functions, so they cannot overfit and achieve near-optimal n^{-4/5} MSE without regularization.
Problem
Generalization of gradient-descent-trained two-layer ReLU networks in univariate nonparametric regression with noisy labels, where interpolating solutions overfit and kernel theory is suboptimal.
Approach
Uses minima stability (lambda_max of Hessian <= 2/eta) to bound a weighted first-order total variation of the learned function even without interpolation, decomposing the noisy-label curvature term into a Gaussian complexity plus a self-bounding MSE term; this yields non-overfitting generalization bounds and near-optimal rates for stable solutions.
Key results
- Stable minima of GD satisfy weighted TV1 bound 1/eta - 1/2 + O~(sigma + sqrt(MSE)), and any interpolating solution has lambda_max >= Omega(n^2 sigma).
- Generalization gap within interior of data support vanishes at rate O~(n^{-2/5}) (in n_I) for stable solutions.
- Near-optimal MSE bound O~(n^{-4/5}) in strict interior for stable solutions, matching minimax BV(1) rate, under an 'optimized' assumption; experiments with eta=0.4 vs 0.01 show large step sizes yield sparse linear splines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the gradient descent learning rate | Two-layer ReLU network · Univariate noisy regression simulation | Weighted TV1 complexity | Helped |
| Increase the gradient descent learning rate | Stable two-layer ReLU solutions · Agnostic statistical learning, strict interior of data support | Generalization gap | Helped |
| Increase the gradient descent learning rate | Stable two-layer ReLU solutions · BV(1) nonparametric regression, strict interior | MSE | Helped |
| Tune the gradient descent learning rate | Two-layer ReLU network · Univariate noisy regression simulation | Bias-variance tradeoff | Mixed |
Surprising findings
- With large learning rate, most learned knots lie outside the data support, so the ReLUs become inactive on training data.
- All interpolating solutions are very sharp when labels are noisy (lambda_max >= Omega(n^2 sigma)).
Experimental setup
Datasets: synthetic 1D regression data (n=30, sigma=0.5)
Metrics: MSE generalization gap weighted TV1 norm Hessian largest eigenvalue
Baselines: Interpolating solutions / kernel regime (NTK) Kernel ridge regression Gradient flow
Builds on: Large learning rate implicit bias (Z. Li et al. 2022, interpolating TV1 bound) Linear stability of GD (Wu et al.) Edge of stability Benign overfitting
Closest papers by meaning
- Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon (NeurIPS 2025 · similarity 0.93)
- The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks (ICLR 2023 · similarity 0.93)
- Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.91)
- Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.90)
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time (ICML 2024 · similarity 0.90)
- Universal Consistency of Wide and Deep ReLU Neural Networks and Minimax Optimal Convergence Rates for Kolmogorov-Donoho Optimal Function Classes (ICML 2024 · similarity 0.89)
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.