mlsanityData to 14 Oct 2026

Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks

arXiv 1905.10961 ↗First posted 27 May 2019stat.ML cs.LGcited by 76

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 18; 2022: 15; 2023: 22; 2024: 9; 2025: 6; 2026: 6.

76 papers.

Sort:

By area:

  1. 2021The Low-Rank Simplicity Bias in Deep Networkscited by 154
  2. 2021Improved architectures and training algorithms for deep operator networkscited by 86
  3. 2023A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scalecited by 77
  4. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  5. 2023An Over-parameterized Exponential Regressioncited by 45
  6. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  7. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  8. 2022Gradient Descent on Neurons and its Link to Approximate Second-Order Optimizationcited by 30
  9. 2021Credit Assignment in Neural Networks through Deep Feedback Controlcited by 29
  10. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  11. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  12. 2022Dual Lottery Ticket Hypothesiscited by 27
38 more
  1. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  2. 2024A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctionscited by 26
  3. 2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
  4. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  5. 2021Single-Shot Pruning for Offline Reinforcement Learningcited by 21
  6. 2024The Challenges of the Nonlinear Regime for Physics-Informed Neural Networkscited by 21
  7. 2021KAISA: An Adaptive Second-Order Optimizer Framework for Deep Neural Networkscited by 20
  8. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  9. 2023Sampling via Gradient Flows in the Space of Probability Measurescited by 20
  10. 2023The Geometry of Neural Nets' Parameter Spaces Under Reparametrizationcited by 16
  11. 2023Gradient Flows for Sampling: Mean-Field Models, Gaussian Approximations and Affine Invariancecited by 16
  12. 2023On the Parameterization of Second-Order Optimization Effective Towards the Infinite Widthcited by 15
  13. 2024An Improved Empirical Fisher Approximation for Natural Gradient Descentcited by 15
  14. 2021Second-Order Neural ODE Optimizercited by 11
  15. 2022Invariance Properties of the Natural Gradient in Overparametrised Systemscited by 11
  16. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  17. 2021A 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 functionscited by 10
  18. 2021Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activationcited by 9
  19. 2021Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functionscited by 9
  20. 2022Amortized Proximal Optimizationcited by 9
  21. 2023Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrumcited by 9
  22. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  23. 2024Efficient, Multimodal, and Derivative-Free Bayesian Inference With Fisher-Rao Gradient Flowscited by 9
  24. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8
  25. 2022A Mini-Block Fisher Method for Deep Neural Networkscited by 8
  26. 2023Natural Gradient Methods: Perspectives, Efficient-Scalable Approximations, and Analysiscited by 8
  27. 2024Understanding Stochastic Natural Gradient Variational Inferencecited by 8
  28. 2021TENGraD: Time-Efficient Natural Gradient Descent with Exact Fisher-Block Inversioncited by 7
  29. 2022Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problemscited by 7
  30. 2022Scalable K-FAC Training for Deep Neural Networks with Distributed Preconditioningcited by 7
  31. 2023Rethinking Gauss-Newton for learning over-parameterized modelscited by 6
  32. 2023On the Disconnect Between Theory and Practice of Neural Networks: Limits of the NTK Perspectivecited by 6
  33. 2022Riemannian Natural Gradient Methodscited by 5
  34. 2023Neural Characteristic Activation Analysis and Geometric Parameterization for ReLU Networkscited by 5
  35. 2021Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Netscited by 4
  36. 2024TENG: Time-Evolving Natural Gradient for Solving PDEs With Deep Neural Nets Toward Machine Precisioncited by 4
  37. 2021SCORE: Approximating Curvature Information under Self-Concordant Regularizationcited by 3
  38. 2022Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometrycited by 3

50 most cited of 76 All 76 (JSON)