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

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