Adaptive Three Operator Splitting

Fabian Pedregosa, Gauthier Gidel
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4085-4094, 2018.

Abstract

We propose and analyze a novel adaptive step size variant of the Davis-Yin three operator splitting, a method that can solve optimization problems composed of a sum of a smooth term for which we have access to its gradient and an arbitrary number of potentially non-smooth terms for which we have access to their proximal operator. The proposed method leverages local information of the objective function, allowing for larger step sizes while preserving the convergence properties of the original method. It only requires two extra function evaluations per iteration and does not depend on any step size hyperparameter besides an initial estimate. We provide a convergence rate analysis of this method, showing sublinear convergence rate for general convex functions and linear convergence under stronger assumptions, matching the best known rates of its non adaptive variant. Finally, an empirical comparison with related methods on 6 different problems illustrates the computational advantage of the adaptive step size strategy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-pedregosa18a, title = {Adaptive Three Operator Splitting}, author = {Pedregosa, Fabian and Gidel, Gauthier}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4085--4094}, 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/pedregosa18a/pedregosa18a.pdf}, url = {https://proceedings.mlr.press/v80/pedregosa18a.html}, abstract = {We propose and analyze a novel adaptive step size variant of the Davis-Yin three operator splitting, a method that can solve optimization problems composed of a sum of a smooth term for which we have access to its gradient and an arbitrary number of potentially non-smooth terms for which we have access to their proximal operator. The proposed method leverages local information of the objective function, allowing for larger step sizes while preserving the convergence properties of the original method. It only requires two extra function evaluations per iteration and does not depend on any step size hyperparameter besides an initial estimate. We provide a convergence rate analysis of this method, showing sublinear convergence rate for general convex functions and linear convergence under stronger assumptions, matching the best known rates of its non adaptive variant. Finally, an empirical comparison with related methods on 6 different problems illustrates the computational advantage of the adaptive step size strategy.} }
Endnote
%0 Conference Paper %T Adaptive Three Operator Splitting %A Fabian Pedregosa %A Gauthier Gidel %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-pedregosa18a %I PMLR %P 4085--4094 %U https://proceedings.mlr.press/v80/pedregosa18a.html %V 80 %X We propose and analyze a novel adaptive step size variant of the Davis-Yin three operator splitting, a method that can solve optimization problems composed of a sum of a smooth term for which we have access to its gradient and an arbitrary number of potentially non-smooth terms for which we have access to their proximal operator. The proposed method leverages local information of the objective function, allowing for larger step sizes while preserving the convergence properties of the original method. It only requires two extra function evaluations per iteration and does not depend on any step size hyperparameter besides an initial estimate. We provide a convergence rate analysis of this method, showing sublinear convergence rate for general convex functions and linear convergence under stronger assumptions, matching the best known rates of its non adaptive variant. Finally, an empirical comparison with related methods on 6 different problems illustrates the computational advantage of the adaptive step size strategy.
APA
Pedregosa, F. & Gidel, G.. (2018). Adaptive Three Operator Splitting. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4085-4094 Available from https://proceedings.mlr.press/v80/pedregosa18a.html.

Related Material