# TENGraD: Time-Efficient Natural Gradient Descent with Exact Fisher-Block Inversion

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 7 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [New insights and perspectives on the natural gradient method](https://mlsanity.com/paper/1412.1193/) (2014)
- [Limitations of the Empirical Fisher Approximation for Natural Gradient Descent](https://mlsanity.com/paper/1905.12558/) (2019)
- [Fast Approximate Natural Gradient Descent in a Kronecker-factored Eigenbasis](https://mlsanity.com/paper/1806.03884/) (2018)
- [Practical Gauss-Newton Optimisation for Deep Learning](https://mlsanity.com/paper/1706.03662/) (2017)
- [A Kronecker-factored approximate Fisher matrix for convolution layers](https://mlsanity.com/paper/1602.01407/) (2016)
- [Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach](https://mlsanity.com/paper/1806.01316/) (2018)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [BackPACK: Packing more into backprop](https://mlsanity.com/paper/1912.10985/) (2019)
- [Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks](https://mlsanity.com/paper/1905.10961/) (2019)
- [Practical Quasi-Newton Methods for Training Deep Neural Networks](https://mlsanity.com/paper/2006.08877/) (2020)
- [Natural Neural Networks](https://mlsanity.com/paper/1507.00210/) (2015)
- [Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems](https://mlsanity.com/paper/1905.11675/) (2019)
- [Efficient Subsampled Gauss-Newton and Natural Gradient Methods for Training Neural Networks](https://mlsanity.com/paper/1906.02353/) (2019)
- [Understanding Approximate Fisher Information for Fast Convergence of Natural Gradient Descent in Wide Neural Networks](https://mlsanity.com/paper/2010.00879/) (2020)

## Built on by (most cited first, 7 of 7)

- [A Mini-Block Fisher Method for Deep Neural Networks](https://mlsanity.com/paper/2202.04124/) (2022)
- [Natural Gradient Methods: Perspectives, Efficient-Scalable Approximations, and Analysis](https://mlsanity.com/paper/2303.05473/) (2023)
- [Scalable K-FAC Training for Deep Neural Networks with Distributed Preconditioning](https://mlsanity.com/paper/2206.15143/) (2022)
- [LAWS: Look Around and Warm-Start Natural Gradient Descent for Quantum Neural Networks](https://mlsanity.com/paper/2205.02666/) (2022)
- [Understanding the Effects of Second-Order Approximations in Natural Policy Gradient Reinforcement Learning](https://mlsanity.com/paper/2201.09104/) (2022)
- [Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning](https://mlsanity.com/paper/2602.20078/) (2026)
- [Natural Gradient Descent for Online Continual Learning](https://mlsanity.com/paper/2603.20898/) (2026)

## Abstract (arXiv)

This work proposes a time-efficient Natural Gradient Descent method, called TENGraD, with linear convergence guarantees. Computing the inverse of the neural network's Fisher information matrix is expensive in NGD because the Fisher matrix is large. Approximate NGD methods such as KFAC attempt to improve NGD's running time and practical application by reducing the Fisher matrix inversion cost with approximation. However, the approximations do not reduce the overall time significantly and lead to less accurate parameter updates and loss of curvature information. TENGraD improves the time efficiency of NGD by computing Fisher block inverses with a computationally efficient covariance factorization and reuse method. It computes the inverse of each block exactly using the Woodbury matrix identity to preserve curvature information while admitting (linear) fast convergence rates. Our experiments on image classification tasks for state-of-the-art deep neural architecture on CIFAR-10, CIFAR-100, and Fashion-MNIST show that TENGraD significantly outperforms state-of-the-art NGD methods and often stochastic gradient descent in wall-clock time.