# Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

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

- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [A Scaling Law for Synthetic-to-Real Transfer: How Much Is Your Pre-training Effective?](https://mlsanity.com/paper/2108.11018/) (2021)
- [Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis](https://mlsanity.com/paper/2206.12802/) (2022)
- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)
- [Understanding Square Loss in Training Overparametrized Neural Network Classifiers](https://mlsanity.com/paper/2112.03657/) (2021)
- [Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networks](https://mlsanity.com/paper/2305.16891/) (2023)
- [An Empirical Study of Scaling Laws for Transfer](https://mlsanity.com/paper/2408.16947/) (2024)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods](https://mlsanity.com/paper/2410.10024/) (2024)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [Geometric structure of shallow neural networks and constructive mathcal L2 cost minimization](https://mlsanity.com/paper/2309.10370/) (2023)
- [Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification](https://mlsanity.com/paper/2510.02779/) (2025)
- [On the Theory of Continual Learning with Gradient Descent for Neural Networks](https://mlsanity.com/paper/2510.05573/) (2025)
- [Fine-grained Analysis of Non-parametric Estimation for Pairwise Learning](https://mlsanity.com/paper/2305.19640/) (2023)
- [On Achieving Optimal Adversarial Test Error](https://mlsanity.com/paper/2306.07544/) (2023)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Optimization Risk Bounds for Kolmogorov-Arnold Networks Trained by DP-SGD with Correlated Noise](https://mlsanity.com/paper/2605.12648/) (2026)
- [Informed Learning by Wide Neural Networks: Convergence, Generalization and Sampling Complexity](https://mlsanity.com/paper/2207.00751/) (2022)
- [Non-Convex Optimizations for Machine Learning with Theoretical Guarantee: Robust Matrix Completion and Neural Network Learning](https://mlsanity.com/paper/2306.16557/) (2023)
- [Uniform convergence of the smooth calibration error and its relationship with functional gradient](https://mlsanity.com/paper/2505.19396/) (2025)
- [Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks](https://mlsanity.com/paper/2606.06764/) (2026)

## Abstract (arXiv)

Recently, several studies have proven the global convergence and generalization abilities of the gradient descent method for two-layer ReLU networks. Most studies especially focused on the regression problems with the squared loss function, except for a few, and the importance of the positivity of the neural tangent kernel has been pointed out. On the other hand, the performance of gradient descent on classification problems using the logistic loss function has not been well studied, and further investigation of this problem structure is possible. In this work, we demonstrate that the separability assumption using a neural tangent model is more reasonable than the positivity condition of the neural tangent kernel and provide a refined convergence analysis of the gradient descent for two-layer networks with smooth activations. A remarkable point of our result is that our convergence and generalization bounds have much better dependence on the network width in comparison to related studies. Consequently, our theory provides a generalization guarantee for less over-parameterized two-layer networks, while most studies require much higher over-parameterization.