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.
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.
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