We propose a preconditioned accelerated stochastic gradient method suitable for large scale optimization. We derive sufficient convergence conditions for the minimization of convex functions using a generic class of diagonal preconditioners and provide a formal convergence proof based on a framework originally used for on-line learning. Inspired by recent popular adaptive per-feature algorithms, we propose a specific preconditioner based on the second moment of the gradient. The sufficient convergence conditions motivate a critical adaptation of the perfeature updates in order to ensure convergence. We show empirical results for the minimization of convex and non-convex cost functions, in the context of neural network training. The method compares favorably with respect to current, first order, stochastic optimization methods.
This paper presents a preconditioned variant of Nesterov's Accelerated Gradient (NAG) for use with Stochastic Gradients. The appears to be an interesting direction given that Nesterov's Acceleration empirically works better than the Heavy Ball (HB) method. There are a few issues that I'd like to understand:
[0] The authors make the assumption A 1-3, wherein, 
- why should the momentum parameter mu drop exponentially? This is not required for the convex case, see Nesterov's (1983) scheme for the smooth case and the smooth+strongly convex case. 
- why should the bounded rate of change (A3) even be satisfied in the first case? Does this hold true even in simple settings such as optimizing a quadratic/for log loss with stochastic and/or deterministic gradients? In short, is this a reasonable assumption (which at the least holds for certain special cases) or one that helps in obtaining a convergence statement (and which is not true even in simple situations)?
[1] Convergence under specific assumptions aside, I am not sure what is the significance of the regret bound provided. In particular, can the authors provide any reasoning as to why this regret bound is better compared to ADAM or its variants [Reddi et al, 2018]? Is there a faster rate of convergence that this proposed method obtains? I dont think a regret bound is reflective of any (realistic) practical behavior and doesn't serve as a means to provide a distinction between two algorithms. What matters is proving a statement that offers a rate of convergence. Other forms of theoretical bounds do not provide any forms of distinction between algorithms of the same class (adagrad, rmsprop, adam and variants) and are not reflective of practical performance.  
[2] The scope of empirical results is rather limited. While I like the notion of having experiments for convex (with least squares/log loss) and non-convex losses, the experiments for the non-convex case are fairly limited in scope. In order to validate the effectiveness of this scheme, performing experiments on a suitable benchmark of some widely used and practically applicable convnet with residual connections/densenet for cifar-10/imagenet is required to indicate that this scheme indeed works well, and to show that it doesn't face issues with regards to generalization (see Wilson et al, 2017 - marginal value of adaptive gradient methods in machine learning).
[3] The paper claims of an "accelerated stochastic gradient" method - this really is a loosely used term for the paper title and its contents. There are efforts that have specifically dealt with acclerating SGD in a very precise sense which the paper doesn't refer to:
- Ghadimi and Lan (2012, 2013), Dieuleveut et al (2017) accelerate SGD with the bounded variance assumption. 
- Accelerating SGD is subtle in a generic sense. See Jain et al. (2017) "Accelerating Stochastic Gradient Descent for Least Squares Regression", Kidambi et al. (2018) "On the insufficiency of existing momentum schemes for stochastic optimization". The former paper presents a rigorous understanding of accelerating SGD. The latter paper highlights the insufficiencies of existing schemes like HB or NAG for stochastic optimization.