Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks

By Guodong Zhang, James Martens, Roger Baker Grosse. 2019

139 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In Scaling & Learning Theory

Citations in the corpus

Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model (2019, background): “Indeed, recent theoretical works [Jacot et al., 2018, Du et al., 2019, Zhang et al., 2019a] show that for wide enough networks, the weights stay close enough to the initialization for the linearized approximation to remain accurate.”
New Insights and Perspectives on the Natural Gradient Method (2014, methodology): “This happens both for gradient descent (Du et al., 2018; Jacot et al., 2018; Lee et al., 2019), and natural gradient descent / GGN-based methods (Zhang et al., 2019; Cai et al., 2019), applied to certain choices for L.”
Picking Winning Tickets Before Training by Preserving Gradient Flow (2020, background): “Deep neural networks exhibit good optimization and generalization performance in the overpa-rameterized regime (Zhang et al., 2016; Neyshabur et al., 2019; Arora et al., 2019; Zhang et al., 2019b), but both training and inference for large networks are computationally expensive.”
Dynamics of Deep Neural Networks and Neural Tangent Hierarchy (2019, methodology): “For two layer neural networks with random training data, quantitative estimates for λ are obtained in (Ghorbani et al., 2019; Zhang et al., 2019; Xie et al., 2016).”