A Proof of results in Section 4

A.1 Auxiliary lemmas Given a function f which is convex, L-Lipschitz and β -smooth. The proof mainly follows from Lemma 3.4 in [ Next we show the convergence rate of SGD with approximate gradients. By plugging into the value of T, η and b, we obtain the stated bound. In this section, we present the DP-FTMRL algorithm and the guarantee it provides.Algorithm 4: A More details of these functions can be found in Appendix B of [23]. Theorem 12. (Regret guarantee) Recall the settings in Theorem 10.