PRECONDITIONER ON MATRIX LIE GROUP FOR SGD
We study two types of preconditioners and preconditioned stochastic gradient descent (SGD) methods in a unified framework. We call the first one the Newton type due to its close relationship to the Newton method, and the second one the Fisher type as its preconditioner is closely related to the inverse of Fisher information matrix. Both preconditioners can be derived from one framework, and efficiently estimated on any matrix Lie groups designated by the user using natural or relative gradient descent minimizing certain preconditioner estimation criteria. Many existing preconditioners and methods, e.g., RMSProp, Adam, KFAC, equilibrated SGD, batch normalization, etc., are special cases of or closely related to either the Newton type or the Fisher type ones. Experimental results on relatively large scale machine learning problems are reported for performance study.
This paper proposes a preconditioned SGD method where the preconditioner is adapted by performing some type of gradient descent on some secondary objective "c".  The preconditioner lives in one of a restricted class of invertible matrices (e.g. symmetric, diagonal, Kronecker-factored) constituting a Lie group (which is where the title comes from). 
I think the idea of designing a preconditioner based on considerations of gradient noise and as well as the Hessian is interesting. However most of that work was done in the Li paper, and including the design of "c".  This paper's contribution seems to be to work out some of the details for various restricted classes of matrices, to construct a "Fisher version" of c, and to run some experiments. 
The problem is that I don't really buy the original motivation for the "c" function from the Li paper, and the newer Fisher version of c proposed in this paper doesn't seem to have any justification at all.  I also find that the paper in general doesn't do a good job of explaining its various choices when designing the algorithm.  This could be somewhat forgiven if the experimental results were strong, but unfortunately they are too limited, and marred by overly-simplistic baselines that aren't properly tuned.
More detailed comments below
Title:
I think the title is poorly chosen.  The paper doesn't use Lie groups or their properties in any significant way, and "learning" is a bad choice of words too, since it involves generalization etc (it's not merely the optimization of some function).  A better title would be "A general framework for adaptive preconditioners" or something.
Intro:
Citation of Adagrad paper is broken
The literature review contained in the intro needs works. I wouldn't call methods like quasi-Newton methods "convex optimization methods".  Those algorithms were around a long time ago before "convex optimization" was a specific topic of study and are probably *less* associated with the convex optimization literature than, say, Adagrad is. And methods like Adagrad aren't exactly first-order methods either. They use adaptively chosen preconditioners (that happen to be diagonal) which puts them in a similar category to methods like LBFGS, KFAC, etc.
It's not clear at this point in the paper what it means for a preconditioner to be "learned on" something.  
Section 2:
The way you discuss quadratic approximations is confusing.  Especially  the sentence "is the sum of approximation error and constant term independent of theta" where you then go on to say that a_z does depend on theta.  I know that this second theta is the "current theta" separate from the theta as it appears in the formula for the approximation but this is really sloppy. Usually people construct the quadratic approximation in terms of the *change in theta* which makes such things cleaner.
You should explain how eqn 8 was derived since it's so crucial to everything that follows.  Citing a previous paper with no further explanation really isn't good enough here.  Surely with all of the notation you have already set up it should be possible to motivate this criterion somehow. The simple fact that it recovers P = H^-1 in the noiseless quadratic case isn't really good enough, since many possible criteria would do the same.
I've skimmed the paper you cited and their justification for this criterion isn't very convincing.  There are other possible criteria that they give and there doesn't seem to be a strong reason to prefer one over the other.
Section 3:
The way you define the Fisher information matrix corresponds to the "empirical Fisher", since z includes the training labels.  This is different from the standard Fisher information matrix.
How can you motivate doing the "replacement" that you do to generate eqn 12? Replacing delta theta with v is just notation, but how can you justify replacement of delta g with g + lambda v?  This isn't a reasonable approximation in any sense that I can discern. Once again this is an absolutely crucial step that comes out of nowhere.  Honestly it feels contrived in order to produce a connection to popular methods like Adam.
Section 4: 
The prominent use of the abstract mathematical term "Lie group" feels unnecessary and like mathematical name-dropping. Why not just talk about certain "classes" of invertible matrices closed under standard operations (which would also help people that don't know what a Lie group is)?  If you are going to invoke some abstract mathematical framework like Lie groups it needs to actually help you do something you couldn't otherwise. You need to use some kind of advanced Theorem for Lie groups. 
Without knowing the general form of R equation 18 is basically vacuous. *any* matrix (in the same class) could be written this way.
I've never heard of the natural gradient being defined using a different metric than the Fisher metric.  If the metric can be arbitrary then even standard gradient descent is a "natural gradient" too (taking the Euclidean metric).  You could argue for a generalized definition that would include only parametrization independent metrics, but then your particular metric wouldn't obviously work.
Section 6:
Rather than comparing to Batch Normalization you would be better off comparing to the old centering and normalization work of Schraudolph et al which the former was based on, which is actually a well-defined preconditioner.
Section 7: 
You really need to sweep over the learning rate parameters for optimizers like SGD with momentum or Adam.   Otherwise the comparisons aren't very interesting. 
"Tikhonov regularization" should just be called L2-regularization