Three Operator Splitting with a Nonconvex Loss Function

Alp Yurtsever, Varun Mangalick, Suvrit Sra

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.

Introduction

In modern optimization, many problems in machine learning and statistics are formulated as the minimization of a composite objective function. A common and challenging template involves the sum of three distinct components: $$\min_{x \in \mathbb{R}^n} f(x) + g(x) + h(x)$$ where $f$ is a nonconvex but smooth loss function, and $g$ and $h$ are convex but potentially nondifferentiable regularizers or indicator functions representing constraints. While standard splitting algorithms excel when all components are convex, the introduction of nonconvexity alongside multiple nonsmooth terms creates significant theoretical and practical hurdles.

Existing iterations of the Three Operator Splitting (TOS) algorithm typically require at least two of the functions to be smooth (possessing Lipschitz continuous gradients). This requirement is a major limitation for applications where $g$ and $h$ are indicator functions used to enforce hard constraints. When a problem involves two sets of constraints whose intersection is difficult to project onto, but whose individual sets are manageable, TOS is a natural candidate. This research bridges the gap by providing the first non-asymptotic convergence rates for TOS in this specific nonconvex, nonsmooth setup.

The Three Operator Splitting Method

The TOS algorithm approaches the tripartite objective by decoupling the influence of each function. At each iteration $t$, the algorithm performs three primary operations:

  1. Gradient Step: A descent step is taken on the nonconvex function $f$ using its gradient $\nabla f$.
  2. Proximal Step on $g$: A proximal operator (a generalized projection) is applied to the result.
  3. Proximal Step on $h$: A second proximal operator is applied to finalize the update.

Theoretical Framework and Convergence

The primary contribution of this work is the rigorous proof of convergence to a first-order stationary point without requiring $g$ or $h$ to be smooth. Because the objective is both nonsmooth and nonconvex, traditional gradient norms are insufficient to measure progress. Instead, the authors utilize a stationarity measure based on variational inequalities to track the algorithm's trajectory toward a solution.

The paper establishes a non-asymptotic bound of $O(1/\epsilon^3)$ iterations to reach an $\epsilon$-stationary point. Furthermore, the analysis is extended to the stochastic setting—where only a noisy, unbiased estimator of $\nabla f$ is available—yielding a total complexity of $O(1/\epsilon^5)$ stochastic gradient evaluations.

Numerical Evaluation: Quadratic Assignment Problems

To demonstrate the practical utility of the proposed method, the authors evaluated TOS on the Quadratic Assignment Problem (QAP), an NP-hard combinatorial optimization problem used in facility location, circuit design, and image matching. Using 134 datasets from the benchmark library QAPLIB (including instances such as chr12a and esc128), TOS was compared against the Frank-Wolfe (FW) method.

Key Findings:

  • Performance: TOS achieved superior solutions in 83 out of 134 instances, while FW performed better in 35, and the methods tied in 16. On average, TOS outperformed FW by a margin of 0.046 in assignment error.
  • Efficiency in Sparsity: TOS proved particularly effective when the underlying matrices were sparse. Unlike FW, which requires solving a linear assignment problem at every iteration, TOS utilizes simpler, more efficient projections.
  • Observed Convergence: While the theoretical guarantee is sublinear, numerical experiments revealed that TOS often converges locally linearly. This suggests that the algorithm may be leveraging deeper structural properties of the problems, such as the Kurdyka-Łojasiewicz (KL) property, which are not yet fully accounted for in the current theory.

Discussion and Future Work

This work provides a robust theoretical foundation for using TOS in constrained nonconvex optimization, particularly when dealing with "split" constraints. However, some limitations remain. The current proof requires the domain of one nonsmooth function ($g$) to be bounded, a condition that future research may relax. Additionally, the $O(1/\epsilon^5)$ complexity in the stochastic setting suggests that incorporating variance reduction techniques could significantly enhance speed.

Future applications of this framework are promising, particularly in training constrained or regularized neural networks where nonconvexity is inherent and complex constraints are increasingly common.

Summary updated

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.
BibTeX
@inproceedings{yurtsever2021three,
  author = {Alp Yurtsever and Varun Mangalick and Suvrit Sra},
  title = {{Three Operator Splitting with a Nonconvex Loss Function}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=OyUCAcowGU},
}
Figure