Kronecker-factor Approximate Curvature (Martens & Grosse, 2015) (K-FAC) is a 2nd-order optimization method which has been shown to give state-of-the-art performance on large-scale neural network optimization tasks (Ba et al., 2017).   It is based on an approximation to the Fisher information matrix (FIM) that makes assumptions about the particular structure of the network and the way it is parameterized. The original K-FAC method was applicable only to fully-connected networks, although it has been recently extended by Grosse & Martens (2016) to handle convolutional networks as well. In this work we extend the method to handle RNNs by introducing a novel approximation to the FIM for RNNs. This approximation works by modelling the covariance structure between the gradient contributions at different time-steps using a chain-structured linear Gaussian graphical model, summing the various cross-covariances, and computing the inverse in closed form. We demonstrate in experiments that our method significantly outperforms general purpose state-of-the-art optimizers like SGD with momentum and Adam on several challenging RNN training tasks. As neural networks have become ubiquitous in both research and applications the need to efficiently train has never been greater. The main workhorses for neural net optimization are stochastic gradient descent (SGD) with momentum and various 2nd-order optimizers that use diagonal curvature-matrix approximations, such as RMSprop BID32 and Adam BID1 . While the latter are typically easier to tune and work better out of the box, they unfortunately only offer marginal performance improvements over well-tuned SGD on most problems.Because modern neural networks have many millions of parameters it is computationally too expensive to compute and invert an entire curvature matrix and so approximations are required. While early work on non-diagonal curvature matrix approximations such as TONGA BID17 and the Hessian-free (HF) approach BID20 BID21 BID4 BID30 demonstrated the potential of such methods, they never achieved wide adoption due to issues of scalability (to large models in the case of the former, and large datasets in the case of the latter).Motivated in part by these older results and by the more recent success of centering and normalization methods (e.g. BID31 BID34 BID15 a new family of methods has emerged that are based on non-diagonal curvature matrix approximations the rely on the special structure of neural networks. Such methods , which include Kronecker-factored approximated curvature (K-FAC) BID24 , Natural Neural Nets BID5 , Practical Riemannian Neural Networks BID18 , and others BID29 , have achieved state-of-the-art optimization performance on various challenging neural network training tasks and benchmarks.While the original K-FAC method is applicable only to standard feed-forward networks with fully connected layers, it has recently been extended to handle convolutional networks BID8 through the introduction of the "Kronecker Factors for Convolution" (KFC) approximation. BID2 later developed a distributed asynchronous version which proposed additional approximations to handle very large hidden layers.In this work we develop a new family of curvature matrix approximations for recurrent neural networks (RNNs) within the same design space. As in the original K-FAC approximation and the KFC approximation, we focus on the Fisher information matrix (a popular choice of curvature matrix), and show how it can be approximated in different ways through the adoption of various approximating assumptions on the statistics of the network's gradients. Our main novel technical contribution is an approximation which uses a chain-structured linear Gaussian graphical model to describe the statistical relationship between gradient contributions coming from different time-steps. Somewhat remarkably, it is possible to sum the required cross-moments to obtain a Fisher approximations which has enough special algebraic structure that it can still be efficiently inverted. In experiments we demonstrate the usefulness of our approximations on several challenging RNN training tasks. We have presented a new family of approximations to the Fisher information matrix of recurrent neural networks (RNNs), extending previous work on Kronecker-factored approximations. With this contribution, recurrent networks can now finally be trained with the K-FAC optimization method. We have demonstrated that our new approximations substantially reduce the required number of iterations for convergence vs standard baseline optimizers on several realistic tasks. And we have also shown that in a modern distributed training setup this results in a substantial savings in wallclock time as well.Jason Weston, Sumit Chopra, and Antoine Bordes. A SUPPLEMENTARY COMPUTATIONS A.1 PROOFS FOR SECTION 3.5.1Proposition 1 GivenF DISPLAYFORM0 , which can be seen as follows: DISPLAYFORM1 And using DISPLAYFORM2 Setting d = 1 and multiplying both sides by V 0 (which is assumed to be invertible) one can also derive the following simple formula for Ψ: DISPLAYFORM3 To proceed from here we define a "transformed" version of the original chain-structured linearGaussian graphical model whose variables areŵ t = V −1/2 0 w t . (Here we assume that V 0 is invertible -it is symmetric by definition.) All quantities related to the original model have their analogues in the transformed model, which we indicate with the hat symbol·.In the transformed model the 2nd-order moments of theŵ t 's are given bŷ DISPLAYFORM4 We observe thatV 0 = I.Analogously to the original model, the transformed version obeyŝ DISPLAYFORM5 =V 1 (usingV 0 = I). This can be seen by noting that DISPLAYFORM6 It also remains true that the spectral radius ofΨ is less than 1, which can be seen in at least one of two ways: by noticing that the transformed model is well-defined in the infinite limit if and only if the original one is, or thatΨ DISPLAYFORM7 is a similar matrix to Ψ (in the technical sense) and hence has the same eigenvalues.As the transformed model is isomorphic to the original one, all of the previously derived relationships which held for it also hold here, simply by replacing each quantity with its transformed version (denoted by the hat symbol·).Given these relations (included the transformed analogue of equation 5) we can expressF T aŝ DISPLAYFORM8 It is a well-known fact that one can evaluate rational functions, and functions that are the limiting values of sequences of rational functions, with matrix arguments. This is done by replacing scalar multiplication with matrix multiplication, division with matrix inversion, and scalar constants with scalar multiples of the identity matrix, etc. Note that because sums of powers and inverses of matrices are co-diagonalizable/commutative when the matrices themselves are, there is no issue of ambiguity caused by mixing commutative and non-commutative algebra in this way.Moreover, the value of some such function f (x), given a matrix argument B, is DISPLAYFORM9 DISPLAYFORM10 undefined from some i, either because of a division by zero, or because the limit which defines f (x) doesn't converge for x = [b] i , then f (B) doesn't exist for that particular B (and otherwise it does).We observe that our above expression for F T can be rewritten aŝ DISPLAYFORM11 By Proposition 3 in Appendix B.1, we have for x = 1 that DISPLAYFORM12 Let U diag(ψ)U −1 =Ψ be the eigendecomposition ofΨ. BecauseΨ has a spectral radius less than 1, we have |[ψ] i | < 1 for each i (so that in particular [ψ] i = 1), and thus we can evaluate ζ T (Ψ) and ζ T (Ψ ) according to the above formula for ζ T (x).
We extend the K-FAC method to RNNs by developing a new family of Fisher approximations. The authors extends the K-FAC method to RNNs and presents 3 ways of approximating F, showing optimization results on 3 datasets, which outperforms ADAM in both number of updates and computation time. Proposes to extend the Kronecker-factor Appropriate Curvature optimization method to the setting of recurrent neural networks. The authors present a second-order method that is specifically designed for RNNs