# Randomized K-FACs: Speeding up K-FAC with Randomized Numerical Linear Algebra

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 30 Jun 2022.

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

- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [New insights and perspectives on the natural gradient method](https://mlsanity.com/paper/1412.1193/) (2014)
- [A Kronecker-factored approximate Fisher matrix for convolution layers](https://mlsanity.com/paper/1602.01407/) (2016)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [Scalable and Practical Natural Gradient for Large-Scale Deep Learning](https://mlsanity.com/paper/2002.06015/) (2020)
- [Activation function design for deep networks: linearity and effective initialisation](https://mlsanity.com/paper/2105.07741/) (2021)
- [Sketchy Empirical Natural Gradient Methods for Deep Learning](https://mlsanity.com/paper/2006.05924/) (2020)
- [Rethinking Exponential Averaging of the Fisher](https://mlsanity.com/paper/2204.04718/) (2022)

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

- [SOAP: Improving and Stabilizing Shampoo using Adam](https://mlsanity.com/paper/2409.11321/) (2024)
- [COSMOS: A Hybrid Adaptive Optimizer for Memory-Efficient Training of LLMs](https://mlsanity.com/paper/2502.17410/) (2025)
- [Curvature-Guided LoRA: Matching Full Fine-Tuning in Function Space](https://mlsanity.com/paper/2603.29824/) (2026)

## Abstract (arXiv)

K-FAC is a successful tractable implementation of Natural Gradient for Deep Learning, which nevertheless suffers from the requirement to compute the inverse of the Kronecker factors (through an eigen-decomposition). This can be very time-consuming (or even prohibitive) when these factors are large. In this paper, we theoretically show that, owing to the exponential-average construction paradigm of the Kronecker factors that is typically used, their eigen-spectrum must decay. We show numerically that in practice this decay is very rapid, leading to the idea that we could save substantial computation by only focusing on the first few eigen-modes when inverting the Kronecker-factors. Importantly, the spectrum decay happens over a constant number of modes irrespectively of the layer width. This allows us to reduce the time complexity of K-FAC from cubic to quadratic in layer width, partially closing the gap w.r.t. SENG (another practical Natural Gradient implementation for Deep learning which scales linearly in width). Randomized Numerical Linear Algebra provides us with the necessary tools to do so. Numerical results show we obtain ≈2.5× reduction in per-epoch time and ≈3.3× reduction in time to target accuracy. We compare our proposed K-FAC sped-up versions SENG, and observe that for CIFAR10 classification with VGG16bn we perform on par with it.