Three Operator Splitting with a Nonconvex Loss Function

Alp Yurtsever, Varun Mangalick, Suvrit Sra
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:12267-12277, 2021.

Abstract

We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-yurtsever21a, title = {Three Operator Splitting with a Nonconvex Loss Function}, author = {Yurtsever, Alp and Mangalick, Varun and Sra, Suvrit}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {12267--12277}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/yurtsever21a/yurtsever21a.pdf}, url = {https://proceedings.mlr.press/v139/yurtsever21a.html}, abstract = {We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.} }
Endnote
%0 Conference Paper %T Three Operator Splitting with a Nonconvex Loss Function %A Alp Yurtsever %A Varun Mangalick %A Suvrit Sra %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-yurtsever21a %I PMLR %P 12267--12277 %U https://proceedings.mlr.press/v139/yurtsever21a.html %V 139 %X We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.
APA
Yurtsever, A., Mangalick, V. & Sra, S.. (2021). Three Operator Splitting with a Nonconvex Loss Function. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:12267-12277 Available from https://proceedings.mlr.press/v139/yurtsever21a.html.

Related Material