2022

Efficient Approximations of the Fisher Matrix in Neural Networks using Kronecker Product Singular Value Decomposition

Koroko, Abdoulaye, Anciaux-Sedrakian, Ani, Gharbia, Ibtihel Ben et al.

Understand

Several studies have shown the ability of natural gradient descent to minimize the objective function more efficiently than ordinary gradient descent based methods.

However, the bottleneck of this approach for training deep neural networks lies in the prohibitive cost of solving a large dense linear system corresponding to the Fisher Information Matrix (FIM) at each iteration.
This has motivated various approximations of either the exact FIM or the empirical one.
The most sophisticated of these is KFAC, which involves a Kronecker-factored block diagonal approximation of the FIM.

Built on

A stochastic approximation method
Robbins, H. and Monro, S · 1951
Earlier work this paper cites.
Calculating the singular values and pseudo-inverse of a matrix
Golub, G. and Kahan, W · 1965
Earlier work this paper cites.
The convergence of a class of double-rank minimization algorithms 1. General considerations
Broyden, C. G · 1970
Earlier work this paper cites.
A new approach to variable metric algorithms
Fletcher, R · 1970
Earlier work this paper cites.
A family of variable-metric methods derived by variational means
Goldfarb, D · 1970
Earlier work this paper cites.
Conditioning of quasi-Newton methods for function minimization
Shanno, D. F · 1970
Earlier work this paper cites.
Improving the convergence of back-propagation learning with second order methods
Becker, S. and Le Cun, Y · 1988
Earlier work this paper cites.
A theoretical framework for back-propagation
LeCun, Y · 1988
Earlier work this paper cites.
On the limited memory BFGS method for large scale optimization
Liu, D. C. and Nocedal, J · 1989
Earlier work this paper cites.
Approximation with Kronecker products
Van Loan, C. F. and Pitsianis, N · 1993
Earlier work this paper cites.
Natural gradient works efficiently in learning
Amari, S.-I · 1998
Earlier work this paper cites.
Methods of Information Geometry , volume 191 of Translations of Mathematical Monographs
Amari, S.-I. and Nagaoka, H · 2000
Earlier work this paper cites.
On “natural” learning and pruning in multilayered perceptrons
Heskes, T · 2000
Earlier work this paper cites.

Similar

The ubiquitous Kronecker product
van Loan, C. F · 2000
Cited alongside, same era.
Fast curvature matrix-vector products for second-order gradient descent
Schraudolph, N. N · 2002
Cited alongside, same era.
Practical quasi-Newton methods for training deep neural networks, 2020
Original
Goldfarb, D., Ren, Y., and Bahamou, A · 2006
Cited alongside, same era.
Reducing the dimensionality of data with neural netwoks
Hinton, G. E. and Salakhutdinov, R. R · 2006
Cited alongside, same era.
Numerical Optimization
Nocedal, J. and Wright, S. J · 2006
Cited alongside, same era.
Topmoumoute online natural gradient algorithm
Le Roux, N., Manzagol, P.-A., and Bengio, Y · 2008
Cited alongside, same era.
Deep learning via Hessian-free optimization
Martens, J · 2010
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
Duchi, J., Hazan, E., and Singer, Y · 2011
Cited alongside, same era.
Numerical Methods for Large Eigenvalue Problems , volume 6
Saad, Y · 2011
Cited alongside, same era.
Two-level K-FAC preconditioning for deep learning
Original
Tselepidis, N., Kohler, J., and Orvieto, A · 2011
Cited alongside, same era.
Lecture 6.5 RMSProp: Divide the gradient by a running average of its recent magnitude
Tieleman, T. and Hinton, G · 2012
Cited alongside, same era.
Revisiting natural gradient for deep networks
Original
Pascanu, R. and Bengio, Y · 2013
Cited alongside, same era.

Then

New insights and perspectives on the natural gradient method
Original
Martens, J · 2014
Later among the works it cites.
Parallel training of DNNs with natural gradient and parameter averaging
Original
Povey, D., Zhang, X., and Khudanpur, S · 2014
Later among the works it cites.
Adam: A method for stochastic optimization
Original
Kingma, D. P. and Ba, J · 2015
Later among the works it cites.
Optimizing neural networks with Kronecker-factored approximate curvature
Martens, J. and Grosse, R · 2015
Later among the works it cites.
Riemannian metrics for neural networks I: feedforward networks
Ollivier, Y · 2015
Later among the works it cites.
A Kronecker-factored approximate Fisher matrix for convolution layers
Grosse, R. and Martens, J · 2016
Later among the works it cites.
Distributed second-order optimization using Kronecker-factored approximations
Ba, J., Grosse, R., and Martens, J · 2017
Later among the works it cites.
Practical Gauss-Newton optimisation for deep learning
Botev, A., Ritter, H., and Barber, D · 2017
Later among the works it cites.
Fast approximate natural gradient descent in a Kronecker factored eigenbasis
George, T., Laurent, C., Bouthillier, X., Ballas, N., and Vincent, P · 2018
Later among the works it cites.
Kronecker-factored curvature approximations for recurrent neural networks
Martens, J., Ba, J., and Johnson, M · 2018
Later among the works it cites.
Limitations of the empirical Fisher approximation for natural gradient descent
Kunstner, F., Hennig, P., and Balles, L · 2019
Later among the works it cites.
PyTorch: An imperative style, high-performance deep learning library
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…