Fast Convergence in Learning Two-Layer Neural Networks with Separable Data
Not on the map. Why?
Abstract (arXiv)
Normalized gradient descent has shown substantial success in speeding up the convergence of exponentially-tailed loss functions (which includes exponential and logistic losses) on linear classifiers with separable data. In this paper, we go beyond linear models by studying normalized GD on two-layer neural nets. We prove for exponentially-tailed losses that using normalized GD leads to linear rate of convergence of the training loss to the global optimum if the iterates find an interpolating model. This is made possible by showing certain gradient self-boundedness conditions and a log-Lipschitzness property. We also study generalization of normalized GD for convex objectives via an algorithmic-stability analysis. In particular, we show that normalized GD does not overfit during training by establishing finite-time generalization bounds.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 29 of its 38 references that are in the map. First posted on arXiv 22 May 2023.
Builds on
29 of 38 references.
References · 29
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
- 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
- 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
- 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
- 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
- 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
- 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
- 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
- 2020Directional convergence and alignment in deep learningcited by 178
17 more
- 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
- 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
- 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
- 2018Convergence of Gradient Descent on Separable Datacited by 110
- 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
- 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 88
- 2018Risk and parameter convergence of logistic regressioncited by 85
- 2019Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networkscited by 60
- 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
- 2013Margins, Shrinkage, and Boostingcited by 35
- 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
- 2020The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networkscited by 33
- 2020Gradient Methods Never Overfit On Separable Datacited by 29
- 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
- 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
- 2021When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?cited by 9
- 2022On Generalization of Decentralized Learning with Separable Datacited by 8
Built on by
Citing papers per year: 2024: 1; 2025: 1; 2026: 1.
3 papers.