too 1 B

Wenextcheck5 that trick I does not improve its convergence rate either. Recall the best known convergence rate of PG is given in6 (Xiong etal. Now, applying trick I (minibatch sampling) to PG, we obtain the convergence rate ofO 1(1 γ)2T +O 1(1 γ)2B .10 ForNPG, it can also be checked that trick I does not improve its rate. II does improve the sample complexityO 1(1 γ)8 4 of NPG given in (Agarwal et al. 2019) toO 1(1 γ)7 3 .