SKFAC: Training Neural Networks With Faster Kronecker-Factored Approximate Curvature

Zedong Tang, Fenlong Jiang, Maoguo Gong, Hao Li, Yue Wu, Fan Yu, Zidong Wang, Min WangCVPR 2021 · OpenReview

Abstract

The bottleneck of computation burden limits the widespread use of the 2nd order optimization algorithms for training deep neural networks. In this paper, we present a computationally efficient approximation for natural gradient descent, named Swift Kronecker-Factored Approximate Curvature (SKFAC), which combines Kronecker factorization and a fast low-rank matrix inversion technique. Our research aims at both fully connected and convolutional layers. For the fully connected layers, by utilizing the low-rank property of Kronecker factors of Fisher information matrix, our method only requires inverting a small matrix to approximate the curvature with desirable accuracy. For convolutional layers, we propose a way with two strategies to save computational efforts without affecting the empirical performance by reducing across the spatial dimension or receptive fields of feature maps. Specifically, we propose two effective dimension reduction methods for this purpose: Spatial Subsampling and Reduce Sum. Experimental results of training several deep neural networks on Cifar-10 and ImageNet-1k datasets demonstrate that SKFAC can capture the main curvature and yield comparative performance to K-FAC. The proposed method bridges the wall-clock time gap between the 1st and 2nd order algorithms.

Introduction

Training deep neural networks involves a fundamental trade-off between per-iteration speed and convergence efficiency. First-order methods like SGD and Adam are computationally inexpensive but often require many iterations to navigate complex loss landscapes. Second-order methods, such as Natural Gradient Descent (NGD), leverage the Fisher Information Matrix (FIM) to capture curvature, enabling larger and more effective steps. However, the FIM's massive size makes direct inversion impractical. While Kronecker-Factored Approximate Curvature (K-FAC) mitigates this by factorizing the FIM, the computational overhead of inverting these factors remains a significant bottleneck. SKFAC is designed to eliminate this "wall-clock time gap" by introducing highly efficient approximation techniques.

Methodology

SKFAC optimizes the inversion process through three primary innovations:

1. Low-Rank Inversion

In typical mini-batch training, the rank of activation and gradient matrices is bounded by the batch size ($M$). When $M$ is significantly smaller than the layer width ($n$), the Kronecker factors are effectively low-rank. By applying the Woodbury Matrix Identity, SKFAC transforms the standard $O(n^3)$ matrix inversion into a much more efficient $O(M^3)$ operation.

2. Dimensionality Reduction for CNNs

Convolutional layers introduce spatial dimensions that exacerbate matrix sizes. SKFAC addresses this with two strategies:

  • Spatial Subsampling (SKFAC-SS): Randomly samples a subset of spatial patches to estimate curvature, maintaining an unbiased estimate of the FIM while reducing data volume.
  • Reduce Sum (SKFAC-RS): Averages activations across spatial dimensions, significantly lowering the matrix rank before inversion.

3. Distributed Efficiency

In multi-GPU environments, SKFAC minimizes communication latency by transmitting low-rank factors instead of full approximate matrices, further accelerating training.

Time breakdown showing the drastic reduction in inversion time achieved by SKFAC variants compared to standard K-FAC.

Key Results

Empirical evaluations on Cifar-10 and ImageNet-1k demonstrate that SKFAC maintains the convergence quality of K-FAC while drastically reducing wall-clock time.

  • Inversion Efficiency: As shown in the time breakdown, matrix inversion in standard K-FAC can consume nearly the entire optimization step. SKFAC reduces this cost to approximately 3.3% - 3.5% of total computation time.
  • Wall-Clock Speedup: On ResNet-50/ImageNet, SKFAC-RS reached the 75% accuracy threshold in 1189 minutes, a 23% reduction compared to K-FAC (1544 minutes) and significantly faster than SGD (1834 minutes).
  • Convergence Stability: Despite using low-rank approximations, SKFAC captures essential curvature information. The use of exponentially decaying moving averages ensures stable curvature estimates throughout training.
Validation error vs. wall-clock time on ImageNet-1k, illustrating that SKFAC variants reach the error threshold significantly faster than K-FAC and SGD.

Conclusion

SKFAC successfully bridges the performance gap between first-order and second-order optimization. By leveraging the low-rank nature of mini-batch gradients and spatial redundancy in CNNs, it provides a scalable, high-speed alternative to K-FAC. Future work will explore extending these low-rank techniques to Transformer architectures and specialized hardware implementations.

Summary updated

Abstract

The bottleneck of computation burden limits the widespread use of the 2nd order optimization algorithms for training deep neural networks. In this paper, we present a computationally efficient approximation for natural gradient descent, named Swift Kronecker-Factored Approximate Curvature (SKFAC), which combines Kronecker factorization and a fast low-rank matrix inversion technique. Our research aims at both fully connected and convolutional layers. For the fully connected layers, by utilizing the low-rank property of Kronecker factors of Fisher information matrix, our method only requires inverting a small matrix to approximate the curvature with desirable accuracy. For convolutional layers, we propose a way with two strategies to save computational efforts without affecting the empirical performance by reducing across the spatial dimension or receptive fields of feature maps. Specifically, we propose two effective dimension reduction methods for this purpose: Spatial Subsampling and Reduce Sum. Experimental results of training several deep neural networks on Cifar-10 and ImageNet-1k datasets demonstrate that SKFAC can capture the main curvature and yield comparative performance to K-FAC. The proposed method bridges the wall-clock time gap between the 1st and 2nd order algorithms.
BibTeX
@inproceedings{tang2021skfac,
  author = {Zedong Tang and Fenlong Jiang and Maoguo Gong and Hao Li and Yue Wu and Fan Yu and Zidong Wang and Min Wang},
  title = {{SKFAC: Training Neural Networks With Faster Kronecker-Factored Approximate Curvature}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2021},
  url = {https://openreview.net/forum?id=eVkEt0tucb},
}
Figure