Ginger: An Efficient Curvature Approximation with Linear Complexity for
  General Neural Networks
Yongchang Hao Yanshuai Cao Lili Mou
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.