Convergence Rates for Projective Splitting

Abstract

Projective splitting is a family of methods for solving inclusions involving sums of maximal monotone operators. First introduced by Eckstein and Svaiter in 2008, these methods have enjoyed significant innovation in recent years, becoming one of the most flexible operator splitting frameworks available. While weak convergence of the iterates to a solution has been established, there have been few attempts to study convergence rates of projective splitting. The purpose of this paper is to do so under various assumptions. To this end, there are three main contributions. First, in the context of convex optimization, we establish an $O(1/k)$ ergodic function convergence rate. Second, for strongly monotone inclusions, strong convergence is established as well as an ergodic $O(1/\sqrt{k})$ convergence rate for the distance of the iterates to the solution. Finally, for inclusions featuring strong monotonicity and cocoercivity, linear convergence is established.

This version adds references to the extragradient method

References in corpus (1)

• Projective Splitting with Forward Steps: Asynchronous and Block-Iterative Operator Splitting

Cited by in corpus (7)

• Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
• Projective Splitting with Forward Steps: Asynchronous and Block-Iterative Operator Splitting
• Projective Splitting with Forward Steps only Requires Continuity
• Uniqueness of DRS as the 2 Operator Resolvent-Splitting and Impossibility of 3 Operator Resolvent-Splitting
• Continuous time approximation of Nash equilibria
• Asynchronous Sequential Inertial Iterations for Common Fixed Points Problems with an Application to Linear Systems
• Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers