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

Abstract

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.

arXiv comment29 pages

References in corpus (22)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Searching for Activation Functions
• A Convergence Theory for Deep Learning via Over-Parameterization
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Recovery Guarantees for One-hidden-layer Neural Networks
• On the Convergence Rate of Training Recurrent Neural Networks
• Learning ReLUs via Gradient Descent
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Stochastic Particle Gradient Descent for Infinite Ensembles

Cited by in corpus (17)

• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• On Convergence and Generalization of Dropout Training
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• Early-stopped neural networks are consistent
• Quantum-enhanced neural networks in the neural tangent kernel framework
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Is deeper better? It depends on locality of relevant features
• Implicit bias of deep linear networks in the large learning rate phase
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably