Appendix A Proofs for Section 2

We construct a "ghost" point: x Section 4.5 of [4], we have From Lemma 3.1 and Proposition 3.2 in [48], we have null[ x ] The last relationship we want to show is just equation (13). We separate the discussion into deterministic and stochastic settings. The total complexity is then K T . By Corollary 3.2 and discussion in Section 3.2, Algorithm 1 combined with By Corollary 3.2, Algorithm 1 combined with EG/OGDA can solve such auxiliary We implement these algorithms in the same way as in Section 5. 17 (a) Distance to limit point We compare EG and Catalyst-EG under same stepsizes in Figure 4(a).