SDCA without Duality, Regularization, and Individual Convexity

Shai Shalev-Shwartz
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:747-754, 2016.

Abstract

Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. We describe variants of SDCA that do not require explicit regularization and do not rely on duality. We prove linear convergence rates even if individual loss functions are non-convex, as long as the expected loss is strongly convex.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-shalev-shwartza16, title = {SDCA without Duality, Regularization, and Individual Convexity}, author = {Shalev-Shwartz, Shai}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {747--754}, 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/shalev-shwartza16.pdf}, url = {https://proceedings.mlr.press/v48/shalev-shwartza16.html}, abstract = {Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. We describe variants of SDCA that do not require explicit regularization and do not rely on duality. We prove linear convergence rates even if individual loss functions are non-convex, as long as the expected loss is strongly convex.} }
Endnote
%0 Conference Paper %T SDCA without Duality, Regularization, and Individual Convexity %A Shai Shalev-Shwartz %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-shalev-shwartza16 %I PMLR %P 747--754 %U https://proceedings.mlr.press/v48/shalev-shwartza16.html %V 48 %X Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. We describe variants of SDCA that do not require explicit regularization and do not rely on duality. We prove linear convergence rates even if individual loss functions are non-convex, as long as the expected loss is strongly convex.
RIS
TY - CPAPER TI - SDCA without Duality, Regularization, and Individual Convexity AU - Shai Shalev-Shwartz 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-shalev-shwartza16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 747 EP - 754 L1 - http://proceedings.mlr.press/v48/shalev-shwartza16.pdf UR - https://proceedings.mlr.press/v48/shalev-shwartza16.html AB - Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. We describe variants of SDCA that do not require explicit regularization and do not rely on duality. We prove linear convergence rates even if individual loss functions are non-convex, as long as the expected loss is strongly convex. ER -
APA
Shalev-Shwartz, S.. (2016). SDCA without Duality, Regularization, and Individual Convexity. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:747-754 Available from https://proceedings.mlr.press/v48/shalev-shwartza16.html.

Related Material