# Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks

arXiv: https://arxiv.org/abs/1905.10961 · HTML: https://mlsanity.com/paper/1905.10961/

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2019.

## Built on by (most cited first, 30 of 76)

- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Improved architectures and training algorithms for deep operator networks](https://mlsanity.com/paper/2110.01654/) (2021)
- [A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale](https://mlsanity.com/paper/2309.06497/) (2023)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [An Over-parameterized Exponential Regression](https://mlsanity.com/paper/2303.16504/) (2023)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Gradient Descent on Neurons and its Link to Approximate Second-Order Optimization](https://mlsanity.com/paper/2201.12250/) (2022)
- [Credit Assignment in Neural Networks through Deep Feedback Control](https://mlsanity.com/paper/2106.07887/) (2021)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [Dual Lottery Ticket Hypothesis](https://mlsanity.com/paper/2203.04248/) (2022)
- [How to Protect Copyright Data in Optimization of Large Language Models?](https://mlsanity.com/paper/2308.12247/) (2023)
- [A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions](https://mlsanity.com/paper/2401.10190/) (2024)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Training Overparametrized Neural Networks in Sublinear Time](https://mlsanity.com/paper/2208.04508/) (2022)
- [Single-Shot Pruning for Offline Reinforcement Learning](https://mlsanity.com/paper/2112.15579/) (2021)
- [The Challenges of the Nonlinear Regime for Physics-Informed Neural Networks](https://mlsanity.com/paper/2402.03864/) (2024)
- [KAISA: An Adaptive Second-Order Optimizer Framework for Deep Neural Networks](https://mlsanity.com/paper/2107.01739/) (2021)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [Sampling via Gradient Flows in the Space of Probability Measures](https://mlsanity.com/paper/2310.03597/) (2023)
- [The Geometry of Neural Nets' Parameter Spaces Under Reparametrization](https://mlsanity.com/paper/2302.07384/) (2023)
- [Gradient Flows for Sampling: Mean-Field Models, Gaussian Approximations and Affine Invariance](https://mlsanity.com/paper/2302.11024/) (2023)
- [On the Parameterization of Second-Order Optimization Effective Towards the Infinite Width](https://mlsanity.com/paper/2312.12226/) (2023)
- [An Improved Empirical Fisher Approximation for Natural Gradient Descent](https://mlsanity.com/paper/2406.06420/) (2024)
- [Second-Order Neural ODE Optimizer](https://mlsanity.com/paper/2109.14158/) (2021)
- [Invariance Properties of the Natural Gradient in Overparametrised Systems](https://mlsanity.com/paper/2206.15273/) (2022)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [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](https://mlsanity.com/paper/2108.04620/) (2021)
- [Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation](https://mlsanity.com/paper/2108.08106/) (2021)

## Abstract (arXiv)

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 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.