Three Operator Splitting with a Nonconvex Loss Function

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.

arXiv commentAppears in Proceedings of the 38th International Conference on Machine Learning (ICML 2021)

References in corpus (14)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Generalized Forward-Backward Splitting
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Regularized $M$-estimators of scatter matrix
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• Estimation of Simultaneously Sparse and Low Rank Matrices
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
• Stochastic Three-Composite Convex Minimization
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
• Proximal Splitting Meets Variance Reduction
• The Traveling Salesman Problem Under Squared Euclidean Distances
• A three-operator splitting algorithm for nonconvex sparsity regularization