Tensor Normal Training for Deep Learning Models

Yi Ren, Donald Goldfarb

TL;DR

Tensor Normal Training (TNT) is a new second-order optimization method that uses the "tensor normal" distribution to efficiently approximate the Fisher Information Matrix. It offers the performance gains of natural gradient methods with the model-agnostic flexibility of first-order optimizers, outperforming Adam and SGD while remaining computationally competitive with state-of-the-art approximations like KFAC and Shampoo.

What Problem Does This Paper Address?

Training deep neural networks is essentially an optimization problem: finding the minimum of a complex, high-dimensional loss surface. Most researchers use first-order methods like SGD or Adam because they are computationally "cheap"—they only look at the gradient (the slope) at the current point. However, these methods ignore the "curvature" of the landscape, often leading to slow convergence or getting stuck in inefficient paths.

Second-order methods (like Newton’s method) use curvature information to take more direct routes to the minimum, but they are usually impractical for deep learning. The "Fisher Information Matrix," which describes this curvature, is far too large to store or invert for models with millions of parameters. Existing workarounds like KFAC are powerful but require custom implementations for every different type of layer (linear, convolutional, etc.). Others, like Shampoo, are easier to use but rely on the "empirical Fisher," which often fails to capture the true geometry of the problem.

Methods

The authors introduce Tensor Normal Training (TNT). The core innovation is the assumption that the "sampling-based" gradients of a model follow a Tensor Normal (TN) distribution.

Key technical components include:

  • Kronecker Separability: By assuming a TN distribution, the massive covariance matrix of the gradients is broken down into a "Kronecker product" of much smaller matrices (one for each dimension of the parameter tensor). This turns an impossible $1,000,000 \times 1,000,000$ matrix problem into several tiny $100 \times 100$ matrix problems.
  • True Fisher Approximation: Unlike Shampoo, which uses the gradients from the actual training data (Empirical Fisher), TNT performs an extra backward pass using labels sampled from the model's own predictive distribution. This theoretically aligns better with the "Natural Gradient" framework.
  • Model Agnosticism: TNT only needs to know the shape of the parameter tensors. It doesn't care if a tensor belongs to a Transformer, a CNN, or an MLP, making it much easier to implement than layer-specific methods like KFAC.
  • Amortization: To keep costs low, TNT doesn't update the curvature information or compute matrix inverses at every single step. These expensive operations are spread out (amortized) over many iterations.
Memory and time complexity comparison of TNT against other optimizers.

Datasets

The authors evaluated TNT across two main categories of problems:

  1. Autoencoders: Tested on the MNIST (handwritten digits) and FACES (olivetti faces) datasets. These are standard benchmarks for testing how well an optimizer can handle "bottleneck" architectures.
  2. Convolutional Neural Networks (CNNs):
    • ResNet-32 trained on CIFAR-10.
  3. VGG16 trained on CIFAR-100. These represent more modern, practical deep learning workloads.

Key Insights and Ideas

  • The "Shape" is Enough: The most surprising insight is that you can get high-quality curvature information just by looking at the dimensions of the parameter tensors, without needing to know the specific mathematical operations (like convolutions) that produced the gradients.
  • Fisher > Empirical Fisher: The paper provides empirical evidence that using the "true" sampling-based Fisher leads to better optimization trajectories than the "empirical" Fisher used by methods like Shampoo.
  • Avoiding the SVD Bottleneck: While some second-order methods rely on Singular Value Decomposition (SVD), which is slow on GPUs, TNT uses standard matrix inversion. On large models like VGG16, this makes TNT significantly faster in "wall-clock" time than KFAC.

Key Results

  • Optimization Speed: On autoencoder tasks, TNT converged significantly faster than Adam and SGD-m, and matched or exceeded the performance of KFAC and Shampoo.
  • Generalization: On CNNs, TNT achieved validation accuracies comparable to finely-tuned SGD (e.g., 93.08% on CIFAR-10 with ResNet-32), but it reached these results in roughly half the number of epochs.
  • Efficiency: Despite the extra backward pass, TNT's per-iteration time is only slightly higher than first-order methods. In terms of total training time (process time), it was often twice as fast as SGD-m on ResNet-32 because it required so few iterations to converge.
Training loss versus epochs and process time, demonstrating TNT's rapid convergence.

Limitations and Future Work

  • The Extra Backward Pass: TNT requires an additional backward pass to compute the sampling-based gradient. While amortized, this still represents a computational overhead that first-order methods avoid.
  • Scale: The experiments were limited to relatively small datasets (CIFAR, MNIST). The authors acknowledge that testing on "industrial-scale" benchmarks like ImageNet or large-scale NLP models is a necessary next step.
  • Distributed Training: The current paper focuses on single-machine performance. Extending the Kronecker-factored updates to a distributed, multi-GPU environment is an open research direction.
  • Hyperparameters: Like most second-order methods, TNT introduces new hyperparameters (like damping values and update frequencies) that may require tuning for optimal performance.

Summary updated

Abstract

Despite the predominant use of first-order methods for training deep learning models, second-order methods, and in particular, natural gradient methods, remain of interest because of their potential for accelerating training through the use of curvature information. Several methods with non-diagonal preconditioning matrices, including KFAC, Shampoo, and K-BFGS, have been proposed and shown to be effective. Based on the so-called tensor normal (TN) distribution, we propose and analyze a brand new approximate natural gradient method, Tensor Normal Training (TNT), which like Shampoo, only requires knowledge of the shape of the training parameters. By approximating the probabilistically based Fisher matrix, as opposed to the empirical Fisher matrix, our method uses the block-wise covariance of the sampling based gradient as the pre-conditioning matrix. Moreover, the assumption that the sampling-based (tensor) gradient follows a TN distribution, ensures that its covariance has a Kronecker separable structure, which leads to a tractable approximation to the Fisher matrix. Consequently, TNT's memory requirements and per-iteration computational costs are only slightly higher than those for first-order methods. In our experiments, TNT exhibited superior optimization performance to state-of-the-art first-order methods, and comparable optimization performance to the state-of-the-art second-order methods KFAC and Shampoo. Moreover, TNT demonstrated its ability to generalize as well as first-order methods, while using fewer epochs.
BibTeX
@inproceedings{ren2021tensor,
  author = {Yi Ren and Donald Goldfarb},
  title = {{Tensor Normal Training for Deep Learning Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=-t9LPHRYKmi},
}
Figure