Ginger: An Efficient Curvature Approximation with Linear Complexity for General Neural Networks
This addresses the scalability issue of second-order optimization for deep learning practitioners, enabling broader application with reduced hardware constraints.
The paper tackles the high computational cost of second-order optimization in deep learning by proposing Ginger, an efficient eigendecomposition method for the inverse of the generalized Gauss-Newton matrix, achieving linear memory and time complexity per iteration and demonstrating effectiveness across various tasks and model architectures.
Second-order optimization approaches like the generalized Gauss-Newton method are considered more powerful as they utilize the curvature information of the objective function with preconditioning matrices. Albeit offering tempting theoretical benefits, they are not easily applicable to modern deep learning. The major reason is due to the quadratic memory and cubic time complexity to compute the inverse of the matrix. These requirements are infeasible even with state-of-the-art hardware. In this work, we propose Ginger, an eigendecomposition for the inverse of the generalized Gauss-Newton matrix. Our method enjoys efficient linear memory and time complexity for each iteration. Instead of approximating the conditioning matrix, we directly maintain its inverse to make the approximation more accurate. We provide the convergence result of Ginger for non-convex objectives. Our experiments on different tasks with different model architectures verify the effectiveness of our method. Our code is publicly available.