NG+ : A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning

Minghan Yang, Dong Xu, Qiwen Cui, Zaiwen Wen, Pengxiang XuarXiv 2021 · OpenReview

Abstract

In this paper, a novel second-order method called NG+ is proposed. By following the rule "the shape of the gradient equals the shape of the parameter", we define a generalized fisher information matrix (GFIM) using the products of gradients in the matrix form rather than the traditional vectorization. Then, our generalized natural gradient direction is simply the inverse of the GFIM multiplies the gradient in the matrix form. Moreover, the GFIM and its inverse keeps the same for multiple steps so that the computational cost can be controlled and is comparable with the first-order methods. A global convergence is established under some mild conditions and a regret bound is also given for the online learning setting. Numerical results on image classification with ResNet50, quantum chemistry modeling with Schnet, neural machine translation with Transformer and recommendation system with DLRM illustrate that NG+ is competitive with the state-of-the-art methods.

Introduction

In deep learning, first-order methods like SGD and Adam are the industry standard because they are computationally cheap and easy to scale. However, they often require many iterations to converge because they ignore the "curvature" of the loss landscape. Second-order methods, such as Natural Gradient Descent, use this curvature information to take more efficient steps, but they are traditionally plagued by massive computational and memory overheads.

For a parameter matrix of size $m \times n$, the standard Fisher Information Matrix (FIM) is a gargantuan $(mn) \times (mn)$ matrix. Inverting such a matrix is impossible for modern deep learning models. While existing approximations like KFAC or Shampoo help, they still introduce significant complexity. The authors of NG+ propose a second-order method that is memory-efficient enough to compete directly with first-order optimizers in wall-clock time.

Methodology

The core innovation of NG+ lies in how it defines and updates its curvature information:

Generalized Fisher Information Matrix (GFIM)

Instead of flattening gradients into long vectors, NG+ respects the parameter structure. It defines the GFIM using direct matrix products of gradients ($G G^\top$ or $G^\top G$). This results in a matrix of size $m \times m$ or $n \times n$—whichever is smaller—drastically reducing the cost of inversion.

Multi-Step Strategy

To further save time, the GFIM and its inverse are not recomputed at every iteration. Instead, they are updated every $T$ steps (e.g., every 500 iterations). Between updates, the algorithm reuses the old curvature information, making the per-step cost nearly identical to first-order methods.

Scalability and Flexibility

For exceptionally large layers, such as embedding layers in recommendation systems, NG+ employs sketching techniques (random uniform row sampling) and block-diagonal approximations. The method also incorporates momentum to accumulate curvature statistics, ensuring stability during training.

Experimental Evaluation

The authors evaluated NG+ across diverse benchmarks, including ImageNet-1k (ResNet50), QM9/MatProj (SchNet), IWSLT14 (Transformer), and the Criteo dataset (DLRM).

Comparison of training and testing accuracy versus wall-clock time for NG+, SGD, LARS, and KFAC on the ImageNet-1k dataset.

As shown in the figure above, NG+ consistently outperforms or matches state-of-the-art optimizers in terms of wall-clock time. On ImageNet, NG+ reached the target 75.9% top-1 accuracy in just 6.7 hours (40 epochs), representing a 37% reduction in total training time over SGD (10.9 hours). In quantum chemistry tasks, NG+ reached validation targets nearly twice as fast as Adam.

Conclusion

NG+ demonstrates that the natural matrix structure of neural network weights can be exploited to simplify second-order optimization without losing its essential benefits. By amortizing the complexity of matrix inversion over multiple steps, NG+ achieves high throughput and superior convergence. Future work includes further hardware-level optimizations and studies on parallel efficiency for extremely large-scale models.

Summary updated

Abstract

In this paper, a novel second-order method called NG+ is proposed. By following the rule ``the shape of the gradient equals the shape of the parameter", we define a generalized fisher information matrix (GFIM) using the products of gradients in the matrix form rather than the traditional vectorization. Then, our generalized natural gradient direction is simply the inverse of the GFIM multiplies the gradient in the matrix form. Moreover, the GFIM and its inverse keeps the same for multiple steps so that the computational cost can be controlled and is comparable with the first-order methods. A global convergence is established under some mild conditions and a regret bound is also given for the online learning setting. Numerical results on image classification with ResNet50, quantum chemistry modeling with Schnet, neural machine translation with Transformer and recommendation system with DLRM illustrate that GN+ is competitive with the state-of-the-art methods.
BibTeX
@misc{yang2021ng,
  author = {Minghan Yang and Dong Xu and Qiwen Cui and Zaiwen Wen and Pengxiang Xu},
  title = {{NG+ : A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning}},
  year = {2021},
  eprint = {2106.07454},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.07454},
}
Figure