  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.
