KRONECKER-FACTORED CURVATURE APPROXIMA- TIONS FOR RECURRENT NEURAL NETWORKS
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 statistical structure between the gradient contributions at different time-steps using a chain-structured linear Gaussian graphical model, summing the various cross-moments, 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.
This paper extends the Kronecker-factor Approximate Curvature (K-FAC) optimization method to the setting of recurrent neural networks. The K-FAC method is an approximate 2nd-order optimization method that builds a block diagonal approximation of the Fisher information matrix, where the block diagonal elements are Kronecker products of smaller matrices. 
In order to approximate the Fisher information matrix for RNNs, the authors assume that the derivative of the loss function with respect to each weight matrix at each time step is independent of the length of the sequence, that these derivatives are temporally homogeneous, that the input and derivatives of the output are independent across every point in time, and that either the one-step cross-covariance of these derivatives is symmetric or that the training sequences are effectively infinite in length. Based on these assumptions, the authors show that the Fisher information can be reduced into a form in which the derivatives of the weight matrices can be approximated by a linear Gaussian graphical model and in which the approximate 2nd order method can be efficiently carried out. The authors compare their method to SGD on two language modeling tasks and against Adam for learning differentiable neural computers.
The paper is relatively clear, and the authors do a reasonable job of introducing related work of the original K-FAC algorithm as well as its extension to CNNs before systematically deriving their method for RNNs. The problem of extending the K-FAC algorithm is natural, and the steps taken in this paper seem natural yet also original and non-trivial.  
The main issue that I have with this paper is the lack of theoretical justification or even intuition for the many approximations carried out in the course of approximating the Fisher information matrix. In many instances, it seemed like these approximations were made purely for convenience and tractability without much regard for (even approximate) correctness. This quality of this paper would be greatly  strengthened if it had some bounds on approximation error or even empirical results testing the validity of the assumptions in the paper. Moreover, the experiments do not demonstrate levels of statistical significance in the results, so it is difficult to assert the practical significance of this work.  
Specific comments and questions
Page 2, "r is is". Typo.
Page 2, "DV". I found the introduction of V without any explanation to be confusing.
Page 2, "P_{y|x}(\theta)". The relation between P_{y|x}(\theta) and f(x,\theta) is never explained.
Page 3, "common practice of computing the natural gradient as (F + \lambda I) \nabla h instead of F^{-1} \nabla h". I don't see how the former can serve as a replacement for the latter.
Page 3, "approximate g and a as statistically independent". Even though K-FAC already exists, it would be good to explain why this assumption is reasonable, since similar assumptions are made for the work presented in this paper.
Page 4, "This new approximation, called "KFC", is derived by assuming....". Same as previous comment. It would be good to briefly discuss why these assumptions are reasonable.
Page 5, Independence of T and w_t's, temporal homogeneity of w_t's,, and independence between a_t's and g_t's. I can see why these are convenient assumptions, but why are they reasonable? Moreover, why is it further natural to assume that A and G are temporally homogeneous as well?
Page 7, "But insofar as the w_t's ... encode the relevant information contained in these external variables, they should be approximately Markovian". I am not sure what this means.
Page 7, "The linear-Gaussian assumption meanwhile is a more severe one to make, but it seems necessary for there to be any hope that the required expectations remain tractable". I am not sure that this is a good enough justification for such an idea, unless there are compelling approximation error bounds. 
Page 8, Option 1. In what situations is it reasonable to assume that V_1 is symmetric? 
Pages 8-9, Option 2. What is a good finite sample size in which the assumption that the training sequences are infinitely long is reasonable in practice? Can the error |\kappa(x) - \zeta_T(x)| be translated into a statement on the approximation error?
Page 9, "V_1 = V_{1,0} = ...". Typos (that appear to have been caught by the authors already).
Page 9, "The 2nd-order statistics ... are accumulated through an exponential moving average during training". How sensitive is the performance of this method to the decay rate of the exponential moving average? 
Page 10, "The additional computations required to get the approximate Fisher inverse from these statistics ... are performed asynchronously on the CPU's". I find it a bit unfair to compare SGD to K-FAC in terms of wall clock time without also using the extra CPU's for SGD as well (e.g. via Hogwild or synchronous parallel SGD).
Page 10, "The hyperparameters of our approach...". What is the sensitivity of the experimental results to these hyperparameters? Moreover, how sensitive are the results to initialization?
Page 10, "we found that each parameter update of our method required about 80% more wall-clock time than an SGD update". How much of this is attributed to the fact that the statistics are computed asynchronously?
Pages 10-12, Experiments. There are no error bars in any of the plots, so it is impossible to ascertain the statistical significance of any of these results. 
Page 11: Figure 2. Where is the Adam batchsize 50 line in the left plot? Why did the Adam batchsize 200 line disappear halfway through the right plot?