Local Convergence Properties of SAGA/Prox-SVRG and Acceleration

Clarice Poon, Jingwei Liang, Carola Schoenlieb

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationProceedings of the 35th International Conference on Machine Learning
EditorsJennifer Dy, Andreas Krause
Place of PublicationStockholmsmässan, Stockholm Sweden
PublisherPMLR
Pages4124-4132
Number of pages9
Volume80
Publication statusPublished - 1 Oct 2018

Publication series

NameProceedings of Machine Learning Research
PublisherPMLR
Volume80
ISSN (Print)1938-7228
ISSN (Electronic)2640-3498

Cite this

Poon, C., Liang, J., & Schoenlieb, C. (2018). Local Convergence Properties of SAGA/Prox-SVRG and Acceleration. In J. Dy, & A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning (Vol. 80, pp. 4124-4132). (Proceedings of Machine Learning Research; Vol. 80). Stockholmsmässan, Stockholm Sweden: PMLR.

Local Convergence Properties of SAGA/Prox-SVRG and Acceleration. / Poon, Clarice; Liang, Jingwei; Schoenlieb, Carola.

Proceedings of the 35th International Conference on Machine Learning. ed. / Jennifer Dy; Andreas Krause. Vol. 80 Stockholmsmässan, Stockholm Sweden : PMLR, 2018. p. 4124-4132 (Proceedings of Machine Learning Research; Vol. 80).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Poon, C, Liang, J & Schoenlieb, C 2018, Local Convergence Properties of SAGA/Prox-SVRG and Acceleration. in J Dy & A Krause (eds), Proceedings of the 35th International Conference on Machine Learning. vol. 80, Proceedings of Machine Learning Research, vol. 80, PMLR, Stockholmsmässan, Stockholm Sweden, pp. 4124-4132.
Poon C, Liang J, Schoenlieb C. Local Convergence Properties of SAGA/Prox-SVRG and Acceleration. In Dy J, Krause A, editors, Proceedings of the 35th International Conference on Machine Learning. Vol. 80. Stockholmsmässan, Stockholm Sweden: PMLR. 2018. p. 4124-4132. (Proceedings of Machine Learning Research).
Poon, Clarice ; Liang, Jingwei ; Schoenlieb, Carola. / Local Convergence Properties of SAGA/Prox-SVRG and Acceleration. Proceedings of the 35th International Conference on Machine Learning. editor / Jennifer Dy ; Andreas Krause. Vol. 80 Stockholmsmässan, Stockholm Sweden : PMLR, 2018. pp. 4124-4132 (Proceedings of Machine Learning Research).
@inproceedings{690a099bb3cc471fb1029305d8ee9c4e,
title = "Local Convergence Properties of SAGA/Prox-SVRG and Acceleration",
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.",
author = "Clarice Poon and Jingwei Liang and Carola Schoenlieb",
year = "2018",
month = "10",
day = "1",
language = "English",
volume = "80",
series = "Proceedings of Machine Learning Research",
publisher = "PMLR",
pages = "4124--4132",
editor = "Jennifer Dy and Andreas Krause",
booktitle = "Proceedings of the 35th International Conference on Machine Learning",

}

TY - GEN

T1 - Local Convergence Properties of SAGA/Prox-SVRG and Acceleration

AU - Poon, Clarice

AU - Liang, Jingwei

AU - Schoenlieb, Carola

PY - 2018/10/1

Y1 - 2018/10/1

N2 - 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.

AB - 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.

M3 - Conference contribution

VL - 80

T3 - Proceedings of Machine Learning Research

SP - 4124

EP - 4132

BT - Proceedings of the 35th International Conference on Machine Learning

A2 - Dy, Jennifer

A2 - Krause, Andreas

PB - PMLR

CY - Stockholmsmässan, Stockholm Sweden

ER -