UNIVERSAL STAGEWISE LEARNING FOR NON- CONVEX PROBLEMS WITH CONVERGENCE ON AV- ERAGED SOLUTIONS
Although stochastic gradient descent (SGD) method and its variants (e.g., stochastic momentum methods, ADAGRAD) are algorithms of choice for solving nonconvex problems (especially deep learning), big gaps still remain between the theory and the practice with many questions unresolved. For example, there is still a lack of theories of convergence for SGD and its variants that use stagewise step size and return an averaged solution in practice. In addition, theoretical insights of why adaptive step size of ADAGRAD could improve non-adaptive step size of SGD is still missing for non-convex optimization. This paper aims to address these questions and fill the gap between theory and practice. We propose a universal stagewise optimization framework for a broad family of non-smooth nonconvex problems with the following key features: (i) at each stage any suitable stochastic convex optimization algorithms (e.g., SGD or ADAGRAD) that return an averaged solution can be employed for minimizing a regularized convex problem; (ii) the step size is decreased in a stagewise manner; (iii) an averaged solution is returned as the final solution. Our theoretical results of stagewise ADAGRAD exhibit its adaptive convergence, therefore shed insights on its faster convergence than stagewise SGD for problems with slowly growing cumulative stochastic gradients. To the best of our knowledge, this is the first work for addressing the unresolved issues of existing theories mentioned earlier. Besides theoretical contributions, our empirical studies show that our stagewise SGD and ADAGRAD improve the generalization performance of existing variants/implementations of SGD and ADAGRAD.
Summary:
The paper presents an analysis and numerical evaluation of stagewise SGD, ADAGRAD and Stochastic momentum methods for solving stochastic non-smooth non-convex optimization problems. 
Comments:
I find the ideas presented in this paper very interesting. The convergence analysis seems correct and the paper is reasonably well written, and tackles an important problem. 
The analysis holds for μ-weekly convex functions. This assumption is really important for the development of the algorithm and the proposed analysis. I like the fact that the authors provide two examples showing that popular objective functions in machine learning satisfy this assumption.
The numerical evaluation is adequate showing the effectiveness  of the proposed stagewise algorithms.  However i have the follow suggestions/minor comments:
1) It will be nice to have also some plots showing the performance of the proposed method on the ImageNet dataset. 
2) Another possible nice experiment will be a comparison of the four stagewise methods (SGD,ADAGRAD,SHB,SNAG) on the same dataset. Which one behaves better? 
Minor Comments:
1) The captions of the figures can be more informative (mention also the division by column). First column is SGD, Second column Adagrad, etc.
2) Typos: 
Section 1, last bullet point, second line: "stagwise"
Section 5, second paragraph , first line :"their their"
page 8, 3 line from the bottom:  "seems, indicate"
2) Missing reference.
In the area of stochastic gradient methods with momentum many papers have been proposed recently for the case of convex optimization that worth to be mentioned:
Gadat, Sébastien, Fabien Panloup, and Sofiane Saadane. "Stochastic heavy ball." Electronic Journal of Statistics 12.1 (2018): 461-529.
Loizou, Nicolas, and Peter Richtárik. "Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods." arXiv preprint arXiv:1712.09677 (2017).
Lan, Guanghui, and Yi Zhou. "An optimal randomized incremental gradient method." Mathematical programming (2017): 1-49.
Overall, I suggest to accept this paper.