# Sketchy Empirical Natural Gradient Methods for Deep Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2020.

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

- [ASDL: A Unified Interface for Gradient Preconditioning in PyTorch](https://mlsanity.com/paper/2305.04684/) (2023)
- [MKOR: Momentum-Enabled Kronecker-Factor-Based Optimizer Using Rank-1 Updates](https://mlsanity.com/paper/2306.01685/) (2023)
- [Riemannian Natural Gradient Methods](https://mlsanity.com/paper/2207.07287/) (2022)
- [Beyond the Mean: Fisher-Orthogonal Projection for Natural Gradient Descent in Large Batch Training](https://mlsanity.com/paper/2508.13898/) (2025)
- [Randomized K-FACs: Speeding up K-FAC with Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2206.15397/) (2022)
- [NG+ : A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning](https://mlsanity.com/paper/2106.07454/) (2021)
- [Brand New K-FACs: Speeding up K-FAC with Online Decomposition Updates](https://mlsanity.com/paper/2210.08494/) (2022)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [Rethinking Exponential Averaging of the Fisher](https://mlsanity.com/paper/2204.04718/) (2022)
- [Center-Manifold Reduction of Learning at Bifurcations: Interference and Rich Learning in Recurrent Neural Networks](https://mlsanity.com/paper/2605.12763/) (2026)
- [Compression Trinity: Exploring Sparsity, Quantization, and Low-Rank Approximations for LLM Compression](https://mlsanity.com/paper/2608.24070/) (2026)

## Abstract (arXiv)

In this paper, we develop an efficient sketchy empirical natural gradient method (SENG) for large-scale deep learning problems. The empirical Fisher information matrix is usually low-rank since the sampling is only practical on a small amount of data at each iteration. Although the corresponding natural gradient direction lies in a small subspace, both the computational cost and memory requirement are still not tractable due to the high dimensionality. We design randomized techniques for different neural network structures to resolve these challenges. For layers with a reasonable dimension, sketching can be performed on a regularized least squares subproblem. Otherwise, since the gradient is a vectorization of the product between two matrices, we apply sketching on the low-rank approximations of these matrices to compute the most expensive parts. A distributed version of SENG is also developed for extremely large-scale applications. Global convergence to stationary points is established under some mild assumptions and a fast linear convergence is analyzed under the neural tangent kernel (NTK) case. Extensive experiments on convolutional neural networks show the competitiveness of SENG compared with the state-of-the-art methods. On the task ResNet50 with ImageNet-1k, SENG achieves 75.9% Top-1 testing accuracy within 41 epochs. Experiments on the distributed large-batch training show that the scaling efficiency is quite reasonable.