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