Revisiting Extragradient-Type Methods: Part 1—Generalizations and Sublinear Convergence Rates
摘要
This paper presents a comprehensive analysis of the well-known extragradient (EG) method for solving both equation and inclusion problems. First, we unify and generalize EG for [non]linear equations to a broader class of algorithms, encompassing various existing schemes and potentially new variants. Next, we analyze both sublinear “best-iterate” and “last-iterate” convergence rates for the entire class of algorithms under a weak-Minty solution and a co-hypomonotone assumption, respectively, and derive new convergence results for two well-known instances. Second, we extend our EG framework above to inclusions under a [relaxed] monotonicity assumption, introducing a new class of algorithms and its corresponding convergence results. Third, we also unify and generalize Tseng’s forward-backward-forward splitting (FBFS) method to a broader class of algorithms to solve [non]linear inclusions when a weak-Minty solution exists, and establish its “best-iterate” convergence rate. Fourth, to complete our picture, we also investigate the sublinear rates of two other common variants of EG using our EG analysis framework developed here: the reflected forward-backward splitting and the golden ratio methods. Finally, we conduct extensive numerical experiments to validate our theoretical findings. Our results demonstrate that several new variants of our proposed algorithms outperform existing schemes in the majority of examples.