Acceleration of SVRG and Katyusha X by Inexact Preconditioning

Yanli Liu, Fei Feng, Wotao Yin
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:4003-4012, 2019.

Abstract

Empirical risk minimization is an important class of optimization problems with many popular machine learning applications, and stochastic variance reduction methods are popular choices for solving them. Among these methods, SVRG and Katyusha X (a Nesterov accelerated SVRG) achieve fast convergence without substantial memory requirement. In this paper, we propose to accelerate these two algorithms by inexact preconditioning, the proposed methods employ fixed preconditioners, although the subproblem in each epoch becomes harder, it suffices to apply fixed number of simple subroutines to solve it inexactly, without losing the overall convergence. As a result, this inexact preconditioning strategy gives provably better iteration complexity and gradient complexity over SVRG and Katyusha X. We also allow each function in the finite sum to be nonconvex while the sum is strongly convex. In our numerical experiments, we observe an on average $8\times$ speedup on the number of iterations and $7\times$ speedup on runtime.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-liu19a, title = {Acceleration of {SVRG} and {K}atyusha X by Inexact Preconditioning}, author = {Liu, Yanli and Feng, Fei and Yin, Wotao}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {4003--4012}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/liu19a/liu19a.pdf}, url = {https://proceedings.mlr.press/v97/liu19a.html}, abstract = {Empirical risk minimization is an important class of optimization problems with many popular machine learning applications, and stochastic variance reduction methods are popular choices for solving them. Among these methods, SVRG and Katyusha X (a Nesterov accelerated SVRG) achieve fast convergence without substantial memory requirement. In this paper, we propose to accelerate these two algorithms by inexact preconditioning, the proposed methods employ fixed preconditioners, although the subproblem in each epoch becomes harder, it suffices to apply fixed number of simple subroutines to solve it inexactly, without losing the overall convergence. As a result, this inexact preconditioning strategy gives provably better iteration complexity and gradient complexity over SVRG and Katyusha X. We also allow each function in the finite sum to be nonconvex while the sum is strongly convex. In our numerical experiments, we observe an on average $8\times$ speedup on the number of iterations and $7\times$ speedup on runtime.} }
Endnote
%0 Conference Paper %T Acceleration of SVRG and Katyusha X by Inexact Preconditioning %A Yanli Liu %A Fei Feng %A Wotao Yin %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-liu19a %I PMLR %P 4003--4012 %U https://proceedings.mlr.press/v97/liu19a.html %V 97 %X Empirical risk minimization is an important class of optimization problems with many popular machine learning applications, and stochastic variance reduction methods are popular choices for solving them. Among these methods, SVRG and Katyusha X (a Nesterov accelerated SVRG) achieve fast convergence without substantial memory requirement. In this paper, we propose to accelerate these two algorithms by inexact preconditioning, the proposed methods employ fixed preconditioners, although the subproblem in each epoch becomes harder, it suffices to apply fixed number of simple subroutines to solve it inexactly, without losing the overall convergence. As a result, this inexact preconditioning strategy gives provably better iteration complexity and gradient complexity over SVRG and Katyusha X. We also allow each function in the finite sum to be nonconvex while the sum is strongly convex. In our numerical experiments, we observe an on average $8\times$ speedup on the number of iterations and $7\times$ speedup on runtime.
APA
Liu, Y., Feng, F. & Yin, W.. (2019). Acceleration of SVRG and Katyusha X by Inexact Preconditioning. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4003-4012 Available from https://proceedings.mlr.press/v97/liu19a.html.

Related Material