SOFIM: Stochastic Optimization Using Regularized Fisher Information Matrix

Mrinmay Sen, A. Kai Qin, Gayathri C, Raghu Kishore N, Yen-Wei Chen, Balasubramanian Raman

TL;DR

This paper introduces SOFIM, a novel stochastic optimization method that leverages a regularized Fisher Information Matrix (FIM) to approximate the Hessian. By combining this with the Sherman-Morrison matrix inversion and Adam's first-moment estimation, SOFIM achieves faster convergence than SGD with momentum and other second-order methods, while maintaining similar computational complexity.

What Problem Does This Paper Address?

Optimizing probabilistic models, crucial for many AI applications like image classification, often involves minimizing a loss function. While first-order methods like Stochastic Gradient Descent (SGD) are computationally efficient for large datasets, they suffer from slow convergence. Second-order methods, like Newton's method, offer faster convergence by using the Hessian matrix (which captures curvature information), but calculating and storing the full Hessian or its inverse becomes computationally prohibitive for large-scale machine learning models. Existing approximations to the Hessian, while helpful, still face challenges in terms of computational cost or effectiveness. This paper aims to bridge this gap by developing a second-order optimization method that is both computationally efficient and achieves faster convergence than first-order methods.

Methods

SOFIM introduces a novel approach by:

  • Regularized Fisher Information Matrix (FIM): Instead of the full Hessian, SOFIM uses a regularized FIM as an approximation. The FIM is related to the expected Hessian for probabilistic models. By adding a regularization term ($\rho I$), they create a more stable and computationally manageable approximation.
  • Sherman-Morrison Matrix Inversion: To efficiently compute the update direction (which involves inverting a matrix related to the FIM), SOFIM employs the Sherman-Morrison formula. This allows for direct calculation of the inverse without explicitly forming and inverting the full matrix, significantly reducing computational cost.
  • First Moment Estimation (Adam-like): To address the issue of non-stationary objectives arising from heterogeneous data in mini-batches, SOFIM incorporates a bias-corrected first moment estimate of the gradient, similar to the Adam optimizer. This helps in adapting the learning process to the changing data distribution.

Essentially, SOFIM combines the benefits of second-order information (via FIM) with efficient computational techniques (Sherman-Morrison) and adaptive learning strategies (first moment estimation).

Datasets

The paper evaluates SOFIM on standard image classification benchmarks:

  • CIFAR10
  • CIFAR100
  • SVHN

These datasets are commonly used for evaluating deep learning models and optimization algorithms.

Key Insights and Ideas

  • FIM as a practical Hessian approximation: The paper demonstrates that a regularized FIM can serve as an effective and computationally feasible substitute for the Hessian in large-scale optimization, offering a good balance between curvature information and computational cost.
  • Sherman-Morrison for efficient updates: The clever application of the Sherman-Morrison formula allows SOFIM to directly compute the Newton update direction without the prohibitive cost of inverting large matrices, making second-order methods more accessible.
  • Synergy of Adam-like adaptation and second-order information: By combining the adaptive learning capabilities of Adam (first moment estimation) with the curvature information from the FIM, SOFIM can handle non-stationary objectives more effectively and converge faster.
  • Improved convergence without increased complexity: A significant finding is that SOFIM achieves faster convergence rates compared to SGD with momentum and other state-of-the-art methods, while maintaining the same computational time and space complexity as SGD with momentum.

Key Results

The experimental results, visualized in Figures 1-9, consistently show that SOFIM:

  • Outperforms SGD with momentum: SOFIM demonstrates significantly faster convergence in terms of both training and test losses across various datasets and models.
  • Achieves higher test accuracy: SOFIM generally reaches higher test accuracies compared to SGD with momentum and other compared methods.
  • Competes with state-of-the-art Newton methods: SOFIM shows comparable or superior performance to methods like Nyström-SGD, L-BFGS, and AdaHessian, often with better convergence speed.
  • Robustness to regularization parameter: The paper investigates the effect of the regularization parameter $\rho$ (Figure 9), finding that $\rho=0.5$ generally yields the best performance, indicating a good balance between the FIM approximation and regularization.

Limitations and Future Work

  • Limitations: The paper notes that Nyström-SGD and L-BFGS sometimes perform less well, potentially due to their requirement for a larger number of selected Hessian columns or iterations, leading to increased time and space complexities compared to SOFIM. The paper also mentions that for $\rho < 0$, SOFIM performs poorly, highlighting the importance of the regularization parameter.
  • Future Work: The authors plan to extend SOFIM to a wider range of machine learning tasks, hybridize it with evolutionary algorithms for enhanced performance, and further explore its efficacy and potential shortcomings.

Summary updated

Abstract

This paper introduces a new stochastic optimization method based on the regularized Fisher information matrix (FIM), named SOFIM, which can efficiently utilize the FIM to approximate the Hessian matrix for finding Newton’s gradient update in large-scale stochastic optimization of machine learning models. It can be viewed as a variant of natural gradient descent, where the challenge of storing and calculating the full FIM is addressed through making use of the regularized FIM and directly finding the gradient update direction via Sherman-Morrison matrix inversion. Additionally, like the popular Adam method, SOFIM uses the first moment of the gradient to address the issue of non-stationary objectives across mini-batches due to heterogeneous data. The utilization of the regularized FIM and Sherman-Morrison matrix inversion leads to the improved convergence rate with the same space and time complexities as stochastic gradient descent (SGD) with momentum. The extensive experiments on training deep learning models using several benchmark image classification datasets demonstrate that the proposed SOFIM outperforms SGD with momentum and several state-of-the-art Newton optimization methods in term of the convergence speed for achieving the pre-specified objectives of training and test losses as well as test accuracy.
BibTeX
@inproceedings{sen2024sofim,
  author = {Mrinmay Sen and A. Kai Qin and Gayathri C and Raghu Kishore N and Yen-Wei Chen and Balasubramanian Raman},
  title = {{SOFIM: Stochastic Optimization Using Regularized Fisher Information Matrix}},
  booktitle = {IJCNN},
  year = {2024},
  url = {https://openreview.net/forum?id=JHMp9rEQCj},
}
Figure