2018

A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Acceleration

Shen, Li, Chen, Congliang, Zou, Fangyu et al.

Understand

Integrating adaptive learning rate and momentum techniques into SGD leads to a large class of efficiently accelerated adaptive stochastic algorithms, such as AdaGrad, RMSProp, Adam, AccAdaGrad, \textit{etc}.

In spite of their effectiveness in practice, there is still a large gap in their theories of convergences, especially in the difficult non-convex stochastic setting.
To fill this gap, we propose \emph{weighted AdaGrad with unified momentum}, dubbed AdaUSM, which has the main characteristics that (1) it incorporates a unified momentum scheme which covers both the heavy ball momentum and the Nesterov accelerated gradient momentum; (2) it adopts a novel weighted adaptive learning rate that can unify the learning rates of AdaGrad, AccAdaGrad, Adam, and RMSProp.
Moreover, when we take polynomially growing weights in AdaUSM, we obtain its $\mathcal{O}(\log(T)/\sqrt{T})$ convergence rate in the non-convex stochastic setting.

Built on

B. T. Polyak, “Some methods of speeding up the convergence of iteration methods,” USSR Computational Mathematics and Mathematical Physics , vol. 4, no. 5, pp. 1–17, 1964
1964
Earlier work this paper cites.
Y. E. Nesterov, “A method for solving the convex programming problem with convergence rate o ⁡ ( 1 / k 2 ) o(1/k^{2}) ,” in Dokl. Akad. Nauk SSSR , vol. 269, 1983, pp. 543–547
1983
Earlier work this paper cites.
H. Robbins and S. Monro, “A stochastic approximation method,” in Herbert Robbins Selected Papers . Springer, 1985, pp. 102–109
1985
Earlier work this paper cites.
L. Bottou, “Online learning and stochastic approximations,” On-line learning in neural networks , vol. 17, no. 9, p. 142, 1998
1998
Earlier work this paper cites.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE , vol. 86, no. 11, pp. 2278–2324, 1998
1998
Earlier work this paper cites.
A. Krizhevsky, “Learning multiple layers of features from tiny images,” Master’s thesis, University of Tront , 2009
2009
Earlier work this paper cites.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on . Ieee, 2009, pp. 248–255
2009
Earlier work this paper cites.
H. B. McMahan and M. Streeter, “Adaptive bound optimization for online convex optimization,” COLT 2010 , p. 244, 2010
2010
Earlier work this paper cites.
J. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization,” Journal of Machine Learning Research , vol. 12, no. Jul, pp. 2121–2159, 2011
2011
Earlier work this paper cites.
A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in neural information processing systems , 2012, pp. 1097–1105
2012
Earlier work this paper cites.
G. Hinton, N. Srivastava, and K. Swersky, “Neural networks for machine learning lecture 6a overview of mini-batch gradient descent,” Cited on , p. 14, 2012
2012
Earlier work this paper cites.
S. Ghadimi and G. Lan, “Stochastic first-and zeroth-order methods for nonconvex stochastic programming,” SIAM Journal on Optimization , vol. 23, no. 4, pp. 2341–2368, 2013
2013
Earlier work this paper cites.
R. Johnson and T. Zhang, “Accelerating stochastic gradient descent using predictive variance reduction,” in Advances in neural information processing systems , 2013, pp. 315–323
2013
Earlier work this paper cites.
Y. Nesterov, Introductory lectures on convex optimization: A basic course . Springer Science & Business Media, 2013, vol. 87
2013
Earlier work this paper cites.
I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” in International conference on machine learning , 2013, pp. 1139–1147
2013
Earlier work this paper cites.

Similar

A. Defazio, F. Bach, and S. Lacoste-Julien, “Saga: A fast incremental gradient method with support for non-strongly convex composite objectives,” in Advances in neural information processing systems , 2014, pp. 1646–1654
2014
Cited alongside, same era.
Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” nature , vol. 521, no. 7553, p. 436, 2015
2015
Cited alongside, same era.
D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in International Conference on Learning Representations , 2015
2015
Cited alongside, same era.
E. Ghadimi, H. R. Feyzmahdavian, and M. Johansson, “Global convergence of the heavy-ball method for convex optimization,” in Control Conference (ECC), 2015 European . IEEE, 2015, pp. 310–315
2015
Cited alongside, same era.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in Proceedings of the IEEE conference on computer vision and pattern recognition , 2015, pp. 1–9
2015
Cited alongside, same era.
I. Goodfellow, Y. Bengio, A. Courville, and Y. Bengio, Deep learning . MIT press Cambridge, 2016, vol. 1
2016
Cited alongside, same era.
S. Ghadimi and G. Lan, “Accelerated gradient methods for nonconvex nonlinear and stochastic programming,” Mathematical Programming , vol. 156, no. 1-2, pp. 59–99, 2016
2016
Cited alongside, same era.
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition , 2016, pp. 770–778
2016
Cited alongside, same era.
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč, “Sarah: A novel method for machine learning problems using stochastic recursive gradient,” in Proceedings of the 34th International Conference on Machine Learning-Volume 70 . JMLR. org, 2017, pp. 2613–2621
2017
Cited alongside, same era.
K. Levy, “Online to offline conversions, universality and adaptive minibatch sizes,” in Advances in Neural Information Processing Systems , 2017, pp. 1613–1622
2017
Cited alongside, same era.
M. C. Mukkamala and M. Hein, “Variants of rmsprop and adagrad with logarithmic regret bounds,” in International Conference on Machine Learning , 2017, pp. 2545–2553
2017
Cited alongside, same era.
G. Huang, Z. Liu, L. van der Maaten, and K. Q. Weinberger, “Densely connected convolutional networks,” in 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) . IEEE, 2017, pp. 2261–2269
2017
Cited alongside, same era.

Then

S. J. Reddi, S. Kale, and S. Kumar, “On the convergence of adam and beyond,” in International Conference on Learning Representations , 2018
2018
Closest in time.
M. Zaheer, S. Reddi, D. Sachan, S. Kale, and S. Kumar, “Adaptive methods for nonconvex optimization,” Advances in neural information processing systems , vol. 31, 2018
2018
Closest in time.
X. Wu, R. Ward, and L. Bottou, “Wngrad: Learn the learning rate in gradient descent,” arXiv preprint arXiv:1803.02865 , 2018
Original
2018
Closest in time.
X. Li and F. Orabona, “On the convergence of stochastic gradient descent with adaptive stepsizes,” in International Conference on Artificial Intelligence and Statistics , 2019, pp. 983–992
2019
Closest in time.
R. Ward, X. Wu, and L. Bottou, “Adagrad stepsizes: Sharp convergence over nonconvex landscapes,” in International Conference on Machine Learning , 2019, pp. 6677–6686
2019
Closest in time.
F. Zou, L. Shen, Z. Jie, W. Zhang, and W. Liu, “A sufficient condition for convergences of adam and rmsprop,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , 2019, pp. 11 127–11 135
2019
Closest in time.
X. Chen, S. Liu, R. Sun, and M. Hong, “On the convergence of a class of adam-type algorithms for non-convex optimization,” in International Conference on Learning Representations , 2019
2019
Closest in time.
Z. Zhuang, A. Cutkosky, and F. Orabona, “Surrogate losses for online learning of stepsizes in stochastic non-convex optimization,” in International Conference on Machine Learning , 2019, pp. 7664–7672
2019
Closest in time.
N. Agarwal, B. Bullins, X. Chen, E. Hazan, K. Singh, C. Zhang, and Y. Zhang, “Efficient full-matrix adaptive regularization,” in International Conference on Machine Learning , 2019, pp. 102–110
2019
Closest in time.
L. Liu, H. Jiang, P. He, W. Chen, X. Liu, J. Gao, and J. Han, “On the variance of the adaptive learning rate and beyond,” arXiv preprint arXiv:1908.03265 , 2019
Original
2019
Closest in time.
A. Kavis, K. Y. Levy, F. Bach, and V. Cevher, “Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization,” in Advances in Neural Information Processing Systems , 2019, pp. 6257–6266
2019
Closest in time.
X. Chen, S. Liu, K. Xu, X. Li, X. Lin, M. Hong, and D. Cox, “Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization,” in Advances in Neural Information Processing Systems , 2019, pp. 7202–7213
2019
Closest in time.
Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang, “A novel convergence analysis for algorithms of the adam family,” arXiv preprint arXiv:2112.03459 , 2021
Original
2021
Closest in time.
C. Chen, L. Shen, F. Zou, and W. Liu, “Towards practical adam: Non-convexity, convergence theory, and mini-batch acceleration,” Journal of Machine Learning Research , vol. 23, pp. 1–47, 2022
2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…