mlsanityData to 7 Oct 2026

Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification

arXiv 2510.02779 ↗First posted 3 Oct 2025cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

Recent advances have significantly improved our understanding of the generalization performance of gradient descent (GD) methods in deep neural networks. A natural and fundamental question is whether GD can achieve generalization rates comparable to the minimax optimal rates established in the kernel setting. Existing results either yield suboptimal rates of O(1/√n), or focus on networks with smooth activation functions, incurring exponential dependence on network depth L. In this work, we establish optimal generalization rates for GD with deep ReLU networks by carefully trading off optimization and generalization errors, achieving only polynomial dependence on depth. Specifically, under the assumption that the data are NTK separable from the margin γ, we prove an excess risk rate of widetildeO(L6 / (n γ2)), which aligns with the optimal SVM-type rate widetildeO(1 / (n γ2)) up to depth-dependent factors. A key technical contribution is our novel control of activation patterns near a reference model, enabling a sharper Rademacher complexity bound for deep ReLU networks trained with gradient descent.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 36 of its 46 references that are in the map. First posted on arXiv 3 Oct 2025.

Builds on

36 of 46 references.

References · 36

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  5. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  6. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  7. 2018On Lazy Training in Differentiable Programmingcited by 671
  8. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  9. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  10. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  11. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  12. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
24 more
  1. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  2. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  3. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  4. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  5. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  6. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  7. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  8. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  9. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  10. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  11. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  12. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  13. 2020Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regimecited by 35
  14. 2020Gradient Methods Never Overfit On Separable Datacited by 29
  15. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  16. 2019On Learning Over-parameterized Neural Networks: A Functional Approximation Perspectivecited by 28
  17. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  18. 2019Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problemscited by 23
  19. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  20. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  21. 2024Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networkscited by 8
  22. 2023Tight Risk Bounds for Gradient Descent on Separable Datacited by 7
  23. 2024Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methodscited by 7
  24. 2022Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networkscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networkscited by 1
  2. 2026Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networkscited by 0
  3. 2026A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networkscited by 0