The proof follows similar steps as in the proof of Proposition 5.1 in [1]} with different constants due to the change in \(\gamma _m\) .

We note that as PE is performed in each epoch, the number of batches is \(\Omega (\log ^2T)\) . However, we constructed the algorithm this way only for simplicity. It is possible to perform PE once and update the estimates of \(g\)  at the end of each batch similar to Algorithm REF .
