# Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes

arXiv: https://arxiv.org/abs/2406.06838 · HTML: https://mlsanity.com/paper/2406.06838/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 66 references that are in the map.
- First posted on arXiv 10 Jun 2024.

## Builds on (most cited first, 30 of 49)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [The large learning rate phase of deep learning: the catapult mechanism](https://mlsanity.com/paper/2003.02218/) (2020)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Understanding Gradient Descent on Edge of Stability in Deep Learning](https://mlsanity.com/paper/2205.09745/) (2022)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [On Linear Stability of SGD and Input-Smoothness of Neural Networks](https://mlsanity.com/paper/2105.13462/) (2021)
- [Learning threshold neurons via the "edge of stability"](https://mlsanity.com/paper/2212.07469/) (2022)
- [The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descent](https://mlsanity.com/paper/2305.17490/) (2023)
- [Benign Overfitting for Two-layer ReLU Convolutional Neural Networks](https://mlsanity.com/paper/2303.04145/) (2023)
- [Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks](https://mlsanity.com/paper/2109.02832/) (2021)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)

## Built on by (most cited first, 12 of 12)

- [Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorization](https://mlsanity.com/paper/2502.03435/) (2025)
- [Simplicity bias and optimization threshold in two-layer ReLU networks](https://mlsanity.com/paper/2410.02348/) (2024)
- [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025)
- [Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region](https://mlsanity.com/paper/2509.25351/) (2025)
- [Where Do Large Learning Rates Lead Us?](https://mlsanity.com/paper/2410.22113/) (2024)
- [Generalization Below the Edge of Stability: The Role of Data Geometry](https://mlsanity.com/paper/2510.18120/) (2025)
- [Sharpness of Minima in Deep Matrix Factorization](https://mlsanity.com/paper/2509.25783/) (2025)
- [Understanding diffusion models requires rethinking (again) generalization](https://mlsanity.com/paper/2605.06077/) (2026)
- [Does Sparse Connectivity Improve Generalization? Convolutional Networks Below the Edge of Stability](https://mlsanity.com/paper/2603.04807/) (2026)
- [Convergence of optimizers implies eigenvalues filtering at equilibrium](https://mlsanity.com/paper/2510.09034/) (2025)
- [A Mechanism Study of Delayed Loss Spikes in Batch-Normalized Linear Models](https://mlsanity.com/paper/2604.16809/) (2026)
- [Residual-Stream Burden Shapes Representation Learning in Diffusion Transformers](https://mlsanity.com/paper/2609.33895/) (2026)

## Abstract (arXiv)

We study the generalization of two-layer ReLU neural networks in a univariate nonparametric regression problem with noisy labels. This is a problem where kernels (e.g. NTK) are provably sub-optimal and benign overfitting does not happen, thus disqualifying existing theory for interpolating (0-loss, global optimal) solutions. We present a new theory of generalization for local minima that gradient descent with a constant learning rate can stably converge to. We show that gradient descent with a fixed learning rate η can only find local minima that represent smooth functions with a certain weighted first order total variation bounded by 1/η - 1/2 + widetildeO(σ + √MSE) where σ is the label noise level, MSE is short for mean squared error against the ground truth, and widetildeO(·) hides a logarithmic factor. Under mild assumptions, we also prove a nearly-optimal MSE bound of widetildeO(n-4/5) within the strict interior of the support of the n data points. Our theoretical results are validated by extensive simulation that demonstrates large learning rate training induces sparse linear spline fits. To the best of our knowledge, we are the first to obtain generalization bound via minima stability in the non-interpolation case and the first to show ReLU NNs without regularization can achieve near-optimal rates in nonparametric regression.