Convergence Analysis of Two-layer Neural Networks with ReLU Activation

Abstract

In recent years, stochastic gradient descent (SGD) based techniques has become the standard tools for training neural networks. However, formal theoretical understanding of why SGD can train neural networks in practice is largely missing. In this paper, we make progress on understanding this mystery by providing a convergence analysis for SGD on a rich subset of two-layer feedforward networks with ReLU activations. This subset is characterized by a special structure called "identity mapping". We prove that, if input follows from Gaussian distribution, with standard $O(1/\sqrt{d})$ initialization of the weights, SGD converges to the global minimum in polynomial number of steps. Unlike normal vanilla networks, the "identity mapping" makes our network asymmetric and thus the global minimum is unique. To complement our theory, we are also able to show experimentally that multi-layer networks with this mapping have better performance compared with normal vanilla networks. Our convergence theorem differs from traditional non-convex optimization techniques. We show that SGD converges to optimal in "two phases": In phase I, the gradient points to the wrong direction, however, a potential function $g$ gradually decreases. Then in phase II, SGD enters a nice one point convex region and converges. We also show that the identity mapping is necessary for convergence, as it moves the initial point to a better place for optimization. Experiment verifies our claims.

References in corpus (9)

• Adam: A Method for Stochastic Optimization
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Provable Bounds for Learning Some Deep Representations
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Recovery Guarantees for One-hidden-layer Neural Networks
• Reliably Learning the ReLU in Polynomial Time
• Learning Halfspaces and Neural Networks with Random Initialization

Cited by in corpus (48)

• Visualizing the Loss Landscape of Neural Nets
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Learning One-hidden-layer Neural Networks with Landscape Design
• FedCP: Separating Feature Information for Personalized Federated Learning via Conditional Policy
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• iPromoter-BnCNN: a Novel Branched CNN Based Predictor for Identifying and Classifying Sigma Promoters
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• On exponential convergence of SGD in non-convex over-parametrized learning
• Real-time System Identification Using Deep Learning for Linear Processes with Application to Unmanned Aerial Vehicles
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Machine Learning-based Framework for Optimally Solving the Analytical Inverse Kinematics for Redundant Manipulators
• Understanding the Loss Surface of Neural Networks for Binary Classification
• Adding One Neuron Can Eliminate All Bad Local Minima
• Convergence guarantees for a class of non-convex and non-smooth optimization problems
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• Theoretical properties of the global optimizer of two layer neural network
• A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Model Order Reduction based on Runge-Kutta Neural Network
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• The Multilinear Structure of ReLU Networks
• Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
• Learnability and Robustness of Shallow Neural Networks Learned With a Performance-Driven BP and a Variant PSO For Edge Decision-Making
• Hardness of Learning Neural Networks with Natural Weights
• Symmetry & critical points for a model shallow neural network
• Learning ReLU Networks via Alternating Minimization
• Predicting Training Time Without Training
• GradSign: Model Performance Inference with Theoretical Insights
• Uniform Convergence of Gradients for Non-Convex Learning and Optimization
• EdgeNet: A novel approach for Arabic numeral classification
• Tune smarter not harder: A principled approach to tuning learning rates for shallow nets
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
• Machine Learning Based on Natural Language Processing to Detect Cardiac Failure in Clinical Narratives
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Recursive Sketches for Modular Deep Learning
• Sharper Utility Bounds for Differentially Private Models
• Nonparametric Learning of Two-Layer ReLU Residual Units
• Accelerated Target Updates for Q-learning
• Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study