Fast Convergence in Learning Two-Layer Neural Networks with Separable Data

2023/05/22 by Hossein Taheri, Christos Thrampoulidis, Taheri, Hossein +1
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and ELM #Neural Networks and Applications #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2305.13471

openalex publication_date 2023/05/22 · openalex created_date 2023/05/25 · openalex updated_date 2026/07/28

Abstract

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.

Related

• On the convergence of gradient descent for two layer neural networks
• Guiding Two-Layer Neural Network Lipschitzness via Gradient Descent Learning Rate Constraints
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods
• Generalization and Stability of Interpolating Neural Networks with Minimal Width