Convergence Rates for Projective Splitting
This work addresses the lack of convergence rate analysis for projective splitting, an incremental improvement for researchers in optimization and operator theory.
The paper tackles the problem of analyzing convergence rates for projective splitting methods in solving inclusions with maximal monotone operators, establishing an O(1/k) ergodic function convergence rate in convex optimization, an O(1/√k) rate for strongly monotone inclusions, and linear convergence under strong monotonicity and cocoercivity.
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.