ASVRG: Accelerated Proximal SVRG

Fanhua Shang, Licheng Jiao, Kaiwen Zhou, James Cheng, Yan Ren, Yufei Jin
Proceedings of The 10th Asian Conference on Machine Learning, PMLR 95:815-830, 2018.

Abstract

This paper proposes an accelerated proximal stochastic variance reduced gradient (ASVRG) method, in which we design a simple and effective momentum acceleration trick. Unlike most existing accelerated stochastic variance reduction methods such as Katyusha, ASVRG has only one additional variable and one momentum parameter. Thus, ASVRG is much simpler than those methods, and has much lower per-iteration complexity. We prove that ASVRG achieves the best known oracle complexities for both strongly convex and non-strongly convex objectives. In addition, we extend ASVRG to mini-batch and non-smooth settings. We also empirically verify our theoretical results and show that the performance of ASVRG is comparable with, and sometimes even better than that of the state-of-the-art stochastic methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v95-shang18b, title = {ASVRG: Accelerated Proximal SVRG}, author = {Shang, Fanhua and Jiao, Licheng and Zhou, Kaiwen and Cheng, James and Ren, Yan and Jin, Yufei}, booktitle = {Proceedings of The 10th Asian Conference on Machine Learning}, pages = {815--830}, year = {2018}, editor = {Zhu, Jun and Takeuchi, Ichiro}, volume = {95}, series = {Proceedings of Machine Learning Research}, month = {14--16 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v95/shang18b/shang18b.pdf}, url = {https://proceedings.mlr.press/v95/shang18b.html}, abstract = {This paper proposes an accelerated proximal stochastic variance reduced gradient (ASVRG) method, in which we design a simple and effective momentum acceleration trick. Unlike most existing accelerated stochastic variance reduction methods such as Katyusha, ASVRG has only one additional variable and one momentum parameter. Thus, ASVRG is much simpler than those methods, and has much lower per-iteration complexity. We prove that ASVRG achieves the best known oracle complexities for both strongly convex and non-strongly convex objectives. In addition, we extend ASVRG to mini-batch and non-smooth settings. We also empirically verify our theoretical results and show that the performance of ASVRG is comparable with, and sometimes even better than that of the state-of-the-art stochastic methods.} }
Endnote
%0 Conference Paper %T ASVRG: Accelerated Proximal SVRG %A Fanhua Shang %A Licheng Jiao %A Kaiwen Zhou %A James Cheng %A Yan Ren %A Yufei Jin %B Proceedings of The 10th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jun Zhu %E Ichiro Takeuchi %F pmlr-v95-shang18b %I PMLR %P 815--830 %U https://proceedings.mlr.press/v95/shang18b.html %V 95 %X This paper proposes an accelerated proximal stochastic variance reduced gradient (ASVRG) method, in which we design a simple and effective momentum acceleration trick. Unlike most existing accelerated stochastic variance reduction methods such as Katyusha, ASVRG has only one additional variable and one momentum parameter. Thus, ASVRG is much simpler than those methods, and has much lower per-iteration complexity. We prove that ASVRG achieves the best known oracle complexities for both strongly convex and non-strongly convex objectives. In addition, we extend ASVRG to mini-batch and non-smooth settings. We also empirically verify our theoretical results and show that the performance of ASVRG is comparable with, and sometimes even better than that of the state-of-the-art stochastic methods.
APA
Shang, F., Jiao, L., Zhou, K., Cheng, J., Ren, Y. & Jin, Y.. (2018). ASVRG: Accelerated Proximal SVRG. Proceedings of The 10th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 95:815-830 Available from https://proceedings.mlr.press/v95/shang18b.html.

Related Material