Three Operator Splitting with a Nonconvex Loss Function

Alp Yurtsever, Varun Mangalick, Suvrit Sra

TL;DR

This paper extends the Three Operator Splitting (TOS) algorithm to solve optimization problems where a nonconvex differentiable loss is combined with two convex, potentially nonsmooth functions. The authors provide the first nonasymptotic convergence guarantees for this setting without requiring extra smoothness on the nonsmooth terms. Furthermore, they demonstrate that TOS significantly outperforms the standard Frank-Wolfe approach on the challenging Quadratic Assignment Problem (QAP).

The Problem: Nonconvexity Meets Nonsmooth Constraints

Many problems in machine learning and statistics follow a "three-term" template:

$$\min_x f(x) + g(x) + h(x)$$

where $f$ is a differentiable loss function, and $g$ and $h$ are regularizers or indicator functions for constraints.

While the Three Operator Splitting (TOS) method is well-established for cases where $f$ is convex, its behavior in the nonconvex regime has historically been less understood. Previous attempts to analyze nonconvex TOS required $g$ and $h$ to be smooth (i.e., having Lipschitz continuous gradients). However, in many real-world applications—like the Quadratic Assignment Problem (QAP)—$g$ and $h$ act as indicator functions for specific sets, making them inherently nonsmooth.

The challenge addressed in this paper is twofold:

  1. Providing theoretical convergence rates for a nonconvex $f$ when $g$ and $h$ are nonsmooth.
  2. Handling "simple" constraints whose intersection forms a "complex" geometry (e.g., the Birkhoff polytope used in graph matching).

Methodological Contributions

The authors analyze the standard TOS algorithm but apply it directly to the nonconvex setting. The primary technical hurdle was defining a meaningful measure of "closeness to a solution," because the standard gradient norm fails when constraints or nonsmooth terms are introduced.

  • Stationarity Measure: The authors propose a measure based on a variational inequality (conceptually similar to the Frank-Wolfe gap) to quantify approximate first-order stationarity.
  • Nonasymptotic Analysis: They prove that TOS reaches an $\epsilon$-stationary point in $O(1/\epsilon^3)$ iterations.
  • Stochastic Extension: They adapt the algorithm for a stochastic setting where only an unbiased estimate of the gradient $\nabla f$ is available, proving a complexity of $O(1/\epsilon^5)$ total samples.
  • Constraint Splitting for QAP: For the QAP, they demonstrate how to split the complex Birkhoff polytope (doubly stochastic matrices) into two simpler sets (row-stochastic and column-stochastic). This clever split allows for highly efficient, parallelizable projections.

Key Insights and Ideas

No Extra Smoothness Required: The most significant theoretical breakthrough is proving that $g$ or $h$ do not need to be smooth to achieve convergence rates. This opens the door for using TOS on hard-constrained problems that were previously out of reach for this specific theoretical framework.

TOS vs. Frank-Wolfe (FW): In the context of QAP, the standard Frank-Wolfe algorithm requires solving a Linear Assignment Problem (LAP) at every iteration, incurring a hefty cost of $O(n^3)$. By splitting the constraints, TOS only requires simple projections that cost $O(n)$ per row/column, which can be executed in parallel.

Locally Linear Convergence & The "Infeasibility" Trade-off: While the theoretical analysis predicts a sublinear convergence rate, empirical results show that TOS often exhibits locally linear convergence on QAP datasets, hitting high-precision solutions much faster than FW. Unlike FW, which strictly stays inside the feasible region, TOS iterates can be slightly "infeasible" during the optimization process. However, this infeasibility vanishes at the same rate as the stationarity error.

Convergence behavior of TOS vs FW, showing locally linear convergence and the infeasibility trade-off.

Key Results

The authors evaluated their method using QAPLIB, a standard benchmark library for the Quadratic Assignment Problem containing 134 distinct datasets (e.g., chr12a, esc128, tai150b). These datasets represent various combinatorial optimization challenges ranging from facility location to graph matching.

  • Performance on QAPLIB: Out of the 134 instances, TOS achieved a better solution than Frank-Wolfe on 83 problems, tied on 16, and was outperformed on only 35.
  • Solution Quality: On average across all datasets, TOS outperformed FW in "assignment error" by a margin of 0.046. In some specific cases (like the chr15b dataset), the performance gap was as large as 0.744.
  • Efficiency: TOS proves particularly advantageous when the cost matrices are sparse. In these cases, the gradient computation becomes the bottleneck rather than the constraint handling, allowing TOS's simplified projections to shine.
Comparison of assignment errors across QAPLIB datasets, demonstrating TOS frequently outperforming FW.

Limitations and Future Work

  • Bounded Domain: The current analysis assumes the domain of $g$ is bounded. While common in constrained optimization, this might limit applications in unconstrained regularization scenarios.
  • Stochastic Complexity: The $O(1/\epsilon^5)$ sample complexity for the stochastic version is relatively high. The authors suggest that integrating variance reduction techniques (like SVRG or SARAH) could potentially improve this to $O(1/\epsilon^3)$.
  • Exploiting Smoothness: The analysis does not explicitly use the smoothness of the differentiable term $f$ to accelerate the rate. Future work could explore if the Kurdyka-Łojasiewicz (KL) property could be used to prove faster asymptotic rates.
  • Parallel Implementation: While the paper notes that the projection steps are highly parallelizable, the benchmarks were performed on a standard CPU. A GPU-based implementation could yield even more dramatic speedups in future applications.

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...
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