mlsanityData to 7 Oct 2026

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

arXiv 2406.06838 ↗First posted 10 Jun 2024cs.LG cs.AI stat.MLcited by 12

Not on the map. Why?

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.

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

Builds on

49 of 66 references.

References · 49

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2018On Lazy Training in Differentiable Programmingcited by 671
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  7. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  8. 2019Benign Overfitting in Linear Regressioncited by 544
  9. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
  10. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  11. 2017How to Escape Saddle Points Efficientlycited by 284
  12. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
37 more
  1. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  2. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  3. 2020The large learning rate phase of deep learning: the catapult mechanismcited by 206
  4. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  6. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 160
  7. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 151
  8. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 126
  9. 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 113
  10. 2019How do infinite width bounded norm networks look in function space?cited by 105
  11. 2018Does data interpolation contradict statistical optimality?cited by 95
  12. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  13. 2021On Linear Stability of SGD and Input-Smoothness of Neural Networkscited by 61
  14. 2022Learning threshold neurons via the "edge of stability"cited by 50
  15. 2023The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descentcited by 44
  16. 2023Benign Overfitting for Two-layer ReLU Convolutional Neural Networkscited by 34
  17. 2021Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networkscited by 32
  18. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  19. 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
  20. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  21. 2023Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyondcited by 20
  22. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  23. 2024How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teacherscited by 18
  24. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  25. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  26. 2020Implicit Bias of Gradient Descent for Mean Squared Error Regression with Two-Layer Wide Neural Networkscited by 15
  27. 2023The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networkscited by 15
  28. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  29. 2014A General Framework for Fast Stagewise Algorithmscited by 11
  30. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  31. 2022Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?cited by 10
  32. 2022Differentially Private Linear Sketches: Efficient Implementations and Applicationscited by 10
  33. 2022Doubly Fair Dynamic Pricingcited by 8
  34. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  35. 2024The Surprising Harmfulness of Benign Overfitting for Adversarial Robustnesscited by 7
  36. 2022The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Datacited by 3
  37. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 6; 2026: 4.

12 papers.

  1. 2025Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorizationcited by 16
  2. 2024Simplicity bias and optimization threshold in two-layer ReLU networkscited by 11
  3. 2025Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regressioncited by 7
  4. 2024Where Do Large Learning Rates Lead Us?cited by 6
  5. 2025Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Regioncited by 5
  6. 2025Sharpness of Minima in Deep Matrix Factorizationcited by 2
  7. 2025Generalization Below the Edge of Stability: The Role of Data Geometrycited by 2
  8. 2026Understanding diffusion models requires rethinking (again) generalizationcited by 2
  9. 2026Does Sparse Connectivity Improve Generalization? Convolutional Networks Below the Edge of Stabilitycited by 1
  10. 2025Convergence of optimizers implies eigenvalues filtering at equilibriumcited by 0
  11. 2026A Mechanism Study of Delayed Loss Spikes in Batch-Normalized Linear Modelscited by 0
  12. 2026Residual-Stream Burden Shapes Representation Learning in Diffusion Transformerscited by 0