Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks

Abstract

Natural gradient descent has proven effective at mitigating the effects of pathological curvature in neural network optimization, but little is known theoretically about its convergence properties, especially for \emph{nonlinear} networks. In this work, we analyze for the first time the speed of convergence of natural gradient descent on nonlinear neural networks with squared-error loss. We identify two conditions which guarantee efficient convergence from random initializations: (1) the Jacobian matrix (of network's output for all training cases with respect to the parameters) has full row rank, and (2) the Jacobian matrix is stable for small perturbations around the initialization. For two-layer ReLU neural networks, we prove that these two conditions do in fact hold throughout the training, under the assumptions of nondegenerate inputs and overparameterization. We further extend our analysis to more general loss functions. Lastly, we show that K-FAC, an approximate natural gradient descent method, also converges to global minima under the same assumptions, and we give a bound on the rate of this convergence.

arXiv commentNeurIPS 2019

References in corpus (28)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• New insights and perspectives on the natural gradient method
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for 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
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• The loss surface of deep and wide neural networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Gradient Descent Converges to Minimizers
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Stronger generalization bounds for deep nets via a compression approach
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Norm-Based Capacity Control in Neural Networks
• Diverse Neural Network Learns True Target Functions
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• When is a Convolutional Filter Easy To Learn?
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Practical Gauss-Newton Optimisation for Deep Learning
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Learning One-hidden-layer Neural Networks under General Input Distributions
• A Coordinate-Free Construction of Scalable Natural Gradient

Cited by in corpus (25)

• Picking Winning Tickets Before Training by Preserving Gradient Flow
• A Theoretical Framework for Target Propagation
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• The Low-Rank Simplicity Bias in Deep Networks
• When Does Preconditioning Help or Hurt Generalization?
• KAISA: An Adaptive Second-Order Optimizer Framework for Deep Neural Networks
• A General Family of Stochastic Proximal Gradient Methods for Deep Learning
• Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation
• Sketchy Empirical Natural Gradient Methods for Deep Learning
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• A Fully Stochastic Second-Order Trust Region Method
• Any Target Function Exists in a Neighborhood of Any Sufficiently Wide Random Network: A Geometrical Perspective
• A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions
• Rethinking Gauss-Newton for learning over-parameterized models
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Depth Without the Magic: Inductive Bias of Natural Gradient Descent
• Understanding Approximate Fisher Information for Fast Convergence of Natural Gradient Descent in Wide Neural Networks
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• TENGraD: Time-Efficient Natural Gradient Descent with Exact Fisher-Block Inversion