Adaptive regularization methods pre-multiply a descent direction by a preconditioning matrix. Due to the large number of parameters of machine learning problems, full-matrix preconditioning methods are prohibitively expensive. We show how to modify full-matrix adaptive regularization in order to make it practical and effective. We also provide novel theoretical analysis for adaptive regularization in non-convex optimization settings. The core of our algorithm, termed GGT, consists of efficient inverse computation of square roots of low-rank matrices. Our preliminary experiments underscore improved convergence rate of GGT across a variety of synthetic tasks and standard deep learning benchmarks.
The paper considers adaptive regularization, which has been popular in neural network learning.  Rather than adapting diagonal elements of the adaptivity matrix, the paper proposes to consider a low-rank approximation to the Gram/correlation matrix.
When you say that full-matrix computation "requires taking the inverse square root", I assume you know that is not really correct?  As a matter of good implementation, one never takes the inverse of anything.  Instead, on solves a linear system, via other means.  Of course, approximate linear system solvers then permit a wide tradeoff space to speed things up.
There are several issues convolved here: one is ``full-matrix,'' another is that this is really a low-rank approximation to a matrix and so not full matrix, another is that this may or may not be implementable on GPUs.  The latter may be important in practice, but it is orthogonal to the full matrix theory.
There is a great deal of discussion about full-matrix preconditioning, but there is no full matrix here.  Instead, it is a low-rank approximation to the full matrix.  If there were theory to be had here, then I would guess that the low-rank approximation may work even when full matrix did not, e.g., since the full matrix case would involve too may parameters.
The discussion of convergence to first order critical points is straightforward.
Adaptivity ratio is mentioned in the intro but not defined there.  Why mention it here, if it's not being defined.
You say that second order methods are outside the scope, but you say that your method is particularly relevant for ill-conditioned problems.  It would help to clarify the connection between the Gram/correlation matrix of gradients and the Hessian and what is being done to ill-conditioning, since second order methods are basically designed for ill-conditioned problems..
It is difficult to know what the theory says about the empirical results, given the tweaks discussed in Sec 2.2, and so it is difficult to know what is the benefit of the method versus the tweaks.
The results shown in Figure 4 are much more interesting than the usual training curves which are shown in the other figures.  If this method is to be useful, understanding how these spectral properties change during training for different types of networks is essential.  More papers should present this, and those that do should do it more systematically. 
You say that you "informally state the main theorem."  The level of formality/informality makes it hard to know what is really being said.  You should remove it if it is not worth stating precisely, or state it precisely.  (It's fair to modularize the proof, but as it is it's hard to know what it's saying, except that your method comes with some guarantee that isn't stated.)