mlsanityData to 7 Oct 2026

Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods

arXiv 2410.10024 ↗First posted 13 Oct 2024cs.LG cs.IT math.ITcited by 7

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the data-dependent convergence and generalization behavior of gradient methods for neural networks with smooth activation. Our first result is a novel bound on the excess risk of deep networks trained by the logistic loss, via an alogirthmic stability analysis. Compared to previous works, our results improve upon the shortcomings of the well-established Rademacher complexity-based bounds. Importantly, the bounds we derive in this paper are tighter, hold even for neural networks of small width, do not scale unfavorably with width, are algorithm-dependent, and consequently capture the role of initialization on the sample complexity of gradient descent for deep nets. Specialized to noiseless data separable with margin γ by neural tangent kernel (NTK) features of a network of width Omega(poly(log(n))), we show the test-error rate to be eO(L)/γ2 n, where n is the training set size and L denotes the number of hidden layers. This is an improvement in the test loss bound compared to previous works while maintaining the poly-logarithmic width conditions. We further investigate excess risk bounds for deep nets trained with noisy data, establishing that under a polynomial condition on the network width, gradient descent can achieve the optimal excess risk. Finally, we show that a large step-size significantly improves upon the NTK regime's results in classifying the XOR distribution. In particular, we show for a one-hidden-layer neural network of constant width m with quadratic activation and standard Gaussian initialization that mini-batch SGD with linear sample complexity and with a large step-size η=m reaches the perfect test accuracy after only ceillog(d) iterations, where d is the data dimension.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 28 of its 33 references that are in the map. First posted on arXiv 13 Oct 2024.

Builds on

28 of 33 references.

References · 28

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  3. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  6. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  7. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  8. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  9. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  10. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  11. 2019Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networkscited by 158
  12. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
16 more
  1. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  2. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  3. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  4. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  5. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  6. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  7. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  8. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
  9. 2024Asymptotics of feature learning in two-layer networks after one gradient-stepcited by 35
  10. 2023Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Datacited by 32
  11. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  12. 2019Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problemscited by 23
  13. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  14. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  15. 2023Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networkscited by 9
  16. 2022Restricted Strong Convexity of Deep Learning Models with Smooth Activationscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 5.

7 papers.

  1. 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classificationcited by 3
  2. 2025On the Theory of Continual Learning with Gradient Descent for Neural Networkscited by 2
  3. 2026Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networkscited by 1
  4. 2026Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networkscited by 0
  5. 2026Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networkscited by 0
  6. 2026Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descentcited by 0
  7. 2026Convergence Guarantees of Gradient Descent for Neural Networks via Generalized Lipschitz Smoothnesscited by 0