  Efficiently approximating local curvature information of the loss function is
a key tool for optimization and compression of deep neural networks. Yet, most
existing methods to approximate second-order information have high
computational or storage costs, which can limit their practicality. In this
work, we investigate matrix-free, linear-time approaches for estimating
Inverse-Hessian Vector Products (IHVPs) for the case when the Hessian can be
approximated as a sum of rank-one matrices, as in the classic approximation of
the Hessian by the empirical Fisher matrix. We propose two new algorithms as
part of a framework called M-FAC: the first algorithm is tailored towards
network compression and can compute the IHVP for dimension $d$, if the Hessian
is given as a sum of $m$ rank-one matrices, using $O(dm^2)$ precomputation,
$O(dm)$ cost for computing the IHVP, and query cost $O(m)$ for any single
element of the inverse Hessian. The second algorithm targets an optimization
setting, where we wish to compute the product between the inverse Hessian,
estimated over a sliding window of optimization steps, and a given gradient
direction, as required for preconditioned SGD. We give an algorithm with cost
$O(dm + m^2)$ for computing the IHVP and $O(dm + m^3)$ for adding or removing
any gradient from the sliding window. These two algorithms yield
state-of-the-art results for network pruning and optimization with lower
computational overhead relative to existing second-order methods.
Implementations are available at [9] and [17].
