Fast Rate Analysis of Some Stochastic Optimization Algorithms

Chao Qu, Huan Xu, Chong Ong
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:662-670, 2016.

Abstract

In this paper, we revisit three fundamental and popular stochastic optimization algorithms (namely, Online Proximal Gradient, Regularized Dual Averaging method and ADMM with online proximal gradient) and analyze their convergence speed under conditions weaker than those in literature. In particular, previous works showed that these algorithms converge at a rate of O (\ln T/T) when the loss function is strongly convex, and O (1 /\sqrtT) in the weakly convex case. In contrast, we relax the strong convexity assumption of the loss function, and show that the algorithms converge at a rate O (\ln T/T) if the \em expectation of the loss function is \em locally strongly convex. This is a much weaker assumption and is satisfied by many practical formulations including Lasso and Logistic Regression. Our analysis thus extends the applicability of these three methods, as well as provides a general recipe for improving analysis of convergence rate for stochastic and online optimization algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-qua16, title = {Fast Rate Analysis of Some Stochastic Optimization Algorithms}, author = {Qu, Chao and Xu, Huan and Ong, Chong}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {662--670}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/qua16.pdf}, url = {https://proceedings.mlr.press/v48/qua16.html}, abstract = {In this paper, we revisit three fundamental and popular stochastic optimization algorithms (namely, Online Proximal Gradient, Regularized Dual Averaging method and ADMM with online proximal gradient) and analyze their convergence speed under conditions weaker than those in literature. In particular, previous works showed that these algorithms converge at a rate of O (\ln T/T) when the loss function is strongly convex, and O (1 /\sqrtT) in the weakly convex case. In contrast, we relax the strong convexity assumption of the loss function, and show that the algorithms converge at a rate O (\ln T/T) if the \em expectation of the loss function is \em locally strongly convex. This is a much weaker assumption and is satisfied by many practical formulations including Lasso and Logistic Regression. Our analysis thus extends the applicability of these three methods, as well as provides a general recipe for improving analysis of convergence rate for stochastic and online optimization algorithms.} }
Endnote
%0 Conference Paper %T Fast Rate Analysis of Some Stochastic Optimization Algorithms %A Chao Qu %A Huan Xu %A Chong Ong %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-qua16 %I PMLR %P 662--670 %U https://proceedings.mlr.press/v48/qua16.html %V 48 %X In this paper, we revisit three fundamental and popular stochastic optimization algorithms (namely, Online Proximal Gradient, Regularized Dual Averaging method and ADMM with online proximal gradient) and analyze their convergence speed under conditions weaker than those in literature. In particular, previous works showed that these algorithms converge at a rate of O (\ln T/T) when the loss function is strongly convex, and O (1 /\sqrtT) in the weakly convex case. In contrast, we relax the strong convexity assumption of the loss function, and show that the algorithms converge at a rate O (\ln T/T) if the \em expectation of the loss function is \em locally strongly convex. This is a much weaker assumption and is satisfied by many practical formulations including Lasso and Logistic Regression. Our analysis thus extends the applicability of these three methods, as well as provides a general recipe for improving analysis of convergence rate for stochastic and online optimization algorithms.
RIS
TY - CPAPER TI - Fast Rate Analysis of Some Stochastic Optimization Algorithms AU - Chao Qu AU - Huan Xu AU - Chong Ong BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-qua16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 662 EP - 670 L1 - http://proceedings.mlr.press/v48/qua16.pdf UR - https://proceedings.mlr.press/v48/qua16.html AB - In this paper, we revisit three fundamental and popular stochastic optimization algorithms (namely, Online Proximal Gradient, Regularized Dual Averaging method and ADMM with online proximal gradient) and analyze their convergence speed under conditions weaker than those in literature. In particular, previous works showed that these algorithms converge at a rate of O (\ln T/T) when the loss function is strongly convex, and O (1 /\sqrtT) in the weakly convex case. In contrast, we relax the strong convexity assumption of the loss function, and show that the algorithms converge at a rate O (\ln T/T) if the \em expectation of the loss function is \em locally strongly convex. This is a much weaker assumption and is satisfied by many practical formulations including Lasso and Logistic Regression. Our analysis thus extends the applicability of these three methods, as well as provides a general recipe for improving analysis of convergence rate for stochastic and online optimization algorithms. ER -
APA
Qu, C., Xu, H. & Ong, C.. (2016). Fast Rate Analysis of Some Stochastic Optimization Algorithms. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:662-670 Available from https://proceedings.mlr.press/v48/qua16.html.

Related Material