Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
This provides theoretical guarantees for a widely used optimization method in deep learning, addressing a gap in understanding for nonlinear networks.
The paper tackles the theoretical convergence of natural gradient descent for nonlinear neural networks, proving that under certain conditions it converges efficiently to global minima for overparameterized two-layer ReLU networks, with extensions to general losses and K-FAC approximations.
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.