Estimate Sequences for Variance-Reduced Stochastic Composite Optimization

Andrei Kulunchakov, Julien Mairal
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3541-3550, 2019.

Abstract

In this paper, we propose a unified view of gradient-based algorithms for stochastic convex composite optimization by extending the concept of estimate sequence introduced by Nesterov. This point of view covers the stochastic gradient descent method, variants of the approaches SAGA, SVRG, and has several advantages: (i) we provide a generic proof of convergence for the aforementioned methods; (ii) we show that this SVRG variant is adaptive to strong convexity; (iii) we naturally obtain new algorithms with the same guarantees; (iv) we derive generic strategies to make these algorithms robust to stochastic noise, which is useful when data is corrupted by small random perturbations. Finally, we show that this viewpoint is useful to obtain new accelerated algorithms in the sense of Nesterov.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kulunchakov19a, title = {Estimate Sequences for Variance-Reduced Stochastic Composite Optimization}, author = {Kulunchakov, Andrei and Mairal, Julien}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3541--3550}, 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/kulunchakov19a/kulunchakov19a.pdf}, url = {https://proceedings.mlr.press/v97/kulunchakov19a.html}, abstract = {In this paper, we propose a unified view of gradient-based algorithms for stochastic convex composite optimization by extending the concept of estimate sequence introduced by Nesterov. This point of view covers the stochastic gradient descent method, variants of the approaches SAGA, SVRG, and has several advantages: (i) we provide a generic proof of convergence for the aforementioned methods; (ii) we show that this SVRG variant is adaptive to strong convexity; (iii) we naturally obtain new algorithms with the same guarantees; (iv) we derive generic strategies to make these algorithms robust to stochastic noise, which is useful when data is corrupted by small random perturbations. Finally, we show that this viewpoint is useful to obtain new accelerated algorithms in the sense of Nesterov.} }
Endnote
%0 Conference Paper %T Estimate Sequences for Variance-Reduced Stochastic Composite Optimization %A Andrei Kulunchakov %A Julien Mairal %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-kulunchakov19a %I PMLR %P 3541--3550 %U https://proceedings.mlr.press/v97/kulunchakov19a.html %V 97 %X In this paper, we propose a unified view of gradient-based algorithms for stochastic convex composite optimization by extending the concept of estimate sequence introduced by Nesterov. This point of view covers the stochastic gradient descent method, variants of the approaches SAGA, SVRG, and has several advantages: (i) we provide a generic proof of convergence for the aforementioned methods; (ii) we show that this SVRG variant is adaptive to strong convexity; (iii) we naturally obtain new algorithms with the same guarantees; (iv) we derive generic strategies to make these algorithms robust to stochastic noise, which is useful when data is corrupted by small random perturbations. Finally, we show that this viewpoint is useful to obtain new accelerated algorithms in the sense of Nesterov.
APA
Kulunchakov, A. & Mairal, J.. (2019). Estimate Sequences for Variance-Reduced Stochastic Composite Optimization. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3541-3550 Available from https://proceedings.mlr.press/v97/kulunchakov19a.html.

Related Material