Convergence Rates for Projective Splitting
Patrick R. Johnstone, Jonathan Eckstein · SIAM Journal on Optimization · 2019
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 aim of this paper is to do so under various assumptions. To this end, it makes four main contributions. First, in the context of convex optimization, an $O(1/k)$ ergodic function convergence rate is established. Second, for strongly monotone inclusions, strong convergence is established as well as an ergodic $O(1/\sqrt{k})$ convergence rate for the distance from the iterates to the solution. Third, for inclusions featuring strong monotonicity and cocoercivity, linear convergence is established. We also consider the special case of one operator. In this case we show that projective splitting reduces to either the extragradient method or the proximal-point method, depending on whether forward or backward steps are used.