Revisiting Natural Gradient for Deep Networks
Authors: Razvan Pascanu, Yoshua Bengio
ICLR 2014

Abstract: The aim of this paper is three-fold. First we show that Hessian-Free (Martens, 2010) and Krylov Subspace Descent (Vinyals and Povey, 2012) can be described as implementations of natural gradient descent due to their use of the extended Gauss-Newton approximation of the Hessian. Secondly we re-derive natural gradient from basic principles, contrasting the difference between two versions of the algorithm found in the neural network literature, as well as highlighting a few differences between natural gradient and typical second order methods. Lastly we show empirically that natural gradient can be robust to overfitting and particularly it can be robust to the order in which the training data is presented to the model.


Peer review:
[Review]:
This paper looks at some connections between the natural gradient and updates based on the Gauss-Newton matrix which have appeared in various recent optimization algorithms for deep networks.  Some of these connections appear to be already mapped out, but the paper presents a unified picture and fills in additional details.  There are some interesting insights about how this interpretation can allow unlabelled data to be used in truncated Newton style methods like Hessian-free optimization (HF).  

Later in the paper connections between Krylov Subspace Descent (KSD) and natural conjugate gradient algorithms, and a new algorithm is proposed which tries to combine the supposed advantages of several of these approaches.    This algorithm, which is a potentially interesting twist on HF that involves taking the previous update and the new proposed update (which will be an approximation of the natural gradient) and jointly optimizing over both of these.  However, I'm not convinced these is a better thing to do than just initialize CG from using previous iterations. While the experiments did demonstrate a distinct advantage to doing it this way in the setting involving no preconditioning, I remain skeptical.  

Overall I think this is a solid paper, and should be accepted.  However, I really want the authors to address my various concerns before I can strongly recommend it.


Detailed comments:

Page 2: The notation in the second paragraph of section 2 is odd.  Although I understand what you mean, I don't think it is proper to use 'R^P->(R^N->[0,inf))'.   Also, 'p_theta(z) = F(theta)' is odd.  Shouldn't it be something like 'p_theta(z) = F(theta)(z)'?

Page 2:  You should explain how a matrix-valued function of theta defines a metric on the space.  This is well known to mathematicians, but many in this audience won't be familiar with these concepts.

Page 2:  Why use row vectors instead of columns vectors?  While technically valid, this will make reading your paper require more mental effort on part of the reader.

Page 2:  'Natural gradient' is not an algorithm, it is a vector quantity.  You should say 'natural gradient descent' or something like that.   I know it is not uncommon to hear people say 'natural gradients' when implicitly referring to the algorithm, not the quantity, but I think this is a bad habit that should be avoided.

Page 2:  'moving in the direction' -> 'moving some given distance in the direction'

Page 2:  What do you mean by 'the change induced in our model is constant'?  Natural gradient descent type algorithms can use dynamically changing step sizes.  Did you mean to say, 'some given value'?

Moreover, this statement doesn't distinguish natural gradient descent from gradient descent.  Gradient descent can also be thought of as (approximately) minimizing L w.r.t. some metric of change.  It may happen to be a parametrization-dependent metric, but the statement is still valid.

Moreover, eqn. 2 isn't even what happens with algorithms that use the natural gradient.  They don't minimize L w.r.t. to some target change in KL, since this is typically intractable.  Instead, they use an approximation.  I know later on you talk about how this approximation is realized, but the point is that algorithms that use the natural gradient are not *defined* in terms of eqn. 2.  They are *defined* in terms of the iteration which can be interpreted as an approximation of this.

Page 4:  This matrix used by Le Roux and others I think is called the 'empirical Fisher', perhaps due to its connection with the empirical distribution over t.  I think it was in a paper of Schraudolph that I remember hearing this term.

Page 4: I would suggest you call it 'Hessian-free optimization'.  It sounds weird to call it just 'Hessian-free', despite the lack of O in the commonly used acronym.

Page 6:   Eqn. 16 isn't exactly the same as the one from Martens (2010).  In particular, you seem to be implicitly using update'*G*update = grad'*inv(G)C*grad in the denominator.  This is only true if update = inv(G)*grad.  But this will only be true if the conjugate gradient method used converges, and in general it won't.

Page 6: The citation here (and also likely the corresponding one in the intro) is wrong.  'Structural damping' is from: 'Learning Recurrent Neural Networks with Hessian-Free Optimization', not the paper cited.

Page 6: Could you explain what you mean by 'fixed coefficient of 1 for the regularization term'?  As far as I understand, the structural damping term can have an arbitrary coefficient in front of it in the original paper.

Page 6: 'just initializing the linear solver close to a solution'.  Actually, this is arguably more complex type of initialization than the one used in KSD.  It actually changes each basis vector of the Krylov subspace, instead of augmenting the space with just one extra direction. 

Page 6: I'm a bit confused about what is going on in section 6.  In particular, what is being said that is particular to the Fisher  information matrix interpretation of G?  Any relationship of KSD to kind of non-linear CG type algorithm seems to be a completely different issue (and one which is not really explored in this section anyway).

Page 7:  You talk about using the same data to estimate the gradient and curvature/metric matrix introducing a bias.  

However, this is going to be true for *any* choice of partial data for these computation.  In particular, your suggestion of taking independent samples for both will NOT make the estimate unbiased.  This is because the inverse of an unbiased estimator is not unbiased estimator of the inverse, and you need to take inverses of the matrix.  Thus this doesn't address the biasedness problem, it just gives a different biased result.

Moreover, there are intuitive and technical reasons not to use different data for these estimates.  See the article 'Training Deep and Recurrent Neural Networks with Hessian-Free Optimization', section 12.1.

Despite the potential issues for optimization, I think it is nonetheless an interesting observation that unlabelled data can be used to compute G in situations where there is a lot more of it than labelled data.  But keep in mind that, in the end, the optimization is driven by the gradient and not by G, and as long as the objective function is convex, this can't possibly help the overfitting problem.  Insofar as it seems to help for non-convex objectives, it is a bit mysterious.  It would be good to understand what is going on here, although I suspect that a theoretical account of this phenomenon would be nearly impossible to give due to the complexity of all of the pieces involved.


Page 8:  It is hard to follow what is happenning in the pseudo code.  Some questions I had were:

Where are these 'newly sampled examples' coming from?

What is the purpose of the first split into 'two large chunks'?

Are the 'heldout examples' from the segment that was 'replaced'?

By 'output of the trained model' you mean the output of the network or the objective functions scores for different cases?

Figure 2:  In figure 8, what is being plotted on the x-axis?  Is that the segment index?  Why should this quantity be monotonic in the index, which seems completely arbitrary due to the presumably random assignment of cases to segments?

Page 8:  Were you running batch NGD here?   Wouldn't comparing a batch method to a stochastic method account for the 'variance' effects?

Also, how can you be sure that you are being fair when comparing the two methods in terms of learning rates.  It's probably not fair to compare them with the same learning rate, since both methods have completely different characteristics.  But then what values can you choose?   Maybe the only fair way would be to pick values that let both methods get to some destination error in roughly the same amount of time?  Even this seems not completely fair, but might be the best compromise.


Page 8:  I'm confused about what this section is saying.  The hypothesis about the 'path that induces least variance' is never clearly articulated until after the results are presented.  Also, you should emphasize here that you are talking about variance of the final outputs.


Page 8:  Why even run these variance experiments with these different chunks/segments at all?  Why not just take multiple runs with some fixed dataset and observe the variance?  What does this cross-validation style chunking actually add to the experiment?


Page 9:  I don't know if it is correct to call NCG a 2nd-order method.  In some sense, it meets that exact definition of a first order method: the iterates are linear combinations of gradients from previous iterations.

Page 9:  What do you mean by 'real conjugate direction'?  Conjugacy, as far as I know, is only strictly defined for quadratic functions.  Perhaps there is a natural way of talking about this in a more general setting, but I don't see how.

Maybe you could achieve a kind of local conjugacy to the immediately previous update direction w.r.t. the current value of G, although is it obvious that if G were constant (e.g. the objective is a quadratic), that a new direction would be conjugate to *all* previous directions?   If this is true, it seems like it would be a well known interpretation of the conjugate gradient algorithm, and would be a much more general statement than what you showed (i.e. because you are replacing the function everywhere with its 2nd-order Taylor series with a fixed Hessian, so it might as well be quadratic).

Actually, isn't the proof of this fact obvious?  That is, one just has to look at the usual linear CG iterates and see that the new direction is a linear combination of the gradient and the old direction, and is optimally chosen from vectors within a subspace which contains the current gradient and the previous direction vector.

Page 9:  'We can show' -> 'As we will show below'

Page 9:  Typo: 'Eucladian'
 
Page 10:  The notation for the natural gradient in the two equations at the top is not consistent.

Page 10: Typo: 'batch model'

Page 10: How many CG steps were used per update computation?  How did you handle the selection of the damping constant lambda here?

Page 10:  If the baseline NGD is basically just HF, then it seems to be quite severely underperforming here.  In particular, an error of about 0.8 after about 10^4.5 s = 9 hours is far far too slow for that dataset given that you are using a GPU.  Even if measured in iterations, 316 is way too many.  On the other hand, the red curve is in the figures is consistent with what I've seen from the standard HF method.

Perhaps this is due to lack of preconditioning.  However, why not use this in the experiments?  This is very easy to implement, and would make your results more directly comparable to previous ones.

I suppose the fact that NCG-L is performing as well as it is without preconditioning is impressive, but something doesn't sit right with me about this.  I would be really interested to hear what happens if you incorporate preconditioning into your scheme.