Direct Acceleration of SAGA using Sampled Negative Momentum

Kaiwen Zhou, Qinghua Ding, Fanhua Shang, James Cheng, Danli Li, Zhi-Quan Luo
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1602-1610, 2019.

Abstract

Variance reduction is a simple and effective technique that accelerates convex (or non-convex) stochastic optimization. Among existing variance reduction methods, SVRG and SAGA adopt unbiased gradient estimators and are the most popular variance reduction methods in recent years. Although various accelerated variants of SVRG (e.g., Katyusha and Acc-Prox-SVRG) have been proposed, the direct acceleration of SAGA still remains unknown. In this paper, we propose a directly accelerated variant of SAGA using a novel Sampled Negative Momentum (SSNM), which achieves the best known oracle complexity for strongly convex problems (with known strong convexity parameter). Consequently, our work fills the void of directly accelerated SAGA.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-zhou19c, title = {Direct Acceleration of SAGA using Sampled Negative Momentum}, author = {Zhou, Kaiwen and Ding, Qinghua and Shang, Fanhua and Cheng, James and Li, Danli and Luo, Zhi-Quan}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1602--1610}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/zhou19c/zhou19c.pdf}, url = {https://proceedings.mlr.press/v89/zhou19c.html}, abstract = {Variance reduction is a simple and effective technique that accelerates convex (or non-convex) stochastic optimization. Among existing variance reduction methods, SVRG and SAGA adopt unbiased gradient estimators and are the most popular variance reduction methods in recent years. Although various accelerated variants of SVRG (e.g., Katyusha and Acc-Prox-SVRG) have been proposed, the direct acceleration of SAGA still remains unknown. In this paper, we propose a directly accelerated variant of SAGA using a novel Sampled Negative Momentum (SSNM), which achieves the best known oracle complexity for strongly convex problems (with known strong convexity parameter). Consequently, our work fills the void of directly accelerated SAGA.} }
Endnote
%0 Conference Paper %T Direct Acceleration of SAGA using Sampled Negative Momentum %A Kaiwen Zhou %A Qinghua Ding %A Fanhua Shang %A James Cheng %A Danli Li %A Zhi-Quan Luo %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-zhou19c %I PMLR %P 1602--1610 %U https://proceedings.mlr.press/v89/zhou19c.html %V 89 %X Variance reduction is a simple and effective technique that accelerates convex (or non-convex) stochastic optimization. Among existing variance reduction methods, SVRG and SAGA adopt unbiased gradient estimators and are the most popular variance reduction methods in recent years. Although various accelerated variants of SVRG (e.g., Katyusha and Acc-Prox-SVRG) have been proposed, the direct acceleration of SAGA still remains unknown. In this paper, we propose a directly accelerated variant of SAGA using a novel Sampled Negative Momentum (SSNM), which achieves the best known oracle complexity for strongly convex problems (with known strong convexity parameter). Consequently, our work fills the void of directly accelerated SAGA.
APA
Zhou, K., Ding, Q., Shang, F., Cheng, J., Li, D. & Luo, Z.. (2019). Direct Acceleration of SAGA using Sampled Negative Momentum. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1602-1610 Available from https://proceedings.mlr.press/v89/zhou19c.html.

Related Material