Local Convergence Properties of SAGA/Prox-SVRG and Acceleration

Clarice Poon, Jingwei Liang, Carola Schoenlieb
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4124-4132, 2018.

Abstract

In this paper, we present a local convergence anal- ysis for a class of stochastic optimisation meth- ods: the proximal variance reduced stochastic gradient methods, and mainly focus on SAGA (Defazio et al., 2014) and Prox-SVRG (Xiao & Zhang, 2014). Under the assumption that the non-smooth component of the optimisation prob- lem is partly smooth relative to a smooth mani- fold, we present a unified framework for the local convergence analysis of SAGA/Prox-SVRG: (i) the sequences generated by the methods are able to identify the smooth manifold in a finite num- ber of iterations; (ii) then the sequence enters a local linear convergence regime. Furthermore, we discuss various possibilities for accelerating these algorithms, including adapting to better lo- cal parameters, and applying higher-order deter- ministic/stochastic optimisation methods which can achieve super-linear convergence. Several concrete examples arising from machine learning are considered to demonstrate the obtained result.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-poon18a, title = {Local Convergence Properties of {SAGA}/{P}rox-{SVRG} and Acceleration}, author = {Poon, Clarice and Liang, Jingwei and Schoenlieb, Carola}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4124--4132}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/poon18a/poon18a.pdf}, url = {https://proceedings.mlr.press/v80/poon18a.html}, abstract = {In this paper, we present a local convergence anal- ysis for a class of stochastic optimisation meth- ods: the proximal variance reduced stochastic gradient methods, and mainly focus on SAGA (Defazio et al., 2014) and Prox-SVRG (Xiao & Zhang, 2014). Under the assumption that the non-smooth component of the optimisation prob- lem is partly smooth relative to a smooth mani- fold, we present a unified framework for the local convergence analysis of SAGA/Prox-SVRG: (i) the sequences generated by the methods are able to identify the smooth manifold in a finite num- ber of iterations; (ii) then the sequence enters a local linear convergence regime. Furthermore, we discuss various possibilities for accelerating these algorithms, including adapting to better lo- cal parameters, and applying higher-order deter- ministic/stochastic optimisation methods which can achieve super-linear convergence. Several concrete examples arising from machine learning are considered to demonstrate the obtained result.} }
Endnote
%0 Conference Paper %T Local Convergence Properties of SAGA/Prox-SVRG and Acceleration %A Clarice Poon %A Jingwei Liang %A Carola Schoenlieb %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-poon18a %I PMLR %P 4124--4132 %U https://proceedings.mlr.press/v80/poon18a.html %V 80 %X In this paper, we present a local convergence anal- ysis for a class of stochastic optimisation meth- ods: the proximal variance reduced stochastic gradient methods, and mainly focus on SAGA (Defazio et al., 2014) and Prox-SVRG (Xiao & Zhang, 2014). Under the assumption that the non-smooth component of the optimisation prob- lem is partly smooth relative to a smooth mani- fold, we present a unified framework for the local convergence analysis of SAGA/Prox-SVRG: (i) the sequences generated by the methods are able to identify the smooth manifold in a finite num- ber of iterations; (ii) then the sequence enters a local linear convergence regime. Furthermore, we discuss various possibilities for accelerating these algorithms, including adapting to better lo- cal parameters, and applying higher-order deter- ministic/stochastic optimisation methods which can achieve super-linear convergence. Several concrete examples arising from machine learning are considered to demonstrate the obtained result.
APA
Poon, C., Liang, J. & Schoenlieb, C.. (2018). Local Convergence Properties of SAGA/Prox-SVRG and Acceleration. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4124-4132 Available from https://proceedings.mlr.press/v80/poon18a.html.

Related Material